一次加法需要多少 CPU 个周期？

Question

我想测量在 Python 3 中进行加法运算所需的时钟周期数。

我写了一个程序计算加法运算的平均值：

from timeit import timeit

def test(n):
    for i in range(n):
      1 + 1

if __name__ == '__main__':

    times = {}
    for i in [2 ** n for n in range(10)]:
      t = timeit.timeit("test(%d)" % i, setup="from __main__ import test", number=100000)
      times[i] = t
      print("%d additions takes %f" % (i, t))

    keys = sorted(list(times.keys()))

    for i in range(len(keys) - 2):
      print("1 addition takes %f" % ((times[keys[i+1]] - times[keys[i]]) / (keys[i+1] - keys[i])))

输出：

16 additions takes 0.288647
32 additions takes 0.422229
64 additions takes 0.712617
128 additions takes 1.275438
256 additions takes 2.415222
512 additions takes 5.050155
1024 additions takes 10.381530
2048 additions takes 21.185604
4096 additions takes 43.122559
8192 additions takes 88.323853
16384 additions takes 194.353927
1  addition takes 0.008292
1 addition takes 0.010068
1 addition takes 0.008654
1 addition takes 0.010318
1 addition takes 0.008349
1 addition takes 0.009075
1 addition takes 0.008794
1 addition takes 0.008905
1 addition takes 0.010293
1 addition takes 0.010413
1 addition takes 0.010551
1 addition takes 0.010711
1 addition takes 0.011035

所以根据这个输出，一次加法大约需要 0.0095 微秒。按照 this page 说明，我计算出一次加法需要 25 CPU 个周期。这是正常值吗？为什么？因为汇编指令ADD只需要1-2CPU个周期。

Answer 1

您正在为函数调用 (test())、for 循环和对 range() 的调用计时。添加根本没有定时。

def test(n):
    for i in range(n):
        1 + 1

import dis
dis.dis(test)

这是您的测试函数的字节码（不包括对 test() 的调用）：

  2           0 SETUP_LOOP              24 (to 27)
              3 LOAD_GLOBAL              0 (range)
              6 LOAD_FAST                0 (n)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                10 (to 26)
             16 STORE_FAST               1 (i)

  3          19 LOAD_CONST               2 (2)   **** 
             22 POP_TOP             
             23 JUMP_ABSOLUTE           13
        >>   26 POP_BLOCK           
        >>   27 LOAD_CONST               0 (None)
             30 RETURN_VALUE

**** 注意，加法是在编译时完成的。相当多的其他语言及其编译器会这样做，包括 C。但是，标准很少定义 1 + 1 实际完成的时间，因此它通常取决于实现。

编辑:

您的 timeit 函数调用可能是这样的：

    t = timeit("x += 1", setup="x = 1", number=100000)

我们可以创建一个虚拟函数来检查操作：

def myfunc(x):
    x += 1

import dis
dis.dis(myfunc)

进行该更改会得到：

1 additions takes 0.008976
2 additions takes 0.007419
4 additions takes 0.007282
8 additions takes 0.007693
16 additions takes 0.007026
32 additions takes 0.007793
64 additions takes 0.010168
128 additions takes 0.008124
256 additions takes 0.009064
512 additions takes 0.007256
1 addition takes -0.001557
1 addition takes -0.000068
1 addition takes 0.000103
1 addition takes -0.000083
1 addition takes 0.000048
1 addition takes 0.000074
1 addition takes -0.000032
1 addition takes 0.000007

 26           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (1)
              6 INPLACE_ADD
              7 STORE_FAST               0 (x)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

请注意，x += 1 是 INPLACE_ADD，不同于 x = x + 1，后者是 BINARY_ADD。因此，您需要决定要测量哪个 OPCode。

Answer 2

您可以使用 dis 模块更深入地了解幕后发生的事情。

具体来说，dis.dis 函数采用一段已编译的 Python 代码和 returns 该片段被解释为的字节码。在 1 + 1 的情况下：

In [1]: import dis

In [2]: def add1and1():
    return 1 + 1

In [3]: dis.dis(add1and1)
  2           0 LOAD_CONST               2 (2)
              3 RETURN_VALUE

所以在这种情况下，当源代码被编译为字节码时，操作 1 + 1 只被执行一次，然后将结果存储为常量。我们可以通过返回传递给函数的参数总和来解决这个问题：

In [1]: import dis

In [2]: def add(x, y):
    return x + y

In [3]: dis.dis(add)
      2           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD          
              7 RETURN_VALUE

所以你真正感兴趣的字节码指令是BINARY_ADD。如果您想了解更多信息，可以在 CPython 解释器的 ceval.c 文件中找到相关部分 (here):

TARGET(BINARY_ADD) {
    PyObject *right = POP();
    PyObject *left = TOP();
    PyObject *sum;
    if (PyUnicode_CheckExact(left) &&
             PyUnicode_CheckExact(right)) {
        sum = unicode_concatenate(left, right, f, next_instr);
        /* unicode_concatenate consumed the ref to v */
    }
    else {
        sum = PyNumber_Add(left, right);
        Py_DECREF(left);
    }
    Py_DECREF(right);
    SET_TOP(sum);
    if (sum == NULL)
        goto error;
    DISPATCH();
}

所以这里发生的事情比您原先预期的要多。我们有：

一个条件来确定我们是使用 BINARY_ADD 进行字符串连接还是添加数字类型
对 PyNumber_Add 的实际调用，其中人们可能期望更多类似 left + right

这两点都可以用Python的动态特性来解释；因为 Python 在您实际调用 add 之前不知道 x 或 y 的类型，类型检查是在运行时间而不是编译时间完成的.可以在动态语言中进行一些巧妙的优化来解决这个问题（参见 JavaScript 的 V8 或 Python 的 PyPy），但一般来说，这是您为解释的灵活性付出的代价，动态输入语言。

一次加法需要多少 CPU 个周期？

How many CPU cycles one addition take?

python

assembly

clock

timeit