循环语句是否影响分支预测？

Question

我试图更好地理解是什么导致分支预测被计算，以及什么不会导致它被计算。

比如说，我有一个包含1和0的数组。我想遍历这个数组，如果读到0则做某件事情，但如果读到1则做另一件事情。

使用JavaScript，代码应该是这样的：

var array = [0, 1, 1, 1, 0, 0, 0];

for(i=0; i < array.length; i++){
    if(array[i] == 0){
        // Do The 0 Instruction

    }else{
        // Do The 1 Instruction

    }
}

我知道这会导致分支预测，因为程序在读取数组数据之前不知道需要执行哪些步骤。

但是如果我对数组进行预处理，将连续的1或0的数量合并成一个数字，会怎样呢？例如，数组将变为以下形式：

var array = [0, 1, 1, 1, 0, 0, 0];
var condensedArray = [1, 3, 3];

现在，我可以使用循环来分支我的指令，而不是使用if语句，就像这样：

var condensedArray = [1, 3, 3];

for(i=0; i < condensedArray.length; i+=2){

  for(j=0; j < condensedArray[i]; j++)
    //Do The 0 Instruction

  for(j=0; j < condensedArray[i+1]; j++)
    //Do The 1 Instruction

}

这种方法是否仍然会计算和错过分支预测？如果是，那么相对于使用if语句测试原始数组的每个索引，它至少更有效吗？

编辑：在评论中，有人问我如何知道数组是以0还是1开头？为了简单起见，我忽略了这一点，并且不想编辑上面的代码使其变得更长，但是我会在程序开头使用一个if语句来判断数组是否以0或1开头。然后，这个单一的分支将使循环按正确的顺序运行。

- YAHsaves

---

在第一个for循环中，如果考虑这个数组[1,0,0,1,1]，如何确保它始终为0呢？这将导致失败。第二个问题是当i变为2时，第二个for循环将抛出ArrayindexOutOfException异常。 - DHARMENDRA SINGH

@DHARMENDRASINGH 我在问题中省略了这一点，但基本上我会在程序开头放置一个单独的if语句，如果数组以0或1开头，则该单个分支将按顺序放置以下循环。抱歉，我会编辑我的答案以反映这一点。 - YAHsaves

我不认为这样优化有什么好处。增加更多的分支不会提高性能。对数据进行排序肯定会有帮助，而这基本上就是你在第二个例子中尝试做的事情。然而，排序需要时间，所以除非你要重复使用数据，否则没有意义。 - ffhighwind

@ffhighwind 在客户端运行程序之前，排序将会被完成。这是关于给客户端哪个数组的问题。而如何添加更多的分支呢？这就是我正在努力解决的问题。 - YAHsaves

Answer 1

基准测试可以告诉我们CPU是否对这样的代码进行分支预测。当您创建两个循环并且它们的退出条件相当容易预测时，CPU可能能够在那里进行分支预测。

- Nowhere man