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

我看着 有序的 _ 容器的来源，惊讶地发现 这条线:

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

这里的 load是一个整数。为什么在一个地方使用位移，而在另一个地方使用乘法？比特移位可能比积分除法快2，这似乎是合理的，但为什么不用移位来代替乘法呢？我以下列情况为基准:

  1. (时间，除)
  2. (移位，移位)
  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)])

enter image description here enter image description here

问题是:

我的测试有效吗? 如果有效，为什么(乘法，移位)比(移位，移位)快？

我在 Ubuntu 14.04上运行 Python 3.5。

剪辑

以上是这个问题的原始陈述，丹 · 盖茨在他的回答中给出了很好的解释。

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

enter image description here enter image description here

17780 次浏览
小开
最佳答案

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

因为 Python 中的整数是任意精度的，所以它们被存储为整数“位”数组，每个整数位的位数有限制。因此，在一般情况下，涉及整数的操作不是单个操作，而是需要处理多个“数字”的情况。在 皮波特中，这个位在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()计算商 还有和余数。对于具有 乘法和 存储在新分配的整数对象中的小除数，计算这个余数，在这种情况下会立即丢弃它们。


提交答案