Was ist ein Beispiel für eine einfache C-Funktion, die schneller in der Inline-Montage implementiert wird?

Question

Ich habe es schwer, meinen Compiler mit Inline-Assembly zu schlagen.

Was sind gute, nicht erfundene Beispiele für eine Funktion, die der Compiler wirklich wirklich schnell und einfach macht? Aber das ist relativ einfach mit Inline-Montage zu machen.

Answer 1

Da es mit dem iPhone und Assemblercode zusammenhängt, gebe ich ein Beispiel, das in der iPhone Welt relevant wäre (und nicht irgendeines sse oder x86 asm). Wenn jemand beschließt, Assembler-Code für eine echte Welt-App zu schreiben, dann wird dies höchstwahrscheinlich eine Art digitale Signalverarbeitung oder Bildmanipulation sein. Beispiele: Umwandeln des Farbraums von RGB-Pixeln, Kodieren von Bildern in das JPEG/PNG-Format oder Kodieren von Tönen in mp3, amr oder g729 für voip-Anwendungen. Im Fall von Sound-Encoding gibt es viele Routinen, die vom Compiler nicht in effizienten Asm-Code übersetzt werden können, sie haben einfach kein Äquivalent in C. Beispiele für die gebräuchlichsten Dinge in der Soundverarbeitung: gesättigte Mathematik, Multiply-Accumulate-Routinen, Matrixmultiplikation .

Beispiel für gesättigte hinzufügen: 32-Bit vorzeichenbehaftete Int hat Bereich: 0x8000 0000 < = int32 < = 0x7fff ffff. Wenn Sie zwei Ints hinzufügen, könnte das Ergebnis überlaufen, aber dies könnte in bestimmten Fällen in der digitalen Signalverarbeitung inakzeptabel sein. Grundsätzlich, wenn Ergebnis Überlauf oder Unterlauf gesättigt add sollte 0x8000 0000 oder 0x7fff ffff zurückgeben. Das wäre eine vollständige c-Funktion, um das zu überprüfen. eine optimierte Version von gesättigten Add könnte sein:

 
int saturated_add(int a, int b) 
{ 
    int result = a + b; 

    if (((a^b) & 0x80000000) == 0) 
    { 
     if ((result^a) & 0x80000000) 
     { 
      result = (a < 0) ? 0x80000000 : 0x7fffffff; 
     } 
    } 
    return result; 
} 

Sie auch mehrere haben kann, wenn/sonst für Überlauf oder auf x86 zu überprüfen, können Sie Überlauf-Flag überprüfen (die auch Sie asm zu verwenden, erfordert). iPhone benutzt Armv6 oder v7 CPU, die dsp asm haben. Die Funktion saturated_add mit mehreren Brunchs (if/else-Anweisungen) und zwei 32-Bit-Konstanten könnte also eine einfache asm-Anweisung sein, die nur einen CPU-Zyklus verwendet. So einfach saturated_add asm Anweisung verwenden könnte gesamten Algorithmus zwei-dreimal schneller machen (und kleiner in der Größe). Hier ist die Qadd Handbuch: QADD

andere Beispiele von Code, der oft in langen Schleifen ausgeführt sind

 
res1 = a + b1*c1; 
res2 = a + b2*c2; 
res3 = a + b3*c3; 

wie nichts scheint hier nicht optimiert werden, sondern auf ARM-CPU können Sie bestimmte dsp Anweisungen verwenden, die nimm weniger Zyklen als einfache Multiplikation! Das stimmt, a + b * c mit bestimmten Anweisungen könnte schneller ausgeführt werden als einfach a * b. Für diese Art von Fällen können Compiler die Logik Ihres Codes einfach nicht verstehen und diese dsp-Anweisungen nicht direkt verwenden. Deshalb müssen Sie asm manuell schreiben, um den Code zu optimieren, ABER Sie sollten nur einige Teile des Codes manuell schreiben, die es sein müssen optimiert. Wenn Sie anfangen, einfache Loops manuell zu schreiben, werden Sie mit Sicherheit den Compiler nicht schlagen! Es gibt mehrere gute Papiere im Internet für die Inline-Assemblierung, um Tannenfilter, amr Codierung/Decodierung etc.

