python - pypy




为什么2*x*x比Python 3.x中的2*(x*x)快,对于整数? (3)

如果你的基准测试是正确的(没有检查),它可能来自这样一个事实,即Python整数可能是两个不同的东西:当它们很小(具有快速计算)时的本机整数,以及当它们增加大小时的大整数(更慢)计算)。 第一种语法在第一次操作后保持较小的尺寸,而第二种语法可能导致两次涉及大整数的操作。

以下Python 3.x整数乘法平均在1.66s和1.77s之间:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
    # num += 2 * (x * x)
    num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))

如果我用2 *(x * x)替换2 * x * x ,则需要在2.042.25之间。 怎么会?

另一方面,它与Java相反: 2 * (x * x)在Java中更快。 Java测试链接: 为什么2 *(i * i)比Java中的2 * i * i更快?

我运行了每个版本的程序10次,这里是结果。

   2 * x * x        |   2 * (x * x)
---------------------------------------
1.7717654705047607  | 2.0789272785186768
1.735931396484375   | 2.1166207790374756
1.7093875408172607  | 2.024367570877075
1.7004504203796387  | 2.047525405883789
1.6676218509674072  | 2.254328966140747
1.699510097503662   | 2.0949244499206543
1.6889283657073975  | 2.0841963291168213
1.7243537902832031  | 2.1290600299835205
1.712965488433838   | 2.1942825317382812
1.7622807025909424  | 2.1200053691864014

据我所知,它归结为使用2 * (x * x)的版本中的更多内存访问。 我打印了反汇编的字节码,它似乎证明:

2 * x * x相关部分:

7          28 LOAD_FAST                1 (num)
           30 LOAD_CONST               3 (2)
           32 LOAD_FAST                2 (x)
           34 BINARY_MULTIPLY
           36 LOAD_FAST                2 (x)
           38 BINARY_MULTIPLY
           40 INPLACE_ADD
           42 STORE_FAST               1 (num)
           44 JUMP_ABSOLUTE           24

2 * (x * x)相关部分:

  7          28 LOAD_FAST                1 (num)
             30 LOAD_CONST               3 (2)
             32 LOAD_FAST                2 (x)
             34 LOAD_FAST                2 (x)
             36 BINARY_MULTIPLY                 <=== 1st multiply x*x in a temp value
             38 BINARY_MULTIPLY                 <=== then multiply result with 2
             40 INPLACE_ADD
             42 STORE_FAST               1 (num)
             44 JUMP_ABSOLUTE           24

首先,请注意我们在Python 2.x中看不到相同的东西:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

所以这让我们相信这是由于Python 3中整数的变化:具体来说,Python 3在任何地方使用long (任意大整数)。

对于足够小的整数(包括我们在这里考虑的整数),CPython实际上只使用O(MN) 等级 - 学校的数字乘法算法 (对于更大的整数,它切换到Karatsuba算法 )。 你可以在source看到这一点。

x*x的位数大约是2*xx两倍(因为log(x 2 )= 2 log(x))。 请注意,此上下文中的“数字”不是基数为10的数字,而是30位值(在CPython的实现中将其视为单个数字)。 因此, 2是单位数值, x2*x是循环的所有迭代的单位数值,但x*xx >= 2**15的两位数。 因此,对于x >= 2**15 2*x*x仅需要逐个单位数的乘法,而2*(x*x)需要单个乘单和一个乘两位数乘法(因为x*x有2个30位数字)。

这是一个直接看到这个的方法(Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

再次,将它与Python 2进行比较,它不会在任何地方使用任意长度的整数:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

(一个有趣的注意事项:如果你看一下这个来源,你会发现算法实际上有一个特殊情况用于平方数字(我们在这里做),但即使这仍然不足以克服2*(x*x)的事实2*(x*x)只需要处理更多数字。)





integer-arithmetic