“Just came across a good paper that discusses these issues:”
Array Layouts for Comparison-Based Searching
比较排序数组、Eytzinger、B 树和 vEB 布局下的搜索速度
论文比较了在内存数组中支持「查找不小于 x 的最小值」的几种布局与搜索算法:有序数组加二分搜索、Eytzinger(BFS)布局、隐式 B 树布局和 van Emde Boas 布局。经过在多种现代硬件上的大量测试和调优,结论是:n 较小时,有序数组加好的二分搜索最佳;n 较大时,Eytzinger 布局通常最快,与 Brodal 等人此前的实验结论相反。最快的 C++ 实现用条件移动避免分支预测失败,并用预取减少缓存延迟。
HN 上的人在讨论二分搜索的分支预测与缓存行为时反复引用它,说明内存延迟而非访问次数才是代价,并用来比较无分支实现与缓存布局的效果。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“I think the summary from this recent paper is spot on:”
“Have a look at Array Layouts for Comparison-Based Searching from pkhuong. They discuss this issue and other variants that paper.”
“Reminds me of this paper on binary search, which also shows a speed up using branch-free comparisons.”
“The more recent results (by the same author) is this paper:”
“The best results I knew of for static ordered search [1] were from the 2015 Khuong-Morin paper [2]”
看全部 8 条 →
“can be restructured with a conditional `first += half` and instead `length -= half` (see, e.g., Listing 2 in Array Layouts for Comparison-Based Searching).”
“but the constants are bad enough to make it impractical[1,2].”
- Array Layouts for Comparison-Based Searching (Khuong and Morin, 2015) ↗nkurz · 2015-10-15 · 2 分
- Array Layouts for Comparison-Based Searching ↗luu · 2015-10-25 · 2 分
- Array Layouts for Comparison-Based Searching ↗chewxy · 2016-04-22 · 1 分
- Array Layouts for Comparison-Based Searching ↗based2 · 2016-08-26 · 2 分
- Array Layouts for Comparison-Based Searching ↗jsnell · 2017-05-13 · 59 分
- Array Layouts for Comparison-Based Searching ↗henning · 2018-10-15 · 2 分