Answer 2

Mein bestes Ergebnis gegenüber einem Compiler war eine einfache Memcpy-Routine ... Ich überspringe viele grundlegende Setup-Sachen (zB brauchte ich nicht viel von einem Stack-Frame, also spare ich ein paar Zyklen dort), und machte ein paar ziemlich haarige Sachen.

Das war vor etwa 6 Jahren, mit einigen proprietären Compiler von unbekannter Qualität. Ich muss den Code, den ich hatte, ausgraben und es jetzt gegen GCC versuchen; Ich weiß nicht, dass es schneller gehen könnte, aber ich würde es nicht ausschließen.

Am Ende, obwohl mein Memcpy durchschnittlich 15x schneller war als das in unserer C-Bibliothek, behielt ich es einfach in meiner Gesäßtasche, für den Fall, dass ich es brauchte. Es war ein Spielzeug für mich, mit PPC Montage zu spielen, und der Geschwindigkeitsschub war in unserer Anwendung nicht notwendig.

Answer 3

Wenn Sie Dinge wie SIMD-Operationen tun wollen, können Sie vielleicht einen Compiler schlagen. Dies erfordert jedoch gute Kenntnisse der Architektur und des Anweisungssatzes.

Answer 4

Wenn Sie nicht SIMD-Operationen betrachten Betrug, können Sie in der Regel SIMD Assembly schreiben, die als Ihre Compiler autovectorization Fähigkeiten viel besser abschneidet (Wenn es noch autovectorization hat!)

Here's ein sehr einfaches SSE (Einer von x86 des SIMD Befehlssätze) Tutorial. Es ist für Visual C++ In-Line-Assembly.

Edit: Hier ist ein kleines Paar von Funktionen, wenn Sie es selbst ausprobieren wollen. Es ist die Berechnung eines N-Längen-Punktprodukts. Man verwendet SSE-2-Anweisungen in-line (GCC-Inline-Syntax), das andere ist sehr einfach C.

Es ist sehr sehr einfach und ich wäre sehr überrascht, wenn ein guter Compiler die einfache C-Schleife nicht vektorisieren könnte , aber wenn nicht, solltest du eine Beschleunigung in der SSE2 sehen. Die SSE 2-Version könnte wahrscheinlich schneller sein, wenn ich mehr Register verwende, aber ich möchte meine sehr schwachen SSE-Fähigkeiten nicht dehnen :).

float dot_asm(float *a, float*b, int n) 
{ 
    float ans = 0; 
    int i; 
    // I'm not doing checking for size % 8 != 0 arrays. 
    while(n > 0) { 
    float tmp[4] __attribute__ ((aligned(16))); 

    __asm__ __volatile__(
      "xorps  %%xmm0, %%xmm0\n\t" 
      "movups  (%0), %%xmm1\n\t" 
      "movups  16(%0), %%xmm2\n\t" 
      "movups  (%1), %%xmm3\n\t" 
      "movups  16(%1), %%xmm4\n\t" 
      "add  $32,%0\n\t" 
      "add  $32,%1\n\t" 
      "mulps  %%xmm3, %%xmm1\n\t" 
      "mulps  %%xmm4, %%xmm2\n\t" 
      "addps  %%xmm2, %%xmm1\n\t" 
      "addps  %%xmm1, %%xmm0" 
      :"+r" (a), "+r" (b) 
      : 
      :"xmm0", "xmm1", "xmm2", "xmm3", "xmm4"); 

    __asm__ __volatile__(
     "movaps  %%xmm0, %0" 
     : "=m" (tmp) 
     : 
     :"xmm0", "memory");    

    for(i = 0; i < 4; i++) { 
     ans += tmp[i]; 
    } 
    n -= 8; 
    } 
    return ans; 
} 

