python - bool 值的大列表和小列表以及字节数组的相对性能

Question

我正在写一个简单的Sieve of Eratosthenes其中，无需执行任何除法或模运算，即可生成直到某个数字 N 的所有素数的列表。抽象地说，我的实现使用了一个由 N 个 bool 值组成的数组，这些值都从 False 开始，并最终在算法过程中翻转为 True。

我想知道如果我将其实现为list，这是否会更快和/或使用更少的内存。的0和1 ，一个list的True和False ，或 bytearray的0和1 .

计时(python 2.7)

使用python 2.7，在使用N = 10k和N = 30M时发现以下内容:

$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'
10 loops, best of 3: 1.42 sec per loop
$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)'
10 loops, best of 3: 1.23 sec per loop
$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'
10 loops, best of 3: 1.65 sec per loop

$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'
500 loops, best of 3: 3.59 msec per loop
$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'
500 loops, best of 3: 4.12 msec per loop
$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'
500 loops, best of 3: 4.25 msec per loop

            10k       3M
byte (01)   4.12 ms   1.23 s
list (01)   3.59 ms   1.42 s
list (TF)   4.25 ms   1.65 s

令我惊讶的是，对于较小的 N 值，list整数是最好的，对于较大的 N 值，bytearray是最好的。 list True 和 False 的判断总是比较慢。

计时(python 3.3)

我也在python 3.3中重复了测试:

$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'
10 loops, best of 3: 2.05 sec per loop
$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)' 
10 loops, best of 3: 1.76 sec per loop
$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'
10 loops, best of 3: 2.02 sec per loop

$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'
500 loops, best of 3: 5.19 msec per loop
$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'
500 loops, best of 3: 5.34 msec per loop
$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'
500 loops, best of 3: 5.16 msec per loop

            10k       3M
byte (01)   5.34 ms   1.76 s
list (01)   5.19 ms   2.05 s
list (TF)   5.16 ms   2.02 s

这里有与 list 相同的排序。对于小N来说更好，而bytearray对于大 N，但是list与 True和False与 list 没有显着差异与 1和0 .

内存使用

Python 2.7 和 3.3 中的内存使用情况完全相同。我用过sys.getsizeof关于list或bytearray ，在算法开始和结束时大小相同。

>>> import sieve
>>> sieve.verbose = True
>>> x = sieve.soe_list(10000)
soe_list, 10000 numbers, size = 83120
>>> x = sieve.soe_byte(10000)
soe_byte, 10000 numbers, size = 10993
>>> x = sieve.soe_list2(10000)
soe_list2, 10000 numbers, size = 83120
>>> x = sieve.soe_list(3000000)
soe_list, 3000000 numbers, size = 26791776
>>> x = sieve.soe_byte(3000000)
soe_byte, 3000000 numbers, size = 3138289
>>> x = sieve.soe_list2(3000000)
soe_list2, 3000000 numbers, size = 26791776

            10k       3M
byte (01)   ~11k      ~3.1M
list (01)   ~83k      ~27M
list (TF)   ~83k      ~27M

我有点惊讶~大 bytearray使用了比大的更多的内存 list鉴于大 bytearray更快。

编辑:哎呀，正如评论中指出的，我错误地读取了自己的值并将 27M 解释为 2.7M。这个列表确实要大得多。

问题

任何人都可以解释为什么这个算法使用 list 运行得更快对于小 N，使用 bytearray 更快对于大N？

测试代码供引用

筛子.py:

import sys

if sys.version_info.major == 3:
    xrange = range

verbose = False

def soe_byte(upper):
    numbers = bytearray(0 for _ in xrange(0,upper+1))
    if verbose:
        print("soe_byte, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
    primes = []
    cur = 2
    while cur <= upper:
        if numbers[cur] == 1:
            cur += 1
            continue
        primes.append(cur)
        for i in xrange(cur,upper+1,cur):
             numbers[i] = 1
    return primes

def soe_list(upper):
    numbers = list(0 for _ in xrange(0,upper+1))
    if verbose:
        print("soe_list, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
    primes = []
    cur = 2
    while cur <= upper:
        if numbers[cur] == 1:
            cur += 1
            continue
        primes.append(cur)
        for i in xrange(cur,upper+1,cur):
             numbers[i] = 1
    return primes

def soe_list2(upper):
    numbers = list(False for _ in xrange(0,upper+1))
    if verbose:
        print("soe_list2, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
    primes = []
    cur = 2
    while cur <= upper:
        if numbers[cur] == True:
            cur += 1
            continue
        primes.append(cur)
        for i in xrange(cur,upper+1,cur):
             numbers[i] = True
    return primes 

Answer 1

Can anyone explain why this algorithm runs faster using a list for small N, and faster using a bytearray for large N?

这都是特定于实现的，但是您会看到这种现象在实践中经常发生，其中使用较小的数据类型在小输入上表现较差，而在大输入上表现更好。

例如，如果您使用按位逻辑提取第 n 位(其中 n 是一个变量)而不是仅使用 bool 值数组，则经常会发生这种情况。当 n 是运行时变量时，从字节中提取第 n 位需要更多指令，而不仅仅是设置整个字节，但位集使用的空间更少。

从广义上讲，这通常是因为用于访问这些较小类型的指令更昂贵，但硬件缓存比 DRAM 访问快得多，并且使用较小类型所获得的改进的空间局部性足以弥补这一点:您的输入尺寸变得越来越大。

换句话说，当您输入更大的输入时，空间局部性发挥着越来越重要的作用，而较小的数据类型可以为您提供更多空间局部性(允许您将更多相邻元素放入缓存行中)。您还可能获得改进的时间局部性(更频繁地访问缓存行中的相同相邻元素)。因此，即使元素在加载到寄存器时需要更多指令或更昂贵的指令，现在您可以从缓存访问更多内存，这一开销也足以得到补偿。

现在至于为什么 bytearrays 可能需要比整数列表更多的指令或更昂贵的指令，我不确定。这是极其具体的具体实现细节。但也许在您的情况下，它试图将字节数组的第 n 个元素加载到双字对齐的边界和双字大小的寄存器中，并且必须使用附加指令和操作数提取特定字节以在寄存器内进行修改。这都是猜测，除非我们知道您的 Python 编译器/解释器为您的特定机器发出的确切机器指令。但无论情况如何，您的测试表明字节数组需要更昂贵的指令才能访问，但对缓存更加友好(当您输入更大的输入时，这不仅仅是补偿)。

无论如何，当涉及较小的数据类型与较大的数据类型时，您会看到这种情况经常发生。这包括压缩，其中处理压缩数据(在注意对齐等硬件细节的情况下仔细创建)有时可以胜过未压缩数据，因为解压缩数据所需的额外处理可以通过压缩数据改进的空间局部性来补偿，但仅限于足够大的输入内存访问开始发挥更关键的作用。