主要观点：

• 二进制搜索算法速度快，但现代 CPU 存在指令流和内存访问可预测性问题，导致缓存未命中和性能下降。
• 采用 Eytzinger 布局可解决内存访问可预测性问题，减少缓存未命中，但需数组预处理，且不适用于需要排序输出的情况。
• 尝试消除分支以提高性能，利用二进制搜索的指数性质，在循环中不检查是否找到目标元素，直接遍历树至叶子节点，可提高性能。
• 添加软件内存预取可进一步提高 Eytzinger 布局的性能，虽ptr::wrapping_offset()有未定义行为风险，但实际安全。

关键信息：

• 测试平台为 Intel Core i7-1068NG7 CPU @ 2.30GHz、32Gb LPDDR4X 3733 MHz、Darwin Kernel Version 22.4.0。
• 二进制搜索性能在数据集大于 L2 缓存（512KB 或 128K u32元素）时开始下降。
• Eytzinger 布局按树深度存储元素，使树兄弟节点在内存中相邻，减少缓存未命中。
• 分支消除可避免 CPU 预测分支错误导致的性能损失，通过特定的索引更新方式解码目标元素索引。
• 内存预取可提前通知 CPU 下一次迭代所需数据，提高 Eytzinger 布局性能。

重要细节：

• 展示不同实现方式的性能对比图，如标准二进制搜索、Eytzinger 布局及其分支消除和内存预取版本。
• 提供 Eytzinger 布局的代码示例，包括基本的二分搜索和分支消除后的版本。
• 提及相关研究文献，如[Eytzinger Binary Search]、[Array Layouts for Comparison-based Searching]等。