From 9a013b7c68f94e6be0fe8748c9012a441fe0273f Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 12 Jan 2026 18:09:43 +0100 Subject: Improve performance of H48 solver with prefetching With this commit we re-structure how the node expansion in the H48 solution search works to allow prefetching of pruning values, showing performance improvements in the range of 30-45% on x86, depending on table size and solution length. A small bug fix related to appending solutions is included in this commit. --- benchmarks/benchmarks.md | 104 ++++++++++++++++++------------------ benchmarks/img/17moves16threads.png | Bin 105391 -> 119331 bytes benchmarks/img/17moves1thread.png | Bin 105189 -> 112954 bytes benchmarks/img/17moves4threads.png | Bin 105326 -> 114709 bytes benchmarks/img/18moves16threads.png | Bin 115210 -> 112774 bytes benchmarks/img/18moves1thread.png | Bin 117889 -> 113328 bytes benchmarks/img/18moves4threads.png | Bin 110133 -> 117736 bytes benchmarks/img/19moves16threads.png | Bin 114824 -> 117654 bytes benchmarks/img/19moves1thread.png | Bin 116892 -> 119075 bytes benchmarks/img/19moves4threads.png | Bin 112923 -> 119488 bytes benchmarks/img/20moves16threads.png | Bin 127508 -> 121476 bytes benchmarks/img/20moves1thread.png | Bin 117068 -> 112429 bytes benchmarks/img/20moves4threads.png | Bin 119011 -> 123801 bytes benchmarks/results_h48.py | 48 ++++++++--------- 14 files changed, 77 insertions(+), 75 deletions(-) (limited to 'benchmarks') diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md index 45ef29b..768a7ea 100644 --- a/benchmarks/benchmarks.md +++ b/benchmarks/benchmarks.md @@ -70,32 +70,32 @@ 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.11| 0.75| 3.43| 27.28| 19.30| -|H48 h11 |56.5 GiB| 0.13| 0.73| 3.43| 23.28| 19.26| +|H48 h11 |56.5 GiB| 0.09| 0.50| 2.24| 15.73| 15.55| |vcube 404 |31.8 GiB| 0.23| 1.24| 6.10| 59.33| 268.26| -|H48 h10 |28.3 GiB| 0.23| 1.20| 6.18| 43.51| 48.84| +|H48 h10 |28.3 GiB| 0.15| 0.76| 3.36| 23.51| 38.05| |vcube 308 |21.2 GiB| 0.17| 1.02| 6.20| 58.70| 604.35| -|H48 h9 |14.1 GiB| 0.36| 2.47| 11.79| | | +|H48 h9 |14.1 GiB| 0.24| 1.48| 6.69| | | |vcube 208 | 7.3 GiB| 0.56| 4.36| 20.58| | | -|H48 h8 | 7.1 GiB| 0.79| 6.09| 25.58| | | -|H48 h7 | 3.5 GiB| 1.07| 8.59| 42.16| | | +|H48 h8 | 7.1 GiB| 0.46| 3.36| 14.13| | | +|H48 h7 | 3.5 GiB| 0.63| 4.85| 23.25| | | |vcube 112 | 2.4 GiB| 0.96| 9.29| 40.52| | | -|H48 h6 | 1.8 GiB| 2.12| 16.29| 82.24| | | +|H48 h6 | 1.8 GiB| 1.25| 9.45| 46.31| | | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |vcube 212 |58.2 GiB| 6.43| 43.80| 199.38| 1587.43| 1122.73| -|H48 h11 |56.5 GiB| 7.33| 41.47| 193.67| 1315.32| 1088.34| +|H48 h11 |56.5 GiB| 5.21| 28.28| 126.68| 889.01| 878.77| |vcube 404 |31.8 GiB| 7.40| 39.47| 194.01| 1887.94| 8535.87| -|H48 h10 |28.3 GiB| 6.60| 34.00| 174.65| 1229.18| 1379.90| +|H48 h10 |28.3 GiB| 4.22| 21.37| 94.86| 664.22| 1075.08| |vcube 308 |21.2 GiB| 3.51| 21.71| 131.50| 1245.26| 12819.94| -|H48 h9 |14.1 GiB| 5.03| 34.85| 166.51| | | +|H48 h9 |14.1 GiB| 3.34| 20.97| 94.57| | | |vcube 208 | 7.3 GiB| 4.08| 31.74| 149.68| | | -|H48 h8 | 7.1 GiB| 5.61| 43.02| 180.71| | | -|H48 h7 | 3.5 GiB| 3.80| 30.34| 148.96| | | +|H48 h8 | 7.1 GiB| 3.25| 23.75| 99.82| | | +|H48 h7 | 3.5 GiB| 2.22| 17.12| 82.14| | | |vcube 112 | 2.4 GiB| 2.33| 22.53| 98.23| | | -|H48 h6 | 1.8 GiB| 3.75| 28.79| 145.36| | | +|H48 h6 | 1.8 GiB| 2.21| 16.70| 81.86| | | @@ -110,32 +110,32 @@ 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.22| 0.97| 6.98| 5.95| +|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.07| 0.36| 1.79| 12.42| 14.03| +|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.11| 0.70| 3.48| 25.61| 25.37| +|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.23| 1.74| 7.19| | | -|H48 h7 | 3.5 GiB| 0.32| 2.45| 12.12| | | +|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.61| 4.61| 24.22| | | +|H48 h6 | 1.8 GiB| 0.33| 2.47| 12.22| | | Time per cube adjusted for table size (in seconds \* GiB, lower 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.53| 12.71| 54.58| 394.33| 336.47| +|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| 2.11| 10.23| 50.61| 350.78| 396.48| +|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.57| 9.96| 49.23| 361.85| 358.45| +|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| 1.66| 12.27| 50.82| | | -|H48 h7 | 3.5 GiB| 1.11| 8.67| 42.83| | | +|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| 1.08| 8.16| 42.81| | | +|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. @@ -153,32 +153,32 @@ 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.08| 0.33| 2.22| 2.41| +|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.13| 0.58| 4.21| 5.56| +|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.25| 1.10| 8.05| 10.77| +|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.08| 0.57| 2.40| | | -|H48 h7 | 3.5 GiB| 0.11| 0.83| 4.00| | | +|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.21| 1.51| 7.74| | | +|H48 h6 | 1.8 GiB| 0.13| 0.91| 4.39| | | Time per cube adjusted for table size (in seconds \* GiB, lower 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.12| 4.61| 18.90| 125.27| 136.10| +|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.86| 3.61| 16.47| 118.85| 157.13| +|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.60| 3.51| 15.57| 113.71| 152.21| +|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.59| 4.03| 16.98| | | -|H48 h7 | 3.5 GiB| 0.41| 2.94| 14.12| | | +|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.38| 2.67| 13.68| | | +|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. @@ -197,32 +197,34 @@ Time per cube (in seconds, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 |56.5 GiB| 0.05| 0.41| 3.69| 31.65| 21.80| -|H48 h10 |28.3 GiB| 0.07| 0.70| 6.73| 58.61| 48.62| -|H48 h9 |14.1 GiB| 0.12| 1.28| 12.93| | | -|H48 h8 | 7.1 GiB| 0.25| 2.72| 27.42| | | -|H48 h7 | 3.5 GiB| 0.37| 4.24| 47.10| | | -|H48 h6 | 1.8 GiB| 0.69| 8.18| 91.85| | | +|H48 h11 |56.5 GiB| 0.04| 0.26| 2.22| 18.96| 16.95| +|H48 h10 |28.3 GiB| 0.05| 0.42| 3.82| 34.42| 36.80| +|H48 h9 |14.1 GiB| 0.08| 0.73| 7.28| | | +|H48 h8 | 7.1 GiB| 0.15| 1.56| 15.41| | | +|H48 h7 | 3.5 GiB| 0.21| 2.38| 26.52| | | +|H48 h6 | 1.8 GiB| 0.39| 4.67| 53.00| | | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 |56.5 GiB| 2.57| 23.07| 208.71| 1788.12| 1231.86| -|H48 h10 |28.3 GiB| 2.01| 19.77| 190.14| 1655.95| 1373.79| -|H48 h9 |14.1 GiB| 1.72| 18.07| 182.67| | | -|H48 h8 | 7.1 GiB| 1.74| 19.21| 193.74| | | -|H48 h7 | 3.5 GiB| 1.29| 14.98| 166.41| | | -|H48 h6 | 1.8 GiB| 1.21| 14.47| 162.36| | | +|H48 h11 |56.5 GiB| 2.11| 14.55| 125.21| 1071.23| 957.47| +|H48 h10 |28.3 GiB| 1.48| 11.96| 107.83| 972.35| 1039.73| +|H48 h9 |14.1 GiB| 1.08| 10.29| 102.88| | | +|H48 h8 | 7.1 GiB| 1.03| 10.99| 108.87| | | +|H48 h7 | 3.5 GiB| 0.74| 8.41| 93.69| | | +|H48 h6 | 1.8 GiB| 0.70| 8.25| 93.68| | | ## Comments on the results -* Adjusting for table size, vcube generally is a bit faster than H48, - except for 20 moves scrambles where H48 is a clear winner. +* 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. However, this advantage will likely disappear (or + 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 diff --git a/benchmarks/img/17moves16threads.png b/benchmarks/img/17moves16threads.png index 487f3a6..45f5901 100644 Binary files a/benchmarks/img/17moves16threads.png and b/benchmarks/img/17moves16threads.png differ diff --git a/benchmarks/img/17moves1thread.png b/benchmarks/img/17moves1thread.png index d42147f..70bcad0 100644 Binary files a/benchmarks/img/17moves1thread.png and b/benchmarks/img/17moves1thread.png differ diff --git a/benchmarks/img/17moves4threads.png b/benchmarks/img/17moves4threads.png index 0b15f3e..edfca34 100644 Binary files a/benchmarks/img/17moves4threads.png and b/benchmarks/img/17moves4threads.png differ diff --git a/benchmarks/img/18moves16threads.png b/benchmarks/img/18moves16threads.png index 15351bd..df5210a 100644 Binary files a/benchmarks/img/18moves16threads.png and b/benchmarks/img/18moves16threads.png differ diff --git a/benchmarks/img/18moves1thread.png b/benchmarks/img/18moves1thread.png index 6812708..dafba4e 100644 Binary files a/benchmarks/img/18moves1thread.png and b/benchmarks/img/18moves1thread.png differ diff --git a/benchmarks/img/18moves4threads.png b/benchmarks/img/18moves4threads.png index fdde486..9b89bed 100644 Binary files a/benchmarks/img/18moves4threads.png and b/benchmarks/img/18moves4threads.png differ diff --git a/benchmarks/img/19moves16threads.png b/benchmarks/img/19moves16threads.png index 7b3a2ab..42212a6 100644 Binary files a/benchmarks/img/19moves16threads.png and b/benchmarks/img/19moves16threads.png differ diff --git a/benchmarks/img/19moves1thread.png b/benchmarks/img/19moves1thread.png index e269b4d..f51886e 100644 Binary files a/benchmarks/img/19moves1thread.png and b/benchmarks/img/19moves1thread.png differ diff --git a/benchmarks/img/19moves4threads.png b/benchmarks/img/19moves4threads.png index 70457c0..44ac692 100644 Binary files a/benchmarks/img/19moves4threads.png and b/benchmarks/img/19moves4threads.png differ diff --git a/benchmarks/img/20moves16threads.png b/benchmarks/img/20moves16threads.png index 5aa5b9d..82c28b2 100644 Binary files a/benchmarks/img/20moves16threads.png and b/benchmarks/img/20moves16threads.png differ diff --git a/benchmarks/img/20moves1thread.png b/benchmarks/img/20moves1thread.png index 44548a5..1f285d9 100644 Binary files a/benchmarks/img/20moves1thread.png and b/benchmarks/img/20moves1thread.png differ diff --git a/benchmarks/img/20moves4threads.png b/benchmarks/img/20moves4threads.png index 30f9744..c23fe81 100644 Binary files a/benchmarks/img/20moves4threads.png and b/benchmarks/img/20moves4threads.png differ diff --git a/benchmarks/results_h48.py b/benchmarks/results_h48.py index 9d8d19c..625b2c5 100644 --- a/benchmarks/results_h48.py +++ b/benchmarks/results_h48.py @@ -1,36 +1,36 @@ h48_single_thread = { - 6: {17: 52.9727, 18: 407.1435, 19: 2055.8785}, - 7: {17: 26.8541, 18: 214.7064, 19: 1053.9732}, - 8: {17: 19.8408, 18: 152.2214, 19: 639.4834}, - 9: {17: 8.9053, 18: 61.6760, 19: 294.6517}, - 10: {17: 5.8445, 18: 30.0880, 19: 154.5389, 20: 1087.6552, "superflip": 48.8410}, - 11: {17: 3.2420, 18: 18.3482, 19: 85.6898, 20: 581.9588, "superflip": 19.2614}, + 6: {17: 31.2308, 18: 236.1986, 19: 1157.7502}, + 7: {17: 15.7227, 18: 121.1488, 19: 581.2004}, + 8: {17: 11.5065, 18: 84.0366, 19: 353.2224}, + 9: {17: 5.9123, 18: 37.1034, 19: 167.3496}, + 10: {17: 3.7338, 18: 18.9061, 19: 83.9382, 20: 587.7489, "superflip": 38.0522}, + 11: {17: 2.3070, 18: 12.5145, 19: 56.0479, 20: 393.3391, "superflip": 15.5523}, } h48_4_threads = { - 6: {17: 15.2251, 18: 115.3688, 19: 605.5267}, - 7: {17: 7.8799, 18: 61.3355, 19: 303.0388}, - 8: {17: 5.8624, 18: 43.4193, 19: 179.8491}, - 9: {17: 2.7696, 18: 17.6190, 19: 87.1236, 20: 640.3405, "superflip": 25.3726}, - 10: {17: 1.8676, 18: 9.0543, 19: 44.7847, 20: 310.3914, "superflip": 14.0333}, - 11: {17: 1.1173, 18: 5.6240, 19: 24.1467, 20: 174.4689, "superflip": 5.9548}, + 6: {17: 8.2859, 18: 61.8403, 19: 305.5934}, + 7: {17: 4.3713, 18: 32.0550, 19: 152.9403}, + 8: {17: 3.2607, 18: 22.6002, 19: 92.7235}, + 9: {17: 1.8164, 18: 9.6520, 19: 43.5002, 20: 313.5156, "superflip": 18.9551}, + 10: {17: 1.2098, 18: 5.1007, 19: 22.8530, 20: 166.2468, "superflip": 9.8108}, + 11: {17: 0.9047, 18: 3.6152, 19: 14.9408, 20: 99.3673, "superflip": 4.1930}, } h48_16_threads = { - 6: {17: 5.3309, 18: 37.8142, 19: 193.5352}, - 7: {17: 2.8657, 18: 20.8215, 19: 99.9139}, - 8: {17: 2.0775, 18: 14.2672, 19: 60.0995}, - 9: {17: 1.0595, 18: 6.2074, 19: 27.5523, 20: 201.2200, "superflip": 10.7739}, - 10: {17: 0.7600, 18: 3.1980, 19: 14.5771, 20: 105.1686, "superflip": 5.5616}, - 11: {17: 0.4946, 18: 2.0381, 19: 8.3613, 20: 55.4269, "superflip": 2.4087}, + 6: {17: 3.2536, 18: 22.7283, 19: 109.8073}, + 7: {17: 1.8312, 18: 11.7609, 19: 54.9974}, + 8: {17: 1.4242, 18: 8.4798, 19: 33.9483}, + 9: {17: 0.9010, 18: 3.8064, 19: 15.8985, 20: 111.3421, "superflip": 8.0916}, + 10: {17: 0.6528, 18: 2.1009, 19: 8.3680, 20: 58.5190, "superflip": 4.1848}, + 11: {17: 0.5918, 18: 1.5379, 19: 5.3942, 20: 33.1522, "superflip": 1.8402}, } h48_all_solutions = { - 6: {17: 17.1587, 18: 204.6182, 19: 2296.3135}, - 7: {17: 9.1380, 18: 106.0127, 19: 1177.4728}, - 8: {17: 6.1641, 18: 67.9895, 19: 685.6033}, - 9: {17: 3.0422, 18: 31.9821, 19: 323.2516}, - 10: {17: 1.7822, 18: 17.4947, 19: 168.2516, 20: 1465.2950, "superflip": 48.6248}, - 11: {17: 1.1364, 18: 10.2076, 19: 92.3419, 20: 791.1480, "superflip": 21.8014}, + 6: {17: 9.8554, 18: 116.6374, 19: 1324.9303}, + 7: {17: 5.2495, 18: 59.4768, 19: 662.9106}, + 8: {17: 3.6359, 18: 38.8943, 19: 385.2452}, + 9: {17: 1.9026, 18: 18.2076, 19: 182.0522}, + 10: {17: 1.3117, 18: 10.5836, 19: 95.4136, 20: 860.4004, "superflip": 36.8007}, + 11: {17: 0.9357, 18: 6.4383, 19: 55.3969, 20: 473.9622, "superflip": 16.9452}, } -- cgit v1.3