From 233169d9ab5fb8a796d91a3694f8a522fa54d194 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 26 Jan 2026 22:52:15 +0100 Subject: Improve multithreading benchmarks (compare speedup factor, not with vcube) --- benchmarks/benchmarks.md | 159 ++++++++++++++++++++++------------------------- 1 file changed, 73 insertions(+), 86 deletions(-) (limited to 'benchmarks/benchmarks.md') 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. -
Single solution, single thread +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. + + +
Results: Single solution, single thread 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).
-
Single solution, 4 threads +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. + + +
Results: Single solution, 4 threads 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| | | + +
-
Single solution, 16 threads + +
Results: Single solution, 16 threads 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| | | - -(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| 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| | | + +
-
All solutions, 16 threads +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. + + +
Results: All solutions (16 threads) 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).
-## 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. -- cgit v1.3