对于Python 3.x整数,时间比比特移位快两倍？

Question

我正在查看sorted_containers的来源,并惊讶地看到这一行:

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

这load是一个整数.为什么在一个地方使用位移,在另一个地方使用乘法？似乎合理的是,位移可能比积分除以2更快,但为什么不用乘法替换乘法呢？我对以下案例进行了基准测试:

1. (次,分)
2. (轮班,轮班)
3. (次,班次)
4. (转移,分裂)

并发现#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)])

问题:

我的考试有效吗？如果是这样,为什么(乘,移)快于(移位,移位)？

我在Ubuntu 14.04上运行Python 3.5.

编辑

以上是问题的原始陈述.Dan Getz在他的回答中提供了一个很好的解释.

为了完整起见,下面是x乘法优化不适用时的示例说明.

Answer 1

这似乎是因为在CPython 3.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 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()调用正整数对象只需获取其第一个30位数字.)如果结果适合单个30位数字,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().该余数是针对带乘法的小除数计算的,并存储在新分配的整数对象中,在这种情况下立即丢弃.