1

在问题为什么处理排序数组比处理未排序数组更快？答案与分支预测对随机顺序数据不好而对排序数据很好有关。但问题是数据是一样的，只是顺序不同。

这让我很困惑，我几乎假设预测是编译的。它要么总是假设为真，要么总是假设为假，但显然它是动态的。既然它是动态的，它怎么知道要预测哪个？某处的缓存中是否有关于它的数据？听说有代码执行缓存和内存缓存，cpu缓存里有数据吗？只有L1吗？

分支预测究竟是如何调整它的预测的，它的数据在哪里来做出这个动态决策呢？

4

1 回答 1

0

您要问的问题是关于分支目标预测的，但这在这个特定示例中并没有发挥作用。这里唯一的区别是分支是否被采用。

这种情况下的代码归结为：

if (data[c] >= 128)
  sum += data;

在一个循环中，所以在汇编中它看起来像：

cmp rsi, 128
jl loop ;this is the one being predicted
add eax, rsi
j loop

在跳转小于中，分支预测器必须猜测是再次进入循环的开头还是失败。如果它做对了，代码将运行得更快，因为指令队列将得到很好的馈送，而不会在管道中出现气泡或停顿。

按照天气预报的原则（明天的天气和今天差不多），如果CPU能记住上次走哪条路，那就更快了。您可以将其视为存储在 CPU 实现中的单个布尔值，该值记录上次是否如此，并再次猜测相同。每次跳转（或不跳转）后，该值将更新以供下次使用。

如果你有一个 (eg) 的模式，aaaaAAAA并且你正在迭代它是否是资本，如果你使用这个简单的预测，那么除了aA转换之外，你一直都是对的。如果数据是，aAaAaAaA那么您将一直是错误的。

因此，数据的模式导致采取/未采取的记录要么接近发生的事情，要么没有发生的事情。在这种情况下，如果您对数据进行排序，那么所有小值都将位于数据的开头，因此分支预测器将在正确预测方面取得成功。如果您有随机数据，那么分支预测器将不太有用。

现代分支预测器要复杂得多。所以这是一个简单的观点。但是，如果您认为分支预测状态是作为分支预测器逻辑的一部分保存在存储单元中的单个布尔值，它可能是有意义的。

于 2020-02-23T17:54:58.020 回答