为何提前跳出for循环比遍历整个向量更慢？

我有一个降序排列的向量，需要手动统计其中大于等于指定整数的元素数量。为此写了两个函数：

• 第一个函数manual_sum_whole_vector：用for循环遍历整个向量，逐个判断元素是否符合条件并计数
• 第二个函数manual_sum_break：同样遍历向量，但遇到小于指定整数的元素时直接跳出循环

按预期，第二个函数应该更快，因为无需遍历全部元素，但实际基准测试显示它的速度反而慢了三倍。

测试代码 #

using BenchmarkTools

function manual_sum_whole_vector(in_vec, i)
    n = 0
    for x in in_vec
        if x >= i
            n += 1
        end
    end
    return n
end

function manual_sum_break(in_vec, i)
    n = 0
    for x in in_vec
        if x >= i
            n += 1
        else
            break
        end
    end
    return n
end

in_vec = collect(100000:-1:1)

@btime manual_sum_whole_vector(in_vec, 12345)
@btime manual_sum_break(in_vec, 12345)

基准测试结果 #

6.575 μs (1 allocation: 16 bytes)
19.625 μs (1 allocation: 16 bytes)

原因分析 #

1. 编译器优化差异：

   • manual_sum_whole_vector中的循环无分支跳转（break），Julia编译器可对其做SIMD（单指令多数据）优化，一次性处理多个元素，大幅提升遍历效率；同时连续的内存访问能充分利用CPU缓存。
   • manual_sum_break中的break语句让循环存在分支逻辑，编译器无法进行SIMD优化和循环展开，每一次迭代都要执行条件判断，额外增加了开销。

2. 优化收益抵消遍历长度优势：
   虽然manual_sum_break少遍历了约12%的元素，但SIMD优化带来的并行处理效率提升，完全覆盖了遍历长度缩短的优势，最终整体速度反而更慢。

优化建议 #

既然向量是降序排列的，完全可以利用这一特性避免线性遍历：

• 使用二分查找快速定位第一个小于指定值的元素位置，直接计算符合条件的元素数量，时间复杂度从O(n)降到O(logn)：

  function manual_sum_binary_search(in_vec, i)
      # 降序向量中，找到第一个小于i的索引
      idx = searchsortedfirst(in_vec, i, rev=true)
      return idx - 1
  end
  
  @btime manual_sum_binary_search(in_vec, 12345) # 速度远快于前两个函数
  

• 或者直接使用Julia内置的count函数，它已经做了底层优化：

  @btime count(x -> x >= 12345, in_vec)
  

内容的提问来源于stack exchange，提问作者Earl Brown