Wann ist Assembler schneller als C?

Question

Einer der angegebenen Gründe für Assembler-Kenntnisse ist, dass man damit gelegentlich Code schreiben kann, der leistungsfähiger ist als der Code in einer höheren Sprache, insbesondere C. Ich habe aber auch schon oft gehört, dass, obwohl das nicht ganz falsch ist, die Fälle, in denen Assembler helfen kann eigentlich zur Generierung von leistungsfähigerem Code verwendet werden können, sind extrem selten und erfordern Expertenwissen und Erfahrung mit Assembler.

Diese Frage geht noch nicht einmal auf die Tatsache ein, dass Assembler-Anweisungen maschinenspezifisch und nicht portierbar sind, oder auf andere Aspekte von Assembler. Es gibt viele gute Gründe, Assembler zu kennen, abgesehen von diesem, natürlich, aber dies soll eine spezifische Frage sein, die nach Beispielen und Daten fragt, nicht ein ausgedehnter Diskurs über Assembler gegenüber höheren Sprachen.

Kann jemand etwas über spezifische Beispiele in welchen Fällen Assembler schneller ist als gut geschriebener C-Code mit einem modernen Compiler, und können Sie diese Behauptung mit Profilergebnissen belegen? Ich bin mir ziemlich sicher, dass es diese Fälle gibt, aber ich möchte wirklich genau wissen, wie esoterisch diese Fälle sind, da dies ein Punkt zu sein scheint, über den man streiten kann.

Answer 1

Hier ist ein Beispiel aus der Praxis: Festkommamultiplikation auf alten Compilern.

Diese sind nicht nur auf Geräten ohne Fließkomma nützlich, sondern auch, wenn es um Präzision geht, da sie 32 Bit Präzision mit einem vorhersehbaren Fehler bieten (Float hat nur 23 Bit und es ist schwieriger, Präzisionsverluste vorherzusagen). z.B. uniform absolut Präzision über den gesamten Bereich, statt annähernd gleichmäßiger relativ Genauigkeit ( float ).

---

Moderne Compiler optimieren dieses Festkomma-Beispiel sehr gut. Für modernere Beispiele, die dennoch compilerspezifischen Code benötigen, siehe

• Ermittlung des hohen Anteils der 64-Bit-Multiplikation ganzer Zahlen : Eine tragbare Version mit uint64_t für 32x32 => 64-Bit-Multiplikationen kann auf einer 64-Bit-CPU nicht optimiert werden, so dass Sie intrinsics oder __int128 für effizienten Code auf 64-Bit-Systemen.
• _umul128 unter Windows 32 Bit : MSVC leistet nicht immer gute Arbeit bei der Multiplikation von 32-Bit-Ganzzahlen mit 64, so dass Intrinsics eine große Hilfe waren.

---

C hat keinen Operator für die Vollmultiplikation (2N-Bit-Ergebnis aus N-Bit-Eingaben). Der übliche Weg, dies in C auszudrücken, besteht darin, die Eingänge in den breiteren Typ zu casten und zu hoffen, dass der Compiler erkennt, dass die oberen Bits der Eingänge nicht interessant sind:

// on a 32-bit machine, int can hold 32-bit fixed-point integers.
int inline FixedPointMul (int a, int b)
{
  long long a_long = a; // cast to 64 bit.

  long long product = a_long * b; // perform multiplication

  return (int) (product >> 16);  // shift by the fixed point bias
}

Das Problem mit diesem Code ist, dass wir etwas tun, das nicht direkt in der C-Sprache ausgedrückt werden kann. Wir wollen zwei 32-Bit-Zahlen multiplizieren und ein 64-Bit-Ergebnis erhalten, von dem wir die mittleren 32 Bit zurückgeben. In C gibt es diese Multiplikation jedoch nicht. Alles, was man tun kann, ist, die ganzen Zahlen auf 64 Bit zu bringen und eine 64*64 = 64 Multiplikation durchzuführen.

x86 (und ARM, MIPS und andere) können jedoch die Multiplikation in einem einzigen Befehl durchführen. Einige Compiler ignorierten diese Tatsache und erzeugten Code, der eine Bibliotheksfunktion zur Laufzeit aufrief, um die Multiplikation durchzuführen. Die Verschiebung mit 16 wird ebenfalls oft von einer Bibliotheksroutine durchgeführt (auch der x86 kann solche Verschiebungen durchführen).

Es bleiben also nur ein oder zwei Bibliotheksaufrufe für einen Multiplikator. Das hat ernste Konsequenzen. Die Verschiebung ist nicht nur langsamer, sondern die Register müssen über die Funktionsaufrufe hinweg beibehalten werden, und auch Inlining und Code-Unrolling werden dadurch nicht gefördert.

