aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--benchmarks/benchmarks.md104
-rw-r--r--benchmarks/img/17moves16threads.pngbin105391 -> 119331 bytes
-rw-r--r--benchmarks/img/17moves1thread.pngbin105189 -> 112954 bytes
-rw-r--r--benchmarks/img/17moves4threads.pngbin105326 -> 114709 bytes
-rw-r--r--benchmarks/img/18moves16threads.pngbin115210 -> 112774 bytes
-rw-r--r--benchmarks/img/18moves1thread.pngbin117889 -> 113328 bytes
-rw-r--r--benchmarks/img/18moves4threads.pngbin110133 -> 117736 bytes
-rw-r--r--benchmarks/img/19moves16threads.pngbin114824 -> 117654 bytes
-rw-r--r--benchmarks/img/19moves1thread.pngbin116892 -> 119075 bytes
-rw-r--r--benchmarks/img/19moves4threads.pngbin112923 -> 119488 bytes
-rw-r--r--benchmarks/img/20moves16threads.pngbin127508 -> 121476 bytes
-rw-r--r--benchmarks/img/20moves1thread.pngbin117068 -> 112429 bytes
-rw-r--r--benchmarks/img/20moves4threads.pngbin119011 -> 123801 bytes
-rw-r--r--benchmarks/results_h48.py48
-rw-r--r--doc/h48.md33
-rw-r--r--src/solvers/h48/solve.h375
-rw-r--r--src/solvers/solutions.h2
-rw-r--r--src/utils/prefetch.h15
-rw-r--r--src/utils/utils.h1
19 files changed, 361 insertions, 217 deletions
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).
70| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 70| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
71|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 71|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
72|vcube 212 |58.2 GiB| 0.11| 0.75| 3.43| 27.28| 19.30| 72|vcube 212 |58.2 GiB| 0.11| 0.75| 3.43| 27.28| 19.30|
73|H48 h11 |56.5 GiB| 0.13| 0.73| 3.43| 23.28| 19.26| 73|H48 h11 |56.5 GiB| 0.09| 0.50| 2.24| 15.73| 15.55|
74|vcube 404 |31.8 GiB| 0.23| 1.24| 6.10| 59.33| 268.26| 74|vcube 404 |31.8 GiB| 0.23| 1.24| 6.10| 59.33| 268.26|
75|H48 h10 |28.3 GiB| 0.23| 1.20| 6.18| 43.51| 48.84| 75|H48 h10 |28.3 GiB| 0.15| 0.76| 3.36| 23.51| 38.05|
76|vcube 308 |21.2 GiB| 0.17| 1.02| 6.20| 58.70| 604.35| 76|vcube 308 |21.2 GiB| 0.17| 1.02| 6.20| 58.70| 604.35|
77|H48 h9 |14.1 GiB| 0.36| 2.47| 11.79| | | 77|H48 h9 |14.1 GiB| 0.24| 1.48| 6.69| | |
78|vcube 208 | 7.3 GiB| 0.56| 4.36| 20.58| | | 78|vcube 208 | 7.3 GiB| 0.56| 4.36| 20.58| | |
79|H48 h8 | 7.1 GiB| 0.79| 6.09| 25.58| | | 79|H48 h8 | 7.1 GiB| 0.46| 3.36| 14.13| | |
80|H48 h7 | 3.5 GiB| 1.07| 8.59| 42.16| | | 80|H48 h7 | 3.5 GiB| 0.63| 4.85| 23.25| | |
81|vcube 112 | 2.4 GiB| 0.96| 9.29| 40.52| | | 81|vcube 112 | 2.4 GiB| 0.96| 9.29| 40.52| | |
82|H48 h6 | 1.8 GiB| 2.12| 16.29| 82.24| | | 82|H48 h6 | 1.8 GiB| 1.25| 9.45| 46.31| | |
83 83
84Time per cube adjusted for table size (in seconds \* GiB, lower is better). 84Time per cube adjusted for table size (in seconds \* GiB, lower is better).
85 85
86| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 86| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
87|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 87|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
88|vcube 212 |58.2 GiB| 6.43| 43.80| 199.38| 1587.43| 1122.73| 88|vcube 212 |58.2 GiB| 6.43| 43.80| 199.38| 1587.43| 1122.73|
89|H48 h11 |56.5 GiB| 7.33| 41.47| 193.67| 1315.32| 1088.34| 89|H48 h11 |56.5 GiB| 5.21| 28.28| 126.68| 889.01| 878.77|
90|vcube 404 |31.8 GiB| 7.40| 39.47| 194.01| 1887.94| 8535.87| 90|vcube 404 |31.8 GiB| 7.40| 39.47| 194.01| 1887.94| 8535.87|
91|H48 h10 |28.3 GiB| 6.60| 34.00| 174.65| 1229.18| 1379.90| 91|H48 h10 |28.3 GiB| 4.22| 21.37| 94.86| 664.22| 1075.08|
92|vcube 308 |21.2 GiB| 3.51| 21.71| 131.50| 1245.26| 12819.94| 92|vcube 308 |21.2 GiB| 3.51| 21.71| 131.50| 1245.26| 12819.94|
93|H48 h9 |14.1 GiB| 5.03| 34.85| 166.51| | | 93|H48 h9 |14.1 GiB| 3.34| 20.97| 94.57| | |
94|vcube 208 | 7.3 GiB| 4.08| 31.74| 149.68| | | 94|vcube 208 | 7.3 GiB| 4.08| 31.74| 149.68| | |
95|H48 h8 | 7.1 GiB| 5.61| 43.02| 180.71| | | 95|H48 h8 | 7.1 GiB| 3.25| 23.75| 99.82| | |
96|H48 h7 | 3.5 GiB| 3.80| 30.34| 148.96| | | 96|H48 h7 | 3.5 GiB| 2.22| 17.12| 82.14| | |
97|vcube 112 | 2.4 GiB| 2.33| 22.53| 98.23| | | 97|vcube 112 | 2.4 GiB| 2.33| 22.53| 98.23| | |
98|H48 h6 | 1.8 GiB| 3.75| 28.79| 145.36| | | 98|H48 h6 | 1.8 GiB| 2.21| 16.70| 81.86| | |
99 99
100<img src="img/17moves1thread.png"> 100<img src="img/17moves1thread.png">
101<img src="img/18moves1thread.png"> 101<img src="img/18moves1thread.png">
@@ -110,32 +110,32 @@ Time per cube (in seconds, lower is better).
110| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 110| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
111|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 111|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
112|vcube 212 |58.2 GiB| 0.03| 0.27| 1.04| 7.70| (a) | 112|vcube 212 |58.2 GiB| 0.03| 0.27| 1.04| 7.70| (a) |
113|H48 h11 |56.5 GiB| 0.04| 0.22| 0.97| 6.98| 5.95| 113|H48 h11 |56.5 GiB| 0.04| 0.14| 0.60| 3.97| 4.19|
114|vcube 404 |31.8 GiB| 0.07| 0.30| 1.65| 16.17| (a) | 114|vcube 404 |31.8 GiB| 0.07| 0.30| 1.65| 16.17| (a) |
115|H48 h10 |28.3 GiB| 0.07| 0.36| 1.79| 12.42| 14.03| 115|H48 h10 |28.3 GiB| 0.05| 0.20| 0.91| 6.65| 9.81|
116|vcube 308 |21.2 GiB| 0.05| 0.35| 1.78| 16.61| (a) | 116|vcube 308 |21.2 GiB| 0.05| 0.35| 1.78| 16.61| (a) |
117|H48 h9 |14.1 GiB| 0.11| 0.70| 3.48| 25.61| 25.37| 117|H48 h9 |14.1 GiB| 0.07| 0.39| 1.74| 12.54| 18.96|
118|vcube 208 | 7.3 GiB| 0.16| 1.47| 5.86| | (a) | 118|vcube 208 | 7.3 GiB| 0.16| 1.47| 5.86| | (a) |
119|H48 h8 | 7.1 GiB| 0.23| 1.74| 7.19| | | 119|H48 h8 | 7.1 GiB| 0.13| 0.90| 3.71| | |
120|H48 h7 | 3.5 GiB| 0.32| 2.45| 12.12| | | 120|H48 h7 | 3.5 GiB| 0.17| 1.28| 6.12| | |
121|vcube 112 | 2.4 GiB| 0.29| 3.13| 11.95| | (a) | 121|vcube 112 | 2.4 GiB| 0.29| 3.13| 11.95| | (a) |
122|H48 h6 | 1.8 GiB| 0.61| 4.61| 24.22| | | 122|H48 h6 | 1.8 GiB| 0.33| 2.47| 12.22| | |
123 123
124Time per cube adjusted for table size (in seconds \* GiB, lower is better). 124Time per cube adjusted for table size (in seconds \* GiB, lower is better).
125 125
126| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 126| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
127|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 127|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
128|vcube 212 |58.2 GiB| 2.03| 15.69| 60.25| 447.97| (a) | 128|vcube 212 |58.2 GiB| 2.03| 15.69| 60.25| 447.97| (a) |
129|H48 h11 |56.5 GiB| 2.53| 12.71| 54.58| 394.33| 336.47| 129|H48 h11 |56.5 GiB| 2.04| 8.17| 33.77| 224.59| 236.92|
130|vcube 404 |31.8 GiB| 2.32| 9.50| 52.46| 514.50| (a) | 130|vcube 404 |31.8 GiB| 2.32| 9.50| 52.46| 514.50| (a) |
131|H48 h10 |28.3 GiB| 2.11| 10.23| 50.61| 350.78| 396.48| 131|H48 h10 |28.3 GiB| 1.37| 5.76| 25.83| 187.88| 277.18|
132|vcube 308 |21.2 GiB| 1.02| 7.52| 37.82| 352.36| (a) | 132|vcube 308 |21.2 GiB| 1.02| 7.52| 37.82| 352.36| (a) |
133|H48 h9 |14.1 GiB| 1.57| 9.96| 49.23| 361.85| 358.45| 133|H48 h9 |14.1 GiB| 1.03| 5.45| 24.58| 177.17| 267.79|
134|vcube 208 | 7.3 GiB| 1.18| 10.69| 42.63| | (a) | 134|vcube 208 | 7.3 GiB| 1.18| 10.69| 42.63| | (a) |
135|H48 h8 | 7.1 GiB| 1.66| 12.27| 50.82| | | 135|H48 h8 | 7.1 GiB| 0.92| 6.39| 26.20| | |
136|H48 h7 | 3.5 GiB| 1.11| 8.67| 42.83| | | 136|H48 h7 | 3.5 GiB| 0.62| 4.53| 21.62| | |
137|vcube 112 | 2.4 GiB| 0.69| 7.59| 28.97| | (a) | 137|vcube 112 | 2.4 GiB| 0.69| 7.59| 28.97| | (a) |
138|H48 h6 | 1.8 GiB| 1.08| 8.16| 42.81| | | 138|H48 h6 | 1.8 GiB| 0.59| 4.37| 21.61| | |
139 139
140(a) vcube cannot parallelize on a single scramble, the results for the 140(a) vcube cannot parallelize on a single scramble, the results for the
141superflip are going to be the same as in the single thread case. 141superflip are going to be the same as in the single thread case.
@@ -153,32 +153,32 @@ Time per cube (in seconds, lower is better).
153| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 153| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
154|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 154|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
155|vcube 212 |58.2 GiB| 0.02| 0.13| 0.45| 2.84| (a) | 155|vcube 212 |58.2 GiB| 0.02| 0.13| 0.45| 2.84| (a) |
156|H48 h11 |56.5 GiB| 0.02| 0.08| 0.33| 2.22| 2.41| 156|H48 h11 |56.5 GiB| 0.02| 0.06| 0.22| 1.33| 1.84|
157|vcube 404 |31.8 GiB| 0.04| 0.14| 0.65| 6.08| (a) | 157|vcube 404 |31.8 GiB| 0.04| 0.14| 0.65| 6.08| (a) |
158|H48 h10 |28.3 GiB| 0.03| 0.13| 0.58| 4.21| 5.56| 158|H48 h10 |28.3 GiB| 0.03| 0.08| 0.33| 2.34| 4.18|
159|vcube 308 |21.2 GiB| 0.03| 0.19| 0.78| 6.67| (a) | 159|vcube 308 |21.2 GiB| 0.03| 0.19| 0.78| 6.67| (a) |
160|H48 h9 |14.1 GiB| 0.04| 0.25| 1.10| 8.05| 10.77| 160|H48 h9 |14.1 GiB| 0.04| 0.15| 0.64| 4.45| 8.09|
161|vcube 208 | 7.3 GiB| 0.08| 0.79| 2.43| | (a) | 161|vcube 208 | 7.3 GiB| 0.08| 0.79| 2.43| | (a) |
162|H48 h8 | 7.1 GiB| 0.08| 0.57| 2.40| | | 162|H48 h8 | 7.1 GiB| 0.06| 0.34| 1.36| | |
163|H48 h7 | 3.5 GiB| 0.11| 0.83| 4.00| | | 163|H48 h7 | 3.5 GiB| 0.07| 0.47| 2.20| | |
164|vcube 112 | 2.4 GiB| 0.15| 1.63| 5.10| | (a) | 164|vcube 112 | 2.4 GiB| 0.15| 1.63| 5.10| | (a) |
165|H48 h6 | 1.8 GiB| 0.21| 1.51| 7.74| | | 165|H48 h6 | 1.8 GiB| 0.13| 0.91| 4.39| | |
166 166
167Time per cube adjusted for table size (in seconds \* GiB, lower is better). 167Time per cube adjusted for table size (in seconds \* GiB, lower is better).
168 168
169| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 169| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
170|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 170|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
171|vcube 212 |58.2 GiB| 0.95| 7.83| 26.04| 165.03| (a) | 171|vcube 212 |58.2 GiB| 0.95| 7.83| 26.04| 165.03| (a) |
172|H48 h11 |56.5 GiB| 1.12| 4.61| 18.90| 125.27| 136.10| 172|H48 h11 |56.5 GiB| 1.34| 3.48| 12.19| 74.93| 103.98|
173|vcube 404 |31.8 GiB| 1.21| 4.60| 20.76| 193.43| (a) | 173|vcube 404 |31.8 GiB| 1.21| 4.60| 20.76| 193.43| (a) |
174|H48 h10 |28.3 GiB| 0.86| 3.61| 16.47| 118.85| 157.13| 174|H48 h10 |28.3 GiB| 0.74| 2.37| 9.46| 66.13| 118.23|
175|vcube 308 |21.2 GiB| 0.67| 4.01| 16.48| 141.49| (a) | 175|vcube 308 |21.2 GiB| 0.67| 4.01| 16.48| 141.49| (a) |
176|H48 h9 |14.1 GiB| 0.60| 3.51| 15.57| 113.71| 152.21| 176|H48 h9 |14.1 GiB| 0.51| 2.15| 8.98| 62.92| 114.31|
177|vcube 208 | 7.3 GiB| 0.56| 5.78| 17.68| | (a) | 177|vcube 208 | 7.3 GiB| 0.56| 5.78| 17.68| | (a) |
178|H48 h8 | 7.1 GiB| 0.59| 4.03| 16.98| | | 178|H48 h8 | 7.1 GiB| 0.40| 2.40| 9.59| | |
179|H48 h7 | 3.5 GiB| 0.41| 2.94| 14.12| | | 179|H48 h7 | 3.5 GiB| 0.26| 1.66| 7.77| | |
180|vcube 112 | 2.4 GiB| 0.35| 3.95| 12.37| | (a) | 180|vcube 112 | 2.4 GiB| 0.35| 3.95| 12.37| | (a) |
181|H48 h6 | 1.8 GiB| 0.38| 2.67| 13.68| | | 181|H48 h6 | 1.8 GiB| 0.23| 1.61| 7.76| | |
182 182
183(a) vcube cannot parallelize on a single scramble, the results for the 183(a) vcube cannot parallelize on a single scramble, the results for the
184superflip are going to be the same as in the single thread case. 184superflip are going to be the same as in the single thread case.
@@ -197,32 +197,34 @@ Time per cube (in seconds, lower is better).
197 197
198| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 198| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
199|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 199|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
200|H48 h11 |56.5 GiB| 0.05| 0.41| 3.69| 31.65| 21.80| 200|H48 h11 |56.5 GiB| 0.04| 0.26| 2.22| 18.96| 16.95|
201|H48 h10 |28.3 GiB| 0.07| 0.70| 6.73| 58.61| 48.62| 201|H48 h10 |28.3 GiB| 0.05| 0.42| 3.82| 34.42| 36.80|
202|H48 h9 |14.1 GiB| 0.12| 1.28| 12.93| | | 202|H48 h9 |14.1 GiB| 0.08| 0.73| 7.28| | |
203|H48 h8 | 7.1 GiB| 0.25| 2.72| 27.42| | | 203|H48 h8 | 7.1 GiB| 0.15| 1.56| 15.41| | |
204|H48 h7 | 3.5 GiB| 0.37| 4.24| 47.10| | | 204|H48 h7 | 3.5 GiB| 0.21| 2.38| 26.52| | |
205|H48 h6 | 1.8 GiB| 0.69| 8.18| 91.85| | | 205|H48 h6 | 1.8 GiB| 0.39| 4.67| 53.00| | |
206 206
207Time per cube adjusted for table size (in seconds \* GiB, lower is better). 207Time per cube adjusted for table size (in seconds \* GiB, lower is better).
208 208
209| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| 209| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
210|:---------|:-------|-------:|-------:|-------:|-------:|--------:| 210|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
211|H48 h11 |56.5 GiB| 2.57| 23.07| 208.71| 1788.12| 1231.86| 211|H48 h11 |56.5 GiB| 2.11| 14.55| 125.21| 1071.23| 957.47|
212|H48 h10 |28.3 GiB| 2.01| 19.77| 190.14| 1655.95| 1373.79| 212|H48 h10 |28.3 GiB| 1.48| 11.96| 107.83| 972.35| 1039.73|
213|H48 h9 |14.1 GiB| 1.72| 18.07| 182.67| | | 213|H48 h9 |14.1 GiB| 1.08| 10.29| 102.88| | |
214|H48 h8 | 7.1 GiB| 1.74| 19.21| 193.74| | | 214|H48 h8 | 7.1 GiB| 1.03| 10.99| 108.87| | |
215|H48 h7 | 3.5 GiB| 1.29| 14.98| 166.41| | | 215|H48 h7 | 3.5 GiB| 0.74| 8.41| 93.69| | |
216|H48 h6 | 1.8 GiB| 1.21| 14.47| 162.36| | | 216|H48 h6 | 1.8 GiB| 0.70| 8.25| 93.68| | |
217 217
218</details> 218</details>
219 219
220## Comments on the results 220## Comments on the results
221 221
222* Adjusting for table size, vcube generally is a bit faster than H48, 222* Adjusting for table size, H48 is generally faster than vcube.
223 except for 20 moves scrambles where H48 is a clear winner. 223* The gap between the two solvers is larger for scrambles with
224 longer optimal solutions.
224* On sets of 25 scrambles, H48 performs better than vcube when using 225* On sets of 25 scrambles, H48 performs better than vcube when using
225 multiple threads. However, this advantage will likely disappear (or 226 multiple threads, compared to their single-threaded performance.
227 However, this advantage will likely disappear (or
226 even invert) if we increase the size of the set. 228 even invert) if we increase the size of the set.
227 229
228## Other notes 230## Other notes
diff --git a/benchmarks/img/17moves16threads.png b/benchmarks/img/17moves16threads.png
index 487f3a6..45f5901 100644
--- a/benchmarks/img/17moves16threads.png
+++ b/benchmarks/img/17moves16threads.png
Binary files differ
diff --git a/benchmarks/img/17moves1thread.png b/benchmarks/img/17moves1thread.png
index d42147f..70bcad0 100644
--- a/benchmarks/img/17moves1thread.png
+++ b/benchmarks/img/17moves1thread.png
Binary files differ
diff --git a/benchmarks/img/17moves4threads.png b/benchmarks/img/17moves4threads.png
index 0b15f3e..edfca34 100644
--- a/benchmarks/img/17moves4threads.png
+++ b/benchmarks/img/17moves4threads.png
Binary files differ
diff --git a/benchmarks/img/18moves16threads.png b/benchmarks/img/18moves16threads.png
index 15351bd..df5210a 100644
--- a/benchmarks/img/18moves16threads.png
+++ b/benchmarks/img/18moves16threads.png
Binary files differ
diff --git a/benchmarks/img/18moves1thread.png b/benchmarks/img/18moves1thread.png
index 6812708..dafba4e 100644
--- a/benchmarks/img/18moves1thread.png
+++ b/benchmarks/img/18moves1thread.png
Binary files differ
diff --git a/benchmarks/img/18moves4threads.png b/benchmarks/img/18moves4threads.png
index fdde486..9b89bed 100644
--- a/benchmarks/img/18moves4threads.png
+++ b/benchmarks/img/18moves4threads.png
Binary files differ
diff --git a/benchmarks/img/19moves16threads.png b/benchmarks/img/19moves16threads.png
index 7b3a2ab..42212a6 100644
--- a/benchmarks/img/19moves16threads.png
+++ b/benchmarks/img/19moves16threads.png
Binary files differ
diff --git a/benchmarks/img/19moves1thread.png b/benchmarks/img/19moves1thread.png
index e269b4d..f51886e 100644
--- a/benchmarks/img/19moves1thread.png
+++ b/benchmarks/img/19moves1thread.png
Binary files differ
diff --git a/benchmarks/img/19moves4threads.png b/benchmarks/img/19moves4threads.png
index 70457c0..44ac692 100644
--- a/benchmarks/img/19moves4threads.png
+++ b/benchmarks/img/19moves4threads.png
Binary files differ
diff --git a/benchmarks/img/20moves16threads.png b/benchmarks/img/20moves16threads.png
index 5aa5b9d..82c28b2 100644
--- a/benchmarks/img/20moves16threads.png
+++ b/benchmarks/img/20moves16threads.png
Binary files differ
diff --git a/benchmarks/img/20moves1thread.png b/benchmarks/img/20moves1thread.png
index 44548a5..1f285d9 100644
--- a/benchmarks/img/20moves1thread.png
+++ b/benchmarks/img/20moves1thread.png
Binary files differ
diff --git a/benchmarks/img/20moves4threads.png b/benchmarks/img/20moves4threads.png
index 30f9744..c23fe81 100644
--- a/benchmarks/img/20moves4threads.png
+++ b/benchmarks/img/20moves4threads.png
Binary files 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 @@
1h48_single_thread = { 1h48_single_thread = {
2 6: {17: 52.9727, 18: 407.1435, 19: 2055.8785}, 2 6: {17: 31.2308, 18: 236.1986, 19: 1157.7502},
3 7: {17: 26.8541, 18: 214.7064, 19: 1053.9732}, 3 7: {17: 15.7227, 18: 121.1488, 19: 581.2004},
4 8: {17: 19.8408, 18: 152.2214, 19: 639.4834}, 4 8: {17: 11.5065, 18: 84.0366, 19: 353.2224},
5 9: {17: 8.9053, 18: 61.6760, 19: 294.6517}, 5 9: {17: 5.9123, 18: 37.1034, 19: 167.3496},
6 10: {17: 5.8445, 18: 30.0880, 19: 154.5389, 20: 1087.6552, "superflip": 48.8410}, 6 10: {17: 3.7338, 18: 18.9061, 19: 83.9382, 20: 587.7489, "superflip": 38.0522},
7 11: {17: 3.2420, 18: 18.3482, 19: 85.6898, 20: 581.9588, "superflip": 19.2614}, 7 11: {17: 2.3070, 18: 12.5145, 19: 56.0479, 20: 393.3391, "superflip": 15.5523},
8} 8}
9 9
10h48_4_threads = { 10h48_4_threads = {
11 6: {17: 15.2251, 18: 115.3688, 19: 605.5267}, 11 6: {17: 8.2859, 18: 61.8403, 19: 305.5934},
12 7: {17: 7.8799, 18: 61.3355, 19: 303.0388}, 12 7: {17: 4.3713, 18: 32.0550, 19: 152.9403},
13 8: {17: 5.8624, 18: 43.4193, 19: 179.8491}, 13 8: {17: 3.2607, 18: 22.6002, 19: 92.7235},
14 9: {17: 2.7696, 18: 17.6190, 19: 87.1236, 20: 640.3405, "superflip": 25.3726}, 14 9: {17: 1.8164, 18: 9.6520, 19: 43.5002, 20: 313.5156, "superflip": 18.9551},
15 10: {17: 1.8676, 18: 9.0543, 19: 44.7847, 20: 310.3914, "superflip": 14.0333}, 15 10: {17: 1.2098, 18: 5.1007, 19: 22.8530, 20: 166.2468, "superflip": 9.8108},
16 11: {17: 1.1173, 18: 5.6240, 19: 24.1467, 20: 174.4689, "superflip": 5.9548}, 16 11: {17: 0.9047, 18: 3.6152, 19: 14.9408, 20: 99.3673, "superflip": 4.1930},
17} 17}
18 18
19h48_16_threads = { 19h48_16_threads = {
20 6: {17: 5.3309, 18: 37.8142, 19: 193.5352}, 20 6: {17: 3.2536, 18: 22.7283, 19: 109.8073},
21 7: {17: 2.8657, 18: 20.8215, 19: 99.9139}, 21 7: {17: 1.8312, 18: 11.7609, 19: 54.9974},
22 8: {17: 2.0775, 18: 14.2672, 19: 60.0995}, 22 8: {17: 1.4242, 18: 8.4798, 19: 33.9483},
23 9: {17: 1.0595, 18: 6.2074, 19: 27.5523, 20: 201.2200, "superflip": 10.7739}, 23 9: {17: 0.9010, 18: 3.8064, 19: 15.8985, 20: 111.3421, "superflip": 8.0916},
24 10: {17: 0.7600, 18: 3.1980, 19: 14.5771, 20: 105.1686, "superflip": 5.5616}, 24 10: {17: 0.6528, 18: 2.1009, 19: 8.3680, 20: 58.5190, "superflip": 4.1848},
25 11: {17: 0.4946, 18: 2.0381, 19: 8.3613, 20: 55.4269, "superflip": 2.4087}, 25 11: {17: 0.5918, 18: 1.5379, 19: 5.3942, 20: 33.1522, "superflip": 1.8402},
26} 26}
27 27
28h48_all_solutions = { 28h48_all_solutions = {
29 6: {17: 17.1587, 18: 204.6182, 19: 2296.3135}, 29 6: {17: 9.8554, 18: 116.6374, 19: 1324.9303},
30 7: {17: 9.1380, 18: 106.0127, 19: 1177.4728}, 30 7: {17: 5.2495, 18: 59.4768, 19: 662.9106},
31 8: {17: 6.1641, 18: 67.9895, 19: 685.6033}, 31 8: {17: 3.6359, 18: 38.8943, 19: 385.2452},
32 9: {17: 3.0422, 18: 31.9821, 19: 323.2516}, 32 9: {17: 1.9026, 18: 18.2076, 19: 182.0522},
33 10: {17: 1.7822, 18: 17.4947, 19: 168.2516, 20: 1465.2950, "superflip": 48.6248}, 33 10: {17: 1.3117, 18: 10.5836, 19: 95.4136, 20: 860.4004, "superflip": 36.8007},
34 11: {17: 1.1364, 18: 10.2076, 19: 92.3419, 20: 791.1480, "superflip": 21.8014}, 34 11: {17: 0.9357, 18: 6.4383, 19: 55.3969, 20: 473.9622, "superflip": 16.9452},
35} 35}
36 36
diff --git a/doc/h48.md b/doc/h48.md
index d9ef192..694a07d 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -251,15 +251,18 @@ Moreover, as an additional heuristic, in case of a 0 read we also look
251up another pruning value in a table that takes into account only the 251up another pruning value in a table that takes into account only the
252position of the edges. This table is small (around 1MB), so repeated 252position of the edges. This table is small (around 1MB), so repeated
253accesses to it are not too slow. In practice, this gives a small speed up 253accesses to it are not too slow. In practice, this gives a small speed up
254of around 5%. More tables could be used to refine the fallback estimate, 254of around 5% for random scrambles. However, for small solvers (low values
255but each additional table leads to longer lookup times, especially if 255of h) and positions where corners are close to solved, this fallback
256it is too large to fit in cache. 256table gives dramatic improvements (up to a factor of 1000x in some
257manual tests).
257 258
258Previous versions of this implementation (up to commit 6c42463, or 259More tables could be used to refine the fallback estimate, but each
259to version 0.2) also included the possibility of a table with 4 bits 260additional table leads to longer lookup times, especially if it is too
260per entry, at least for the `h0` case. Such tables did not require 261large to fit in cache. Previous versions of this implementation (up
261a fallback lookup, but due to their large size they were not less 262to commit 6c42463, or to version 0.2) also included the possibility of
262efficient. Therefore, they have been removed. 263a table with 4 bits per entry, at least for the `h0` case. Such tables
264did not require a fallback lookup, but due to their large size they were
265not less efficient. Therefore, they have been removed.
263 266
264### Estimation refinements 267### Estimation refinements
265 268
@@ -312,6 +315,20 @@ inverse position*, then the coordinate on the normal position has not
312changed. Thus if we keep track of the last computed pruning value, 315changed. Thus if we keep track of the last computed pruning value,
313we can reuse it and avoid an expensive table lookup. 316we can reuse it and avoid an expensive table lookup.
314 317
318### Pruning pipeline and prefetching
319
320To improve the memory access pattern and exploit
321[prefetching](https://en.wikipedia.org/wiki/Cache_prefetching)
322opportunities, we don't expand each neighbor one by one in the
323pruning phase. Instead, we employ a *pruning pipeline*, where we
324first compute the cube and inverse position for each neighbor, and
325then we proceed through a series of stages, at each of which we
326compute some prune off some nodes and we pre-compute the data
327necessary for the next step.
328
329This pipeline-based strategy gives an speedup of around 25%.
330Adding manual prefetching, we get an additional 20% speedup.
331
315### Other optimizations 332### Other optimizations
316 333
317The H48 solver uses various other optimizations. 334The H48 solver uses various other optimizations.
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 4aa3799..15ac6ea 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -1,11 +1,5 @@
1#define H48_STARTING_MOVES 4 1#define H48_STARTING_MOVES 4
2 2#define H48_STARTING_CUBES 43254
3#if H48_STARTING_MOVES == 3
4#define H48_STARTING_CUBES 3240 /* Number of 3-move sequences */
5#elif H48_STARTING_MOVES == 4
6#define H48_STARTING_CUBES 43254 /* Number of 4-move sequences */
7#endif
8
9#define H48_SORT_TASKS_MIN_DEPTH 16 3#define H48_SORT_TASKS_MIN_DEPTH 16
10#define H48_LOG_PROGRESS_MIN_DEPTH 15 4#define H48_LOG_PROGRESS_MIN_DEPTH 15
11 5
@@ -14,6 +8,7 @@ typedef struct {
14 uint8_t moves[H48_STARTING_MOVES]; 8 uint8_t moves[H48_STARTING_MOVES];
15 int64_t rank; 9 int64_t rank;
16 uint64_t tmask[H48_STARTING_MOVES]; 10 uint64_t tmask[H48_STARTING_MOVES];
11 uint8_t pval;
17} solve_h48_task_t; 12} solve_h48_task_t;
18 13
19typedef struct { 14typedef struct {
@@ -25,15 +20,13 @@ typedef struct {
25 solution_settings_t *solution_settings; 20 solution_settings_t *solution_settings;
26 const uint64_t *tmask; 21 const uint64_t *tmask;
27 solution_list_t *solution_list; 22 solution_list_t *solution_list;
28 int8_t lb_normal; 23 uint8_t lb_normal;
29 int8_t lb_inverse; 24 uint8_t lb_inverse;
30 bool use_lb_normal;
31 bool use_lb_inverse;
32 uint8_t h; 25 uint8_t h;
33 uint8_t base; 26 uint8_t base;
34 const uint32_t *cocsepdata; 27 const uint32_t *cocsepdata;
35 const unsigned char *h48data; 28 const unsigned char *h48data;
36 const unsigned char *h48data_fallback_eoesep; 29 const unsigned char *eoesepdata;
37 uint64_t movemask_normal; 30 uint64_t movemask_normal;
38 uint64_t movemask_inverse; 31 uint64_t movemask_inverse;
39 uint64_t nodes_visited; 32 uint64_t nodes_visited;
@@ -58,11 +51,30 @@ typedef struct {
58 uint64_t tmask[H48_STARTING_MOVES]; 51 uint64_t tmask[H48_STARTING_MOVES];
59} dfsarg_solve_h48_maketasks_t; 52} dfsarg_solve_h48_maketasks_t;
60 53
54typedef struct {
55 cube_t cube;
56 cube_t inverse;
57 uint64_t coord;
58 uint8_t m;
59 uint8_t pn;
60 uint8_t pi;
61 uint8_t stop;
62} h48_prune_t;
63
61STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, 64STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned,
62 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long, 65 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long,
63 const unsigned char *, unsigned, char *, 66 const unsigned char *, unsigned, char *,
64 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); 67 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
65STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); 68STATIC_INLINE void h48_prune_pipeline(dfsarg_solve_h48_t [static 1],
69 h48_prune_t [static NMOVES], uint8_t, bool);
70STATIC_INLINE uint8_t h48_prune_lookup(
71 uint64_t, cube_t, dfsarg_solve_h48_t [static 1]);
72STATIC_INLINE uint8_t h48_prune_lookup_nocoord(
73 cube_t, dfsarg_solve_h48_t [static 1]);
74STATIC_INLINE void h48_prune_restore_normal(const h48_prune_t [static 1],
75 dfsarg_solve_h48_t [static 1], uint8_t);
76STATIC_INLINE void h48_prune_restore_inverse(const h48_prune_t [static 1],
77 dfsarg_solve_h48_t [static 1], uint8_t);
66STATIC int64_t solve_h48_maketasks( 78STATIC int64_t solve_h48_maketasks(
67 dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], 79 dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1],
68 solve_h48_task_t [static H48_STARTING_CUBES], int [static 1]); 80 solve_h48_task_t [static H48_STARTING_CUBES], int [static 1]);
@@ -104,151 +116,242 @@ STATIC long long solve_h48_dispatch(
104 poll_status, poll_status_data); 116 poll_status, poll_status_data);
105} 117}
106 118
107STATIC_INLINE bool 119STATIC_INLINE uint8_t
108solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) 120h48_prune_lookup(
121 uint64_t coord,
122 cube_t cube,
123 dfsarg_solve_h48_t arg[static 1]
124)
109{ 125{
110 uint32_t data, data_inv; 126 uint8_t p, pmin, pe;
111 int64_t coord;
112 int8_t target, nh, n;
113 uint8_t pval, pval_min, pval_eoesep;
114 127
115 arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES; 128 arg->table_lookups++;
116 arg->nodes_visited++; 129 p = get_h48_pval_and_min(arg->h48data, coord, &pmin);
130 if (p == 0) {
131 arg->table_fallbacks++;
132 pe = get_eoesep_pval_cube(arg->eoesepdata, cube);
133 return MAX(pmin, pe);
134 } else {
135 return p + arg->base;
136 }
137}
117 138
118 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; 139STATIC_INLINE uint8_t
119 target = arg->target_depth - n; 140h48_prune_lookup_nocoord(
141 cube_t cube,
142 dfsarg_solve_h48_t arg[static 1]
143)
144{
145 uint32_t cdata;
146 uint64_t coord;
120 147
121 /* We'll never get a bound higher than base + 3 */ 148 get_h48_cdata(cube, arg->cocsepdata, &cdata);
122 if (arg->base + 3 <= target) 149 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), arg->h);
123 return false; 150 return h48_prune_lookup(coord, cube, arg);
151}
124 152
125 /* Preliminary probing using last computed bound, if possible */ 153STATIC_INLINE void
154h48_prune_pipeline(
155 dfsarg_solve_h48_t arg[static 1],
156 h48_prune_t prune[static NMOVES],
157 uint8_t target,
158 bool normal
159)
160{
161 uint64_t i;
162 uint32_t cdata;
163 uint8_t m, p;
126 164
127 if ((arg->use_lb_normal && arg->lb_normal > target) || 165 /* Stage 0: initialize the neighbors array */
128 (arg->use_lb_inverse && arg->lb_inverse > target)) 166 memset(prune, 0, NMOVES * sizeof(h48_prune_t));
129 return true; 167 if (normal) {
168 for (m = 0; m < NMOVES; m++) {
169 prune[m].pi = m % 3 == 1 ? arg->lb_inverse : 0;
170 if (!(arg->movemask_normal & MM_SINGLE(m)) ||
171 prune[m].pi > target) {
172 prune[m].stop = 1;
173 continue;
174 }
175 prune[m].cube = move(arg->cube, m);
176 prune[m].inverse = premove(arg->inverse, m);
177 prune[m].m = m;
178 arg->nodes_visited++;
179 }
180 } else {
181 for (m = 0; m < NMOVES; m++) {
182 prune[m].pi = m % 3 == 1 ? arg->lb_normal : 0;
183 if (!(arg->movemask_inverse & MM_SINGLE(m)) ||
184 prune[m].pi > target) {
185 prune[m].stop = 1;
186 continue;
187 }
188 prune[m].cube = move(arg->inverse, m);
189 prune[m].inverse = premove(arg->cube, m);
190 prune[m].m = m;
191 arg->nodes_visited++;
192 }
193 }
130 194
131 /* Preliminary corner probing */ 195 /* We'll never get a bound higher than base + 3 */
196 if (target > arg->base + 3)
197 return;
132 198
133 if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target || 199 /* Stage 1: cdata and prefetch inverse */
134 get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target) 200 for (m = 0; m < NMOVES; m++) {
135 return true; 201 if (prune[m].stop)
202 continue;
136 203
137 /* Inverse probing */ 204 p = get_h48_cdata(prune[m].inverse, arg->cocsepdata, &cdata);
205 if (p > target) {
206 prune[m].stop = 1;
207 continue;
208 }
209 if (prune[m].pi == 0) {
210 prune[m].coord = coord_h48_edges(prune[m].inverse,
211 COCLASS(cdata), TTREP(cdata), arg->h);
212 i = H48_INDEX(H48_LINE_EXT(prune[m].coord));
213 prefetch(arg->h48data, i);
214 }
215 }
138 216
139 if (!arg->use_lb_inverse) { 217 /* Stage 2: get pval from inverse, prefetch normal */
140 arg->table_lookups++; 218 for (m = 0; m < NMOVES; m++) {
141 arg->use_lb_inverse = true; 219 if (prune[m].stop)
142 coord = coord_h48_edges( 220 continue;
143 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h);
144 pval = get_h48_pval_and_min(arg->h48data, coord, &pval_min);
145 221
146 if (pval == 0) { 222 if (prune[m].pi == 0) {
147 arg->table_fallbacks++; 223 prune[m].pi = h48_prune_lookup(
224 prune[m].coord, prune[m].inverse, arg);
225 if (prune[m].pi > target) {
226 prune[m].stop = 1;
227 continue;
228 }
229 }
148 230
149 pval_eoesep = get_eoesep_pval_cube( 231 p = get_h48_cdata(prune[m].cube, arg->cocsepdata, &cdata);
150 arg->h48data_fallback_eoesep, arg->inverse); 232 if (p > target) {
151 pval = MAX(pval_min, pval_eoesep); 233 prune[m].stop = 1;
152 } else { 234 continue;
153 pval += arg->base;
154 } 235 }
236 prune[m].coord = coord_h48_edges(
237 prune[m].cube, COCLASS(cdata), TTREP(cdata), arg->h);
238 i = H48_INDEX(H48_LINE_EXT(prune[m].coord));
239 prefetch(arg->h48data, i);
240 }
155 241
156 arg->lb_inverse = pval; 242 /* Stage 3: get pval from normal */
243 for (m = 0; m < NMOVES; m++) {
244 if (prune[m].stop)
245 continue;
246
247 prune[m].pn = h48_prune_lookup(
248 prune[m].coord, prune[m].cube, arg);
249 prune[m].stop = prune[m].pn > target;
157 } 250 }
251}
158 252
159 if (arg->lb_inverse > target) 253STATIC_INLINE void
160 return true; 254h48_prune_restore_normal(
161 nh = arg->lb_inverse == target; 255 const h48_prune_t prune[static 1],
162 arg->movemask_normal = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES; 256 dfsarg_solve_h48_t arg[static 1],
257 uint8_t target
258)
259{
260 uint8_t nm;
163 261
164 /* Normal probing */ 262 arg->cube = prune->cube;
263 arg->inverse = prune->inverse;
264 arg->lb_inverse = prune->pi;
265 arg->lb_normal = prune->pn;
165 266
166 if (!arg->use_lb_normal) { 267 nm = arg->solution_moves->nmoves;
167 arg->table_lookups++; 268 arg->solution_moves->moves[nm-1] = prune->m;
168 arg->use_lb_normal = true; 269 arg->movemask_normal = allowedmask[movebase(prune->m)];
169 coord = coord_h48_edges(
170 arg->cube, COCLASS(data), TTREP(data), arg->h);
171 pval = get_h48_pval_and_min(arg->h48data, coord, &pval_min);
172 270
173 if (pval == 0) { 271 if (arg->lb_inverse == target)
174 arg->table_fallbacks++; 272 arg->movemask_normal &= MM18_NOHALFTURNS;
273 if (arg->lb_normal == target)
274 arg->movemask_inverse &= MM18_NOHALFTURNS;
275}
175 276
176 pval_eoesep = get_eoesep_pval_cube( 277STATIC_INLINE void
177 arg->h48data_fallback_eoesep, arg->cube); 278h48_prune_restore_inverse(
178 pval = MAX(pval_min, pval_eoesep); 279 const h48_prune_t prune[static 1],
179 } else { 280 dfsarg_solve_h48_t arg[static 1],
180 pval += arg->base; 281 uint8_t target
181 } 282)
283{
284 uint8_t nm;
182 285
183 arg->lb_normal = pval; 286 arg->cube = prune->inverse;
184 } 287 arg->inverse = prune->cube;
288 arg->lb_inverse = prune->pn;
289 arg->lb_normal = prune->pi;
185 290
186 if (arg->lb_normal > target) 291 nm = arg->solution_moves->npremoves;
187 return true; 292 arg->solution_moves->premoves[nm-1] = prune->m;
188 nh = arg->lb_normal == target; 293 arg->movemask_inverse = allowedmask[movebase(prune->m)];
189 arg->movemask_inverse = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES;
190 294
191 return false; 295 if (arg->lb_inverse == target)
296 arg->movemask_normal &= MM18_NOHALFTURNS;
297 if (arg->lb_normal == target)
298 arg->movemask_inverse &= MM18_NOHALFTURNS;
192} 299}
193 300
194STATIC int64_t 301STATIC int64_t
195solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) 302solve_h48_dfs(dfsarg_solve_h48_t arg[static 1])
196{ 303{
197 int64_t ret, n; 304 int64_t ret, n;
198 uint8_t m, nm, lbn, lbi, t; 305 uint8_t m, nm, nn, ni, target;
199 uint64_t mm_normal, mm_inverse; 306 uint64_t mm_normal, mm_inverse;
200 bool ulbi, ulbn; 307 cube_t cube, backup_cube, backup_inverse;
201 cube_t backup_cube, backup_inverse; 308 h48_prune_t prune[NMOVES];
202
203 nm = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
204 if (equal(arg->cube, SOLVED_CUBE)) {
205 if (arg->target_depth != nm)
206 return 0;
207 wrapthread_mutex_lock(arg->solutions_mutex);
208 ret = appendsolution(arg->solution_moves, H48_STARTING_MOVES,
209 arg->tmask, arg->solution_settings, arg->solution_list);
210 wrapthread_mutex_unlock(arg->solutions_mutex);
211 return ret;
212 }
213 309
214 if (solve_h48_stop(arg)) 310 if (equal(arg->cube, SOLVED_CUBE) || /* Solved before target depth */
311 arg->solution_list->nsols >= arg->solution_settings->maxsolutions)
215 return 0; 312 return 0;
216 313
217 t = arg->solution_list->shortest_sol + arg->solution_settings->optimal; 314 nn = arg->solution_moves->nmoves;
218 if (nm + 1 > MIN(t, arg->target_depth) || 315 ni = arg->solution_moves->npremoves;
219 arg->solution_list->nsols >= arg->solution_settings->maxsolutions) 316 nm = nn + ni;
317 target = arg->target_depth - (nm + 1);
318 mm_normal = arg->movemask_normal;
319 mm_inverse = arg->movemask_inverse;
320 if (target == 0) { /* Last move */
321 arg->solution_moves->nmoves++;
322 for (m = 0; m < NMOVES; m++) {
323 if (!(mm_normal & mm_inverse & MM_SINGLE(m)))
324 continue;
325 cube = move(arg->cube, m);
326 arg->solution_moves->moves[nn] = m;
327 arg->nodes_visited++;
328 if (!equal(cube, SOLVED_CUBE))
329 continue;
330 wrapthread_mutex_lock(arg->solutions_mutex);
331 ret = appendsolution(arg->solution_moves,
332 H48_STARTING_MOVES, arg->tmask,
333 arg->solution_settings, arg->solution_list);
334 wrapthread_mutex_unlock(arg->solutions_mutex);
335 arg->solution_moves->nmoves--;
336 return ret;
337 }
338 arg->solution_moves->nmoves--;
220 return 0; 339 return 0;
340 }
221 341
222 backup_cube = arg->cube; 342 backup_cube = arg->cube;
223 backup_inverse = arg->inverse; 343 backup_inverse = arg->inverse;
224 lbn = arg->lb_normal;
225 lbi = arg->lb_inverse;
226 ulbn = arg->use_lb_normal;
227 ulbi = arg->use_lb_inverse;
228 344
229 ret = 0; 345 ret = 0;
230 mm_normal = arg->movemask_normal;
231 if (arg->solution_moves->nmoves > 0) {
232 m = arg->solution_moves->moves[arg->solution_moves->nmoves-1];
233 mm_normal &= allowedmask[movebase(m)];
234 }
235 mm_inverse = arg->movemask_inverse;
236 if (arg->solution_moves->npremoves > 0) {
237 m = arg->solution_moves->premoves[arg->solution_moves->npremoves-1];
238 mm_inverse &= allowedmask[movebase(m)];
239 }
240 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { 346 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
347 h48_prune_pipeline(arg, prune, target, true);
241 arg->solution_moves->nmoves++; 348 arg->solution_moves->nmoves++;
242 for (m = 0; m < 18; m++) { 349 for (m = 0; m < NMOVES; m++) {
243 if (!(mm_normal & MM_SINGLE(m))) 350 if (prune[m].stop)
244 continue; 351 continue;
245 arg->solution_moves->moves[ 352 arg->movemask_normal = mm_normal;
246 arg->solution_moves->nmoves-1] = m; 353 arg->movemask_inverse = mm_inverse;
247 arg->cube = move(backup_cube, m); 354 h48_prune_restore_normal(&prune[m], arg, target);
248 arg->inverse = premove(backup_inverse, m);
249 arg->lb_inverse = lbi;
250 arg->use_lb_normal = false;
251 arg->use_lb_inverse = ulbi && m % 3 == 1;
252 n = solve_h48_dfs(arg); 355 n = solve_h48_dfs(arg);
253 if (n < 0) 356 if (n < 0)
254 return n; 357 return n;
@@ -256,17 +359,14 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1])
256 } 359 }
257 arg->solution_moves->nmoves--; 360 arg->solution_moves->nmoves--;
258 } else { 361 } else {
362 h48_prune_pipeline(arg, prune, target, false);
259 arg->solution_moves->npremoves++; 363 arg->solution_moves->npremoves++;
260 for (m = 0; m < 18; m++) { 364 for (m = 0; m < NMOVES; m++) {
261 if(!(mm_inverse & MM_SINGLE(m))) 365 if (prune[m].stop)
262 continue; 366 continue;
263 arg->solution_moves->premoves[ 367 arg->movemask_normal = mm_normal;
264 arg->solution_moves->npremoves-1] = m; 368 arg->movemask_inverse = mm_inverse;
265 arg->inverse = move(backup_inverse, m); 369 h48_prune_restore_inverse(&prune[m], arg, target);
266 arg->cube = premove(backup_cube, m);
267 arg->lb_normal = lbn;
268 arg->use_lb_inverse = false;
269 arg->use_lb_normal = ulbn && m % 3 == 1;
270 n = solve_h48_dfs(arg); 370 n = solve_h48_dfs(arg);
271 if (n < 0) 371 if (n < 0)
272 return n; 372 return n;
@@ -277,6 +377,8 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1])
277 377
278 arg->cube = backup_cube; 378 arg->cube = backup_cube;
279 arg->inverse = backup_inverse; 379 arg->inverse = backup_inverse;
380 arg->movemask_normal = mm_normal;
381 arg->movemask_inverse = mm_inverse;
280 382
281 return ret; 383 return ret;
282} 384}
@@ -286,7 +388,7 @@ solve_h48_runthread(void *arg)
286{ 388{
287 int i, j; 389 int i, j;
288 uint8_t lastmove; 390 uint8_t lastmove;
289 int64_t nprev; 391 int64_t d, f, nprev;
290 dfsarg_solve_h48_t *dfsarg; 392 dfsarg_solve_h48_t *dfsarg;
291 393
292 dfsarg = (dfsarg_solve_h48_t *)arg; 394 dfsarg = (dfsarg_solve_h48_t *)arg;
@@ -309,11 +411,15 @@ solve_h48_runthread(void *arg)
309 move(dfsarg->cube, dfsarg->tasks[i].moves[j]); 411 move(dfsarg->cube, dfsarg->tasks[i].moves[j]);
310 dfsarg->inverse = inverse(dfsarg->cube); 412 dfsarg->inverse = inverse(dfsarg->cube);
311 413
414 dfsarg->nodes_visited++;
415 if (dfsarg->tasks[i].pval + H48_STARTING_MOVES
416 > dfsarg->target_depth)
417 continue;
418
312 dfsarg->lb_normal = 0; 419 dfsarg->lb_normal = 0;
313 dfsarg->lb_inverse = 0; 420 dfsarg->lb_inverse = 0;
314 dfsarg->use_lb_normal = false; 421 dfsarg->movemask_normal = allowedmask[
315 dfsarg->use_lb_inverse = false; 422 movebase(dfsarg->tasks[i].moves[H48_STARTING_MOVES-1])];
316 dfsarg->movemask_normal = MM18_ALLMOVES;
317 dfsarg->movemask_inverse = MM18_ALLMOVES; 423 dfsarg->movemask_inverse = MM18_ALLMOVES;
318 dfsarg->tmask = dfsarg->tasks[i].tmask; 424 dfsarg->tmask = dfsarg->tasks[i].tmask;
319 425
@@ -331,8 +437,9 @@ solve_h48_runthread(void *arg)
331 inspired by Andrew Skalski's vcube. 437 inspired by Andrew Skalski's vcube.
332 */ 438 */
333 lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1]; 439 lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1];
334 dfsarg->tasks[i].rank = (dfsarg->nodes_visited - nprev) * 440 d = (int64_t)dfsarg->nodes_visited - nprev;
335 (movebase(lastmove) % 2 == 0 ? 47525 : 58206); 441 f = movebase(lastmove) % 2 == 0 ? 47525 : 58206;
442 dfsarg->tasks[i].rank = d * f;
336 nprev = dfsarg->nodes_visited; 443 nprev = dfsarg->nodes_visited;
337 } 444 }
338 445
@@ -374,6 +481,8 @@ solve_h48_maketasks(
374 481
375 if (mtarg->nmoves == H48_STARTING_MOVES) { 482 if (mtarg->nmoves == H48_STARTING_MOVES) {
376 tasks[*ntasks].cube = mtarg->cube; 483 tasks[*ntasks].cube = mtarg->cube;
484 tasks[*ntasks].pval =
485 h48_prune_lookup_nocoord(mtarg->cube, solve_arg);
377 memcpy(tasks[*ntasks].moves, mtarg->moves, 486 memcpy(tasks[*ntasks].moves, mtarg->moves,
378 H48_STARTING_MOVES * sizeof(uint8_t)); 487 H48_STARTING_MOVES * sizeof(uint8_t));
379 memcpy(tasks[*ntasks].tmask, mtarg->tmask, 488 memcpy(tasks[*ntasks].tmask, mtarg->tmask,
@@ -393,7 +502,7 @@ solve_h48_maketasks(
393 502
394 mtarg->nmoves++; 503 mtarg->nmoves++;
395 backup_cube = mtarg->cube; 504 backup_cube = mtarg->cube;
396 for (m = 0; m < 18; m++) { 505 for (m = 0; m < NMOVES; m++) {
397 if (!(mm & MM_SINGLE(m))) 506 if (!(mm & MM_SINGLE(m)))
398 continue; 507 continue;
399 508
@@ -514,7 +623,7 @@ solve_h48(
514 .base = info.base, 623 .base = info.base,
515 .cocsepdata = cocsepdata, 624 .cocsepdata = cocsepdata,
516 .h48data = h48data, 625 .h48data = h48data,
517 .h48data_fallback_eoesep = eoesep, 626 .eoesepdata = eoesep,
518 .solution_moves = &solution_moves[i], 627 .solution_moves = &solution_moves[i],
519 .solution_settings = &settings, 628 .solution_settings = &settings,
520 .solution_list = &sollist, 629 .solution_list = &sollist,
diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h
index d92d5ad..8817348 100644
--- a/src/solvers/solutions.h
+++ b/src/solvers/solutions.h
@@ -108,7 +108,7 @@ last_solution_is_duplicate(const solution_list_t l[static 1])
108 j--; 108 j--;
109 for (i = l->used-2; l->buf[i] == l->buf[j]; i--, j--) { 109 for (i = l->used-2; l->buf[i] == l->buf[j]; i--, j--) {
110 if (l->buf[i-1] == '\n') { 110 if (l->buf[i-1] == '\n') {
111 if (l->buf[j-1] == '\n' || j == 0) 111 if (j == 0 || l->buf[j-1] == '\n')
112 return true; 112 return true;
113 else break; 113 else break;
114 } 114 }
diff --git a/src/utils/prefetch.h b/src/utils/prefetch.h
new file mode 100644
index 0000000..89b14e8
--- /dev/null
+++ b/src/utils/prefetch.h
@@ -0,0 +1,15 @@
1#if defined(AVX2)
2
3#define prefetch(a, i) _mm_prefetch(a+i, _MM_HINT_T0)
4
5#else
6#if defined(__GNUC__) || defined(__clang__)
7
8#define prefetch(a, i) __builtin_prefetch(a+i, 0, 0)
9
10#else
11
12#define prefetch(a, i) (void)i
13
14#endif
15#endif
diff --git a/src/utils/utils.h b/src/utils/utils.h
index 383781a..e322f20 100644
--- a/src/utils/utils.h
+++ b/src/utils/utils.h
@@ -4,3 +4,4 @@
4#include "math.h" 4#include "math.h"
5#include "sleep.h" 5#include "sleep.h"
6#include "wrapthread.h" 6#include "wrapthread.h"
7#include "prefetch.h"

Generated with cgit - Back to sebastiano.tronto.net