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.

1 files changed, 24 insertions, 24 deletions

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},
 }