Leistung von vorzeichenlosen vs. vorzeichenbehafteten Ganzzahlen

Gibt es einen Leistungsgewinn/-verlust durch die Verwendung von vorzeichenlosen Ganzzahlen gegenüber vorzeichenbehafteten Ganzzahlen?

Wenn ja, gilt das auch für kurz und lang?

Division durch Potenzen von 2 ist schneller mit unsigned int, weil es in eine einzelne Verschiebungsanweisung optimiert werden kann. Mit signed int, erfordert es normalerweise mehr Maschinenbefehle, weil die Division rundet gegen null, aber Verschiebung nach rechts rundet Nieder. Beispiel:

int foo(int x, unsigned y)
{
    x /= 8;
    y /= 8;
    return x + y;
}

Hier ist das Relevante x Teil (signierte Teilung):

movl 8(%ebp), %eax
leal 7(%eax), %edx
testl %eax, %eax
cmovs %edx, %eax
sarl $3, %eax

Und hier ist das Relevante y Teil (Teilung ohne Vorzeichen):

movl 12(%ebp), %edx
shrl $3, %edx

In C++ (und C) ist der Überlauf von vorzeichenbehafteten Ganzzahlen undefiniert, während der Überlauf von vorzeichenlosen Ganzzahlen so definiert ist, dass er herumläuft. Beachten Sie, dass Sie z. B. in gcc das Flag -fwrapv verwenden können, um einen signierten Überlauf zu definieren (zum Umbrechen).

Undefinierter vorzeichenbehafteter Ganzzahlüberlauf lässt den Compiler davon ausgehen, dass keine Überläufe auftreten, was zu Optimierungsmöglichkeiten führen kann. Siehe zB diesen Blogbeitrag zur Diskussion.

unsigned führt zu gleicher oder besserer Leistung als signed. Einige Beispiele:

• Division durch eine Konstante, die eine Potenz von 2 ist (siehe auch die Antwort von FredÜberlauf)
• Division durch eine konstante Zahl (z. B. implementiert mein Compiler die Division durch 13 mit 2 asm-Anweisungen für unsigned und 6 Anweisungen für signed)
• Prüfen, ob eine Zahl gerade ist (ich habe keine Ahnung, warum mein MS Visual Studio-Compiler sie mit 4 Anweisungen für implementiert signed Zahlen; gcc macht es mit 1 Anweisung, genau wie in der unsigned Fall)

short führt in der Regel zu gleicher oder schlechterer Leistung als int (vorausgesetzt sizeof(short) < sizeof(int)). Leistungseinbußen treten auf, wenn Sie ein Ergebnis einer arithmetischen Operation zuweisen (was normalerweise int, noch nie short) zu einer Variablen vom Typ short, das im Register des Prozessors gespeichert ist (ebenfalls vom Typ int). Alle Konvertierungen von short zu int dauern und sind nervig.

Hinweis: Einige DSPs haben schnelle Multiplikationsanweisungen für die signed short Typ; in diesem speziellen Fall short ist schneller als int.

Was den Unterschied zwischen int und long, kann ich nur vermuten (ich bin mit 64-Bit-Architekturen nicht vertraut). Natürlich, wenn int und long dieselbe Größe haben (auf 32-Bit-Plattformen), ist auch ihre Leistung dieselbe.

Eine sehr wichtige Ergänzung, auf die von mehreren Personen hingewiesen wurde:

Was für die meisten Anwendungen wirklich zählt, ist der Speicherbedarf und die genutzte Bandbreite. Sie sollten die kleinsten notwendigen ganzen Zahlen verwenden (short, vielleicht sogar signed/unsigned char) für große Arrays.

Dies führt zu einer besseren Leistung, aber der Gewinn ist nicht linear (dh nicht um den Faktor 2 oder 4) und etwas unvorhersehbar – er hängt von der Cache-Größe und der Beziehung zwischen Berechnungen und Speicherübertragungen in Ihrer Anwendung ab.

Dies hängt von der genauen Implementierung ab. In den meisten Fällen wird es jedoch keinen Unterschied geben. Wenn es Ihnen wirklich wichtig ist, müssen Sie alle Varianten ausprobieren, die Sie in Betracht ziehen, und die Leistung messen.

Dies ist ziemlich stark vom jeweiligen Prozessor abhängig.

Auf den meisten Prozessoren gibt es Anweisungen sowohl für vorzeichenbehaftete als auch für vorzeichenlose Arithmetik, daher hängt der Unterschied zwischen der Verwendung von vorzeichenbehafteten und vorzeichenlosen Ganzzahlen davon ab, welche der Compiler verwendet.

Wenn eines der beiden schneller ist, ist es völlig prozessorspezifisch, und höchstwahrscheinlich ist der Unterschied winzig, wenn er überhaupt existiert.

Der Leistungsunterschied zwischen vorzeichenbehafteten und vorzeichenlosen Ganzzahlen ist tatsächlich allgemeiner als die Akzeptanzantwort vermuten lässt. Die Division einer vorzeichenlosen Ganzzahl durch eine beliebige Konstante kann schneller durchgeführt werden als die Division einer vorzeichenbehafteten Ganzzahl durch eine Konstante, unabhängig davon, ob die Konstante eine Zweierpotenz ist. Sehen http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

Am Ende seines Beitrags fügt er den folgenden Abschnitt ein:

Eine natürliche Frage ist, ob die gleiche Optimierung die vorzeichenbehaftete Division verbessern könnte; Leider scheint dies aus zwei Gründen nicht der Fall zu sein:

Die Erhöhung des Dividenden muss zu einer Erhöhung der Größe werden, dh Erhöhung, wenn n > 0, Verringerung, wenn n < 0. Dies führt zu einem zusätzlichen Aufwand.

Die Strafe für einen unkooperativen Divisor ist bei einer vorzeichenbehafteten Division nur etwa halb so hoch, wodurch ein kleineres Fenster für Verbesserungen bleibt.

Somit scheint es, dass der Abrundungsalgorithmus dazu gebracht werden könnte, in einer vorzeichenbehafteten Division zu arbeiten, aber der Standard-Aufrundungsalgorithmus unterlegen sein wird.

Nicht nur die Division durch Potenzen von 2 ist mit unsigned Type schneller, auch die Division durch alle anderen Werte ist mit unsigned Type schneller. Wenn Sie sich ansehen Agner Fogs Anleitungstabellen Sie werden sehen, dass nicht signierte Divisionen eine ähnliche oder bessere Leistung als signierte Versionen aufweisen

Zum Beispiel mit dem AMD K7

Dasselbe gilt für Intel Pentium

Natürlich sind die ziemlich alt. Neuere Architekturen mit mehr Transistoren könnten die Lücke schließen, aber die grundlegenden Dinge gelten: Im Allgemeinen benötigen Sie mehr Mikrooperationen, mehr Logik und mehr Latenz, um eine vorzeichenbehaftete Division durchzuführen