bad*_*nts 3 python optimization branch-prediction
从这里 - 分支预测问题,我开始编写程序的Python版本来检查Python中已排序/未排序版本的运行时.我先尝试排序.
这是代码:
import time
from random import *
arraysize = 327
data = []
for c in range(arraysize):
data.append( randint( 1 , 256 ) )
## !!! with this, the next loop runs faster
data.sort()
## test
start_time = time.clock()
sum = 0
for i in range(100000):
for c in range(arraysize):
if data[c] >= 128:
sum += data[c]
print time.clock() - start_time
我不确定我的简单时序方法的准确性,但似乎已经足够了.当我设置时,arraysize = 32768我第一次等待> 20分钟!超过20分钟!但是arraysize = 327,我有时间8.141656691s.
如果我的代码中某处出错,请纠正我,或者在某种程度上使用Numpy/Scipy会加快速度.谢谢.
我从@mgilson的答案开始,并重新做了一点.我想测试"决策位"和查找表技术,如我对原始问题的回答中所述:https://stackoverflow.com/a/17782979/166949
我对原版做了一些修改.有些只是反映我个人偏好的风格.但是,我发现了原版中的错误,我认为测量正确的代码很重要.
我现在使用Python代码从命令行获取参数,并编写了一个使用Python 2.x,Python 3.x和PyPy运行Python脚本的shell脚本.确切的版本是:Python 2.7.6,Python 3.4.0和PyPy 2.7.3
我在Linux Mint 17,64位版本上运行测试.CPU是AMD Phenom 9850,运行频率为2.5 GHz,内存为16 GB.Linux内核版本uname -r为:3.13.0-24-generic
我从命令行获取参数的原因是327是一个非常短的列表.我认为sum()当列表更长时,和生成器表达式会做得更好,所以我从命令行传递了列表大小和试验次数.结果显示了哪个Python,以及列表长度和试验次数.
结论:令我惊讶的是,即使有一个很长的列表,Python也是最快的使用sum()列表理解!运行生成器有一些开销似乎比构建列表然后将其拆除的开销慢.
但是,如果列表真的很大,我预计生成器将开始超出列表理解.随着一百万随机值的列表,listcomp仍然更快,但当我达到1600万随机值时,genexp变得更快.并且对于较短列表,生成器表达式的速度惩罚不大.所以我仍然喜欢生成器表达式作为在Python中解决这个问题的首选方法.
有趣的是,PyPy在查找表时速度最快.这是有道理的:这是我在C中找到的最快的方式,而PyPy正在从JIT生成本机代码.
对于CPython,使用其虚拟机,调用单个操作比几个操作更快; Python VM的开销可能超过更昂贵的基本操作.因此,整数除法比位掩码加位移更快,因为除法是单个操作.但在PyPy中,位屏蔽+移位比分区快得多.
此外,在CPython中,使用sum()让你的代码在C内部运行,因此它可以非常快; 但是在PyPy中,sum()慢于编写一个直接循环,JIT可以变成一个邪恶的快速原生循环.我的猜测是,生成器机器很难让PyPy陷入困境并优化为本机代码.
shell脚本:
for P in python python3 pypy; do
echo "$P ($1, $2)"
$P test_branches.py $1 $2
echo
done
Python代码:
import random
import sys
import timeit
try:
RANGE = xrange
except NameError:
RANGE = range
if len(sys.argv) != 3:
print("Usage: python test_branches.py <length_of_array> <number_of_trials>")
sys.exit(1)
TEST_DATA_LEN = int(sys.argv[1])
NUM_REPEATS = int(sys.argv[2])
_test_data = [random.randint(0,255) for _ in RANGE(TEST_DATA_LEN)]
def test0(data):
"""original way"""
total = 0
for i in RANGE(TEST_DATA_LEN):
if data[i] >= 128:
total += data[i]
return total
def test1(data):
"""better loop"""
total = 0
for n in data:
if n >= 128:
total += n
return total
def test2(data):
"""sum + generator"""
return sum(n for n in data if n >= 128)
def test3(data):
"""sum + listcomp"""
return sum([n for n in data if n >= 128])
def test4(data):
"""decision bit -- bit mask and shift"""
lst = [0, 0]
for n in data:
lst[(n & 0x80) >> 7] += n
return lst[1]
def test5(data):
"""decision bit -- division"""
lst = [0, 0]
for n in data:
lst[n // 128] += n
return lst[1]
_lut = [0 if n < 128 else n for n in RANGE(256)]
def test6(data):
"""lookup table"""
total = 0
for n in data:
total += _lut[n]
return total
def test7(data):
"""lookup table with sum()"""
return sum(_lut[n] for n in data)
test_functions = [v for k,v in globals().items() if k.startswith("test")]
test_functions.sort(key=lambda x: x.__name__)
correct = test0(_test_data)
for fn in test_functions:
name = fn.__name__
doc = fn.__doc__
if fn(_test_data) != correct:
print("{}() not correct!!!".format(name))
s_call = "{}(_test_data)".format(name)
s_import = "from __main__ import {},_test_data".format(name)
t = timeit.timeit(s_call,s_import,number=NUM_REPEATS)
print("{:7.03f}: {}".format(t, doc))
结果:
python (327, 100000)
3.170: original way
2.211: better loop
2.378: sum + generator
2.188: sum + listcomp
5.321: decision bit -- bit mask and shift
4.977: decision bit -- division
2.937: lookup table
3.464: lookup table with sum()
python3 (327, 100000)
5.786: original way
3.444: better loop
3.286: sum + generator
2.968: sum + listcomp
8.858: decision bit -- bit mask and shift
7.056: decision bit -- division
4.640: lookup table
4.783: lookup table with sum()
pypy (327, 100000)
0.296: original way
0.312: better loop
1.932: sum + generator
1.011: sum + listcomp
0.172: decision bit -- bit mask and shift
0.613: decision bit -- division
0.140: lookup table
1.977: lookup table with sum()
python (65536, 1000)
6.528: original way
4.661: better loop
4.974: sum + generator
4.150: sum + listcomp
10.971: decision bit -- bit mask and shift
10.218: decision bit -- division
6.052: lookup table
7.070: lookup table with sum()
python3 (65536, 1000)
12.999: original way
7.618: better loop
6.826: sum + generator
5.587: sum + listcomp
19.326: decision bit -- bit mask and shift
14.917: decision bit -- division
9.779: lookup table
9.575: lookup table with sum()
pypy (65536, 1000)
0.681: original way
0.884: better loop
2.640: sum + generator
2.642: sum + listcomp
0.316: decision bit -- bit mask and shift
1.573: decision bit -- division
0.280: lookup table
1.561: lookup table with sum()
python (1048576, 100)
10.371: original way
7.065: better loop
7.910: sum + generator
6.579: sum + listcomp
17.583: decision bit -- bit mask and shift
15.426: decision bit -- division
9.285: lookup table
10.850: lookup table with sum()
python3 (1048576, 100)
20.435: original way
11.221: better loop
10.162: sum + generator
8.981: sum + listcomp
29.108: decision bit -- bit mask and shift
23.626: decision bit -- division
14.706: lookup table
14.173: lookup table with sum()
pypy (1048576, 100)
0.985: original way
0.926: better loop
5.462: sum + generator
6.623: sum + listcomp
0.527: decision bit -- bit mask and shift
2.334: decision bit -- division
0.481: lookup table
5.800: lookup table with sum()
python (16777216, 10)
15.704: original way
11.331: better loop
11.995: sum + generator
13.787: sum + listcomp
28.527: decision bit -- bit mask and shift
25.204: decision bit -- division
15.349: lookup table
17.607: lookup table with sum()
python3 (16777216, 10)
32.822: original way
18.530: better loop
16.339: sum + generator
14.999: sum + listcomp
47.755: decision bit -- bit mask and shift
38.930: decision bit -- division
23.704: lookup table
22.693: lookup table with sum()
pypy (16777216, 10)
1.559: original way
2.234: better loop
6.586: sum + generator
10.931: sum + listcomp
0.817: decision bit -- bit mask and shift
3.714: decision bit -- division
0.752: lookup table
3.837: lookup table with sum()