探究数组排序提升Python程序的循环的运行效率的原因

早上我偶然看见一篇介绍两个Python脚本的博文，其中一个效率更高。这篇博文已经被删除，所以我没办法给出文章链接，但脚本基本可以归结如下：
fast.py

import time
a = [i for i in range(1000000)]
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

slow.py

import time
from random import shuffle
a = [i for i in range(1000000)]
shuffle(a)
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

如你所见，两个脚本有完全相同的行为。都产生一个包含前一百万个整数的列表，并打印对这些整数求和的时间。唯一的不同是 slow.py 先将整数随机排序。尽管这看起来有些奇怪，似乎随机化足够将程序明显变慢。在我机器上，运行的Python2.7.3， fast.py 始终比 slow.py 快十分之一秒（fast.py 执行大约耗时四分之三秒，这是不平常的增速）。你不妨也试试看。（我没有在Python3上测试，但结果应该不会差太多。）

那为什么列表元素随机化会导致这么明显的减速呢？博文的原作者把这记作“分支预测（branch prediction）”。如果你对这个术语不熟悉，可以在 StackOverflow 的提问中看看，这里很好地解释了这个概念。（我的疑虑是原文的原作者遇到了这个问题或者与此类似的问题，并把这个想法应用到不太适合应用的Python片段中。）

当然，我怀疑分支预测（branch prediction）是否是真正导致问题的原因。在这份Python代码中没有顶层条件分支，而且合乎情理的是两个脚本在循环体内有严格一致的分支。程序中没有哪一部分是以这些整数为条件的，并且每个列表的元素都是不依赖于数据本身的。当然，我还是不确定python是否算得上足够“底层”，以至于CPU级别的分支预测能够成为python脚本性能分析中的一个因素。Python毕竟是一门高级语言。

因此，如果不是分支预测的原因，那为什么 slow.py 会这么慢？通过一点研究，经过一些“失败的开端”之后，我觉得自己找到了问题。这个答案需要对Python内部虚拟机有点熟悉。

失败的开端：列表vs.生成器（lists and generators）

我的第一想法是Python对排序的列表[i for i in range(1000000)] 的处理效率要比随机列表高。换句话说，这个列表可以用下面的生成器替代：

def numbers():
  i = 0
  while i < 1000000:
    yield i
    i += 1

我想这可能在时间效率上更高效些。毕竟，如果Python在内部使用生成器替代真正的列表可以避免在内存中一次保存所有整数的麻烦，这可以节省很多开销。slow.py 中的随机列表不能轻易的被一个简单生成器捕获，所有VM（虚拟机）无法进行这样的优化。

然而，这不是一个有用的发现。如果在slow.py的 shuffle() 和循环之间插入 a.sort()，程序会像 fast.py一样快。很明显，数字排序后的一些细节让程序更快。

失败的开端：列表对比数组

我的第二个想法是有可能数据结构造成的缓存问题。a 是一个列表，这自然让我相信a实际上是通过链表来实现的。如果shuffle操作故意随机化这个链表的节点，那么 fast.py 可能可以把列表的所有链表元素分配在相邻地址，从而采用高级局部缓存，而slow.py会出现很多缓存未命中的情况，因为每个节点引用不在同一个缓存行上的另外一个节点。

不幸的是，这也不对。Python的列表对象不是链接的列表，而是真正意义上的数组。尤其是用C结构体定义了Python列表对象：

typedef struct {
 PyObject_VAR_HEAD
 PyObject **ob_item;
 Py_ssize_t allocated;
} PyListObject;

……换句话说，ob_item 是一个指向PyObjects指针数组的指针，并且分配的大小是我们分配给数组的大小。因此，这对于解决这个问题也没帮助（尽管这对我不确定Python中关于列表操作的算法复杂度有些安慰：列表的添加操作算法复杂度是O(1)，访问任意列表元素的算法复杂度是O(1)，等等）。我只是想说明为什么Guido选择称它们为列表“lists”而不是数组“arrays”，而实际上它们却是数组。

解决办法：整体对象

数组元素在内存中是相邻的，因此这样的数据结构不会带来缓存问题。事实证明缓存位置是 slow.py 变慢的原因，但这来自于一个意料之外的地方。在Python中，整数是分配在堆中的对象而不是一个简单的值。尤其是在虚拟机中，整数对象看起来像下面这样：

typedef struct {
 PyObject_HEAD
 long ob_ival;
} PyIntObject;

上面结构体中唯一“有趣”的元素是ob_ival（类似于C语言中的整数）。如果你觉得使用一个完整的堆对象来实现整数很浪费，你也许是对的。很多语言就为了避免这样而做优化。例如 Matz的 Ruby 解释器通常以指针的方式存储对象，但是对频繁使用的指针做例外处理。简单来说，Ruby解释器把定长数作为对象应用塞到同样的空间，并用最低有效位来标记这是一个整数而不是一个指针（在所有现代系统中，malloc总是返回以2的倍数对齐的内存地址）。在那时，你只需要通过合适的位移来获取整数的值——不需要堆位置或者重定向。如果CPython做类似的优化，slow.py 和 fast.py 会有同样的速度（而且他们可能都会更快）。

那么CPython是怎样处理整数的呢？解释器的什么行为给我们如此多的疑惑？Python解释器每次将整数分配到40Byte的“块”中（block）。当Python需要生成新的整型对象时，就在当前的整数“块”中开辟下一个可用空间，并将整数存储在其中。我们的代码在数组中分配一百万个整数，大部分相邻的整数会被放到相邻的内存中。因此，在有序的一百万个数中遍历展现出不错的缓存定位，而在随机排序的前一百万个数中定位出现频繁的缓存未命中。

因此，“为什么对数组排序使得代码更快”的答案就是它根本没有这个作用。没有打乱顺序的数组遍历的速度更快，因为我们访问整型对象的顺序和分配的顺序一致（他们必须被分配）。