14

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

但我只是尝试了使用 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'
4

5 回答 5

19

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

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

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

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

于 2012-10-11T15:14:14.647 回答
5

我将原始代码移植到 Python 并使用 PyPy 运行它。我可以确认排序数组的处理速度比未排序数组快，并且无分支方法也可以消除运行时间类似于排序数组的分支。我相信这是因为 PyPy 是一个 JIT 编译器，所以分支预测正在发生。

[编辑]

这是我使用的代码：

随机导入
进口时间

def runme（数据）：
  总和 = 0
  开始 = time.time()

  对于 xrange(100000) 中的 i：
    对于数据中的 c：
      如果 c >= 128：
        总和 += c

  结束 = time.time()
  打印结束 - 开始
  打印总和

def runme_branchless（数据）：
  总和 = 0
  开始 = time.time()

  对于 xrange(100000) 中的 i：
    对于数据中的 c：
      t = (c - 128) >> 31
      总和 += ~t & c

  结束 = time.time()
  打印结束 - 开始
  打印总和

数据 = 列表（）

对于 xrange(32768) 中的 i：
  data.append(random.randint(0, 256))

sorted_data = 排序（数据）
运行（排序数据）
运行（数据）
runme_branchless(sorted_data)
runme_branchless（数据）
于 2012-10-15T06:44:00.273 回答
5

两个原因：

  • 您的数组大小太小而无法显示效果。
  • Python 比 C 有更多的开销，因此整体效果不太明显。
于 2012-10-11T15:09:25.473 回答
4

sorted()返回一个排序数组而不是就地排序。您实际上是在测量同一个阵列两次。

于 2012-10-11T15:10:47.703 回答
-3

单击此处查看更多答案和类似问题。对数据进行排序时性能大幅提高的原因是分支预测惩罚被删除，正如 Mysticial 的回答中所解释的那样。

于 2014-06-16T13:32:47.410 回答