fortran中二分搜索效率与线性搜索效率的比较

Question

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

我有一个用fortran (77!)编写的应用程序。对于我的那部分代码，一个常见的操作是在一个数组中查找索引，以便gx(i) <= xin < gx(i+1)。我目前已经将其实现为binary search --很抱歉使用语句标签和goto --我已经对使用Fortran90的等价语句进行了注释...

        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

然而，今天，我在维基百科上读到了关于二进制搜索的内容，我发现了这一点：

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.

我不能完全理解这句话--我的印象是缓存提取是一次收集大块的，所以如果我们从数组的开头开始，我认为大多数数组都已经在缓存中了(至少和线性搜索一样多)，所以我认为这无关紧要。

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

Answer 1

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

问题是分支预测对于二进制搜索很可能失败，因为分支是以依赖于数据的方式随机采用或跳过的。分支预测未命中会停止CPU流水线。

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

延缓CPU流水线是非常昂贵的。核心i7在每个时钟周期最多可以停用4条指令(在3 GHz时每秒12 GHz指令！)。但只有在你没有拖延的情况下。

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