GCC kompiliert die Zählung der führenden Nullen schlecht, sofern nicht Haswell angegeben wurde

Dies ist unter anderem ⁰ , um die Funktion lg(unsigned int x) effizient zu implementieren, die den Logarithmus zur Basis 2 von x , Abrundung ¹ , verwendet:

Das funktioniert auf einfache Art und Weise - bedenke insbesondere den Fall x == 1 und clz(x) == 31 - dann x == 2^0 so lg(x) == 0 und 31 - 31 == 0 und wir erhalten das korrekte Ergebnis. Höhere Werte von x funktionieren ähnlich.

Unter der Annahme, dass das Built-in effizient implementiert ist, endet es viel besser als die alternativen reinen C-Lösungen .

Nun ist die Operation führende Nullen zählen im Wesentlichen das Duale des bsr Anweisung in x86. Dies gibt den Index des höchstwertigen 1-Bit ² in dem Argument zurück. Wenn also 10 führende Nullen vorhanden sind, befindet sich das erste 1-Bit in Bit 21 des Arguments. Im Allgemeinen haben wir 31 - clz(x) == bsr(x) und in so bsr tatsächlich direkt implementiert unsere gewünschte lg() -Funktion, ohne den überflüssigen 31U - ... -Teil.

Tatsächlich können Sie zwischen der Zeile lesen und sehen, dass die Funktion __builtin_clz mit bsr implementiert wurde: Sie ist definiert als undefiniertes Verhalten , wenn das Argument Null ist, wenn of Natürlich ist die Operation "führende Nullen" perfekt als 32 (oder was auch immer die Bitgröße von int ist) mit einem Nullargument definiert. So wurde __builtin_clz sicherlich mit der Idee implementiert, effizient auf eine bsr Anweisung auf x86 abgebildet zu werden.

Betrachtet man jedoch, was GCC tatsächlich macht, bei -O3 mit anderen Standardoptionen: fügt eine Menge zusätzlichen Junk hinzu :

Die xor edi,31 -Zeile ist effektiv ein not edi für die unteren 4 Bits, die wirklich wichtig sind, das ist off-by-one ³ von neg edi , was das Ergebnis von bsr in verwandelt %Code%. Dann wird clz ausgeführt.

Jedoch mit 31 - clz(x) vereinfacht der Code genau die erwartete Anweisung -mtune=haswell :

Warum das der Fall ist, ist mir sehr unklar. Der Befehl bsr gibt es seit ein paar Jahrzehnten vor Haswell, und das Verhalten ist, AFAIK, unverändert. Es ist nicht nur ein Problem von tuning für einen bestimmten arch, da bsr + eine Menge zusätzlicher Anweisungen nicht schneller ist als eine einfache bsr und weiterhin bsr führt immer noch zu im langsameren Code.

Die Situation für 64-bit Ein- und Ausgaben ist sogar etwas schlechter : Es gibt ein Extra -mtune=haswell im kritischen Pfad, was nichts zu tun scheint, da das Ergebnis von movsx niemals negativ sein wird. Auch hier ist die clz Variante optimal mit einer einzelnen -march=haswell Anweisung.

Betrachten wir abschließend die großen Player im Nicht-Windows-Compiler-Bereich bsr und icc . clang macht nur einen schlechten Job und fügt redundantes Zeug wie icc - wtf hinzu? neg eax; add eax, 31; neg eax; add eax, 31; macht einen guten Job unabhängig von clang .

⁰ So wie das Scannen einer Bitmap für das erste gesetzte Bit.

¹ Der Logarithmus von 0 ist nicht definiert, und daher ist der Aufruf unserer Funktion mit einem 0-Argument undefiniertes Verhalten .

² Hier ist das LSB das 0. Bit und das MSB ist das 31. Bit.

³ Erinnern Sie sich, dass -march in Zweierkomplement.