Was ist der Leistungsunterschied zwischen vorzeichenlosen und vorzeichenbehafteten ganzen Zahlen? [geschlossen]

42

Ich bin mir des Leistungseinbruchs bewusst, wenn ich signierte Ints mit Floats mische.

Ist es schlimmer, nicht signierte Ints mit Floats zu mischen?

Gibt es einen Treffer beim Mischen von signierten / nicht signierten ohne Floats?

Haben die verschiedenen Größen (u32, u16, u8, i32, i16, i8) einen Einfluss auf die Leistung? Auf welchen Plattformen?

Luis
quelle
2
Ich habe den PS3-spezifischen Text / Tag entfernt, da dies eine gute Frage zu jeder Architektur ist und die Antwort für alle Architekturen gilt, die Ganzzahl- und Gleitkommaregister trennen, was praktisch alles von ihnen ist.

Antworten:

36

Der große Nachteil beim Mischen von Ints (jeglicher Art) und Floats besteht darin, dass sich diese in unterschiedlichen Registersätzen befinden. Um von einem Registersatz zum anderen zu gelangen, müssen Sie den Wert in den Speicher schreiben und zurücklesen, was zu einem Load-Hit-Store- Stall führt.

Wenn Sie zwischen verschiedenen Größen oder Signaturen von Ints wechseln, bleibt alles im selben Registersatz, sodass Sie die große Strafe vermeiden. Es kann kleinere Strafen aufgrund von Sign-Extensions usw. geben, aber diese sind viel kleiner als bei einem Load-Hit-Store.

celion
quelle
Der Artikel, den Sie verlinkt haben, besagt, dass der PS3-Zellenprozessor eine Ausnahme ist, da anscheinend alles in demselben Registersatz gespeichert ist (ungefähr in der Mitte des Artikels zu finden oder nach "Zelle" zu suchen).
Bummzack
4
@bummzack: Das gilt nur für die SPEs, nicht für die PPE; Die SPEs haben eine sehr spezielle Gleitkomma-Umgebung, und die Besetzung ist immer noch relativ teuer. Außerdem sind die Kosten für vorzeichenbehaftete und nicht vorzeichenbehaftete ganze Zahlen weiterhin gleich.
Das ist ein guter Artikel, und es ist wichtig, über LHS Bescheid zu wissen (und ich stimme dafür), aber meine Frage bezieht sich auf die mit den Zeichen verbundenen Strafen. Ich weiß, dass diese klein und wahrscheinlich vernachlässigbar sind, aber ich würde immer noch gerne echte Zahlen oder Referenzen darüber sehen.
Luis
1
@ Luis - Ich habe versucht, eine öffentliche Dokumentation zu diesem Thema zu finden, kann sie aber derzeit nicht finden. Wenn Sie Zugriff auf die Xbox360-Dokumentation haben, gibt es ein gutes Whitepaper von Bruce Dawson, das einige davon behandelt (und es ist im Allgemeinen sehr gut).
celion
@ Luis: Ich habe unten eine Analyse gepostet, aber wenn Sie zufrieden sind, geben Sie celion bitte die Antwort - alles, was er gesagt hat, ist richtig, alles, was ich getan habe, ist, GCC ein paar Mal auszuführen.
12

Ich vermute, dass sich Informationen über die Xbox 360 und die PS3 wie die meisten Details auf niedriger Ebene hinter Wänden befinden, die nur für Entwickler lizenziert sind. Wir können jedoch ein äquivalentes x86-Programm erstellen und es zerlegen, um eine allgemeine Vorstellung zu erhalten.

Lassen Sie uns zunächst sehen, welche Kosten für die Erweiterung ohne Vorzeichen anfallen:

unsigned char x = 1;
unsigned int y = 1;
unsigned int z;
z = x;
z = y;

Der relevante Teil zerlegt sich in (unter Verwendung von GCC 4.4.5):

    z = x;
  27:   0f b6 45 ff             movzbl -0x1(%ebp),%eax
  2b:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  2e:   8b 45 f8                mov    -0x8(%ebp),%eax
  31:   89 45 f4                mov    %eax,-0xc(%ebp)

