探究分支预测惩罚的影响因素：两种数组对比方法性能差异解析

我有两个数组x和y。x中的值是随机的，而y已被划分为正数和负数子数组。x的元素数量从数千到数百万不等，而y的元素数量通常不超过几十到几百个。我仅在元素符号相同时对比两个数组中的值。我可以通过两种方法实现此操作，其中方法2的速度要快得多（我认为几乎快一倍）。

方法1 #

Loop over x
  If negative, loop over negative y and compare
  If positive, loop over positive y and compare

方法2 #

对x进行分区，以便可以轻松确定负数和正数元素的索引。这将方法1从单个循环转换为两个双重嵌套for循环（除分区伪代码中的if语句外，无分支）。

Partition x by sign

Loop over negative x
  Loop over negative y
    Compare x and y

Loop over positive x
  Loop over positive y
    Compare x and y

按符号分区（先负数，后正数）： #

N = length(x)
j = 1
for (i in 1:N)
  if (x[i] < 0)
    swap(x[i], x[j])    // modify x in place
    j = j + 1

// j will be the index of the first positive element, 
// or N + 1 if all elements were negative.

核心问题 #

哪些因素会影响分支预测惩罚，使得方法2的速度远快于方法1？

每个分支中的指令数量是否重要？方法2仅包含一个执行元素交换的分支，比方法1中包含循环的分支简单得多；但方法2需要对较长的数组x多做一次遍历以完成分区。

内容的提问来源于stack exchange，提问作者Tyler Sagendorf