Improve multithreading benchmarks (compare speedup factor, not with vcube)

1 files changed, 71 insertions, 84 deletions

diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md
index 768a7ea..3fc2093 100644
--- a/benchmarks/benchmarks.md
+++ b/benchmarks/benchmarks.md
@@ -38,21 +38,6 @@ may be particularly inaccurate, because writing the solution (together
 with some log messages) to standard output may take a significant portion
 of the time, depending on the terminal emulator used and other factors.
 
-The main test we performed was finding a single optimal solution, and we
-compared the results with vcube. This test was run in a single-thread
-configuration and in two multithread configurations (with 4 and 16
-threads).  We also ran a test on finding *all* optimal solutions which,
-as far as I know, is a use case not supported by vcube; this latter test
-was only run on 16 threads.
-
-Since the size of the pruning table used by the solver is of utmost
-importance, we include two statistics: time per cube and time per cube
-*adjusted by table size*.  The adjustment we took simply consists in
-multiplying the time per cube by the size of the table. Empirically
-this leads to more even results across the board, as the speed of the
-solvers of the same family seems to scale linearly with the size of the
-pruning table.
-
 All benchmark tests were done on the following configuration:
 
 * CPU: AMD Ryzen 7 7700 (8 cores, 16 virtual threads)
@@ -61,9 +46,29 @@ All benchmark tests were done on the following configuration:
 * Operating system: Debian 13 (Linux kernel 6.12.57)
 * Compiler: GCC 14.2.0 for H48 and Clang 19.1.7 for vcube
 
-## Results (click on each item to expand)
+## Benchmark results
+
+### Single solution, single thread
+
+The first test we performed was finding a single optimal solution, and
+we compared the results with vcube.
 
-<details><summary>Single solution, single thread</summary>
+This test was run in a single-thread configuration, because the two
+solvers use very different strategies for multithreading: vcube can only
+parallelize by solving one cube per thread, while H48 is able to take
+advantage of multiple threads even when solving a single cube. Therefore
+we prefer to compare their single-threaded performance only.
+
+Since the size of the pruning table used by the solver is of utmost
+importance, we include two statistics: time per cube and time per cube
+*adjusted by table size*.  The adjustment we took simply consists in
+multiplying the time per cube by the size of the table. Empirically this
+leads to more even results across the board, although the speed of the
+solvers of the same family does not scale exactly linearly with the size
+of the pruning table.
+
+<!-- The following details block can be found in benchmarks/single_thread_comparison.md -->
+<details><summary>Results: Single solution, single thread</summary>
 
 Time per cube (in seconds, lower is better).
 
@@ -103,95 +108,92 @@ Time per cube adjusted for table size (in seconds \* GiB, lower is better).
 <img src="img/20moves1thread.png">
 </details>
 
-<details><summary>Single solution, 4 threads</summary>
+As we can see, adjusting for table size, H48 is generally faster than
+vcube.  The gap between the two solvers is larger for scrambles with
+longer optimal solutions.
+
+### Single solution, multiple threads
+
+The same benchmark as before is repeated using 4 and 16 threads (recall
+that the CPU used for these tests has 8 physical cores and 16 virtual
+threads).
+
+As mentioned above, we don't compare these results to vcube. Instead,
+we compare them with the single-threaded results for H48 and we show
+how far the speedup factor is from a theoretically optimal 4x and 16x.
+
+<!-- The following details block can be found in benchmarks/tables_4_threads.md -->
+<details><summary>Results: Single solution, 4 threads</summary>
 
 Time per cube (in seconds, lower is better).
 
 |  Solver  |  Size  |17 moves|18 moves|19 moves|20 moves|Superflip|
 |:---------|:-------|-------:|-------:|-------:|-------:|--------:|
-|vcube 212 |58.2 GiB|    0.03|    0.27|    1.04|    7.70|   (a)   |
 |H48 h11   |56.5 GiB|    0.04|    0.14|    0.60|    3.97|     4.19|
-|vcube 404 |31.8 GiB|    0.07|    0.30|    1.65|   16.17|   (a)   |
 |H48 h10   |28.3 GiB|    0.05|    0.20|    0.91|    6.65|     9.81|
-|vcube 308 |21.2 GiB|    0.05|    0.35|    1.78|   16.61|   (a)   |
 |H48 h9    |14.1 GiB|    0.07|    0.39|    1.74|   12.54|    18.96|
