在这篇文章中为什么处理排序数组比处理随机数组更快 https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array,它说分支预测是排序数组性能提升的原因。
但我只是用Python尝试了这个例子;我认为排序数组和随机数组之间没有区别(我尝试了 bytearray 和 array;并使用 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'
我可能是错的,但我看到链接的问题和您的示例之间存在根本区别:Python 解释字节码,C++ 编译为本机代码。
在 C++ 代码中if
直接翻译成cmp
/jl
序列,CPU 分支预测器可以将其视为特定于该周期的单个“预测点”。
在Python中,比较实际上是几个函数调用,所以有(1)更多的开销,(2)我认为执行该比较的代码是解释器中用于每个其他整数比较的函数 - 所以它是一个“预测点”而不是特定于当前块,这使得分支预测器更难正确猜测。
Edit: 另外,如中所述this http://www.jilp.org/vol5/v5paper12.pdf论文中,解释器内部有更多的间接分支,因此 Python 代码中的这种优化可能会被解释器本身的分支错误预测所掩盖。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)