Question

仅理解计算机的基本组成部分并不足以理解高性能编程的问题。所有这些组件的互动与合作还会引入新的复杂度。本段将研究一些样本问题，描述理想的解决方案以及Python如何实现它们。

警告：本段可能看上去让人绝望——大多数问题似乎都证明Python并不适合解决性能问题。这不是真的，原因有两点。首先，在所有这些“高性能计算要素”中，我们忽视了一个至关重要的要素：开发者。原生Python在性能上欠缺的功能会被迅速开发出来。另外，我们会在本书中介绍各种模块和原理来帮助减轻这里遇到的问题。当这两点结合起来，我们就能在快速开发Python的同时移除很多性能局限。

理想计算模型和Python虚拟机

为了更好地理解高性能编程的要素，让我们来看一段用于判断质数的简单代码样例：

import math
def check_prime(number):
  sqrt_number = math.sqrt(number)
  number_float = float(number)
  for i in xrange(2, int(sqrt_number)+1):
    if (number_float / i).is_integer():
      return False
  return True

print "check_prime(10000000) = ", check_prime(10000000) # False
print "check_prime(10000019) = ", check_prime(10000019) # True

让我们用抽象的计算模型来分析这段代码对比Python运行这段代码时实际发生了什么。由于是抽象模型，我们将忽略很多理想化的计算机以及Python运行代码方式的细节。不过，这是一个在解决实际问题之前很好的练习：思考算法中的通用组件以及如何最优地使用这些组件来解决问题。只要明白在理想情况下以及实际在Python中发生了什么，我们就能让自己的Python代码一步步接近最优。

1．理想计算模型

在代码的开头，我们将number的值保存于RAM中。为了计算sqrt_number和number_float，我们需要将该值传入CPU。在理想情况下，我们只需要传一次，它将被保存在CPU的L1/L2缓存中，然后CPU会进行两次计算并将结果传回RAM保存。这是一个理想的情况，因为我们令从RAM中读取number的值的次数最少，转而以快很多的L1/L2缓存的读取代替。另外，我们还令前端总线传输数据的次数最少，以更快的后端总线（连接CPU和各类缓存）的传输代替之。将数据保持在需要的地方并尽量少移动这一场景对于优化来说至关重要。所谓“沉重数据”的概念指的是移动数据需要花费时间，而这就是我们需要避免的。

在代码的循环部分，与其一次次将i输入CPU，我们更希望一次就将number_float和多个i的值输入CPU进行检查。这是可能的，因为CPU的矢量操作不需要额外的时间代价，意味着它可以一次进行多个独立计算。所以我们希望将number_float传入CPU缓存，以及在缓存放得下的情况下传入尽可能多的i的值。对于每一对number_float/i，我们将进行除法计算并检查结果是否为整数，然后传回一个信号表明是否有任意一个结果确实为整数。如果是，则函数结束。如果否，我们继续下一批计算。这样，对于多个i的值，我们只需要传回一个结果，而不是依靠总线返回所有的值。这利用了CPU的矢量化计算的能力，或者说在一个时钟周期内以一条指令操作了多个数据。

这一矢量操作的概念可以用下列代码来表述：

import math
def check_prime(number):
  sqrt_number = math.sqrt(number)
  number_float = float(number)
  numbers = range(2, int(sqrt_number)+1)
  for i in xrange(0, len(numbers), 5):
    # the following line is not valid Python code
    result = (number_float / numbers[i:(i+5)]).is_integer()
    if any(result):
      return False
  return True

这里，我们让程序一次对5个i的值进行除法和整数检查。当被正确地矢量化时，CPU仅需一条指令完成这行代码而不是对每个i进行独立操作。理想情况下，any(result)操作将只发生于CPU内部而无须将数据传回RAM。我们将在第6章讨论更多关于矢量操作的细节，包括它具体如何工作以及在什么情况下有利于你的代码。

2．Python虚拟机

Python解释器为了抽离底层用到的计算元素做了很多工作。这让编程人员无须考虑如何为数组分配内存、如何组织内存以及用什么样的顺序将内存传入CPU。这是Python的一个优势，让你能够集中在算法的实现上。然而它有一个巨大的性能代价。

首先我们要意识到Python核心运行于一组非常优化的指令上。而诀窍就是让Python以正确的次序执行它们来获得更好的性能。比如下例，我们可以轻松看出，虽然两个算法都有O(n)的运行时间，search_fast会比search_slow快，因为它提前中止了循环，跳过了不必要的计算。

def search_fast(haystack, needle):
  for item in haystack:
    if item == needle:
      return True
  return False

def search_slow(haystack, needle):
  return_value = False
  for item in haystack:
    if item == needle:
      return_value = True
  return return_value

通过性能分析查找代码的慢速区域以及寻找更有效的算法其实就是寻找这些无用的操作并删除它们，最终的结果是一样的，但计算和传输数据的次数却大大减少了。

而Python虚拟机抽象层的影响之一就是矢量操作变得不是直接可用了。我们最初的质数函数会循环遍历i的每一个值而不是将多次遍历组合成一个矢量操作。而我们抽象以后的矢量化代码并不是合法的Python代码，因为我们不能用一个列表去除一个浮点。numpy这样的外部库可以通过增加矢量化数学操作的方式帮助我们解决这个问题。

另外，Python抽象还影响了任何需要为下一次计算保存L1/L2缓存中相关数据的优化。这有很多原因，首先是Python对象不再是内存中最优化的布局。这是因为Python是一种垃圾收集语言——内存会被自动分配并在需要时释放。这会导致内存碎片并影响向CPU缓存的传输。另外，我们也没有任何机会去直接改变数据结构在内存中的布局，这意味着总线上的一次传输可能并不包含一次计算的所有相关信息，即使这些信息少于总线带宽。

第二个问题更加基本，根源是Python的动态类型以及Python并不是一门编译性的语言。很多C语言开发者已经在多年开发过程中意识到，编译器总是比你聪明。当编译静态代码时，编译器可以做很多的事情来改变对象的内存布局以及让CPU运行某些指令来优化它们。然而，Python并不是一种编译性的语言：更糟的是，它还具有动态类型，意味着任何算法上可能的优化机会都会更加难以实现，因为代码的功能有可能在运行时被改变。有很多方法可以缓解这一问题，其中最主要的一个方法就是使用Cython，它可以将Python代码进行编译并允许用户“提示”编译器代码究竟有多“动态”。

最后，之前提到的GIL会影响并行代码的性能。比如，假设我们改变代码来使用多个CPU核心，每个核心收到一堆数字，取值范围是2到sqrtN。每个核心可以对自身收到的数据进行计算，当它们都完成时可以互相进行比较。这看上去是一个好方案，虽然我们失去了提前中止循环的能力，但是随着我们使用的核心数的增加，每个核心需要进行的检查数降低了（例如，如果我们有M个核心，每个核心只需要进行sqrtN/M次检查）。然而，由于GIL，一次仅有一个核心可以被使用。这意味着我们还是以非并行的方式运行这段代码，而且还不能提前中止。我们可以使用多进程（multiprocessing模块）而不是多线程，或者使用Cython或外部函数来避免这个问题。