C++ unterzeichnet und unsigned int vs long long Geschwindigkeit

Question

Heute, bemerkte ich, dass die Geschwindigkeit von mehreren einfachen bitweise und arithmetischen Operationen signifikant zwischen int, unsigned, long long und unsigned long long auf meinem 64-Bit-PC unterscheidet.

Insbesondere ist die folgende Schleife etwa doppelt so schnell für unsigned wie für long long, was ich nicht erwartet habe.

int k = 15; 
int N = 30; 
int mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    int lo = mask & ~(mask - 1); 
    int lz = (mask + lo) & ~mask; 
    mask |= lz; 
    mask &= ~(lz - 1); 
    mask |= (lz/lo/2) - 1; 
} 

(vollständiger Code here)

Hier sind die Zeiten (in Sekunden) (für g++ -O, -O2 und -O3):

1.834207723 (int) 
3.054731598 (long long) 
1.584846237 (unsigned) 
2.201142018 (unsigned long long) 

Diese Zeiten sind sehr konstant (dh 1% Spanne). Ohne -O Flag, jeder ist etwa eine Sekunde langsamer, aber die relativen Geschwindigkeiten sind die gleichen.

Gibt es einen klaren Grund dafür? Vektorisierung könnte es für die 32-Bit-Typen sein, aber ich kann nicht sehen, wo der große Unterschied zwischen long long und unsigned long long herkommt. Sind einige Operationen bei einigen Typen nur sehr viel langsamer als bei anderen, oder ist es nur eine allgemeine Sache, dass 64-Bit-Typen langsamer sind (sogar bei 64-Bit-Architekturen)?

Für alle Interessierten schleift diese Schleife alle Untermengen von {1,2,...,30} mit genau 15 Elementen. Dies geschieht durch Schleifen (in der Reihenfolge) über alle ganzen Zahlen kleiner als 1<<30 mit genau 15 gesetzten Bits. Für den aktuellen Fall ist das 155117520 Iterationen. Ich kenne die Quelle dieses Snippets nicht mehr, aber this Post erklärt etwas mehr.

bearbeiten

Es scheint aus dem Assembler-Code, der die Division schneller gemacht werden kann, wenn der Typ nicht signiert ist. Ich denke, das macht Sinn, weil wir das Vorzeichen nicht berücksichtigen müssen.

Darüber hinaus sind die 32-Bit-Operationen verwenden movl und andere xxxl Anweisungen, während die 64-Bit-Operationen und movqxxxq verwenden.

Edit 2

Nach dem Lesen der Post I verbunden ist, habe ich beschlossen, die Formel dort gegeben zu verwenden:

T k = 15; 
T N = 30; 
T mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    T t = mask | (mask - 1); 
    mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1)); 
} 

Dies ein Drittel der Zeit des Codes in etwa läuft oben gepostet, und verwendet die gleiche Zeit für alle vier Typen.

Answer 1

Der langsamste Betrieb in Ihrem Code ist

mask |= (lz/lo/2) - 1 

32-Bit-Division deutlich schneller als die Abteilung 64-Bit ist. Bei Ivy Bridge zum Beispiel dauert 32 Bit IDIV 19-26 Takte, während 64 Bit IDIV 28-103 Takten Latenzzeit benötigt.

Die unsignierte Version ist auch schneller als signiert, da die Division durch 2 im unsignierten Fall eine einfache Bitverschiebung ist und keine Größenerweiterungsanrufe (CDQ, CQO) vorhanden sind.

im unsigned Fall ist einfach Bitverschiebung während in signierten

[1] http://www.agner.org/optimize/instruction_tables.pdf