Performance Comparison
Benchmark project is here.
All tests were run on a machine with the following specifications:
3 GHz 6-Core Intel Core i5, 40GB 2667 MHz DDR4
All results are presented in seconds.
Solvers:
- iOverlay(Rust) v1.9.0 (multithreading on/off)
- iOverlay(Swift) v1.13.0
- Clipper2(C++) v1.4.0
- Boost(C++) v1.86.0
Checkerboard Test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 | Boost |
|---|---|---|---|---|---|
| 5 | 0.000014 | 0.000006 | 0.000006 | 0.000007 | 0.000045 |
| 25 | 0.000100 | 0.000036 | 0.000036 | 0.000038 | 0.000595 |
| 113 | 0.000589 | 0.000197 | 0.000196 | 0.000208 | 0.004446 |
| 481 | 0.004105 | 0.001117 | 0.001117 | 0.001017 | 0.060791 |
| 1985 | 0.012643 | 0.004914 | 0.004935 | 0.005182 | 1.103624 |
| 8065 | 0.055664 | 0.020674 | 0.019785 | 0.024013 | 21.080339 |
| 32513 | 0.234840 | 0.091871 | 0.083285 | 0.154054 | 412.630289 |
| 130561 | 0.993920 | 0.424643 | 0.372978 | 1.067439 | ---- |
| 523265 | 4.410302 | 2.043570 | 2.008339 | 8.346041 | ---- |
| 2095105 | 18.451646 | 9.291384 | 7.936810 | 73.312335 | ---- |
| 8384513 | 78.719305 | 38.639666 | 33.742216 | 644.337867 | ---- |
Not Overlap Test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 | Boost |
|---|---|---|---|---|---|
| 5 | 0.000009 | 0.000003 | 0.000003 | 0.000005 | 0.000003 |
| 25 | 0.000041 | 0.000012 | 0.000011 | 0.000021 | 0.000021 |
| 113 | 0.000204 | 0.000061 | 0.000062 | 0.000097 | 0.000223 |
| 481 | 0.001052 | 0.000346 | 0.000344 | 0.000457 | 0.002621 |
| 1985 | 0.004978 | 0.001679 | 0.001668 | 0.002114 | 0.036257 |
| 8065 | 0.021336 | 0.005912 | 0.005425 | 0.010783 | 0.558494 |
| 32513 | 0.089523 | 0.028454 | 0.024718 | 0.056281 | 8.852867 |
| 130561 | 0.375594 | 0.127448 | 0.107485 | 0.369146 | 146.041905 |
| 523265 | 1.663087 | 0.635898 | 0.538060 | 2.695334 | ---- |
| 2095105 | 6.947932 | 2.708549 | 2.470210 | 20.665812 | ---- |
| 8384513 | 28.777569 | 13.514846 | 9.601191 | 167.966801 | ---- |
Lines Net Test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 | Boost |
|---|---|---|---|---|---|
| 4 | 0.000014 | 0.000004 | 0.000004 | 0.000004 | 0.000014 |
| 8 | 0.000049 | 0.000014 | 0.000014 | 0.000012 | 0.000054 |
| 16 | 0.000195 | 0.000049 | 0.000050 | 0.000043 | 0.000370 |
| 32 | 0.001295 | 0.000195 | 0.000196 | 0.000176 | 0.003175 |
| 64 | 0.004994 | 0.001013 | 0.001016 | 0.000749 | 0.055749 |
| 128 | 0.021239 | 0.004046 | 0.003970 | 0.003441 | 23.531991 |
| 256 | 0.091427 | 0.018815 | 0.020870 | 0.018417 | 412.528984 |
| 512 | 0.255989 | 0.088601 | 0.096745 | 0.115229 | ---- |
| 1024 | 1.146842 | 0.417128 | 0.397470 | 0.759640 | ---- |
| 2048 | 4.808548 | 1.844754 | 1.537385 | 5.595165 | ---- |
| 4096 | 20.190101 | 7.514548 | 7.696920 | 45.934461 | ---- |
Spiral Test
* There is now boost results for this test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 |
|---|---|---|---|---|
| 2 | 0.000006 | 0.000002 | 0.000002 | 0.000002 |
| 4 | 0.000010 | 0.000005 | 0.000005 | 0.000004 |
| 8 | 0.000019 | 0.000009 | 0.000009 | 0.000007 |
| 16 | 0.000040 | 0.000020 | 0.000020 | 0.000014 |
| 32 | 0.000095 | 0.000048 | 0.000048 | 0.000031 |
| 64 | 0.000218 | 0.000129 | 0.000127 | 0.000083 |
| 128 | 0.000490 | 0.000304 | 0.000305 | 0.000202 |
| 256 | 0.001105 | 0.000668 | 0.000669 | 0.000476 |
| 512 | 0.003385 | 0.001599 | 0.001606 | 0.001195 |
| 1024 | 0.006174 | 0.003572 | 0.003560 | 0.002941 |
| 2048 | 0.013200 | 0.005000 | 0.004930 | 0.007578 |
| 4096 | 0.026065 | 0.009576 | 0.009528 | 0.020287 |
| 8192 | 0.055944 | 0.017583 | 0.018779 | 0.054647 |
| 16384 | 0.112375 | 0.040145 | 0.040263 | 0.181050 |
| 32768 | 0.237412 | 0.076642 | 0.076609 | 0.606854 |
| 65536 | 0.473847 | 0.181912 | 0.181387 | 2.013809 |
| 131072 | 0.981729 | 0.343917 | 0.331046 | 6.547658 |
| 262144 | 1.979541 | 0.781770 | 0.833816 | 21.171540 |
| 524288 | 4.101912 | 1.417144 | 1.472624 | 72.147615 |
| 1048576 | 8.254108 | 3.188509 | 3.232834 | 259.866180 |
Windows Test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 | Boost |
|---|---|---|---|---|---|
| 8 | 0.000016 | 0.000006 | 0.000006 | 0.000008 | 0.000006 |
| 32 | 0.000062 | 0.000021 | 0.000021 | 0.000028 | 0.000037 |
| 128 | 0.000276 | 0.000096 | 0.000097 | 0.000112 | 0.000266 |
| 512 | 0.001306 | 0.000519 | 0.000516 | 0.000507 | 0.002482 |
| 2048 | 0.005543 | 0.001675 | 0.001548 | 0.002454 | 0.030949 |
| 8192 | 0.023805 | 0.007519 | 0.006780 | 0.012364 | 0.448009 |
| 32768 | 0.104822 | 0.038832 | 0.034149 | 0.076850 | 7.013886 |
| 131072 | 0.445712 | 0.192338 | 0.159685 | 0.568316 | 109.745463 |
| 524288 | 1.862371 | 0.835050 | 0.703147 | 4.142673 | ---- |
| 2097152 | 7.657815 | 3.761808 | 3.182362 | 33.165570 | ---- |
| 8388608 | 30.833973 | 15.476744 | 12.058687 | 265.387333 | ---- |
Nested Squares Test
| Squares | Swift | Rust (mt off) | Rust (mt on) | Clipper2 | Boost |
|---|---|---|---|---|---|
| 4 | 0.000022 | 0.000009 | 0.000009 | 0.000012 | 0.000153 |
| 8 | 0.000045 | 0.000017 | 0.000017 | 0.000023 | 0.000387 |
| 16 | 0.000098 | 0.000035 | 0.000034 | 0.000050 | 0.000792 |
| 32 | 0.000238 | 0.000081 | 0.000081 | 0.000118 | 0.001757 |
| 64 | 0.000624 | 0.000210 | 0.000217 | 0.000291 | 0.004145 |
| 128 | 0.001853 | 0.000594 | 0.000608 | 0.000806 | 0.010646 |
| 256 | 0.002398 | 0.001992 | 0.002016 | 0.003415 | 0.036101 |
| 512 | 0.005013 | 0.002555 | 0.002641 | 0.015989 | 0.141906 |
| 1024 | 0.016067 | 0.007851 | 0.005925 | 0.081267 | 0.560183 |
| 2048 | 0.033194 | 0.024523 | 0.018777 | 0.461883 | 2.425802 |
| 4096 | 0.150601 | 0.060516 | 0.044756 | 2.347209 | 11.419096 |
| 8192 | 0.311691 | 0.245160 | 0.165539 | 10.612424 | 49.299261 |
| 16384 | 0.752357 | 0.485605 | 0.331655 | 46.205474 | 206.646450 |
| 32768 | 2.581991 | 1.814993 | 1.148905 | 251.260857 | ---- |
| 65536 | 10.368794 | 4.031631 | 2.197493 | 3502.233611 | ---- |
| 131072 | 23.250746 | 15.731705 | 8.194153 | ---- | ---- |
| 262144 | 48.529555 | 30.809760 | 15.285741 | ---- | ---- |