python - 为什么在 Python 中处理排序的数组并不比处理未排序的数组快？

Question

在这篇文章中 Why is processing a sorted array faster than random array ，它说分支预测是排序数组性能提升的原因。

但我只是用 Python 尝试了这个例子；我认为排序数组和随机数组之间没有区别(我尝试了 bytearray 和数组；并使用 line_profile 来分析计算)。

我错过了什么吗？

这是我的代码:

from array import array
import random
array_size = 1024
loop_cnt = 1000
# I also tried 'array', and it's almost the same
a = bytearray(array_size)
for i in xrange(array_size):
    a.append(random.randint(0, 255))
#sorted                                                                         
a = sorted(a)
@profile
def computation():
    sum = 0
    for i in xrange(loop_cnt):
        for j in xrange(size):
            if a[j] >= 128:
                sum += a[j]

computation()
print 'done'

Answer 1

我可能错了，但我看到链接问题和您的示例之间存在根本区别:Python 解释字节码，C++ 编译为 native 代码。

在 if 直接转换为 cmp/jl 序列的 C++ 代码中，CPU 分支预测器可以将其视为特定于该周期的单个“预测点”。

在 Python 中，比较实际上是几个函数调用，因此 (1) 更多的开销和 (2) 我认为执行该比较的代码是解释器中用于其他所有整数比较的函数 - 所以它是一个“预测” spot”不特定于当前 block ，这使分支预测器更难正确猜测。

---

编辑:同样，如 this 中所述论文中，解释器内部有更多的间接分支，因此 Python 代码中的这种优化可能无论如何都会被解释器本身的分支错误预测所掩盖。