Auf 32-Bit-CPUs ist ein Integer-Typ effizienter als ein "kurzer" Typ?

Question

Auf einer 32-Bit-CPU ist eine Ganzzahl 4 Byte und eine kurze Ganzzahl 2 Byte. Wenn ich eine C/C++ - Anwendung schreibe, die viele numerische Werte verwendet, die immer in den angegebenen Bereich einer kurzen Ganzzahl passen, ist es effizienter, 4-Byte-Ganzzahlen oder 2-Byte-Ganzzahlen zu verwenden?

Ich habe gehört es vorgeschlagen, dass 4 Byte Integer effizienter sind, da dies die Bandbreite des Busses aus dem Speicher an die CPU passt. Wenn ich jedoch zwei kurze Ganzzahlen addiere, würde die CPU beide Werte in einem einzigen Durchgang parallel packen (also die 4-Byte-Bandbreite des Busses überspannen)?

Answer 1

Ja, Sie sollten auf jeden Fall eine 32-Bit-Ganzzahl auf einer 32-Bit-CPU verwenden, andernfalls kann es die unbenutzten Bits maskieren (dh es wird immer die Mathematik in 32 Bits machen, dann die Antwort in 16 Bits umwandeln))

Es wird nicht zwei 16-Bit-Operationen gleichzeitig für Sie tun, aber wenn Sie den Code selbst schreiben und Sie sicher sind, dass es nicht überläuft, können Sie es selbst tun.

Bearbeiten: Ich sollte hinzufügen, dass es auch etwas von Ihrer Definition von "effizient" abhängt. Während es 32-Bit-Operationen schneller ausführen kann, werden Sie natürlich doppelt so viel Speicher verwenden.

Wenn diese irgendwo für Zwischenberechnungen in einer inneren Schleife verwendet werden, verwenden Sie 32-Bit. Wenn Sie dies jedoch von der Festplatte lesen, oder wenn Sie nur für einen Cache-Fehler bezahlen müssen, kann es trotzdem besser sein, 16-Bit-Ganzzahlen zu verwenden. Wie bei allen Optimierungen gibt es nur eine Möglichkeit zu wissen: Profil es.

Answer 2

Wenn Sie eine große Anzahl von Zahlen haben, dann gehen Sie mit der kleinsten Größe, die funktioniert. Es wird effizienter sein, mit einem Array von 16-Bit-Kurzschlüssen als 32-Bit-Ints zu arbeiten, da Sie die doppelte Cache-Dichte erhalten. Die Kosten einer Vorzeichenerweiterung, die die CPU zu tun hat, um mit 16-Bit-Werten in 32-Bit-Registern zu arbeiten, sind im Vergleich zu den Kosten eines Cache-Fehltreffers vernachlässigbar vernachlässigbar.

Wenn Sie einfach Membervariablen in Klassen verwenden, die mit anderen Datentypen gemischt sind, ist es weniger klar, da die Padding-Anforderungen wahrscheinlich den Platz sparenden Vorteil der 16-Bit-Werte beseitigen.

Answer 3

Kommt drauf an. Wenn Sie CPU-gebunden sind, sind 32-Bit-Operationen auf einer 32-Bit-CPU schneller als 16 Bit. Wenn Sie speichergebunden sind (insbesondere wenn Sie zu viele L2-Cache-Fehler haben), verwenden Sie die kleinsten Daten, die Sie hineinquetschen können.

Sie können herausfinden, welchen Sie einen Profiler verwenden, der sowohl CPU- als auch L2-Fehler wie Intel's VTune misst. Sie werden Ihre App 2 Mal mit der gleichen Auslastung ausführen und die 2 Runs in einer Ansicht der Hotspots in Ihrer App zusammenführen. Sie können für jede Codezeile sehen, wie viele Zyklen für diese Zeile ausgegeben wurden. Wenn bei einer teuren Codezeile 0 Cache-Fehler angezeigt werden, sind Sie CPU-gebunden. Wenn Sie Unmengen von Fehlschüssen sehen, sind Sie an die Erinnerung gebunden.

Answer 4

Wenn Sie mit einem großen Dataset arbeiten, ist das größte Problem der Speicherbedarf. Ein gutes Modell in diesem Fall ist die Annahme, dass die CPU unendlich schnell ist und sich damit beschäftigt, sich darüber Gedanken zu machen, wie viele Daten in den/aus dem Speicher verschoben werden müssen. Tatsächlich sind CPUs jetzt so schnell, dass es manchmal effizienter ist, die Daten zu codieren (z. B. zu komprimieren). Auf diese Weise arbeitet die CPU (möglicherweise viel) mehr (Decodierung/Codierung), aber die Speicherbandbreite wird wesentlich reduziert.

