二进制搜索效率与 fortran 中的线性搜索效率 [英] binary search efficiency vs. linear search efficiency in fortran

问题描述

这个问题是关于线性搜索的效率与对连续存储中预排序数组的二分搜索效率的对比...

This question is about the efficiency of a linear search vs. the efficiency of a binary search for a pre-sorted array in contiguous storage...

我有一个用 fortran (77!) 编写的应用程序.我的部分代码的一个常见操作是在数组中查找索引，使得 gx(i) <= xin <gx(i+1).我目前已将其实现为 binary search - 对不起语句标签和 goto - 我已经评论了使用 fortran 90 的等效语句..

I have an application written in fortran (77!). One frequent operation for my part of the code is to find the index in an array such that gx(i) <= xin < gx(i+1). I've currently implemented this as a binary search -- sorry for the statement labels and goto -- I've commented what the equivalent statments would be using fortran 90...

        i=1
        ih=nx/2
201     continue  !do while (.true.)
           if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then  !found what we want
              ilow=i+1; ihigh=i
              s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow))
              s2=1.0-s1
              return
           endif
           if(i.ge.ih)then
              goto 202 !exit
           endif
           if(xin.le.(gx(ih))then !xin is in second half of array
              i=ih
              ih=nx-(nx-ih)/2
           else !xin is in first half of array
              i=i+1
              ih=i+(ih-i)/2
           endif
        goto 201  !enddo

然而，今天，我在 Wikipedia 上阅读有关二进制搜索的内容时遇到了这个问题:

However, today, I was reading on Wikipedia about binary search and I came across this:

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a
linear search may have superior performance simply because 
it exhibits better locality of reference.

我不完全理解这个说法——我的印象是缓存提取是一次以大(ish)块收集的，所以如果我们从数组的开头开始，我认为大部分数组会已经在缓存中(至少与线性搜索一样多)，所以我认为这无关紧要.

I don't completely understand this statement -- my impression was that cache fetches were gathered in large(ish) chunks at a time, so if we start at the beginning of the array, I thought that most of the array would be in cache already (at least as much as it would be for a linear search), so I didn't think that would matter.

所以我的问题是，有什么方法可以判断哪种算法性能更好(线性搜索还是二进制搜索?)是否存在数组大小边界?我目前正在使用大小约为 100 个元素的数组...

So my question is, is there any way to tell which algorithm will perform better (linear or binary search?) Is there an array size boundary? I'm currently using arrays of size around 100 elements...

推荐答案

对于小数组，问题不是缓存.你是对的:一个小数组很可能被快速缓存.

For small arrays, the problem is not cache. You are right: A small array is likely to be cached quickly.

问题在于分支预测对于二分搜索可能会失败，因为分支是以数据相关的方式随机选取或跳过的.分支预测未命中会使 CPU 流水线停滞.

The problem is that branch prediction is likely to fail for binary search because branches are taken or skipped at random in a data-dependent way. Branch prediction misses stall the CPU pipeline.

这种影响可能很严重.您可以在执行单个二进制搜索分支(并且您需要执行多个二进制搜索分支)的同时轻松地线性搜索 3 到 8 个元素.需要测量准确的盈亏平衡点.

This effect can be severe. You can easily search 3 to 8 elements linearly in the same time it takes to do a single binary search branch (and you need to do multiple binary search branches). The exact break even point needs to be measured.

停止 CPU 管道非常昂贵.Core i7 每个时钟周期最多可以退出 4 条指令(3 GHz 时每秒 12 条千兆指令！).但前提是你不拖延.

Stalling the CPU pipeline is extremely expensive. A Core i7 can retire up to 4 instructions per clock cycle (12 giga-instructions per second at 3 GHz!). But only, if you are not stalling.

存在使用条件移动 CPU 指令进行二进制搜索的无分支算法.这些算法基本上展开 32 个搜索步骤并在每个步骤中使用 CMOV(32 个步骤是理论上的最大值).它们是无分支的，但不是无停顿的:每个下一步都 100% 依赖于前一个，因此 CPU 无法在指令流中提前充电.它必须一直等待.所以他们没有解决这个问题，只是稍微改进一下.

There are branch-free algorithms doing binary search by using conditional-move CPU instructions. These algorithms basically unroll 32 search steps and use a CMOV in each step (32 steps are the theoretical maximum). They are branch-free but not stall free: Each next step depends 100% on the previous one so the CPU cannot charge ahead in the instruction stream. It has to wait all the time. So they don't solve this problem, only improve it slightly.

这篇关于二进制搜索效率与 fortran 中的线性搜索效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！