两个整数的“min”与“bit hacking”一样快？
我正在观看关于“Bit Hacking”的系列讲座 ，并且发现了两个整数的最小值：
return x ^ ((y ^ x) & -(x > y)) 其中说比以前快：
if x < y: return x else: return y
由于min函数可以处理两个以上的整数（浮点数，string，列表，甚至自定义对象），所以我认为调用min(x, y)会花费比上面优化的位更长的时间。 令我惊讶的是，他们几乎完全相同：
>>> 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这样多function的function如何能够如此快速和优化呢？
注意：我使用Python 3.5运行上面的代码。 我假设这是相同的Python 2.7 +，但没有testing
我创build了以下的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机器，但是在执行时间方面，是不是应该把“bit hacking”卸载到本地c上呢？
让我们稍微深入一下，找出怪诞背后的真实原因（如果有的话）。
让我们创build3个方法，看看他们的python字节码和运行时间…
import dis def func1(x, y): return min(x, y) def func2(x, y): if x < y: return x return y def func3(x, y): return x ^ ((y ^ x) & -(x > y)) print "*" * 80 dis.dis(func1) print "*" * 80 dis.dis(func2) print "*" * 80 dis.dis(func3)
这个程序的输出是…
***************************************************** 4 0 LOAD_GLOBAL 0 (min) 3 LOAD_FAST 0 (x) 6 LOAD_FAST 1 (y) 9 CALL_FUNCTION 2 12 RETURN_VALUE ***************************************************** 7 0 LOAD_FAST 0 (x) 3 LOAD_FAST 1 (y) 6 COMPARE_OP 0 (<) 9 POP_JUMP_IF_FALSE 16 8 12 LOAD_FAST 0 (x) 15 RETURN_VALUE 9 >> 16 LOAD_FAST 1 (y) 19 RETURN_VALUE ***************************************************** 12 0 LOAD_FAST 0 (x) 3 LOAD_FAST 1 (y) 6 LOAD_FAST 0 (x) 9 BINARY_XOR 10 LOAD_FAST 0 (x) 13 LOAD_FAST 1 (y) 16 COMPARE_OP 4 (>) 19 UNARY_NEGATIVE 20 BINARY_AND 21 BINARY_XOR 22 RETURN_VALUE
以下是每个函数的运行时间
%timeit func1(4343,434234) 1000000 loops, best of 3: 282 ns per loop %timeit func2(23432, 3243424) 10000000 loops, best of 3: 137 ns per loop %timeit func3(928473, 943294) 1000000 loops, best of 3: 246 ns per loop
func2是最快的，因为它在python解释器中的工作量最less。 怎么样？。 看看func2的字节码，我们看到，无论是x > y还是x < y ，python解释器都会执行6条指令。
func3将执行11条指令（因此几乎是func2的两倍…实际上，它非常接近137.0 * 11/6 = 251 ns）。
func1只有5个python指令，通过之前2点的逻辑，我们可能会认为func1应该是最快的。 然而，在那里有一个CALL_FUNCTION …函数调用在Python中有很多开销（因为它为函数调用创build了一个新的eval框架 – 这是我们在python stacktrace中看到的 – 一堆eval框架）。
更多细节：因为python被解释，所以每个python字节码指令比单个C / asm语句花费的时间要长。 事实上，你可以看一下python解释器的源代码，看看每个指令的开销是30左右的C语句（这是从ceval.c python主解释器循环的粗略看）。 for (;;)循环每循环执行一条python指令（忽略优化）。
https://github.com/python/cpython/blob/master/Python/ceval.c#L1221
因此，每条指令都有很多开销，所以在python中比较2个微小的C代码片段没有任何意义。 一个将花费34个CPU，另一个将花费32个CPU周期，因为python解释器为每条指令增加了30个周期开销。
在OP的C模块中，如果我们在C函数内部循环执行一百万次比较，那么这个循环就不会有python解释器对每条指令的开销。 它可能会快30到40倍。
python优化技巧
对代码进行剖析以查找热点，将热代码重构为自己的函数（在此之前写入热点testing以确保重构不会破坏内容），避免来自热代码的函数调用（如果可能的话，内联函数），使用dis模块find方法来减lesspython指令的数量（ if x比if x is True …惊讶吗？），最后修改你的algorithm。 最后，如果python加速不够，请在C中重新实现你的新函数
ps：上面的解释被简化，以保持答案在合理的大小。 例如，并不是所有的python指令都花费相同的时间，并且有优化，所以不是每个指令都有相同的开销…而且有更多的东西。 为简洁起见，请忽略此类疏忽。
这可能是由于如何在Python中实现min函数。
许多python内build实际上是在低级语言（如C或汇编）中实现的，并使用python apis以便在python中调用。
在C语言中，你的技巧可能非常快，但是在Python中，语句的解释开销将远远超过调用低级语言实现的复杂函数的开销。
如果你真的想要一个公平的testing比较一个C程序或实现该技术的C python扩展到你的python调用min ，看看它如何比较，我期望这将解释你看到的结果。
编辑：
感谢@ Two-BitAlchemist我现在可以给一些更多的细节，这个位twiddling在python中不能很好地工作。 看起来整数不是以显而易见的方式存储的，而是实际上是一个相当复杂的扩展对象，用来存储潜在的非常大的数字。
在这里有一些细节可以在这里find （感谢Two-BitAlchemist），虽然它在较新的Python版本中有所改变。 仍然要指出的是，当我们触摸python中的一个整数时，我们当然不会操纵一组简单的位，而是一个复杂的对象，其中的位操作实际上是虚拟方法调用，而且开销巨大（与他们所做的相比）。
那么，90年代有点诡计的速度可能会更快，但是现在的机器速度要慢两倍。 比较你自己：
// gcc -Wall -Wextra -std=c11 ./min.c -D_POSIX_SOURCE -Os // ./a.out 42 #include <stdio.h> #include <stdlib.h> #include <time.h> #define COUNT (1 << 28) static int array[COUNT]; int main(int argc, char **argv) { (void) argc; unsigned seed = atoi(argv[1]); for (unsigned i = 0; i < COUNT; ++i) { array[i] = rand_r(&seed); } clock_t begin = clock(); int x = array[0]; for (unsigned i = 1; i < COUNT; ++i) { int y = array[i]; #if 1 x = x ^ ((y ^ x) & -(x > y)); # else if (y < x) { x = y; } #endif } clock_t end = clock(); double time_spent = (double)(end - begin) / CLOCKS_PER_SEC; printf("Minimum: %d (%.3f seconds)\n", x, time_spent); return 0; }
“naïve”实现平均为0.277秒，而“优化”实现为0.442秒。 在CS课程中总是有一丝怀疑。 至less从CMOVxx指令（在1995年joinPentium Pro之后），这个黑客攻击解决scheme就不可能有更快的速度。
在一个i5-750（海湾合作委员会（Debian 5.2.1-23）5.2.1 20151028）：
optimized naïve O0 1.367 0.781 O1 0.530 0.274 O2 0.444 0.271 O3 0.442 0.144 Os 0.446 0.273
事后思考：编译器开发人员是非常聪明的人，他们在工作日中查找和实现优化。 如果这个黑客技巧比较快，那么你的编译器会以这种方式实现min() 。 而且你可以放心的假设编译器能够理解你在循环中做了什么。 但是在英特尔，AMD等公司工作的人也很聪明，所以如果他们发现编译器黑客做了一些奇怪的黑客行为，他们会优化min()和max()等重要的操作。
对于好奇：这是用-O3“优化”实现生成的代码：
mov $0x40600b00, %ebp # int *e = &array[COUNT]; mov 0x600b00, %ebx # int x = array[0]; mov $0x600b04, %edx # int *i = &array[1]; loop: mov (%rdx), %eax # int y = *i; xor %ecx, %ecx # int tmp = ( cmp %ebx, %eax # y < x setl %cl # ? 1 : 0 ); xor %ebx, %eax # y ^= x; add $0x4, %rdx # ++i; neg %ecx # tmp = -tmp; and %ecx, %eax # y &= tmp; xor %eax, %ebx # x ^= y; cmp %rdx, %rbp # if (i != e) { jne loop # goto loop; }
和-Os（-O3的天真实施是巨大的，充满了我不得不查看SSE指令）：
mov 600ac0, %ebx # int x = array[0]; mov $0x40600abc,%ecx # int *e = &array[COUNT]; mov $0x600ac0,%eax # int *i = &array[0]; loop: mov 0x4(%rax),%edx # int y = *(i + 1); cmp %edx,%ebx # if (x > y) { cmovg %edx,%ebx # x = y; } add $0x4,%rax # ++i; cmp %rcx,%rax # if (i != e) { jne loop # goto loop; }
前几天我在这里做了这样的事情。 接下来是更为明显的例子，其中跳跃 （预测不佳）是杀人行为。
Steinalgorithm中的每个操作都非常简单：testing最低有效位，向右移位一位，增加一个
int。 但分支是一个杀手！采用现代超标量高度stream水线处理内核，一个条件分支打破了stream水线。 x86处理器使用分支预测和推测执行来缓解这个问题，但是这里的分支决策在每次迭代中基本上是随机的。 它一半的时间猜测错误。
＆vellip;
但我还剩下一个窍门
if (n>m) std::swap (n, m);是一个分支点，循环会多次采用其中一种方式。 也就是说，这是另一个“坏”的分支。
使用非分支位操作replace条件分支（在后面解释;比OP更清晰的例子）确实导致代码的可测量的加速。 这是另一个答案所不同的结果，所以我的“现代”forms可能会更好地工作，这不仅仅是一个分钟，而是同时需要最小和最大，所以即使在常规实施中也需要更多的任务。
结果表明，所有这些math和注册使用比分支便宜：44变成39或37，84变成75.这是整体algorithm加快了大约11％ 。
以下是Python 2.7中的一些时间（因为我错了，我很抱歉）：
def mymin(x, y): if x < y: return x return y
10000000 loops, best of 3: 0.0897 usec per loop
def mymin(x, y): return y
10000000 loops, best of 3: 0.0738 usec per loop
mymin = min
10000000 loops, best of 3: 0.11 usec per loop
mymin = operator.add
10000000 loops, best of 3: 0.0657 usec per loop
这是什么意思？ 这意味着几乎所有的成本都在调用函数。 CPython最快的实际速度是每个循环0.066个usec，这样add实现。
C中的min函数将会有
-
less开销，因为它不处理任意的参数和
cmp，但是 -
更多的开销，因为它会产生一个新的整数，而不是只是返回旧的。
PyArg_ParseTuple可能也不快。
实际的C指令比较或位移实际上没有任何成本。 他们是免费的。 阿姆达尔的法律正在嘲笑你。
同时，PyPy每min大约需要0.0003次使用，或者less了200倍的时间。 显然C指令至less是便宜的，因为它们编译成好的机器码。
也许我会换另一种方式
什么比分支或比较更昂贵？
-
分配，Python分配函数的框架和分配元组来存储参数。
-
stringparsing，即
PyArg_ParseTuple。 -
可变参数，也被
PyArg_ParseTuple。 -
表查找，
PyLong_FromLong执行。 -
由CPython的内部字节码调度执行的计算转换（我相信2.7使用
switch语句，它甚至更慢）。
用C实现的min的主体不是问题。
标杆pipe理和科学一样是一门艺术。 除了各种语言及其内部实现的技术细节之外，在一个例子中，要测量的语句在函数调用中调用一次，而在另一个例子中有一个数组引用的for循环中。
函数调用和数组引用的开销大大超过了您要testing的函数的时间。 想象一下，每个指令需要几十条指令。 在循环/函数调用中，您正在尝试测量几条指令的速度！
C示例要好得多，因为它比Python示例的开销less得多，并且它被编译并仔细分析了机器代码。 您可以推测机器码的速度，但是要真正衡量它，您需要一个更复杂的基准testing，以最大限度地实现您要testing的代码的执行，并最大限度地减less其他指令。 各种编译器优化也可能会扭曲你的计时，甚至优化你想要测量的部分。
以C为例，对于每次迭代，循环开销是4条指令，而您要testing的是1或2条指令的速度，具体取决于值。 这很难做到！
更不用说，你正在使用经过的时间作为一个度量，甚至在一个“空闲”的系统有大量的随机中断，页面错误和其他活动扭曲的时间。 你有一个巨大的arrays，可以是错误的。一个操作可能会更快的CISC机器，而不是RISC机器，虽然在这里我假设你正在谈论x86类机器。
我知道这并不能回答这个问题，而更多的是分析了所使用的基准testing方法，以及它们如何影响获得真正可量化的答案。
你测量的方式是有缺陷的。
timeit使用真的很复杂。 当你在命令行上写下这些内容时：
$ python -m timeit "min(4, 5)" 10000000 loops, best of 3: 0.143 usec per loop
python会很乐意告诉你，每个循环花了0.143次。
$python -m timeit "any([0,3])" 10000000 loops, best of 3: 0.157 usec per loop
嗯，怪异的，非常类似的运行时间。
Ipython会揭示一些：
In [3]: %timeit any([0,3]) The slowest run took 17.13 times longer than the fastest. This could mean that an intermediate result is being cached 10000000 loops, best of 3: 167 ns per loop
啊东西正在被caching。
In [1]: %timeit min(4,5) The slowest run took 18.31 times longer than the fastest. This could mean that an intermediate result is being cached 10000000 loops, best of 3: 156 ns per loop In [4]: %timeit 4 ^ ((5 ^ 4) & -(4 > 5)) The slowest run took 19.02 times longer than the fastest. This could mean that an intermediate result is being cached 10000000 loops, best of 3: 100 ns per loop
我尝试了很多东西，但是我无法摆脱caching。 我不知道如何正确测量这个代码。