Wenn Ihre Datenmenge also groß ist, ist es wahrscheinlich besser, 16-Bit-Ganzzahlen zu verwenden. Wenn Ihre Liste sortiert ist, können Sie ein Codierungsschema entwerfen, das eine differenzielle oder Lauflängencodierung beinhaltet, wodurch die Speicherbandbreite noch weiter reduziert wird.

Answer 5

Wenn Sie "viele" Ganzzahlwerte verwenden, ist der Engpass in Ihrer Verarbeitung wahrscheinlich eine Bandbreite für den Arbeitsspeicher. 16-Bit-Ganzzahlen packen enger in den Daten-Cache und würden daher ein Performance-Gewinn sein.

Wenn Sie auf einer sehr großen Datenmenge Zahlen verarbeiten, sollten Sie What Every Programmer Should Know About Memory von Ulrich Drepper lesen. Konzentrieren Sie sich auf Kapitel 6, um die Effizienz des Daten-Cache zu maximieren.

Answer 6

Wenn Sie 32bit sagen, nehme ich an, Sie meinen x86. 16-Bit-Arithmetik ist ziemlich langsam: die Operandengröße Präfix macht die Decodierung wirklich langsam. Machen Sie also Ihre temporären Variablen nicht kurz int oder int16_t.

Allerdings kann x86 effizient 16- und 8-Bit-Integer in 32- oder 64-Bit-Register laden. (movzx/movsx: Null- und Zeichenerweiterung). Sie können also short int für Array- und struct-Felder verwenden, aber stellen Sie sicher, dass Sie int oder long für Ihre temporären Variablen verwenden.

Allerdings, wenn ich zusammen zwei kurze ganze Zahlen bin hinzufügen, würde das CPU-Paket beiden Werte in einem einzigen Durchgang parallel (also überspannt die 4-Byte-Bandbreite des Busses)?

Das ist Unsinn. Lade-/Speicherbefehle interagieren mit dem L1-Cache, und der begrenzende Faktor ist die Anzahl der Ops; Breite ist irrelevant. z.B. auf core2: 1 Beladung und 1 Filiale pro Zyklus, unabhängig von der Breite. L1-Cache hat einen 128- oder 256-Bit-Pfad zum L2-Cache.

Wenn Lasten Ihr Flaschenhals sind, kann eine breite Ladung, die Sie nach dem Laden mit Schichten oder Masken aufteilen, helfen. Oder verwenden Sie SIMD, um Daten parallel zu verarbeiten, ohne sie nach dem parallelen Laden zu entpacken.

Answer 7

Hören Sie nicht auf den Rat, versuchen Sie es.

Dies wird wahrscheinlich stark von der Hardware/Compiler, den Sie verwenden, abhängen. Ein kurzer Test sollte diese Frage kurz machen. Wahrscheinlich weniger Zeit, um den Test zu schreiben, als die Frage hier zu schreiben.

Answer 8

Eine 32-Bit-CPU ist eine CPU, die normalerweise intern mit 32-Bit-Werten arbeitet. Dies bedeutet jedoch nicht, dass sie langsamer ist, wenn dieselbe Operation für einen 8/16-Bit-Wert ausgeführt wird. Zum Beispiel kann x86, das bis zum 8086 noch abwärtskompatibel ist, auf Bruchteilen eines Registers arbeiten. Das heißt, selbst wenn ein Register 32 Bit breit ist, kann es nur auf dem ersten 16 oder dem ersten 8 Bit dieses Registers arbeiten und es wird überhaupt keine Verlangsamung geben. Dieses Konzept wurde sogar von x86_64 übernommen, wo die Register 64 Bit sind, aber sie können immer noch nur mit den ersten 32, 16 oder 8 Bit arbeiten.

