performance - fortran中的二进制搜索效率与线性搜索效率

Question

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

我有一个用fortran编写的应用程序(77!)。我这部分代码的一个常见操作是在数组中找到索引，例如gx(i) <= xin < gx(i+1)。我目前已将其实现为binary search-对语句标签和goto表示抱歉-我已经评论了将使用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上阅读了有关二进制搜索的信息，发现了这一点:

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)，因此，如果我们从数组的开头开始，我认为大多数数组都将在高速缓存中已经(至少与线性搜索一样多)，所以我认为这无关紧要。

所以我的问题是，有没有办法判断哪种算法会更好地执行(线性或二进制搜索？)是否存在数组大小边界？我目前正在使用大小约为100个元素的数组...

Answer 1

对于小型阵列，问题不在于高速缓存。您说对了:小型阵列很可能会被快速缓存。

问题在于，二进制预测可能会因分支预测失败而失败，因为分支是以依赖于数据的方式随机获取或跳过的。分支预测未命中会使CPU管道停顿。

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

拖延CPU管道非常昂贵。 Core i7每个时钟周期最多可以淘汰4条指令(在3 GHz时每秒12条千兆指令!)。但是只有在您不拖延的情况下。

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