Wenn Sie denselben Code in (Inline-)Assembler umschreiben, können Sie einen erheblichen Geschwindigkeitsgewinn erzielen.

Außerdem ist die Verwendung von ASM nicht der beste Weg, um das Problem zu lösen. Die meisten Compiler erlauben es Ihnen, einige Assembler-Anweisungen in intrinsischer Form zu verwenden, wenn Sie sie nicht in C ausdrücken können. Der VS.NET2008-Compiler beispielsweise stellt die 32*32=64-Bit-Mul als __emul und die 64-Bit-Verschiebung als __ll_rshift dar.

Mit Hilfe von Intrinsics können Sie die Funktion so umschreiben, dass der C-Compiler eine Chance hat zu verstehen, was vor sich geht. Dies ermöglicht das Inlining des Codes, die Zuweisung von Registern, die Eliminierung gemeinsamer Unterausdrücke und die Weitergabe von Konstanten. Sie erhalten eine enorme Leistungsverbesserung gegenüber dem handgeschriebenen Assembler-Code.

Als Referenz: Das Endergebnis für das Festkomma-Mul für den VS.NET-Compiler ist:

int inline FixedPointMul (int a, int b)
{
    return (int) __ll_rshift(__emul(a,b),16);
}

Der Leistungsunterschied bei Festkommadivisionen ist sogar noch größer. Ich hatte Verbesserungen bis zum Faktor 10 für Division schweren Festkomma-Code durch das Schreiben ein paar asm-Zeilen.

---

Die Verwendung von Visual C++ 2013 ergibt für beide Wege den gleichen Assemblercode.

gcc4.1 aus dem Jahr 2007 optimiert auch die reine C-Version sehr gut. (Der Godbolt-Compiler-Explorer hat keine früheren Versionen von gcc installiert, aber vermutlich können auch ältere GCC-Versionen dies ohne Intrinsics tun).

