aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-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
13 files changed, 53 insertions, 51 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

Generated with cgit - Back to sebastiano.tronto.net