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

Question

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

rperformancebenchmarkingbranch-predictioninterpreted-language

9

一些参考资料：

_{这是对这个问题的跟进为什么处理排序数组比处理未排序数组快？}

_{我在 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)

问题：

首先，我想知道为什么"Sorted"向量并不总是最快的，而且与Java中表达的幅度不同？
其次，为什么排序后的执行时间与未排序的执行时间相比具有更高的变化性？

N.B. 我的CPU是。

更新：

为了调查变异部分，我使用了100百万元素（n=1e8）的向量进行了microbenchmark，并重复了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

- M--

1

关于 R 语言 的一些有用链接： 1.评估 R 语言的设计 2. 在 R 中实现持久 O(1) 栈和队列 3. R 的字节码编译器 - M--

1

@M--的链接中的第一个似乎已经失效，但可能在这里找到：https://haben-michael.github.io/stats195/Morendat%20et%20al.%20--%20Evaluating%20the%20design%20of%20the%20R%20language.pdf。 - Oliver

1

不完全相同，但相关的问题：为什么R中的duplicated在排序数据上表现更好 - Joseph Wood

1

在运行compiler::enableJIT(0)之后，您应该重新检查基准测试。 - Roland

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

解释器开销以及作为解释器的本身，解释了大部分平均差异。我无法解释更高的方差。

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

在实际CPU硬件上运行的代码是R解释器，而不完全是您的R程序。

R程序中的控制依赖关系（例如if()）变成解释器中的数据依赖关系。当前正在执行的内容只是运行在真正CPU上的解释器数据。

R程序中的不同操作变成解释器中的控制依赖关系。例如，评估myvec [i]然后是+运算符可能会由解释器中的两个不同函数完成。还有一个单独的函数用于>和if()语句。

经典的解释器循环基于分派指向函数指针表的间接分支。 CPU需要预测最近使用的许多目标地址之一，而不是取/不取选择。我不知道R是否像那样使用单个间接分支，或者尝试更高级别，例如将每个解释器块的结尾分派到下一个块，而不是返回到主分派循环。

现代Intel CPU（如Haswell及更高版本）具有IT-TAGE（间接标记几何历史长度）预测。执行路径上先前分支的取/不取状态用作索引进入预测表中。这基本上解决了解释器分支预测问题，使其能够做出令人惊讶的好工作，特别是当解释代码（在您的情况下为R代码）重复执行相同操作时。

分支预测和解释器性能 - 不要相信民间传说 (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 中使用了感知器预测器，就像神经网络。

在 R 解释器中，if() 结构被执行可能需要进行不同的操作，因此根据数据的不同，某些分支是可以预测的，而某些分支则是无法预测的。 当然，作为解释器，它的每个步骤都要比简单的机器代码循环执行要多得多。

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

当然，你的两个测试都是在同一台硬件上使用相同的解释器进行的。 我不知道你使用的 CPU 的类型。

如果 CPU 是 Haswell 之前的 Intel 或 Zen 之前的 AMD，则即使在已排序的数组情况下，您仍可能会遇到许多错误预测，除非模式足够简单以便间接分支历史预测器能够锁定。这将掩盖更多噪音中的差异。

由于您确实看到了明显的差异，我猜测 CPU 在已排序的情况下不会产生太多错误预测，因此在未排序的情况下有提升的空间。