Also im Grunde das gleiche - in einem Fall bewegen wir ein Byte, in dem anderen bewegen wir ein Wort. Nächster:

signed char x = 1;
signed int y = 1;
signed int z;
z = x;
z = y;

Verwandelt sich in:

   z = x;
  11:   0f be 45 ff             movsbl -0x1(%ebp),%eax
  15:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  18:   8b 45 f8                mov    -0x8(%ebp),%eax
  1b:   89 45 f4                mov    %eax,-0xc(%ebp)

Die Kosten für die Vorzeichenerweiterung sind also unabhängig von den Kosten movsblund nicht movzbl- der Unteranweisungsebene. Das ist auf modernen Prozessoren aufgrund der Arbeitsweise der modernen Prozessoren im Grunde unmöglich zu quantifizieren. Alles andere, angefangen von der Speichergeschwindigkeit über das Caching bis hin zu dem, was zuvor in der Pipeline war, wird die Laufzeit dominieren.

In den ~ 10 Minuten, die ich für das Schreiben dieser Tests benötigt habe, hätte ich leicht einen echten Leistungsfehler finden können, und sobald ich eine Stufe der Compileroptimierung aktiviert habe, ist der Code für solch einfache Aufgaben nicht mehr erkennbar.

Dies ist kein Stapelüberlauf, daher hoffe ich, dass hier niemand behaupten wird, dass die Mikrooptimierung keine Rolle spielt. Spiele arbeiten oft mit sehr großen und numerischen Daten. Daher kann die sorgfältige Berücksichtigung von Verzweigungen, Besetzungen, Zeitplanung, Strukturanpassung usw. zu wichtigen Verbesserungen führen. Jeder, der viel Zeit mit der Optimierung von PPC-Code verbracht hat, hat wahrscheinlich mindestens eine Horrorgeschichte über Load-Hit-Stores. Aber in diesem Fall ist es wirklich egal. Die Speichergröße Ihres Integer-Typs wirkt sich nicht auf die Leistung aus, solange er ausgerichtet ist und in ein Register passt.