-|vcube 208 | 7.3 GiB|    0.16|    1.47|    5.86|        |   (a)   |
 |H48 h8    | 7.1 GiB|    0.13|    0.90|    3.71|        |         |
 |H48 h7    | 3.5 GiB|    0.17|    1.28|    6.12|        |         |
-|vcube 112 | 2.4 GiB|    0.29|    3.13|   11.95|        |   (a)   |
 |H48 h6    | 1.8 GiB|    0.33|    2.47|   12.22|        |         |
 
-Time per cube adjusted for table size (in seconds \* GiB, lower is better).
+Speed-up factor (higher is better).
 
 |  Solver  |  Size  |17 moves|18 moves|19 moves|20 moves|Superflip|
 |:---------|:-------|-------:|-------:|-------:|-------:|--------:|
-|vcube 212 |58.2 GiB|    2.03|   15.69|   60.25|  447.97|   (a)   |
-|H48 h11   |56.5 GiB|    2.04|    8.17|   33.77|  224.59|   236.92|
-|vcube 404 |31.8 GiB|    2.32|    9.50|   52.46|  514.50|   (a)   |
-|H48 h10   |28.3 GiB|    1.37|    5.76|   25.83|  187.88|   277.18|
-|vcube 308 |21.2 GiB|    1.02|    7.52|   37.82|  352.36|   (a)   |
-|H48 h9    |14.1 GiB|    1.03|    5.45|   24.58|  177.17|   267.79|
-|vcube 208 | 7.3 GiB|    1.18|   10.69|   42.63|        |   (a)   |
-|H48 h8    | 7.1 GiB|    0.92|    6.39|   26.20|        |         |
-|H48 h7    | 3.5 GiB|    0.62|    4.53|   21.62|        |         |
-|vcube 112 | 2.4 GiB|    0.69|    7.59|   28.97|        |   (a)   |
-|H48 h6    | 1.8 GiB|    0.59|    4.37|   21.61|        |         |
-
-(a) vcube cannot parallelize on a single scramble, the results for the
-superflip are going to be the same as in the single thread case.
+|H48 h11   |56.5 GiB|    2.55|    3.46|    3.75|    3.96|     3.71|
+|H48 h10   |28.3 GiB|    3.09|    3.71|    3.67|    3.54|     3.88|
+|H48 h9    |14.1 GiB|    3.25|    3.84|    3.85|        |         |
+|H48 h8    | 7.1 GiB|    3.53|    3.72|    3.81|        |         |
+|H48 h7    | 3.5 GiB|    3.60|    3.78|    3.80|        |         |
+|H48 h6    | 1.8 GiB|    3.77|    3.82|    3.79|        |         |
+<img src="img/4threads.png">
 
-<img src="img/17moves4threads.png">
-<img src="img/18moves4threads.png">
-<img src="img/19moves4threads.png">
-<img src="img/20moves4threads.png">
 </details>
 
-<details><summary>Single solution, 16 threads</summary>
+<!-- The following details block can be found in benchmarks/tables_16_threads.md -->
+<details><summary>Results: Single solution, 16 threads</summary>
 
 Time per cube (in seconds, lower is better).
 
 |  Solver  |  Size  |17 moves|18 moves|19 moves|20 moves|Superflip|
 |:---------|:-------|-------:|-------:|-------:|-------:|--------:|
-|vcube 212 |58.2 GiB|    0.02|    0.13|    0.45|    2.84|   (a)   |
 |H48 h11   |56.5 GiB|    0.02|    0.06|    0.22|    1.33|     1.84|
-|vcube 404 |31.8 GiB|    0.04|    0.14|    0.65|    6.08|   (a)   |
 |H48 h10   |28.3 GiB|    0.03|    0.08|    0.33|    2.34|     4.18|
-|vcube 308 |21.2 GiB|    0.03|    0.19|    0.78|    6.67|   (a)   |
 |H48 h9    |14.1 GiB|    0.04|    0.15|    0.64|    4.45|     8.09|
-|vcube 208 | 7.3 GiB|    0.08|    0.79|    2.43|        |   (a)   |
 |H48 h8    | 7.1 GiB|    0.06|    0.34|    1.36|        |         |
 |H48 h7    | 3.5 GiB|    0.07|    0.47|    2.20|        |         |
-|vcube 112 | 2.4 GiB|    0.15|    1.63|    5.10|        |   (a)   |
 |H48 h6    | 1.8 GiB|    0.13|    0.91|    4.39|        |         |
 
