分支预测如何影响 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?
• 其次，为什么排序的执行时间与未排序的执行时间相比具有更高的变化？

NB我的 CPU 是i7-6820HQ @ 2.70GHz Skylake，四核超线程。

更新：

为了研究变异部分，我microbenchmark使用了 1 亿个元素的向量 ( 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()）成为解释器中的数据依赖。当前正在执行的只是运行在真实 CPU 上的解释器的数据。

R 程序中的不同操作成为解释器中的控制依赖。例如，myvec[i]对+运算符的求值可能由解释器中的两个不同函数完成。还有一个单独的函数 for>和 forif()语句。

经典的解释器循环基于从函数指针表调度的间接分支。 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 在推土机系列和 Zen 中使用了感知器预测器：就像一个神经网络。

将if()采取不结果需要做不同的操作，所以它不会居然还做一些分支在R解释或多或少预见取决于数据。 但当然，作为一个解释器，它在每一步做的工作比简单的机器代码循环多得多。

因此，由于解释器的开销，额外的分支错误预测占总时间的比例要小得多。

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

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

由于您确实看到了非常明显的差异，我猜想 CPU 在已排序的情况下不会错误预测太多，因此在未排序的情况下它有变得更糟的空间。