user744
quelle
2
(CW, weil dies wirklich nur ein Kommentar zu Celions Antwort ist, und weil ich neugierig bin, welche Code-Änderungen die Leute zur Veranschaulichung
Informationen zur PS3-CPU sind leicht und legal verfügbar, sodass die Diskussion von CPU-Inhalten im Zusammenhang mit PS3 kein Problem darstellt. Bis Sony die Unterstützung für OtherOS entfernte, konnte jeder Linux auf eine PS3 stecken und programmieren. Die GPU war tabu, aber die CPU (einschließlich der SPEs) sind in Ordnung. Auch ohne die Unterstützung von OtherOS können Sie ganz einfach das entsprechende GCC finden und sehen, wie das Code-Gen aussieht.
JasonD
@Jason: Ich habe meinen Beitrag als CW gekennzeichnet. Wenn jemand dies tut, kann er die Informationen bereitstellen. Jeder, der Zugriff auf den offiziellen GameOS-Compiler von Sony hat - der wirklich der einzige ist, auf den es ankommt -, wird wahrscheinlich daran gehindert.
Tatsächlich ist die vorzeichenbehaftete Ganzzahl bei PPC IIRC teurer. Es hat einen winzigen Leistungseinbruch, aber es ist da ... auch viele Details zu PS3 PPU / SPU sind hier zu finden: jheriko-rtw.blogspot.co.uk/2011/07/ps3-ppuspu-docs.html und hier: jheriko-rtw.blogspot.co.uk/2011/03/ppc-instruction-set.html . Neugierig, was dieser GameOS-Compiler ist? Ist das der GCC Compier oder der SNC? Abgesehen von den bereits erwähnten Dingen haben die signierten Vergleiche einen Overhead, wenn es um die Optimierung innerster Schleifen geht. Ich habe jedoch keinen Zugang zu den Dokumenten, die dies beschreiben - und selbst wenn ...
jheriko
4

Signed Integer-Operationen können auf fast allen Architekturen teurer sein. Zum Beispiel ist die Division durch eine Konstante schneller, wenn sie nicht vorzeichenbehaftet ist, zB:

unsigned foo(unsigned a) { return a / 1024U; }

wird optimiert auf:

unsigned foo(unsigned a) { return a >> 10; }

Aber...

int foo(int a) { return a / 1024; }

optimiert auf:

int foo(int a) {
  return (a + 1023 * (a < 0)) >> 10;
}

oder auf Systemen, bei denen die Verzweigung billig ist,

int foo(int a) {
  if (a >= 0) return a >> 10;
  else return (a + 1023) >> 10;
}

Gleiches gilt für Modulo. Dies gilt auch für Nicht-Potenzen von 2 (das Beispiel ist jedoch komplexer). Wenn Ihre Architektur keine Hardwareteilung aufweist (z. B. die meisten ARMs), sind vorzeichenlose Teilungen von Nicht-Konstanten auch schneller.

Wenn Sie dem Compiler mitteilen, dass sich keine negativen Zahlen ergeben können, können Sie Ausdrücke optimieren, insbesondere solche, die für die Schleifenbeendigung und andere Bedingungen verwendet werden.

Was verschiedene Größen betrifft, gibt es zwar einen leichten Einfluss, aber Sie müssten diesen abwägen, anstatt weniger Speicher zu verschieben. In diesen Tagen gewinnen Sie wahrscheinlich mehr durch den Zugriff auf weniger Speicher als durch die Größenerweiterung. Sie sind an diesem Punkt sehr weit in der Mikrooptimierung.

John Ripley
quelle
Ich habe Ihren optimierten Code bearbeitet, um besser zu reflektieren, was GCC tatsächlich generiert, selbst bei -O0. Ein Zweig zu haben, war irreführend, wenn man es mit einem Test + Lea ohne Zweig machen konnte.
2
Auf x86 vielleicht. In ARMv7 wird es nur unter bestimmten Bedingungen ausgeführt.
John Ripley
3

Vorgänge mit signiertem oder nicht signiertem int verursachen auf aktuellen Prozessoren (x86_64, x86, PowerPC, Arm) dieselben Kosten. Auf 32-Bit-Prozessoren sollten u32, u16, u8, s32, s16, s8 identisch sein. Sie können mit schlechter Ausrichtung Strafe haben.

Die Konvertierung von int in float oder float in int ist jedoch eine kostspielige Operation. Sie können leicht eine optimierte Implementierung finden (SSE2, Neon ...).

Der wichtigste Punkt ist wahrscheinlich der Speicherzugriff. Wenn Ihre Daten nicht in den L1 / L2-Cache passen, verlieren Sie mehr Zyklus als Konvertierung.

Ellis
quelle
2

Jon Purdy sagt oben (ich kann es nicht kommentieren), dass unsigned möglicherweise langsamer ist, weil es nicht überlaufen kann. Ich stimme nicht zu, vorzeichenlose Arithmetik ist einfache Moular-Arithmetik modulo 2 zur Anzahl der Bits im Wort. Vorzeichenbehaftete Operationen können im Prinzip Überläufe erleiden, sind jedoch normalerweise deaktiviert.

Manchmal können Sie clevere (aber nicht sehr lesbare) Dinge tun, z. B. zwei oder mehr Datenelemente in ein int packen und mehrere Operationen pro Anweisung erhalten (Taschenarithmetik). Aber du musst verstehen, was du tust. Natürlich können Sie dies mit MMX auf natürliche Weise tun. Wenn Sie jedoch manchmal die größte von HW unterstützte Wortgröße verwenden und die Daten manuell packen, erhalten Sie die schnellste Implementierung.

Seien Sie vorsichtig bei der Datenausrichtung. Bei den meisten HW-Implementierungen sind nicht ausgerichtete Lasten und Speicher langsamer. Natürliche Ausrichtung bedeutet, dass zum Beispiel ein 4-Byte-Wort ein Vielfaches von vier ist und acht-Byte-Wortadressen ein Vielfaches von acht Byte sein sollten. Dies überträgt sich auf SSE (128 Bit begünstigen die 16-Byte-Ausrichtung). AVX wird diese "Vektor" -Registergrößen bald auf 256 Bit und dann auf 512 Bit erweitern. Ausgerichtete Ladungen / Lager sind schneller als nicht ausgerichtete. Für HW-Geeks kann eine nicht ausgerichtete Speicheroperation Dinge wie Cacheline und sogar Seitengrenzen umfassen, bei denen die HW vorsichtig sein muss.


quelle
1

Es ist etwas besser, für Schleifenindizes vorzeichenbehaftete Ganzzahlen zu verwenden, da der vorzeichenbehaftete Überlauf in C undefiniert ist, sodass der Compiler davon ausgeht, dass solche Schleifen weniger Eckfälle haben. Dies wird durch gccs "-fstrict-overflow" (standardmäßig aktiviert) gesteuert und der Effekt ist wahrscheinlich schwer zu bemerken, ohne die Assembly-Ausgabe zu lesen.

Darüber hinaus funktioniert x86 besser, wenn Sie keine Typen mischen, da es Speicheroperanden verwenden kann. Wenn Typen konvertiert werden müssen (Vorzeichen- oder Null-Erweiterungen), bedeutet dies ein explizites Laden und die Verwendung eines Registers.

Halten Sie sich an int für lokale Variablen, und das meiste davon geschieht standardmäßig.

alex komisch
quelle
0

Celion weist darauf hin, dass der Mehraufwand beim Konvertieren zwischen Ints und Floats hauptsächlich mit dem Kopieren und Konvertieren von Werten zwischen Registern zusammenhängt. Der einzige Mehraufwand für unsignierte Ints an und für sich ergibt sich aus ihrem garantierten Wraparound-Verhalten, das eine gewisse Überlaufprüfung im kompilierten Code erfordert.

Die Konvertierung zwischen vorzeichenbehafteten und vorzeichenlosen Ganzzahlen verursacht im Grunde genommen keinen Mehraufwand. Verschiedene Größen von Integer kann (verschwindend) schneller oder langsamer Zugriff je nach Plattform. Im Allgemeinen ist die Größe der ganzen Zahl, die auf die Wortgröße der Plattform am nächsten ist die schnellste sein , Zugang, aber die Gesamtleistung Unterschied hängt von vielen anderen Faktoren ab , vor allem Größe Cache: Wenn Sie verwenden , uint64_twenn alles , was Sie brauchen , ist uint32_t, kann es Es kann sein, dass weniger Ihrer Daten sofort in den Cache passen und Sie möglicherweise einen gewissen Mehraufwand haben.

Es ist jedoch etwas übertrieben, darüber nachzudenken. Wenn Sie Typen verwenden, die für Ihre Daten geeignet sind, sollten die Dinge einwandfrei funktionieren, und die Menge an Leistung, die durch die Auswahl von Typen auf der Grundlage der Architektur erzielt werden kann, ist ohnehin vernachlässigbar.

Jon Purdy
quelle
Auf welche Überlaufprüfung beziehen Sie sich? Sofern Sie nicht eine niedrigere Stufe als Assembler meinen, ist der Code zum Hinzufügen von zwei Zoll auf den meisten Systemen identisch und auf den wenigen Systemen, die z. B. die Zeichengröße verwenden, nicht wirklich länger. Einfach anders.
@ Joe Wreschnig: Verdammt. Ich kann es anscheinend nicht finden, aber ich weiß, dass ich Beispiele für verschiedene Assembler-Ausgaben gesehen habe, die für ein definiertes Umgehungsverhalten verantwortlich sind, zumindest auf bestimmten Plattformen. Der einzige verwandte Beitrag, den ich finden konnte: stackoverflow.com/questions/4712315/…
Jon Purdy
Unterschiedliche Assembler-Ausgabe für unterschiedliches Wraparound-Verhalten liegt darin begründet, dass der Compiler Optimierungen in dem vorzeichenbehafteten Fall vornehmen kann, z. Es ist wirklich eine ganz andere Situation.