-Time per cube adjusted for table size (in seconds \* GiB, lower is better).
+Speed-up factor (higher is better).
 
 |  Solver  |  Size  |17 moves|18 moves|19 moves|20 moves|Superflip|
 |:---------|:-------|-------:|-------:|-------:|-------:|--------:|
-|vcube 212 |58.2 GiB|    0.95|    7.83|   26.04|  165.03|   (a)   |
-|H48 h11   |56.5 GiB|    1.34|    3.48|   12.19|   74.93|   103.98|
-|vcube 404 |31.8 GiB|    1.21|    4.60|   20.76|  193.43|   (a)   |
-|H48 h10   |28.3 GiB|    0.74|    2.37|    9.46|   66.13|   118.23|
-|vcube 308 |21.2 GiB|    0.67|    4.01|   16.48|  141.49|   (a)   |
-|H48 h9    |14.1 GiB|    0.51|    2.15|    8.98|   62.92|   114.31|
-|vcube 208 | 7.3 GiB|    0.56|    5.78|   17.68|        |   (a)   |
-|H48 h8    | 7.1 GiB|    0.40|    2.40|    9.59|        |         |
-|H48 h7    | 3.5 GiB|    0.26|    1.66|    7.77|        |         |
-|vcube 112 | 2.4 GiB|    0.35|    3.95|   12.37|        |   (a)   |
-|H48 h6    | 1.8 GiB|    0.23|    1.61|    7.76|        |         |
+|H48 h11   |56.5 GiB|    3.90|    8.14|   10.39|   11.86|     8.45|
+|H48 h10   |28.3 GiB|    5.72|    9.00|   10.03|   10.04|     9.09|
+|H48 h9    |14.1 GiB|    6.56|    9.75|   10.53|        |         |
+|H48 h8    | 7.1 GiB|    8.08|    9.91|   10.40|        |         |
+|H48 h7    | 3.5 GiB|    8.59|   10.30|   10.57|        |         |
+|H48 h6    | 1.8 GiB|    9.60|   10.39|   10.54|        |         |
+<img src="img/16threads.png">
 
-(a) vcube cannot parallelize on a single scramble, the results for the
-superflip are going to be the same as in the single thread case.
-
-<img src="img/17moves16threads.png">
-<img src="img/18moves16threads.png">
-<img src="img/19moves16threads.png">
-<img src="img/20moves16threads.png">
 </details>
 
-<details><summary>All solutions, 16 threads</summary>
+We can see that H48 scales pretty well with 4 threads, getting close
+to the 4x theoretical maximum speedup in slower cases (small table or
+long solutions).
+
+In the 16 threads benchmark shows that, although the virtual threads
+help push us beyond the 8x theoretical speedup that would be provided
+by the 8 cores, we are nowhere near a 16x speedup.
+
+### All solutions
 
-*Note: vcube does not have an option for finding multiple solutions.*
+Finally, we ran a test on finding *all* optimal solutions which, as
+far as I know, is a use case not supported by vcube. For convenience,
+this test is only run on 16 threads.
+
+<!-- The following details block can be found in benchmarks/all_solutions.md -->
+<details><summary>Results: All solutions (16 threads)</summary>
 
 Time per cube (in seconds, lower is better).
 
@@ -217,16 +219,6 @@ Time per cube adjusted for table size (in seconds \* GiB, lower is better).
 
 </details>
 
-## Comments on the results
-
-* Adjusting for table size, H48 is generally faster than vcube.
-* The gap between the two solvers is larger for scrambles with
-  longer optimal solutions.
-* On sets of 25 scrambles, H48 performs better than vcube when using
-  multiple threads, compared to their single-threaded performance.
-  However, this advantage will likely disappear (or
-  even invert) if we increase the size of the set.
-
 ## Other notes
 
 * To repeat the benchmarks, use `./benchmarks/run-h48-benchmarks.sh`.
@@ -249,8 +241,3 @@ Time per cube adjusted for table size (in seconds \* GiB, lower is better).
 * For H48, both GCC and Clang have been tried, with the same options;
   the resulting executable was about 10% faster with GCC compared to Clang.
   vcube only supports compiling with Clang.
-* The performance of the H48 solver depends slightly, but measurably, on the
-  alignment of the pruning table in memory. This is not handled by the core
-  library, but by the program that uses it. For these tests, we have used as
-  reference implementation the program in `tools/301_solve_file`, which
-  ensures 64-byte alignment.