除非Haswell指明,否则GCC会很难编制前导零数
GCC支持__builtin_clz(int x)
builtin,它计算参数中前导零 (连续最重要的零)的数量。
除了0之外 ,这对于有效地实现lg(unsigned int x)
函数非常有用,它取lg(unsigned int x)
的基数为2的对数,向下舍入为1 :
/** return the base-2 log of x, where x > 0 */ unsigned lg(unsigned x) { return 31U - (unsigned)__builtin_clz(x); }
这是直截了当的方式 – 特别是考虑情况x == 1
和clz(x) == 31
– 然后x == 2^0
所以lg(x) == 0
和31 - 31 == 0
我们得到正确的结果。 较高的x
值类似地起作用。
假设内置程序有效实现,这比其他纯C解决方案更好。
现在,它发生了, 计数前导零操作本质上是x86中bsr
指令的双重。 返回参数中最重要的1位2的索引。 因此,如果有10个前导零,则第一个1位位于参数的第21位。 一般来说,我们有31 - clz(x) == bsr(x)
,所以bsr
实际上直接实现了我们想要的lg()
函数,没有多余的31U - ...
部分。
事实上,你可以在行之间读取并看到__builtin_clz
函数是用bsr
实现的:如果参数为零,它被定义为未定义的行为 ,当然“当前的零”操作被完美地定义为32 (或者int
任何位大小),带有零参数。 所以__builtin_clz
肯定是在有效映射到x86上的bsr
指令的想法下实现的。
然而,看看GCC实际上做了什么,在-O3
有其他默认选项:它增加了大量的额外垃圾 :
lg(unsigned int): bsr edi, edi mov eax, 31 xor edi, 31 sub eax, edi ret
xor edi,31
行实际上对于实际上重要的底部4位实际上not edi
,这是来自neg edi
的一个3 ,它将bsr
的结果转换为clz
。 然后执行31 - clz(x)
。
但是使用-mtune=haswell
, 代码可以简化为预期的单个bsr
指令:
lg(unsigned int): bsr eax, edi ret
为什么会这样,我不清楚。 bsr
指令在Haswell之前已经存在了几十年,并且AFAIK的行为没有改变。 这不仅仅是针对特定arch进行调优的问题,因为bsr
+一堆额外指令不会比普通bsr
更快,而且使用-mtune=haswell
仍会导致代码变慢。
64位输入和输出的情况甚至更糟糕 :在关键路径中有一个额外的movsx
似乎什么都不做,因为clz
的结果永远不会是负数。 同样, -march=haswell
变体对于单个bsr
指令是最佳的。
最后,让我们检查一下非Windows编译器空间中的大玩家icc
和clang
。 icc
只是做得不好,并添加了诸如neg eax; add eax, 31; neg eax; add eax, 31;
类的冗余内容neg eax; add eax, 31; neg eax; add eax, 31;
neg eax; add eax, 31; neg eax; add eax, 31;
– wtf? clang
做得很好,不管是什么。
0例如扫描第一个设置位的位图。
1 0的对数是未定义的 ,因此使用0参数调用我们的函数是未定义的行为 。
2这里,LSB是第0位,MSB是第31位。
3回想一下二进制补码中的-x == ~x + 1
。
这看起来像gcc的一个已知问题: https : //gcc.gnu.org/bugzilla/show_bug.cgi? id = 50168