Python中的基准测试:为什么我的代码在重复时运行得更慢？

Question

我有一个简单的Eratosthanes Sieve实现如下:

# Generate all primes less than k
def sieve(k):
    s = [True] * k
    s[0] = s[1] = False
    for i in range(4, k, 2):
        s[i] = False

    for i in range(3, int(sqrt(k)) + 2, 2):
        if s[i]:            
            for j in range(i ** 2, k, i * 2):
                s[j] = False

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

我通过在10M以下重复生成质数来对此代码进行基准测试:

st = time()
for x in range(1000):
    rt = time()
    sieve(10000000)
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st) / (x + 1))

我很困惑,因为每次测试运行所花费的时间显着增加:

run   t  avg
  0 1.49 1.49
  1 1.79 1.66
  2 2.23 1.85
  3 2.72 2.07
  4 2.67 2.20
  5 2.87 2.31
  6 3.05 2.42
  7 3.57 2.56
  8 3.38 2.65
  9 3.48 2.74
 10 3.81 2.84
 11 3.75 2.92
 12 3.85 2.99
 13 4.14 3.07
 14 4.02 3.14
 15 4.05 3.20
 16 4.48 3.28
 17 4.41 3.34
 18 4.19 3.39
 19 4.22 3.43
 20 4.65 3.49

但是,更改每个实例range可以xrange消除此问题:

run   t  avg
  0 1.26 1.26
  1 1.23 1.28
  2 1.24 1.27
  3 1.25 1.26
  4 1.23 1.26
  5 1.23 1.25
  6 1.25 1.25
  7 1.25 1.25
  8 1.23 1.25
  9 1.25 1.25
 10 1.24 1.25

为什么会这样？它真的是所有的GC开销吗？20次运行后减速3倍似乎很多......

Answer 1

这（还）不是答案，而只是有组织的实验的集合。

这真的很有趣。Python 的内存分配器似乎发生了一些非常可疑的事情。

这是我减少测试用例的尝试：

def sieve(k):
    s = [True] * k

    for i in xrange(3, int(sqrt(k)) + 2, 2):
        for j in range(i ** 2, k, i * 2):
            s[j] = False

    return [ i for i in range(3, k, 2) if s[i] ]

st = time()
for x in range(1000):
    rt = time()
    sieve(10000000)
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st) / (x + 1))

请注意，如果我删除if s[i]，使内部成为rangean xrange，使返回值成为生成器，或者pass在内部for循环中（或使其成为s[j] = True），则行为消失并且时间平坦。

随着函数运行，Python 的内存使用量稳步增加，最终达到稳定状态（此时运行时间也开始稳定，约为初始值的 250%）。

我的假设是，大量的内部变量range（大小不断减小）加上最终的数组，会导致某种最坏情况的堆碎片，使得继续分配对象变得非常困难。

我的建议是制作一个简化的测试用例，并将其作为 bug 提交给 Python 开发人员 (bugs.python.org)。