我正在观看一个关于"位黑客"的系列讲座，并遇到了以下优化，以找到两个整数的最小值：
return x ^ ((y ^ x) & -(x > y))
据说比：
if x < y:
return x
else:
return y
由于 min 函数可以处理的不仅仅是两个整数(浮点数、字符串、列表甚至自定义对象(，因此我认为调用min(x, y)将比上面优化的位 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
虽然我知道这是一台虚拟机机器，但随着"位黑客攻击"被卸载到本机 c 中，执行时间不应该还有更大的差距吗？
由于min函数在python中的实现方式。
许多 python 内置函数实际上是用低级语言(如 C 或汇编(实现的，并使用 python API 以便在 python 中可调用。
你的位摆弄技术在 C 中可能非常快，但在 python 中，语句的解释开销将远远超过调用用低级语言实现的复杂函数的开销。
如果你真的想要一个公平的测试，将一个C程序，或者实现该技术的C python扩展与你的python min调用进行比较，看看它是如何比较的，我希望这将解释你看到的结果。
编辑：
多亏了@Two BitAlchemist，我现在可以提供更多细节，说明这个位twidding在python中不能很好地工作的其他原因。看起来整数不是以明显的方式存储的，而实际上是一个相当复杂的扩展对象，旨在存储潜在的非常大的数字。
可以在这里找到一些细节(感谢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;
}
在"朴素"实现中平均为 0.277 秒，但在"优化"实现中平均为 0.442 秒。在CS课上总是有一点怀疑。至少自CMOVxx指令(1995年随奔腾Pro一起添加(以来，位黑客解决方案不可能更快。
在 i5-750 (gcc (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; }
让我们在这里做一个更深入的探讨，找出这种怪异背后的真正原因(如果有的话(。
让我们创建 3 个方法并查看它们的 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 解释器中要做的工作量最少。如何？。查看 func2 的字节码，我们看到在 x > y 或 x < y 的情况下，python 解释器将执行 6 条指令。
func3 将执行 11 条指令(因此几乎是 func2 的两倍...实际上，它非常接近137.0 * 11/6 = 251 ns(。
func1只有 5 条 python 指令，根据前 2 点的逻辑，我们可能会认为 func1 应该是最快的。但是，那里有一个CALL_FUNCTION...函数调用在 Python 中有很多开销(因为它为函数调用创建了一个新的 eval 帧 - 这是我们在 Python 堆栈跟踪中看到的东西 - 一堆评估帧(。
更多细节：因为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 个周期，另一个需要 32 个 cpu 周期，因为 python 解释器为每个指令增加了 30 个周期的开销。
在 OP 的 C 模块中，如果我们在 C 函数内部循环以进行比较一百万次，则该循环将不会有每条指令的 python 解释器的开销。它的运行速度可能会快 30 到 40 倍。
蟒蛇优化的提示...
分析你的代码以查找热点，将热代码重构为它自己的函数(在此之前为热点编写测试以确保重构不会破坏东西(，避免从热代码调用函数(如果可能的话是内联函数(，使用新函数上的dis模块来找到减少 python 指令数量的方法(if x比if x is True更快......惊讶？(，最后修改你的算法。最后，如果 python 加速还不够，请在 C 中重新实现您的新函数。
ps ：上面的解释经过简化，以使答案保持在合理的大小范围内。例如，并非所有 python 指令都需要相同的时间，并且有优化，因此并非每个指令都有相同的开销......等等。为简洁起见，请忽略此类遗漏。
前我在这里做了这样的事情。紧随其后的是更明显的例子，其中跳跃(预测不佳(正在扼杀性能。
[在斯坦算法中]的每个操作都非常简单：测试最低有效位，右移一位，递增一个
int。 但树枝是杀手锏！使用现代超标量高度流水线处理核心，条件分支会中断流水线。 x86 处理器使用分支预测和推测执行来缓解这种情况，但这里的分支决策在每次迭代中基本上是随机的。 它有一半时间猜错了。
和维利普;
但我还有一个技巧。
if (n>m) std::swap (n, m);是一个分支点，在循环时会多次采用一种或另一种方式。 也就是说，这是另一个"坏"分支。
用非分支位操作替换条件分支(在帖子中解释;比OP更清晰的示例(确实导致了代码的可测量加速。 这是一个与另一个答案不同的结果，所以我的"现代"形式可能会更好用，它不仅仅是一个最小值，而是同时需要最小值和最大值，因此即使在常规实现中也需要更多赋值。
结果表明，所有这些数学和寄存器的使用都比分支便宜：44 变为 39 或 37,84 变为 75。 这大约是整个算法中 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 微塞，这是add实现的。
你在 C 中的min函数将具有
开销更少，因为它不处理任意参数和
cmp，但是更多的开销，因为它生成一个新整数，而不仅仅是返回旧整数。
PyArg_ParseTuple可能也不快。
实际的C指令用于比较或位移位实际上没有任何成本。他们是免费的。阿姆达尔定律在嘲笑你。
同时，PyPy 每次调用大约需要 0.0003 usec 来min，或减少 200 倍的时间。显然，C 指令至少是那么便宜，因为它们可以编译成好的机器代码。
也许我会换一种说法...
有什么比分支或比较更贵的？
分配，Python 用于分配函数的框架并分配元组以存储参数。
字符串分析，
PyArg_ParseTuple这样做。varargs，也被
PyArg_ParseTuple使用。表查找，
PyLong_FromLong执行。计算
gotos，由 CPython 的内部字节码调度执行(我相信 2.7 使用switch语句，这甚至更慢(。
用 C 实现的 min 主体不是问题所在。
基准测试既是一门艺术，也是一门科学。撇开各种语言及其内部实现的技术细节不谈，在一个示例中，要测量的语句在函数调用中调用一次，在另一个示例中，如果有数组引用，则在 for 循环中调用一次。
函数调用以及数组引用和循环的开销大大超过了您尝试测量的函数的时间。想象一下每个指令所需的数十条指令。在该循环/函数调用中，您正在尝试测量几条指令的速度！
C 示例要好得多，因为它比 Python 示例的开销少得多，并且经过编译并仔细分析了机器代码。您可以推测该机器代码的速度，但要实际测量它，您需要一个更复杂的基准，以最大限度地提高您尝试测试的代码的执行并最小化其他指令。各种编译器优化也会扭曲您的时序，甚至优化您认为要测量的部分内容！
以 C 为例，对于每次迭代，循环开销为 4 条指令，您尝试测量的是 1 或 2 条指令的速度，具体取决于值。这很难做到！
更不用说您使用经过的时间作为度量，即使在"空闲"系统上，也有很多随机中断、页面错误和其他活动来扭曲计时。你有一个巨大的阵列，可能会出错。在CISC机器上，一个操作可能比RISC机器更快，尽管在这里我假设你说的是x86类机器。
我知道这并不能回答这个问题，它更多的是对所使用的基准测试方法的分析，以及它们如何影响获得真正可量化的答案。
你的测量方式是有缺陷的。
timeit使用起来非常复杂。当你在命令行上写这个时：
$ python -m timeit "min(4, 5)"
10000000 loops, best of 3: 0.143 usec per loop
Python 会很高兴地告诉你，每个循环需要 0.143 个 usec。
$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
啊东西正在缓存。
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
我尝试了很多东西，但我无法摆脱缓存。我不知道如何正确测量此代码。