本文算法完全来自于丹大师的博客，只是简单做一点内容上的扩展。
提前省流：具体算法就是减少分支；丹大师的测试结果在现在看来不适用。
基本的查找
常规的容器一般使用如下查找算法：
#include <cstddef>
bool find(int* arr, size_t size, int val) {
#pragma clang loop unroll_count(4)
for(size_t i = 0; i < size; ++i) {
if(val == arr[i]) return true;
}
return false;
}
clang++-18 生成如下指令（-O3，简化了重复占版面的循环展开）：
0000000000000000 <_Z4findPimi>:
0: 48 85 f6 test %rsi,%rsi // 判断是否为空
3: 74 23 je 28 <_Z4findPimi+0x28> // 如果是，则返回 false
5: b0 01 mov $0x1,%al // 返回值预设 true，同时作为下标计数器（见 1c）
7: 39 17 cmp %edx,(%rdi) // 对比 val 和 arr[0]
9: 74 1c je 27 <_Z4findPimi+0x27> // 如果相等，则返回预设的 true
b: b9 01 00 00 00 mov $0x1,%ecx // %rcx/%ecx 和 %rax 用于下标计数器（见 18）
10: 48 89 c8 mov %rcx,%rax // %rax 此时用于下标计数器，初始值为 1
13: 48 39 ce cmp %rcx,%rsi // 如果下标已经到达末尾……
16: 74 09 je 21 <_Z4findPimi+0x21> // 那就跳转
18: 48 8d 48 01 lea 0x1(%rax),%rcx // 否则后续下标间接增加 1（为啥不直接生成 inc %rcx？）
1c: 39 14 87 cmp %edx,(%rdi,%rax,4) // 对比 arr[i] == val
1f: 75 ef jne 10 <_Z4findPimi+0x10> // 不符合条件就进入下一次循环
21: 48 39 f0 cmp %rsi,%rax // 对比 i < size
24: 0f 92 c0 setb %al // 未达末尾就返回 true
27: c3 ret
28: 31 c0 xor %eax,%eax
2a: c3 ret
NOTE: 这是 libstdc++ 标准库实际使用的 std::find 实现，细微区别在于人家是坚持手作 unroll。
优化的查找
假设容器的 sentinel 具有值语义且可修改，可以优化如下：
#include <cstddef>
bool find_v2(int* arr, size_t size, int val) {
// Hidden sentinel!
arr[size] = val;
#pragma clang loop unroll_count(4)
for(size_t i = 0; ; ++i) {
if(val == arr[i]) return i != size;
}
// Unreachable.
return false;
}
clang++-18 生成如下指令（-O3，同理没有循环展开部分）：
0000000000000000 <_Z7find_v2Pimi>:
0: 89 14 b7 mov %edx,(%rdi,%rsi,4) // sentinel 赋值
3: 31 c0 xor %eax,%eax // 作为下标计数器，初始值为 0
5: 66 66 2e 0f 1f 84 00 data16 cs nopw 0x0(%rax,%rax,1) // 仅用于对齐
c: 00 00 00 00
10: 48 89 c1 mov %rax,%rcx // 作为下标计数器
13: 48 ff c0 inc %rax // 下一次循环的下标
16: 39 14 8f cmp %edx,(%rdi,%rcx,4) // 对比 arr[i] == val
19: 75 f5 jne 10 <_Z7find_v2Pimi+0x10> // 不满足则进入下一次循环
1b: 48 ff c6 inc %rsi // %rsi = size + 1
1e: 48 39 c6 cmp %rax,%rsi // 如果 i+1 != size+1 的话……
21: 0f 95 c0 setne %al // 那就返回 true
24: c3 ret // （所以为啥不直接拿 %rcx 和 %rsi 比呢……）
简单来说就是每次循环都减少了一次 v1 版本中的 i < size 分支判断指令，因为我们的哨兵总能让这个隐含的条件自然结束。从 jcc 指令的数目也可以粗略猜到性能差异，但是我们需要实测。
NOTE: 完整的指令可以参考 godbolt。
基准测试一
// clang++ -S -O3 find.cpp -o - | llvm-mca
Iterations: 100
Instructions: 4000
Total Cycles: 760
Total uOps: 4000
Dispatch Width: 6
uOps Per Cycle: 5.26
IPC: 5.26
Block RThroughput: 7.5 // 😞
// clang++ -S -O3 find_v2.cpp -o - | llvm-mca
Iterations: 100
Instructions: 3000
Total Cycles: 608
Total uOps: 3000
Dispatch Width: 6
uOps Per Cycle: 4.93
IPC: 4.93
Block RThroughput: 5.0 // 😄
先使用 LLVM-MCA 做静态性能预测，可以看出 v2 版本的代码生成质量更优。
基准测试二
// best case: 查找数组中的首个元素
// worst case: 查找数组中的末尾元素
// average case: 查找数组中的中间元素
CPU Caches:
L1 Data 32 KiB (x8)
L1 Instruction 32 KiB (x8)
L2 Unified 1024 KiB (x8)
L3 Unified 16384 KiB (x1)
Load Average: 0.24, 0.25, 0.11
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
BM_find_best_case/8 1.01 ns 1.01 ns 658995011
BM_find_best_case/16 1.01 ns 1.01 ns 659940864
BM_find_best_case/32 1.01 ns 1.01 ns 663255342
BM_find_best_case/64 1.01 ns 1.01 ns 659104479
BM_find_best_case/128 1.01 ns 1.01 ns 667078063
BM_find_best_case/256 1.00 ns 1.00 ns 665760535
BM_find_best_case/512 0.998 ns 0.998 ns 672838919
BM_find_best_case/1024 1.47 ns 1.47 ns 467624330
BM_find_best_case/2048 1.01 ns 1.01 ns 662828304
BM_find_best_case/4096 1.02 ns 1.02 ns 655883031
BM_find_best_case/8192 1.01 ns 1.01 ns 661704357
BM_find_best_case/16384 1.02 ns 1.02 ns 657260684
BM_find_best_case/32768 1.02 ns 1.02 ns 658413702
BM_find_best_case/65536 1.01 ns 1.01 ns 661556933
BM_find_best_case/131072 1.02 ns 1.02 ns 670742089
BM_find_best_case/262144 1.01 ns 1.01 ns 661440824
BM_find_best_case/524288 1.01 ns 1.01 ns 664805149
BM_find_best_case/1048576 1.01 ns 1.01 ns 679291625
BM_find_best_case/2097152 1.02 ns 1.02 ns 671568522
BM_find_best_case/4194304 1.00 ns 1.00 ns 682087755
BM_find_best_case/8388608 1.00 ns 1.00 ns 682462635
BM_find_best_case/16777216 1.48 ns 1.48 ns 474557730
BM_find_best_case/33554432 1.48 ns 1.48 ns 473469374
BM_find_best_case/67108864 1.90 ns 1.90 ns 364997786
BM_find_v2_best_case/8 1.05 ns 1.05 ns 634366581
BM_find_v2_best_case/16 1.04 ns 1.04 ns 583873592
BM_find_v2_best_case/32 1.05 ns 1.05 ns 645523533
BM_find_v2_best_case/64 1.04 ns 1.04 ns 642675493
BM_find_v2_best_case/128 1.06 ns 1.06 ns 642491168
BM_find_v2_best_case/256 1.04 ns 1.04 ns 638667286
BM_find_v2_best_case/512 1.05 ns 1.05 ns 639525158
BM_find_v2_best_case/1024 2.15 ns 2.15 ns 320029152
BM_find_v2_best_case/2048 1.08 ns 1.08 ns 615228415
BM_find_v2_best_case/4096 1.09 ns 1.09 ns 616060495
BM_find_v2_best_case/8192 1.08 ns 1.08 ns 619851387
BM_find_v2_best_case/16384 1.09 ns 1.09 ns 623755858
BM_find_v2_best_case/32768 1.10 ns 1.10 ns 591332645
BM_find_v2_best_case/65536 1.10 ns 1.10 ns 623551623
BM_find_v2_best_case/131072 1.10 ns 1.10 ns 616512218
BM_find_v2_best_case/262144 1.09 ns 1.09 ns 616320040
BM_find_v2_best_case/524288 1.07 ns 1.07 ns 617523472
BM_find_v2_best_case/1048576 1.08 ns 1.08 ns 620027567
BM_find_v2_best_case/2097152 1.10 ns 1.10 ns 610900178
BM_find_v2_best_case/4194304 1.10 ns 1.10 ns 624739188
BM_find_v2_best_case/8388608 1.09 ns 1.09 ns 649713977
BM_find_v2_best_case/16777216 2.14 ns 2.14 ns 330665800
BM_find_v2_best_case/33554432 2.15 ns 2.15 ns 329984987
BM_find_v2_best_case/67108864 3.43 ns 3.43 ns 230014000
BM_find_worst_case/8 1.95 ns 1.95 ns 352421202
BM_find_worst_case/16 3.56 ns 3.55 ns 195380271
BM_find_worst_case/32 6.74 ns 6.74 ns 95370364
BM_find_worst_case/64 13.1 ns 13.1 ns 50075888
BM_find_worst_case/128 26.0 ns 26.0 ns 26253410
BM_find_worst_case/256 52.0 ns 52.0 ns 12500177
BM_find_worst_case/512 104 ns 104 ns 6585238
BM_find_worst_case/1024 214 ns 214 ns 3239463
BM_find_worst_case/2048 421 ns 421 ns 1675597
BM_find_worst_case/4096 821 ns 821 ns 797520
BM_find_worst_case/8192 1657 ns 1657 ns 408924
BM_find_worst_case/16384 3280 ns 3280 ns 210586
BM_find_worst_case/32768 6670 ns 6670 ns 101040
BM_find_worst_case/65536 13158 ns 13158 ns 51230
BM_find_worst_case/131072 26715 ns 26715 ns 26424
BM_find_worst_case/262144 53396 ns 53395 ns 12372
BM_find_worst_case/524288 105524 ns 105524 ns 6150
BM_find_worst_case/1048576 210971 ns 210972 ns 3145
BM_find_worst_case/2097152 424554 ns 424557 ns 1655
BM_find_worst_case/4194304 871541 ns 871546 ns 770
BM_find_worst_case/8388608 1722983 ns 1722995 ns 395
BM_find_worst_case/16777216 3484659 ns 3484711 ns 199
BM_find_worst_case/33554432 6981308 ns 6981458 ns 97
BM_find_worst_case/67108864 14016949 ns 14005970 ns 50
BM_find_v2_worst_case/8 1.87 ns 1.87 ns 367027163
BM_find_v2_worst_case/16 2.65 ns 2.65 ns 258739829
BM_find_v2_worst_case/32 4.32 ns 4.32 ns 161791764
BM_find_v2_worst_case/64 7.64 ns 7.64 ns 85923262
BM_find_v2_worst_case/128 14.3 ns 14.3 ns 48003896
BM_find_v2_worst_case/256 26.9 ns 26.9 ns 24655725
BM_find_v2_worst_case/512 52.8 ns 52.9 ns 12588132
BM_find_v2_worst_case/1024 111 ns 111 ns 6055381
BM_find_v2_worst_case/2048 214 ns 215 ns 3206550
BM_find_v2_worst_case/4096 424 ns 424 ns 1650669
BM_find_v2_worst_case/8192 867 ns 868 ns 762432
BM_find_v2_worst_case/16384 1923 ns 1925 ns 366180
BM_find_v2_worst_case/32768 3774 ns 3778 ns 180173
BM_find_v2_worst_case/65536 7354 ns 7660 ns 83772
BM_find_v2_worst_case/131072 14210 ns 15502 ns 45643
BM_find_v2_worst_case/262144 28925 ns 31555 ns 21975
BM_find_v2_worst_case/524288 58576 ns 63901 ns 10677
BM_find_v2_worst_case/1048576 105916 ns 115545 ns 5809
BM_find_v2_worst_case/2097152 217553 ns 237331 ns 2926
BM_find_v2_worst_case/4194304 495386 ns 540422 ns 1205
BM_find_v2_worst_case/8388608 985209 ns 1060639 ns 661
BM_find_v2_worst_case/16777216 2259903 ns 2259874 ns 321
BM_find_v2_worst_case/33554432 4586589 ns 4516989 ns 159
BM_find_v2_worst_case/67108864 9597705 ns 9425770 ns 83
BM_find_average_case/8 1.54 ns 1.51 ns 451508820
BM_find_average_case/16 2.30 ns 2.26 ns 305975643
BM_find_average_case/32 4.01 ns 3.94 ns 177846394
BM_find_average_case/64 7.17 ns 7.11 ns 92837892
BM_find_average_case/128 13.5 ns 13.5 ns 50191614
BM_find_average_case/256 26.3 ns 26.3 ns 25961168
BM_find_average_case/512 52.8 ns 51.9 ns 12803869
BM_find_average_case/1024 106 ns 104 ns 6555978
BM_find_average_case/2048 208 ns 208 ns 3375323
BM_find_average_case/4096 420 ns 420 ns 1674677
BM_find_average_case/8192 835 ns 835 ns 803151
BM_find_average_case/16384 1647 ns 1647 ns 414660
BM_find_average_case/32768 3307 ns 3307 ns 207517
BM_find_average_case/65536 6671 ns 6671 ns 100027
BM_find_average_case/131072 13404 ns 13404 ns 50081
BM_find_average_case/262144 26478 ns 26478 ns 26062
BM_find_average_case/524288 54283 ns 54283 ns 12388
BM_find_average_case/1048576 105745 ns 105745 ns 6332
BM_find_average_case/2097152 213429 ns 213427 ns 3243
BM_find_average_case/4194304 423439 ns 423438 ns 1580
BM_find_average_case/8388608 863090 ns 863078 ns 809
BM_find_average_case/16777216 1732264 ns 1732225 ns 389
BM_find_average_case/33554432 3611597 ns 3611527 ns 202
BM_find_average_case/67108864 6959930 ns 6960173 ns 100
BM_find_v2_average_case/8 1.45 ns 1.45 ns 478012856
BM_find_v2_average_case/16 1.84 ns 1.84 ns 370132859
BM_find_v2_average_case/32 2.71 ns 2.71 ns 260878805
BM_find_v2_average_case/64 4.25 ns 4.25 ns 163010343
BM_find_v2_average_case/128 7.84 ns 7.84 ns 84815178
BM_find_v2_average_case/256 14.3 ns 14.3 ns 47580872
BM_find_v2_average_case/512 27.0 ns 27.0 ns 24920250
BM_find_v2_average_case/1024 54.1 ns 54.4 ns 11824927
BM_find_v2_average_case/2048 111 ns 112 ns 5973142
BM_find_v2_average_case/4096 217 ns 219 ns 3233183
BM_find_v2_average_case/8192 417 ns 423 ns 1666755
BM_find_v2_average_case/16384 861 ns 872 ns 783335
BM_find_v2_average_case/32768 1881 ns 1906 ns 358115
BM_find_v2_average_case/65536 3761 ns 3810 ns 186855
BM_find_v2_average_case/131072 7429 ns 7526 ns 89232
BM_find_v2_average_case/262144 15052 ns 15248 ns 45060
BM_find_v2_average_case/524288 29185 ns 31492 ns 21300
BM_find_v2_average_case/1048576 56859 ns 62028 ns 10558
BM_find_v2_average_case/2097152 108465 ns 118326 ns 5626
BM_find_v2_average_case/4194304 217734 ns 237525 ns 2904
BM_find_v2_average_case/8388608 482902 ns 520782 ns 1344
BM_find_v2_average_case/16777216 1115999 ns 1115973 ns 637
BM_find_v2_average_case/33554432 2230035 ns 2229990 ns 321
BM_find_v2_average_case/67108864 4369605 ns 4369533 ns 161
然后使用 google benchmark 做运行时跑分。可以看出，任意数据规模，v2 算法均有明显优势。
NOTES:
- 一个有趣的现象：丹大师在 2016 年测试得出的结论是，非循环展开的版本 v2 比 v1 快约 20%。但是 2025 年的现在，实测是非循环展开版本 v1 比 v2 还要快（当然了，全部展开的话就是上述表现，v2 把 v1 吊着打）。
- 这么多年了，编译器生成的代码倒是差异不大。也就是说，很可能是体系结构的更新导致了「算法过期」这种现象，有空 perf 剖析一下。
通用扩展
如果像上面所说的，要求 sentinel 可修改，那基本上应用场景是非常窄的。比如考虑常见的迭代器模式 \([begin, end)\)，对于一个子范围（range）来说，end 可能是有意义的数据，是不应修改的；其次，对于完整的范围来说，end 根本没有值语义，是无法执行写操作的。
// 简单起见，就不写 begin 和 end 迭代器了
template <typename T /*, typename Iter*/>
bool find_v2_subrange(T* arr, size_t size, T val) {
auto old = std::move(arr[size]);
arr[size] = std::move(val);
#pragma clang loop unroll_count(4)
for(size_t i = 0; ; ++i) {
if(val == arr[i]) {
arr[size] = std::move(old);
return i != size;
}
}
// 实际上这段代码不可达，不需继续处理
return false;
}
但是只要你的元素是可移动的，那么不覆盖到哨兵的子范围可以轻松实现如上版本。不过「可移动」其实也意味着 const range 肯定用不了这种优化。
template <typename T /*, typename Iter*/>
bool find_v2_range(T* arr, size_t size, T val) {
// 会多出一些分支
if(size == 0) return false;
if(arr[size - 1] == val) return true;
auto old = std::move(arr[size - 1]);
arr[size - 1] = std::move(val);
#pragma clang loop unroll_count(4)
for(size_t i = 0; ; ++i) {
if(val == arr[i]) {
arr[size - 1] = std::move(old);
return i != size - 1;
}
}
// 实际上这段代码不可达，不需继续处理
return false;
}
对于任意范围该如何支持？不考虑改动数据结构本身的话，那就先判断实质 sentinel 前的一个元素，然后照着抄就好了。
总结
这篇文章也就只是搜索一些 branchless programming（不懂，别问）资料时顺手做的测试，实际上这种优化方法也是老黄历了，没想到跑得还挺快。
总之，不考虑那么远，如果特定场景合适（流式数据！），不妨试试 v2 算法。
后记：自动向量化
考虑进一步的编译器优化，自然是想到 -march 或者 vectorize(enable) 编译器选项来提供更加激进的向量化，比如指定 skylake-avx512。不过 Clang 拒绝了，上述两种实现都是生成此前相同的指令。
clang++ find.cpp -O3 -march=native -Rpass-analysis=loop-vectorize -c
find.cpp:4:5: remark: loop not vectorized: could not determine number of loop iterations [-Rpass-analysis=loop-vectorize]
4 | for(size_t i = 0; i < 512; ++i) {
| ^
NOTES:
- 虽然 Clang 可以用 -Rpass-analysis=loop-vectorize 来分析拒绝向量化的原因……
- 但是如上所示，事实上它也会胡说八道。
- GCC trunk 版本可以做到向量化，还没仔细分析过指令（godbolt），TODO。
- 再次测试编译期已知大小的未展开 v1 的代码生成（godbolt）。使用
std::array<int, N>时，当N > 74就是 v1 算法，但是更小的规模就会在 v1 的基础上继续做向量化展开。有点超出预料，有空也可以测一下性能。
图文无关