Siehe Quelle + asm für x86 (32-bit) und ARM auf der Godbolt-Compiler-Explorer%3B%0A%7D%0A%23endif%0A%0A%0A/+Intrinsics+are+more+useful+for+extended+precision%0A++when+there+isn!'t+a+wide-enough+type.%0A++e.g.+128-bit+integer+on+compilers+without+__int128%0A+/%0A'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:32.75251522372254,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:g412,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-m32++-fomit-frame-pointer',source:1),l:'5',n:'0',o:'x86-64+gcc+4.1.2+(Editor+%231,+Compiler+%231)+C%2B%2B',t:'0')),k:34.10775747948107,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:arm710,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-mthumb+-mcpu%3Dcortex-m4',source:1),l:'5',n:'0',o:'ARM+gcc+7.2.1+(none)+(Editor+%231,+Compiler+%232)+C%2B%2B',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:33.91415144294414,l:'3',n:'0',o:'',t:'0'),(g:!((g:!((h:compiler,i:(compiler:clang30,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-m32',source:1),l:'5',n:'0',o:'x86-64+clang+3.0.0+(Editor+%231,+Compiler+%233)+C%2B%2B',t:'0')),k:33.33333333333333,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cl19_2015_u3_32,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-Ox',source:1),l:'5',n:'0',o:'x86+MSVC+19+2015+U3+(Editor+%231,+Compiler+%234)+C%2B%2B',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:33.33333333333333,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4) . (Leider gibt es keine Compiler, die alt genug sind, um schlechten Code aus der einfachen reinen C-Version zu erzeugen).

---

Moderne CPUs können Dinge tun, für die C keine Operatoren hat überhaupt , wie popcnt oder Bit-Scan, um das erste oder letzte gesetzte Bit zu finden . (POSIX hat eine ffs() Funktion, aber ihre Semantik entspricht nicht der x86 bsf / bsr . Siehe https://en.wikipedia.org/wiki/Find_first_set ).

Einige Compiler können manchmal eine Schleife erkennen, die die Anzahl der gesetzten Bits in einer Ganzzahl zählt, und kompilieren sie zu einer popcnt Anweisung (falls zur Kompilierzeit aktiviert), aber es ist viel zuverlässiger, die __builtin_popcnt in GNU C, oder auf x86, wenn Sie nur Hardware mit SSE4.2 anvisieren: _mm_popcnt_u32 von <immintrin.h> .

Oder in C++: Zuweisung an eine std::bitset<32> und verwenden .count() . (Dies ist ein Fall, in dem die Sprache einen Weg gefunden hat, eine optimierte Implementierung von popcount über die Standardbibliothek portabel zu machen, und zwar auf eine Weise, die immer zu etwas Korrektem kompiliert wird und die Vorteile von allem nutzen kann, was das Ziel unterstützt). Siehe auch https://en.wikipedia.org/wiki/Hamming_weight#Language_support .

Ähnlich, ntohl kann kompiliert werden zu bswap (x86 32-Bit-Byte-Swap für Endian-Konvertierung) auf einigen C-Implementierungen, die es haben.

---

Ein weiterer wichtiger Bereich für intrinsics oder handgeschriebene asm ist die manuelle Vektorisierung mit SIMD-Anweisungen. Compiler sind nicht schlecht bei einfachen Schleifen wie dst[i] += src[i] * 10.0; , aber oft schlecht oder gar nicht automatisch vektorisieren, wenn die Dinge komplizierter werden. Es ist zum Beispiel unwahrscheinlich, dass Sie etwas wie Wie implementiert man atoi mit SIMD? automatisch vom Compiler aus skalarem Code erzeugt.

Answer 2

Vor vielen Jahren brachte ich jemandem das Programmieren in C bei. Die Aufgabe bestand darin, eine Grafik um 90 Grad zu drehen. Er kam mit einer Lösung zurück, die mehrere Minuten in Anspruch nahm, vor allem weil er Multiplizieren und Dividieren usw. verwendete.

Ich zeigte ihm, wie er das Problem mit Hilfe von Bitverschiebungen umschreiben konnte, und die Verarbeitungszeit sank auf dem nicht optimierenden Compiler, den er hatte, auf etwa 30 Sekunden.

Ich hatte gerade einen optimierenden Compiler bekommen und derselbe Code rotierte die Grafik in < 5 Sekunden. Ich schaute mir den Assembler-Code an, den der Compiler erzeugte, und entschied nach dem, was ich sah, auf der Stelle, dass meine Tage des Assembler-Schreibens vorbei waren.

Answer 3

So gut wie immer, wenn der Compiler Fließkommacode sieht, ist eine handgeschriebene Version schneller, wenn Sie einen alten, schlechten Compiler verwenden. ( Update 2019: Dies gilt nicht generell für moderne Compiler. Vor allem, wenn man für etwas anderes als x87 kompiliert; Compiler haben es leichter mit SSE2 oder AVX für skalare Mathematik oder mit jedem nicht-x86er mit einem flachen FP-Registersatz, im Gegensatz zum Registerstapel von x87).

Der Hauptgrund ist, dass der Compiler keine robusten Optimierungen durchführen kann. Siehe diesen Artikel von MSDN für eine Diskussion zu diesem Thema. Hier ist ein Beispiel, bei dem die Assembler-Version doppelt so schnell ist wie die C-Version (kompiliert mit VS2K5):

#include "stdafx.h"
#include <windows.h>

float KahanSum(const float *data, int n)
{
   float sum = 0.0f, C = 0.0f, Y, T;

   for (int i = 0 ; i < n ; ++i) {
      Y = *data++ - C;
      T = sum + Y;
      C = T - sum - Y;
      sum = T;
   }

   return sum;
}

float AsmSum(const float *data, int n)
{
  float result = 0.0f;

  _asm
  {
    mov esi,data
    mov ecx,n
    fldz
    fldz
l1:
    fsubr [esi]
    add esi,4
    fld st(0)
    fadd st(0),st(2)
    fld st(0)
    fsub st(0),st(3)
    fsub st(0),st(2)
    fstp st(2)
    fstp st(2)
    loop l1
    fstp result
    fstp result
  }

  return result;
}

int main (int, char **)
{
  int count = 1000000;

  float *source = new float [count];

  for (int i = 0 ; i < count ; ++i) {
    source [i] = static_cast <float> (rand ()) / static_cast <float> (RAND_MAX);
  }

  LARGE_INTEGER start, mid, end;

  float sum1 = 0.0f, sum2 = 0.0f;

  QueryPerformanceCounter (&start);

  sum1 = KahanSum (source, count);

  QueryPerformanceCounter (&mid);

  sum2 = AsmSum (source, count);

  QueryPerformanceCounter (&end);

  cout << "  C code: " << sum1 << " in " << (mid.QuadPart - start.QuadPart) << endl;
  cout << "asm code: " << sum2 << " in " << (end.QuadPart - mid.QuadPart) << endl;

  return 0;
}

Und einige Zahlen von meinem PC, auf dem ein Standard-Release-Build läuft * :

  C code: 500137 in 103884668
asm code: 500137 in 52129147

Aus Interesse habe ich die Schleife mit einem dec/jnz ausgetauscht, und es machte keinen Unterschied bei den Zeiten - manchmal schneller, manchmal langsamer. Ich schätze, dass der speicherbegrenzte Aspekt andere Optimierungen in den Schatten stellt. (Anmerkung des Herausgebers: Wahrscheinlich ist der FP-Latenz-Engpass ausreichend, um die zusätzlichen Kosten für loop . Wenn man zwei Kahan-Summen parallel für die ungeraden/geraden Elemente durchführt und diese am Ende addiert, könnte man dies vielleicht um einen Faktor 2 beschleunigen).

Ups, ich habe eine etwas andere Version des Codes ausgeführt und die Zahlen falsch herum ausgegeben (d.h. C war schneller!). Ich habe das korrigiert und die Ergebnisse aktualisiert.

Answer 4

Ohne ein konkretes Beispiel oder einen Profiler-Beweis anzuführen, kann man einen besseren Assembler als den Compiler schreiben, wenn man mehr weiß als der Compiler.

Im Allgemeinen weiß ein moderner C-Compiler viel mehr darüber, wie der betreffende Code zu optimieren ist: Er weiß, wie die Pipeline des Prozessors funktioniert, er kann versuchen, Anweisungen schneller umzuordnen als ein Mensch, und so weiter - das ist im Grunde dasselbe wie ein Computer, der genauso gut oder besser ist als der beste menschliche Spieler bei Brettspielen usw., einfach weil er die Suche im Problemraum schneller durchführen kann als die meisten Menschen. Auch wenn Sie theoretisch in einem bestimmten Fall genauso gut wie der Computer sein können, können Sie es sicherlich nicht mit der gleichen Geschwindigkeit tun, was es für mehr als ein paar Fälle undurchführbar macht (d.h. der Compiler wird Sie mit Sicherheit übertreffen, wenn Sie versuchen, mehr als ein paar Routinen in Assembler zu schreiben).

Andererseits gibt es Fälle, in denen der Compiler nicht so viele Informationen hat - ich würde sagen, vor allem bei der Arbeit mit verschiedenen Formen externer Hardware, von denen der Compiler keine Kenntnis hat. Das Hauptbeispiel sind wahrscheinlich Gerätetreiber, bei denen ein Assembler in Verbindung mit dem Wissen eines Menschen über die betreffende Hardware bessere Ergebnisse liefern kann, als ein C-Compiler es könnte.

Andere haben spezielle Anweisungen erwähnt, die ich im obigen Absatz anspreche - Anweisungen, von denen der Compiler möglicherweise nur begrenzte oder gar keine Kenntnis hat, was es einem Menschen ermöglicht, schnelleren Code zu schreiben.

Answer 5

In meinem Beruf gibt es drei Gründe, warum ich die Montage kennen und anwenden muss. In der Reihenfolge ihrer Wichtigkeit:

1. Debugging - Ich erhalte oft Bibliothekscode mit Fehlern oder unvollständiger Dokumentation. Ich finde heraus, was er tut, indem ich auf der Baugruppenebene einsteige. Das muss ich etwa einmal pro Woche tun. Ich verwende es auch als Werkzeug zum Debuggen von Problemen, bei denen meine Augen den idiomatischen Fehler in C/C++/C# nicht erkennen können. Mit einem Blick auf die Baugruppe lässt sich das umgehen.

2. Optimierung - der Compiler optimiert recht gut, aber ich spiele in einer anderen Liga als die meisten. Ich schreibe Bildverarbeitungscode, der in der Regel mit einem Code beginnt, der wie folgt aussieht:

   for (int y=0; y < imageHeight; y++) {
       for (int x=0; x < imageWidth; x++) {
          // do something
       }
   }

   Der "etwas tun"-Teil findet in der Regel in der Größenordnung von mehreren Millionen Mal statt (d. h. zwischen 3 und 30). Durch die Einsparung von Zyklen in dieser Phase des "etwas tun" werden die Leistungsgewinne enorm vergrößert. Normalerweise fange ich nicht damit an, sondern schreibe zuerst den Code, der funktionieren soll, und tue dann mein Bestes, um den C-Code so umzugestalten, dass er von Natur aus besser ist (besserer Algorithmus, weniger Last in der Schleife usw.). Normalerweise muss ich Assembler lesen, um zu sehen, was vor sich geht, und selten muss ich ihn schreiben. Ich mache das vielleicht alle zwei oder drei Monate.

3. etwas zu tun, was mir die Sprache nicht erlaubt. Dazu gehören die Prozessorarchitektur und spezifische Prozessoreigenschaften, der Zugriff auf Flags, die sich nicht in der CPU befinden (Mann, ich wünschte wirklich, man könnte in C auf das Carry-Flag zugreifen), usw. Ich mache das vielleicht einmal im Jahr oder in zwei Jahren.