float dot_c(float *a, float *b, int n) { 

    float ans = 0; 
    int i; 
    for(i = 0;i < n; i++) { 
    ans += a[i]*b[i]; 
    } 
    return ans; 
} 

Answer 5

Sofern Sie eine assembly guru die Chancen zu schlagen, den Compiler sind sehr niedrig.

ein Fragment aus dem oben genannten Link,

Zum Beispiel war das Bit-orientierte "XOR % EAX,% EAX" -Anweisung der schnellste Weg, ein Register auf Null in den frühen Generationen zu setzen der x86, aber der meiste Code wird von Compiler und Compiler selten erzeugt generiert XOR-Anweisung. So ist die IA Designer, beschlossen, die häufig vorkommende Compiler erzeugten Anweisungen bis zu der Vorderseite des kombinatorischen Dekodierlogik macht die wörtliche „MOVL $ 0,% EAX“ Anweisung zu bewegen schneller ausgeführt als den XOR-Befehl.

Answer 6

Ich implementierte eine einfache Kreuzkorrelation mit einer generischen "Strait C" Implementierung. Und dann, als es länger dauerte als die Zeitscheibe, die ich zur Verfügung hatte, griff ich auf die explizite Parallelisierung des Algorithmus zurück und benutzte den intrinsischen Prozessor, um die spezifischen Anweisungen zu zwingen, in den Berechnungen verwendet zu werden. In diesem speziellen Fall wurde die Rechenzeit von> 30 ms auf etwas mehr als 4 ms reduziert. Ich hatte ein 15ms-Fenster, um die Verarbeitung abzuschließen, bevor die nächste Datenerfassung stattfand.

Dies war eine SIMD-Typ-Optimierung auf einem VLWI-Prozessor. Dies erfordert nur 4 oder so der Prozessor-Intrinsics, die im Grunde Assembler-Anweisungen sind, die den Anschein eines Funktionsaufrufs im Quellcode geben. Sie könnten das Gleiche mit der Inline-Assemblierung tun, aber die Syntax- und Registerverwaltung ist etwas besser mit Prozessor-Intrinsics.

Wenn es auf die Größe ankommt, ist der Assembler König. Ich ging mit einem Typen zur Schule, der einen Vollbild-Texteditor in weniger als 512 Bytes geschrieben hat.

Answer 7

Ich habe einen Prüfsummenalgorithmus, der erfordert, dass Wörter um eine bestimmte Anzahl von Bits gedreht werden. Zur Umsetzung es, habe ich dieses Makro bekam:

//rotate word n right by b bits 
#define ROR16(n,b) (((n)>>(b))|(((n)<<(16-(b)))&0xFFFF)) 

//... and inside the inner loop: 
sum ^= ROR16(val, pos); 

Visual Studio Release-Build dazu erweitert: (val in Axt ist, pos in dx ist, sum in bx)

mov   ecx,10h 
sub   ecx,edx 
mov   ebp,eax 
shl   ebp,cl 
mov   cx,dx 
sar   ax,cl 
add   esi,2 
or   bp,ax 
xor   bx,bp 

Je mehr effiziente äquivalente hand erzeugt Montage wäre:

mov  cl,dx 
ror  ax,cl 
xor  bx,ax 

I nicht herausgefunden haben, wie die Anweisung von ror reinen ‚c‘ emittieren Code. Jedoch ...
Während ich dies aufschrieb, erinnerte ich mich an Compiler-Intrinsik. Ich kann den zweiten Satz von Anweisungen mit erzeugen:

sum ^= _rotr16(val,pos); 

So ist meine Antwort: Auch wenn Sie denken, dass Sie die reinen C-Compiler schlagen können, überprüfen Sie die Spezifika vor der Montage Inline greifen zu müssen.