python - Python 中的基准测试 : Why does my code run slower with repetition?

Question

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

# 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]，将内部 range 设为 xrange，将返回值设为生成器，或者在内部for循环中传递(或使其成为s[j] = True)，行为消失，时间平坦。

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

我的假设是，大量内部 range(大小递减)加上最终数组会导致某种最坏情况下的堆碎片，从而很难继续分配对象。

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