对于 Python 3.x 整数，比位移快两倍？

Question

我正在查看sorted_containers and was surprised to see this line的来源：

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

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

（次，除）
（班次，班次）
（时间，班次）
（移位，除法）

并发现 #3 始终比其他替代方案更快：

# 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)])

问题：

我的测试有效吗？如果是这样，为什么 (multiply, shift) 比 (shift, shift) 快？

我运行 Python 3.5 在 Ubuntu 14.04.

编辑

以上为问题原文。 Dan Getz 在他的回答中提供了很好的解释。

为了完整起见，这里是较大 x 乘法优化不适用时的示例插图。

Answer 1

这似乎是因为小数的乘法在 CPython 3.5 中得到了优化，而小数的左移则没有。作为计算的一部分，正向左移总是创建一个更大的整数对象来存储结果，而对于您在测试中使用的那种乘法，一种特殊的优化避免了这种情况并创建了一个正确大小的整数对象。这可以在 the source code of Python's integer implementation.

中看到

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

当操作的输入和输出保持在此 30 位限制内时，可以以优化方式而不是一般方式处理操作。 integer multiplication implementation的开头如下：

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 digits, 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
    }

因此，当两个整数相乘时，每个整数都适合 30 位数字，这是由 CPython 解释器直接乘法完成的，而不是将整数作为数组处理。 (MEDIUM_VALUE() called on a positive integer object simply gets its first 30-bit digit.) If the result fits in a single 30-bit digit, PyLong_FromLongLong()会在比较少的操作中注意到这一点，并创建一个个位数的整数对象来存储它。

相比之下，左移并没有这样优化，每次左移都是将整数作为数组进行移位处理。特别是，如果您查看 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(). This remainder is computed for a small divisor with a multiplication, and is stored in a newly-allocated integer object 计算商和余数，在这种情况下它会立即被丢弃。

对于 Python 3.x 整数，比位移快两倍？

Times-two faster than bit-shift, for Python 3.x integers?

python

performance

bit-shift

python-3.x

integer-arithmetic

整数除法