我正在观看关于"Bit Hacking"的系列讲座,并且遇到了以下优化,以找到最少的两个整数:
return x ^ ((y ^ x) & -(x > y))
据说速度比:
if x < y:
return x
else:
return y
由于该min函数可以处理的不仅仅是两个整数(浮点数,字符串,列表甚至自定义对象),我认为调用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仍然如此快速和优化？
注意:我使用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机器,但是当"黑客攻击"被卸载到本机c时,不应该在执行时间方面存在更大的差距吗？
Val*_*ity 33
这可能是由于min函数在python中的实现方式.
许多python内置实际上是用低级语言(如C或汇编语言)实现的,并使用python apis以便在python中可调用.
你的比特摆弄技术在C语言中可能非常快,但在python中,语句的解释开销将远远超过调用低级语言中实现的复杂函数的开销.
如果你真的想要一个公平的测试比较一个C程序,或实现该技术的C python扩展到你的python调用min并看看它如何比较,我希望这将解释你看到的结果.
编辑:
感谢@ Two-BitAlchemist,我现在可以提供一些更多的细节,其中包含这个有点麻烦的其他原因在python中不能正常工作.似乎整数不是以明显的方式存储,而是实际上是一个相当复杂的扩展对象,旨在存储可能非常大的数字.
关于这方面的一些细节可以在这里找到(感谢Two-BitAlchemist)虽然看起来这在新的python版本中有所改变.还有一点是,当我们触摸python中的整数时,我们肯定不会操纵一个简单的位集,而是一个复杂的对象,其中位操作实际上是虚拟方法调用,具有巨大的开销(与他们的工作相比).
kay*_*kay 23
好吧,在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年添加Pentium 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; }
Jug*_*Jug 14
让我们稍微深入一点,找出这种奇怪背后的真正原因(如果有的话).
让我们创建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指令,并且通过前两个点的逻辑,我们可能认为func1应该是最快的.但是,有一个CALL_FUNCTION......并且函数调用在Python中有很多开销(因为它为函数调用创建了一个新的eval框架 - 这就是我们在python stacktrace中看到的东西 - 一堆eval框架) .
更多细节:因为解释了python,每个python字节码指令比单个C/asm语句花费更长的时间.实际上,您可以查看python解释器源代码,看看每条指令的开销大约是30个C语句(这是从ceval.c python主解释器循环的粗略看看).的for (;;)循环执行每个循环周期(忽略优化)一个蟒指令.
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倍.
python优化提示......
分析你的代码以找到热点,将热代码重构为自己的函数(在此之前编写热点测试以确保重构不会破坏东西),避免热代码的函数调用(如果可能的话,内联函数),dis在新的模块上使用模块函数找到减少python指令数量的方法(if x比if x is True...... 更快？),最后修改你的算法.最后,如果python加速不够,请在C中重新实现新函数.
ps:上面的解释被简化,以使答案保持在合理的大小范围内.例如,并非所有python指令都花费相同的时间,并且存在优化,因此并非每条指令都具有相同的开销......还有更多的东西.为简洁起见,请忽略此类遗漏.