Python质数计算：处理池为何更慢？

Question

最近我在玩Python的多进程库，特别喜欢它的处理池功能。这个功能很简单易用，我能想到很多应用场景。我做了一些之前听说过的项目来熟悉这个库，最近还完成了一个程序，用暴力破解的方法来玩猜单词游戏。

总之，我在比较一下在100万到200万之间求所有质数的执行时间，分别用单线程和处理池来执行。对于猜单词的程序，把游戏放进处理池后，执行时间提高了大约8倍（我用的是8核的i7处理器），但在计算这些质数时，处理时间反而增加了近4倍。

有没有人能告诉我这是为什么呢？这里有代码，感兴趣的可以看看或者测试一下：

#!/user/bin/python.exe
import math
from multiprocessing import Pool

global primes
primes = []

def log(result):
    global primes

    if result:
        primes.append(result[1])

def isPrime( n ):
    if n < 2:
        return False
    if n == 2:
        return True, n

    max = int(math.ceil(math.sqrt(n)))
    i = 2
    while i <= max:
        if n % i == 0:
            return False
        i += 1
    return True, n


def main():

   global primes

   #pool = Pool()

   for i in range(1000000, 2000000):
       #pool.apply_async(isPrime,(i,), callback = log)
       temp = isPrime(i)
       log(temp)

   #pool.close()
   #pool.join()

   print sum(primes)

   return

if __name__ == "__main__":
    main()

目前这个代码是单线程运行的，如果想用处理池运行，只需取消注释处理池的相关语句，并把主循环中的其他行注释掉。

Answer 1

使用multiprocessing的最有效方法是把工作分成n个大小相等的部分，其中n是池的大小，应该大致等于你电脑上的核心数量。这样做的原因是，启动子进程和它们之间的通信所需的工作量比较大。如果每个工作的大小相对于工作部分来说太小，那么进程间通信的开销就会变得很重要。

在你的情况下，你让多进程处理每个素数，这样做不是最好的方法。更好的做法是给每个工作者分配一个值的范围（可能只是一个起始值和结束值），让它返回在这个范围内找到的所有素数。

在识别较大的素数时，随着起始值的增大，所需的工作量也会增加。因此，你可能不想把总范围分成正好n个部分，而是分成n*k个相等的部分，其中k是一个合理的小数字，比如10到100。这样，当一些工作者比其他工作者先完成时，还有更多的工作可以做，这样就可以在所有工作者之间有效地平衡工作量。

编辑：这里有一个改进的例子，展示这个解决方案可能是什么样子的。我尽量少改动，这样你可以进行直接比较。

#!/user/bin/python.exe
import math
from multiprocessing import Pool

global primes
primes = set()

def log(result):
    global primes

    if result:
        # since the result is a batch of primes, we have to use 
        # update instead of add (or for a list, extend instead of append)
        primes.update(result)

def isPrime( n ):
    if n < 2:
        return False
    if n == 2:
        return True, n

    max = int(math.ceil(math.sqrt(n)))
    i = 2
    while i <= max:
        if n % i == 0:
            return False
        i += 1
    return True, n

def isPrimeWorker(start, stop):
    """
    find a batch of primes
    """
    primes = set()
    for i in xrange(start, stop):
        if isPrime(i):
            primes.add(i)

    return primes



def main():

    global primes

    pool = Pool()

    # pick an arbitrary chunk size, this will give us 100 different 
    # chunks, but another value might be optimal
    step = 10000

    # use xrange instead of range, we don't actually need a list, just
    # the values in that range.
    for i in xrange(1000000, 2000000, step):
        # call the *worker* function with start and stop values.
        pool.apply_async(isPrimeWorker,(i, i+step,), callback = log)

    pool.close()
    pool.join()

    print sum(primes)

    return

if __name__ == "__main__":
    main()