python - 两个整数的 `min` 如何与 'bit hacking' 一样快？

Question

我正在观看“Bit Hacking”上的 lecture series，并发现了以下用于查找两个整数的最小值的优化:

return x ^ ((y ^ x) & -(x > y))

据说比:

if x < y:
    return x
else:
    return y

由于 min 函数不仅可以处理两个整数( float 、字符串、列表，甚至自定义对象)，我假设调用 min(x, y)会比上面优化的 bit hack 花费更长的时间。令我惊讶的是，它们几乎完全相同:

>>> python -m timeit "min(4, 5)"
1000000 loops, best of 3: 0.203 usec per loop

>>> python -m timeit "4 ^ ((5 ^ 4) & -(4 > 5))"
10000000 loops, best of 3: 0.19 usec per loop

即使对于大于 255 的数字也是如此(预分配的 Python 整数对象)

>>> python -m timeit "min(15456, 54657)"
10000000 loops, best of 3: 0.191 usec per loop

python -m timeit "15456 ^ ((54657 ^ 15456) & -(54657 > 15456))"
10000000 loops, best of 3: 0.18 usec per loop

像 min 这样用途广泛的函数为何还能如此快速和优化？

^{注意:我使用 Python 3.5 运行上述代码。我假设这与 Python 2.7+ 相同，但尚未测试}

---

我创建了以下 c 模块:

#include <Python.h>

static PyObject * my_min(PyObject *self, PyObject *args){
    const long x;
    const long y;

    if (!PyArg_ParseTuple(args, "ll", &x, &y))
        return NULL;

    return PyLong_FromLong(x ^ ((y ^ x) & -(x > y)));
}

static PyMethodDef MyMinMethods[] = 
{
    { "my_min", my_min, METH_VARARGS, "bit hack min"
    },
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initmymin(void)
{
    PyObject *m;

    m = Py_InitModule("mymin", MyMinMethods);
    if (m == NULL)
        return;

}

编译它，并将其安装到我的系统(ubuntu VM 机器)上。然后我运行了以下内容:

>>> python -m timeit 'min(4, 5)'
10000000 loops, best of 3: 0.11 usec per loop

>>> python -m timeit -s 'import mymin' 'mymin.my_min(4,5)'
10000000 loops, best of 3: 0.129 usec per loop

虽然我知道这是一台 VM 机器，但在将“位黑客”卸载到 native c 时，执行时间不应该还有更大的差距吗？

Answer 1

这可能是由于 min 函数在 python 中是如何实现的。

许多 python 内置函数实际上是用 C 或汇编等低级语言实现的，并使用 python api 以便在 python 中可调用。

在 C 中，您的位摆弄技术可能非常快，但在 python 中，语句的解释开销将远远超过调用甚至以低级语言实现的复杂函数的开销。

如果您真的想要一个公平的测试，将 C 程序或实现该技术的 C python 扩展与您的 min 的 python 调用进行比较并查看它的比较，我希望这将解释您看到的结果.

编辑:

感谢@Two-BitAlchemist，我现在可以提供更多详细信息，说明这个位旋转在 python 中无法正常工作的其他原因。看起来整数并没有以明显的方式存储，但实际上是一个相当复杂的扩展对象，旨在存储可能非常大的数字。

可以找到一些关于此的详细信息 here (感谢 Two-BitAlchemist)虽然看起来这在较新的 python 版本中有所改变。仍然有一点是，当我们在 python 中触摸整数时，我们肯定不是在操作一组简单的位，而是在一个复杂的对象中，位操作实际上是具有巨大开销的虚拟方法调用(与它们所做的相比)。