Python3.x整数比位移快2倍？

Question

我在查看sorted_containers的源代码时，惊讶地看到了这一行：

self._load, self._twice, self._half = load, load * 2, load >> 1

这里的load是一个整数。为什么在一个地方使用位移位，而在另一个地方使用乘法？位移位可能比整数除以2快，这似乎是合理的，但为什么不把乘法也换成移位呢？我对以下案例进行了基准测试：

1. （乘以，除法）
2. （shift,shift)
3. （次数，移位）
4. （移位、除法）

# self._load, self._twice, self._half = load, load * 2, load >> 1

import random
import timeit
import pandas as pd

x = random.randint(10 ** 3, 10 ** 6)

def test_naive():
    a, b, c = x, 2 * x, x // 2

def test_shift():
    a, b, c = x, x << 1, x >> 1    

def test_mixed():
    a, b, c = x, x * 2, x >> 1    

def test_mixed_swapped():
    a, b, c = x, x << 1, x // 2

def observe(k):
    print(k)
    return {
        'naive': timeit.timeit(test_naive),
        'shift': timeit.timeit(test_shift),
        'mixed': timeit.timeit(test_mixed),
        'mixed_swapped': timeit.timeit(test_mixed_swapped),
    }

def get_observations():
    return pd.DataFrame([observe(k) for k in range(100)])

以上是问题的原话。丹·盖茨在他的回答中提供了一个极好的解释。

为了完整起见，下面是不应用乘法优化时较大x的示例说明。

Answer 1

这似乎是因为在CPython3.5中优化了小数乘法，使小数左移不是这样。正左移总是创建一个较大的整数对象来存储结果，作为计算的一部分，而对于您在测试中使用的那种类型的乘法，一个特殊的优化避免了这一点，并创建了一个大小正确的整数对象。这可以在Python的整数实现的源代码中看到。

因为Python中的整数是任意精度的，所以它们被存储为整数“数字”的数组，对每个整数数字的位数有限制。所以在一般情况下，涉及整数的操作不是单次操作，而是需要处理多个“数字”的情况。在pyport.h中，此位限制在64位平台上定义为30位，否则定义为15位。（为了使解释简单，我将从这里开始将其称为30，但请注意，如果您使用的是为32位编译的Python，那么您的基准测试结果将取决于x是否小于32,768。）

当一个操作的输入和输出停留在这个30位限制内时，就可以以优化的方式而不是一般的方式来处理该操作。整数乘法实现的开始如下：

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit dihtml" target="_blank">gits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

相反，左移位不是这样优化的，每次左移位都将被移位的整数作为数组处理。特别是，如果您查看long_lshift()的源代码，在小但正的左移的情况下，总是创建一个2位整数对象，即使以后将其长度截断为1：（我在/*****/中的注释）

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
    /*** ... ***/

    wordshift = shiftby / PyLong_SHIFT;   /*** zero for small w ***/
    remshift  = shiftby - wordshift * PyLong_SHIFT;   /*** w for small w ***/

    oldsize = Py_ABS(Py_SIZE(a));   /*** 1 for small v > 0 ***/
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;   /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
    z = _PyLong_New(newsize);

    /*** ... ***/
}

您没有问到整数地板分割比右移更差的性能，因为这符合您（和我）的期望。但一个小正数除以另一个小正数也不如小乘法优化。每个//都使用函数long_divrem()计算商和余数。这个余数是为一个带乘法的小除数计算的，并存储在一个新分配的整数对象中，在这种情况下，该对象会被立即丢弃。