为什么处理排序数组的速度不比Python中的未排序数组快？

Question

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

但我只是尝试使用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++编译为本机代码.

在if直接转换为cmp/ jl序列的C++代码中,CPU分支预测器可将其视为单个"预测点",特定于该循环.

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

编辑:另外,在概述这个文件里有这样一个解释器更间接分支,所以在你的Python代码这样的优化可能会被在解释自己的分支预测失误反正埋葬.

Answer 2

两个原因:

• 您的数组太小,无法显示效果.
• Python比C具有更多的开销,因此整体效果不太明显.

Answer 3

我将原始代码移植到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)