Auch x86-CPUs laden immer eine ganze Cache-Zeile aus dem Speicher, wenn nicht bereits im Cache, und eine Cache-Zeile ist sowieso größer als 4 Byte (für 32-Bit-CPUs eher 8 oder 16 Byte) und lädt 2 Byte aus dem Speicher ist genauso schnell wie das Laden von 4 Bytes aus dem Speicher. Wenn viele Werte aus dem Speicher verarbeitet werden, können 16-Bit-Werte tatsächlich viel schneller als 32-Bit-Werte sein, da es weniger Speicherübertragungen gibt. Wenn eine Cache-Zeile 8 Bytes groß ist, gibt es vier 16-Bit-Werte pro Cache-Zeile, aber nur zwei 32-Bit-Werte. Bei Verwendung von 16-Bit-Werten haben Sie also alle vier Werte einen Speicherzugriff , was zu doppelt so vielen Übertragungen für die Verarbeitung eines großen int-Arrays führt.

Andere CPUs, wie zum Beispiel PPC, können nicht nur einen Bruchteil eines Registers verarbeiten, sie verarbeiten immer das volle Register. Diese CPUs haben jedoch üblicherweise spezielle Ladeoperationen, die es ihnen ermöglichen, z. Laden Sie einen 16-Bit-Wert aus dem Speicher, erweitern Sie ihn auf 32 Bit und schreiben Sie ihn in ein Register.Später haben sie eine spezielle Speicheroperation, die den Wert aus dem Register übernimmt und nur die letzten 16 Bits in den Speicher zurückspeichert; Beide Operationen benötigen nur einen CPU-Zyklus, genau wie ein 32-Bit-Lade-/Speichervorgang, so dass es auch keinen Geschwindigkeitsunterschied gibt. Und da PPC nur arithmetische Operationen an Registern durchführen kann (im Gegensatz zu x86, das auch direkt im Speicher arbeiten kann), findet diese Lade-/Speicherprozedur trotzdem statt, egal ob Sie 32 Bit Inte oder 16 Bit Inte verwenden.

Der einzige Nachteil, wenn Sie mehrere Operationen auf einer 32-Bit-CPU verketten, die nur mit vollen Registern arbeiten kann, ist, dass das 32-Bit-Ergebnis der letzten Operation möglicherweise auf 16 Bit vor dem nächsten zurückgeschnitten werden muss Die Operation wird ausgeführt, andernfalls ist das Ergebnis möglicherweise nicht korrekt. Ein solcher Rückschnitt ist jedoch nur ein einzelner CPU-Zyklus (eine einfache AND-Operation), und Compiler sind sehr gut darin, herauszufinden, wann ein solcher Rückschnitt wirklich notwendig ist, und wenn er weggelassen wird, hat er keinen Einfluss auf das Endergebnis , also wird ein solcher Rückschnitt nicht nach jeder Anweisung ausgeführt, er wird nur durchgeführt, wenn es wirklich unvermeidlich ist. Einige CPUs bieten verschiedene "erweiterte" Anweisungen, die einen solchen Verzicht überflüssig machen, und ich habe viel Code in meinem Leben gesehen, wo ich eine solche Kürzung erwartet hatte, aber der Compiler hat einen Weg gefunden vermeide es vollständig.

Also, wenn Sie hier eine allgemeine Regel erwarten, muss ich Sie enttäuschen. Man kann auch nicht mit Sicherheit sagen, dass 16-Bit-Operationen für 32-Bit-Operationen gleich schnell sind, noch kann jemand mit Sicherheit sagen, dass 32-Bit-Operationen immer schneller sind. Es hängt auch davon ab, was genau dein Code mit diesen Zahlen macht und wie es das macht. Ich habe Benchmarks gesehen, bei denen 32-Bit-Operationen bei bestimmten 32-Bit-CPUs schneller waren als der gleiche Code bei 16-Bit-Operationen, aber ich habe auch schon das Gegenteil gesehen. Selbst wenn Sie von einem Compiler zu einem anderen wechseln oder Ihre Compiler-Version aktualisieren, wird möglicherweise bereits alles wieder umgestellt. Ich kann nur folgendes sagen: Wer behauptet, dass die Arbeit mit Shorts wesentlich langsamer ist als die Arbeit mit Ints, soll bitte einen Beispielquellcode für diesen Anspruch angeben und CPU und Compiler nennen, die er zum Testen verwendet hat, da ich so etwas noch nie erlebt habe über die letzten 10 Jahre. Es kann Situationen geben, in denen die Arbeit mit Ints vielleicht 1-5% schneller ist, aber nichts unter 10% ist nicht "signifikant" und die Frage ist, ob es sich lohnt, in manchen Fällen doppelt so viel Speicher zu verschwenden, nur weil es Sie kaufen kann 2% Leistung? Ich denke nicht.