分支预测如何影响 R 中的性能？

Question

一些参考资料：

_{这是后续为什么处理排序数组比处理未排序数组更快？}

_{r 标签中我发现与分支预测有点相关的唯一帖子是这个为什么采样矩阵行很慢？}

问题解释：

我正在调查处理排序数组是否比处理未排序数组更快（与

Java

和

C

– 第一个链接中测试的问题相同）以查看分支预测是否以相同的方式影响

R

。

参见下面的基准示例：

set.seed(128)
#or making a vector with 1e7
myvec <- rnorm(1e8, 128, 128)  

myvecsorted <- sort(myvec)

mysumU = 0
mysumS = 0

SvU <- microbenchmark::microbenchmark(
  Unsorted = for (i in 1:length(myvec)) {
    
    if (myvec[i] > 128) {
      mysumU = mysumU + myvec[i]
    }
    
  } ,
  Sorted = for (i in 1:length(myvecsorted)) {
    
    if (myvecsorted[i] > 128) {
      mysumS = mysumS + myvecsorted[i]
    }
    
  } ,
  times = 10)

ggplot2::autoplot(SvU)

问题：

• 首先，我想知道为什么 “已排序” 向量不是一直都是最快的，而且与

  Java

  中表示的幅度不同？
• 第二，为什么排序的执行时间与未排序的执行时间相比有更高的变化？

N.B. 我的 CPU 是 i7-6820HQ @ 2.70GHz Skylake，四核超线程.

更新：

为了研究variation部分，我用一亿个元素的向量（

microbenchmark

）做了

n=1e8

，并重复基准测试100次（

times=100

）。这是与该基准相关的情节。

这是我的

sessioninfo

：

R version 3.6.1 (2019-07-05)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 10 x64 (build 16299)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.1252  LC_CTYPE=English_United States.1252    LC_MONETARY=English_United States.1252
[4] LC_NUMERIC=C                           LC_TIME=English_United States.1252    

attached base packages:
[1] compiler  stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] rstudioapi_0.10      reprex_0.3.0         cli_1.1.0            pkgconfig_2.0.3      evaluate_0.14        rlang_0.4.0         
[7] Rcpp_1.0.2           microbenchmark_1.4-7 ggplot2_3.2.1 

Answer 1

口译员开销，只是口译员，解释了大部分平均差异。我没有更高方差的解释。

---

R 是一种解释型语言，不是像 Java 那样编译成机器代码的 JIT，也不是像 C 那样提前编译。（我不太了解 R 内部结构，只了解 CPU 和性能，所以我做了很多 这里的假设。）

在实际 CPU 硬件上运行的代码是

R 解释器，不完全是你的 R 程序。

R 程序中的控制依赖项（如

if()

）成为解释器中的

data 依赖项。当前正在执行的只是在真实 CPU 上运行的解释器的数据。

R程序中的不同操作在解释器中成为控制依赖。例如，评估

myvec[i]

 然后 

+

 运算符可能由解释器中的两个不同函数完成。以及 

>

 和 

if()

 语句的单独函数。

经典的解释器循环基于 indirect 分支，它从函数指针表中调度。 CPU 需要预测许多最近使用的目标地址之一，而不是采取/不采取选择。我不知道 R 是否使用像这样的单个间接分支，或者是否试图更有趣，比如将每个解释器块的末尾分派到下一个，而不是返回到主分派循环。

现代英特尔 CPU（如 Haswell 及更高版本）具有 IT-TAGE（间接标记几何历史长度）预测。沿执行路径的先前分支的采用/未采用状态用作预测表的索引。这主要解决了解释器分支预测问题，让它做得非常好，特别是当解释代码（在你的例子中是 R 代码）重复做同样的事情时。

• Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore (2015) - Haswell 的 ITTAGE 对口译员来说是一个巨大的改进，推翻了以前认为口译员派遣的单一间接分支是一场灾难的智慧。我不知道 R 实际使用的是什么；有一些有用的技巧。
• X86 预取优化：“computed goto”线程代码 有更多链接。
• https://comparch.net/2013/06/30/why-tage-is-the-best/
• https://danluu.com/branch-prediction/ 在底部有一些相关链接。还提到 AMD 在 Bulldozer 系列和 Zen 中使用了 Perceptron 预测器：就像神经网络一样。

if()

被采取

does导致需要做不同的操作，所以它does实际上仍然使R解释器中的一些分支根据数据或多或少是可预测的。当然作为解释器，它是在每个步骤中做much比数组上的简单机器代码循环更多的工作。

因此，由于解释器的开销，额外的分支错误预测只占总时间的一小部分。

---

当然，你的两个测试都是在同一个硬件上使用同一个解释器。我不知道你有什么样的CPU。

如果它是比 Haswell 更早的 Intel 或比 Zen 更早的 AMD，即使使用排序数组，你也可能会得到很多错误预测，除非模式足够简单，间接分支历史预测器可以锁定。那会掩盖更多噪音的差异。

既然你确实看到了一个非常明显的差异，我猜 CPU 在排序的情况下不会错误预测太多，所以在未排序的情况下它有变得更糟的空间。