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

Question

在这篇文章中，为什么处理排序数组比处理随机数组更快，它说分支预测是排序数组性能提升的原因。

但是我刚刚使用Python尝试了这个例子；我认为排序数组和随机数组没有区别（我尝试了字节数组和数组；并使用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并使用PyPy运行它。我可以确认排序数组的处理速度比未排序的数组快，并且无分支方法还可以消除运行时间与排序数组相似的分支。我相信这是因为PyPy是一个JIT编译器，所以分支预测正在发生。

[编辑]

这是我使用的代码：

import random
import time

def runme(data):
  sum = 0
  start = time.time()

  for i in xrange(100000):
    for c in data:
      if c >= 128:
        sum += c

  end = time.time()
  print end - start
  print sum

def runme_branchless(data):
  sum = 0
  start = time.time()

  for i in xrange(100000):
    for c in data:
      t = (c - 128) >> 31
      sum += ~t & c

  end = time.time()
  print end - start
  print sum

data = list()

for i in xrange(32768):
  data.append(random.randint(0, 256))

sorted_data = sorted(data)
runme(sorted_data)
runme(data)
runme_branchless(sorted_data)
runme_branchless(data)

Answer 2

两个原因：

• 您的数组大小太小，无法显示效果。
• Python的开销比C的开销更大，因此整体效果不太明显。

Answer 3

我可能错了，但我看到了链接问题和您的例子之间的根本区别:Python解释字节码，C编译成本机代码。

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

在Python中，这种比较实际上是几个函数调用，所以(1)有更多的开销,( 2)我假设执行这种比较的代码是用于每隔一个整数比较的解释器中的一个函数——所以它是一个“预测点”,不是特定于当前块的，这使得分支预测器更难正确猜测。

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