前段时间在折腾数独,看了一下比较快的几个实现,基本都要靠 SIMD,最后选中的是 tdoku,不过里面的 SIMD 都是 x86 上的,我现在主力机已经变成了 M1 Ultra Mac Studio,于是开始折腾 SIMD everywhere。
使用方法还是很简单的,引入 SIMDe 的头文件,然后把 _mm_blabla 都加上 simde 的前缀变成 simde_mm_blabla,然后对应修改一下宏开关和 CMake 文件就好。当然也有一些调用没法翻译,例如 _mm_cmpeq_epi8_mask,用宏开关回退处理一下就好。
然后跑了一下性能测试,以下结果是默认包含更早的指令集的,比如 AVX512 默认就开启了所有 SSE 以及 AVX2 AVX1 等。
AVX512
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 441192.3 | 2.3 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 145510.3 | 6.9 | 47.7% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 134246.9 | 7.4 | 78.7% | 0.61 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 48798.4 | 20.5 | 7.9% | 9.05 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 10001.8 | 100.0 | 0.0% | 55.00 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 8302.0 | 120.5 | 0.0% | 65.00 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 5304.0 | 188.5 | 0.0% | 113.19 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 185128.5 | 5.4 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 1767598.2 | 0.6 | 97.4% | 0.28 |
AVX2
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 457427.4 | 2.2 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 153541.9 | 6.5 | 47.4% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 140428.5 | 7.1 | 78.7% | 0.61 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 51233.8 | 19.5 | 7.9% | 9.06 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 10519.0 | 95.1 | 0.0% | 55.03 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 8706.3 | 114.9 | 0.0% | 64.97 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 5442.9 | 183.7 | 0.0% | 113.07 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 191109.5 | 5.2 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 1814562.8 | 0.6 | 97.4% | 0.28 |
AVX
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 644955.6 | 1.6 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 218633.8 | 4.6 | 47.6% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 198852.5 | 5.0 | 78.6% | 0.62 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 72522.9 | 13.8 | 7.9% | 9.06 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 14989.6 | 66.7 | 0.0% | 54.92 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 12312.2 | 81.2 | 0.0% | 64.97 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 7976.6 | 125.4 | 0.0% | 113.19 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 271330.8 | 3.7 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 2201973.6 | 0.5 | 97.4% | 0.32 |
SSE 4.2
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 649117.3 | 1.5 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 214462.4 | 4.7 | 47.5% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 194553.9 | 5.1 | 78.7% | 0.61 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 70727.5 | 14.1 | 7.9% | 9.06 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 14585.9 | 68.6 | 0.0% | 54.94 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 11865.1 | 84.3 | 0.0% | 64.99 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 7667.1 | 130.4 | 0.0% | 113.12 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 268004.8 | 3.7 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 2327193.4 | 0.4 | 97.4% | 0.28 |
SSE 4.1
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 630080.5 | 1.6 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 209809.2 | 4.8 | 47.4% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 192380.4 | 5.2 | 78.7% | 0.61 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 70330.4 | 14.2 | 7.9% | 9.06 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 14396.9 | 69.5 | 0.0% | 54.96 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 12090.5 | 82.7 | 0.0% | 64.96 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 7959.7 | 125.6 | 0.0% | 113.17 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 255759.0 | 3.9 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 2227786.9 | 0.4 | 97.4% | 0.28 |
SSSE 3
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 636460.5 | 1.6 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 211631.3 | 4.7 | 47.9% | 1.12 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 192110.1 | 5.2 | 78.7% | 0.62 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 71057.8 | 14.1 | 7.9% | 9.05 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 14736.9 | 67.9 | 0.0% | 54.96 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 12656.2 | 79.0 | 0.0% | 64.95 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 8108.5 | 123.3 | 0.0% | 113.09 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 279108.4 | 3.6 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 2416115.4 | 0.4 | 97.5% | 0.27 |
SSE 2
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 276657.1 | 3.6 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 92831.1 | 10.8 | 47.4% | 1.12 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 84223.8 | 11.9 | 78.7% | 0.62 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 30532.7 | 32.8 | 7.9% | 9.04 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 6300.4 | 158.7 | 0.0% | 54.85 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 5162.1 | 193.7 | 0.0% | 64.99 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 3302.7 | 302.8 | 0.0% | 113.13 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 112815.9 | 8.9 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 1169978.6 | 0.9 | 97.4% | 0.28 |
None
|data/puzzles0_kaggle | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 273777.6 | 3.7 | 100.0% | 0.00 |
|data/puzzles1_unbiased | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 89851.1 | 11.1 | 47.3% | 1.13 |
|data/puzzles2_17_clue | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 80658.1 | 12.4 | 78.7% | 0.62 |
|data/puzzles3_magictour_top1465 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 29483.5 | 33.9 | 7.9% | 9.06 |
|data/puzzles4_forum_hardest_1905 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 6055.2 | 165.1 | 0.0% | 55.05 |
|data/puzzles5_forum_hardest_1905_11+ | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 5052.6 | 197.9 | 0.0% | 64.90 |
|data/puzzles6_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 3295.0 | 303.5 | 0.0% | 113.23 |
|data/puzzles7_serg_benchmark | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 111730.9 | 9.0 | 0.0% | 7.13 |
|data/puzzles8_gen_puzzles | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|tdoku T/shrc+./m+| 1176020.0 | 0.9 | 97.4% | 0.28 |
开 SSSE 3 到 AVX 性能都差不多,相比于 x86 的原生性能,差距还是比较明显的,只能说 neon 这玩意儿坑略多。
Apple 在 M 处理器上还有 AMX,支持类似 AVX 512 的 512 的位宽,不过是有点类似后门的玩意儿,只能通过阿婆自己的 Accelerate 库间接调用,也有人做了逆向。以后有空再折腾吧。