大小列表和布尔值字节数组的相对性能
Relative performance of large and small lists and bytearrays of boolean values
我正在写一个简单的 Sieve of Eratosthenes，其中生成一个包含不超过某个数字 N 的所有素数的列表，而无需执行任何除法或模运算。抽象地说，我的实现使用了一个包含 N 个布尔值的数组，这些值都以 False 开头，并最终在算法过程中翻转为 True。
我想知道这是否会更快 and/or 如果我将它实现为 0 和 1 的 list，[=14] 使用更少的内存=] 的 True 和 False，或 bytearray 的 0 和 1。
计时 (python 2.7)
使用python2.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最好。 True 和 False 的 list 总是比较慢。
计时 (python 3.3)
我也在python3.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 与带有 1 和 0 的 list 没有显着差异。
内存使用
内存使用在 python 2.7 和 3.3 中完全相同。我在list或bytearray上使用了sys.getsizeof，在算法的开始和结束时大小相同。
>>> 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。这个列表真的要大得多。
问题
谁能解释为什么这个算法对小 N 使用 list 运行得更快，而对大 N 使用 bytearray 运行得更快？
测试代码供参考
sieve.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
Can anyone explain why this algorithm runs faster using a list for
small N, and faster using a bytearray for large N?
这完全是特定于实现的，但您会发现这种现象在实践中很常见，即使用较小的数据类型在小输入上表现更差，而在大输入上表现更好。
例如，如果您使用按位逻辑提取第 n 位（其中 n 是一个变量）而不是仅使用布尔数组，则这种情况很常见。当 n 是一个运行时变量时，从一个字节中提取第 n 位需要更多的指令，而不是仅仅设置整个字节，但是位集使用较少的 space.
从广义上讲，这通常是因为用于访问那些较小类型的指令更昂贵，但硬件缓存比 DRAM 访问快得多，而且使用较小类型所获得的改进的空间局部性足以弥补随着您的输入尺寸越来越大。
换句话说，当您输入较大的输入时，空间局部性扮演着越来越重要的角色，而较小的数据类型则为您提供更多空间局部性（允许您将更多相邻元素放入缓存行）。您还可能获得改进的时间局部性（更频繁地访问缓存行中的相同相邻元素）。因此，即使这些元素在加载到寄存器中时需要更多指令或更昂贵的指令，但现在您正在从缓存中访问更多内存这一事实足以弥补这些开销。
现在至于为什么 bytearrays 可能需要比整数列表更多的指令或更昂贵的指令，我不确定。这是个案，具体实施的细节。但也许在您的情况下，它试图将 bytearray 的第 n 个元素加载到 dword 对齐的边界和 dword 大小的寄存器中，例如，并且必须提取特定字节以使用其他指令和操作数在寄存器内进行修改。这都是猜测，除非我们知道您的 Python compiler/interpreter 为您的特定机器发出的确切机器指令。但无论如何，您的测试表明 bytearrays 需要更昂贵的指令才能访问，但对缓存更友好（当您输入更大的输入时，这不仅仅是补偿）。
无论如何，当涉及到较小的数据类型与较大的数据类型时，您会发现这种事情经常发生。这包括压缩，在处理压缩数据时，仔细创建并注意对齐等硬件细节，有时可以胜过未压缩数据，因为解压缩数据所需的额外处理由压缩数据的改进空间局部性补偿，但仅适用于足够大的输入内存访问开始发挥更关键的作用。
我正在写一个简单的 Sieve of Eratosthenes，其中生成一个包含不超过某个数字 N 的所有素数的列表，而无需执行任何除法或模运算。抽象地说，我的实现使用了一个包含 N 个布尔值的数组，这些值都以 False 开头，并最终在算法过程中翻转为 True。
我想知道这是否会更快 and/or 如果我将它实现为 0 和 1 的 list，[=14] 使用更少的内存=] 的 True 和 False，或 bytearray 的 0 和 1。
计时 (python 2.7)
使用python2.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最好。 True 和 False 的 list 总是比较慢。
计时 (python 3.3)
我也在python3.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 与带有 1 和 0 的 list 没有显着差异。
内存使用
内存使用在 python 2.7 和 3.3 中完全相同。我在list或bytearray上使用了sys.getsizeof，在算法的开始和结束时大小相同。
>>> 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。这个列表真的要大得多。
问题
谁能解释为什么这个算法对小 N 使用 list 运行得更快，而对大 N 使用 bytearray 运行得更快？
测试代码供参考
sieve.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
Can anyone explain why this algorithm runs faster using a list for small N, and faster using a bytearray for large N?
这完全是特定于实现的，但您会发现这种现象在实践中很常见，即使用较小的数据类型在小输入上表现更差，而在大输入上表现更好。
例如，如果您使用按位逻辑提取第 n 位（其中 n 是一个变量）而不是仅使用布尔数组，则这种情况很常见。当 n 是一个运行时变量时，从一个字节中提取第 n 位需要更多的指令，而不是仅仅设置整个字节，但是位集使用较少的 space.
从广义上讲，这通常是因为用于访问那些较小类型的指令更昂贵，但硬件缓存比 DRAM 访问快得多，而且使用较小类型所获得的改进的空间局部性足以弥补随着您的输入尺寸越来越大。
换句话说，当您输入较大的输入时，空间局部性扮演着越来越重要的角色，而较小的数据类型则为您提供更多空间局部性（允许您将更多相邻元素放入缓存行）。您还可能获得改进的时间局部性（更频繁地访问缓存行中的相同相邻元素）。因此，即使这些元素在加载到寄存器中时需要更多指令或更昂贵的指令，但现在您正在从缓存中访问更多内存这一事实足以弥补这些开销。
现在至于为什么 bytearrays 可能需要比整数列表更多的指令或更昂贵的指令，我不确定。这是个案，具体实施的细节。但也许在您的情况下，它试图将 bytearray 的第 n 个元素加载到 dword 对齐的边界和 dword 大小的寄存器中，例如，并且必须提取特定字节以使用其他指令和操作数在寄存器内进行修改。这都是猜测，除非我们知道您的 Python compiler/interpreter 为您的特定机器发出的确切机器指令。但无论如何，您的测试表明 bytearrays 需要更昂贵的指令才能访问，但对缓存更友好（当您输入更大的输入时，这不仅仅是补偿）。
无论如何，当涉及到较小的数据类型与较大的数据类型时，您会发现这种事情经常发生。这包括压缩，在处理压缩数据时，仔细创建并注意对齐等硬件细节，有时可以胜过未压缩数据，因为解压缩数据所需的额外处理由压缩数据的改进空间局部性补偿，但仅适用于足够大的输入内存访问开始发挥更关键的作用。