Inline-Assembler

Ethon

Lies dich mal hier durch: http://www.agner.org/optimize/

Als Beispiel könntest du dir die optimierten Versionen von memcpy etc ansehen, die mit den 128bit-Registern kopieren usw.

NEO.PIXEL

@ Ethon:
So was hatte ich gesucht..
Danke

@ abc.w
Also wäre es bei xchg sinnvoll beide Variablen ins Register zu laden und dann
erst zu tauschen?
Und seit wann ist unsigned int == 32bit? Oder was meinst du damit?

abc.w

NEO.PIXEL schrieb:

Also wäre es bei xchg sinnvoll beide Variablen ins Register zu laden und dann erst zu tauschen?

Ob sinvoll ist - weiß ich nicht. Man könnte auch einfach so was machen:

mov ax, a
mov bx, b
mov b, ax
mov a, bx

Am Besten selber messen und vergleichen. Lesen, was andere dazu meinen oder welche Erfahrungen sie damit gemacht haben, bei sich ausprobieren und wieder vergleichen. Das sinnvollste ist auf jeden Fall, mehrere Möglichkeiten implementieren, messen und vergleichen. Dann lässt sich aussagen, ob etwas schneller ist oder nicht.

NEO.PIXEL schrieb:

Und seit wann ist unsigned int == 32bit? Oder was meinst du damit?

Ach so, meinst du sizeof(unsigned int) ist bei deinem Compiler 2 Bytes? Habe ich noch nie gesehen... ich würde sagen, benutze am Besten uint16_t oder füge in deinem Code so was wie:

typedef char check_for_unsigned_int[(sizeof(unsigned int) == 2) ? 1 : -1];

damit der Code nicht baut und man auf diesen Umstand gleich aufmerksam wird, wenn jemand den Code portieren soll... aber andererseits verwendest du Inline-Assembler und damit ist dein Code bereits auf deinen Compiler festgenagelt, also nicht mehr portabel und so gesehen, macht es keinen Sinn, irgendwelche Checks einzubauen oder sich über Datentypen Gedanken zu machen...

NEO.PIXEL

Ok unsigned int ist tatsächlich 4 Byte groß.. Mein Fehler

Hab dann jetzt einfach mal versucht mit den mir bekannten Mitteln selbst nachzumessen:

#include <iostream>
#include <ctime>

inline void swap_cpp(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

inline void swap_mov(int& a, int& b)
{
  asm volatile("mov ecx, eax\n\t"
	       "mov eax, ebx\n\t"
	       "mov ebx, ecx"
	       :"=a"(a), "=b"(b)
	       :"a"(a), "b"(b));
}

inline void swap_xchg(int& a, int& b)
{
  asm volatile("xchg eax, ebx" : "=a"(a), "=b"(b) : "a"(a), "b"(b));
}

inline void show(const char* c, clock_t& s, clock_t& e)
{
  std::cout<<c
	   <<":\t\t"
	   <<(e-s)/(0.001*CLOCKS_PER_SEC)
	   <<" ms"
	   <<std::endl;
}

int main(void)
{
  int a = 789, b = -987;
  clock_t start, end;
  const unsigned L = 1e8;

  start = clock();
  for(unsigned i = 0; i < L; i++)	swap_cpp(a, b);
  end = clock();
  show("swap_cpp", start, end);

  start = clock();
  for(unsigned i = 0; i < L; i++)	swap_mov(a, b);
  end = clock();
  show("swap_mov", start, end);

  start = clock();
  for(unsigned i = 0; i < L; i++)	swap_xchg(a, b);
  end = clock();
  show("swap_xchg", start, end);

  return 0;
}

Ergebnis:

swap_cpp: 2210 ms
swap_mov: 2520 ms
swap_xchg: 2490 ms

Womit der Compiler (gcc version 4.5.2, Ubuntu) klar gewonnen hat
Aber xchg scheint, sofern beide Variablen im Register, schneller zu sein als mov..

Pikkolini

Der Compiler ist eigentlich sehr oft besser als der Otto-Normal-Programmierer

void swap(int a, int b) {
	int temp = a;
	a = b;
	b = temp;
}

int main()
{
	int a = 42;
	int b = 23;
	swap(a,b);
	std::cout << a << b << std::endl;
	return 0;
}

Bei diesem Code wird das swap z.B. einfach wegoptimiert und der Compiler macht aus
std::cout << a << b << std::endl;
einfach
std::cout << b << a << std::endl;
Und das schaffste mit Inline-Assembler in dieser Form (mit meinen Kentnissen) nicht.

abc.w

NEO.PIXEL schrieb:

Ergebnis: ...
Womit der Compiler (gcc version 4.5.2, Ubuntu) klar gewonnen hat
Aber xchg scheint, sofern beide Variablen im Register, schneller zu sein als mov..

Ich würde jetzt noch mit ein Paar Compiler-Optionen rumspielen: -Os, -O2, -O3. Dann noch immer schön -g0 verwenden. Dann immer Warnungen einschalten: -Wall -Wextra -Werror -pedantic...

g++ main.cpp -o main -Os -g0 -Wall -Wextra -Werror -pedantic
g++ main.cpp -o main -O2 -g0 -Wall -Wextra -Werror -pedantic
g++ main.cpp -o main -O3 -g0 -Wall -Wextra -Werror -pedantic

Pikkolini schrieb:

void swap(int a, int b) {
	int temp = a;
	a = b;
	b = temp;
}

...

Ih glaube, du hast dich vertippt... Diese swap-Funktion wird natürlich wegoptimiert, weil sie nichts zurückgibt und im Prinzip nichts wirklich verändert...

NEO.PIXEL

Hab mal mit den Compileroptionen rumgespielt..

Ergebnis nach Weiteroptimieren mit -Os, -O2, -O3:

swap_cpp: 250 ms
swap_mov: 270 ms
swap_xchg: 690 ms

Jetzt ist xchg tatsächlich mit Abstand am langsamsten..

camper

Optimierungen dieser Art sind... keine.
Die einzig brauchbare Form von Assembler-swap sieht so aus (ist zudem sehr portabel):

void swap(int& a, int& b)
{
    asm( "" : "=x" (a), "=x" (b) : "1" (a), "0" (b));
}

Besser als normaler Dreickstausch ist das allerdings ebenso nicht.

volkard

NEO.PIXEL schrieb:

inline void swap_mov(int& a, int& b)
{
  asm volatile("mov ecx, eax\n\t"
	       "mov eax, ebx\n\t"
	       "mov ebx, ecx"
	       :"=a"(a), "=b"(b)
	       :"a"(a), "b"(b));
}

Das kettet die drei movs leider direkt aneinander und der Compiler traut sich nicht, über Deinen Code nachzudenken, und ihn mit seinem zu vermischen und vielleicht was dazuwischenzumachen, was gerade vom Pipeline-Füllen oder Sprungzielausrichten oder so ihm gerade am besten passen würde, oder vielleicht braucht er eax und ebx für was besseres und hätte esi und edi gerade frei?

Generell versuche ich, dem Compiler maximale Freiheit zu lassen.

cfoobar

Ich hab da mal eine Frage an die Experten hier. Ist es tatsächlich so dass der Compiler besser optimiert auch wenn man per Hand mit SSE etc arbeitet?

Ich beschäftige mich mit Grafikprogrammierung und daher auch ein wenig mit der Mathematik dahinter. Wenn ich da irgendwelche Matrizenoperationen oder z.B. nen schnellen Sinus per Polynom oder Taylorreihe annähere, dann lese ich oft auch was über SSE-Optimierungen in Assembler.

Ich habe seit dem C64 und Amiga nix mehr mit Assembler gemacht, aber ich meine gelesen zu haben dass man mit SSE so Rechnungen wie Addition und Multiplikation in einem Rutsch machen kann?

Gruß Chris

padreigh

Mich wundert diese Assembler Interesse etwas - der Compiler macht doch auch nichts anderes als Assembler. Der wird wohl kaum Additionen und so in fünf Schritten machen ... Ich stand bisher auf dem Standpunkt das Assembler nur nützt wenn man Insiderwissen hat oder wirklich auf 99.8% statt 99.437% Performance aus ist? Und wenn man nicht misst oder deassembliert landet man schnell bei 99.02% weil man was weniger schlau macht als der Compiler? _Gerade_ für Grafikzeug, wäre es da nicht vorteilhafter wenn man immer wiederkehrende Rechnungn auf der GPU ausführt statt die CPU mit eigenem Assembler besser auslasten zu wollen?

Tachyon

NEO.PIXEL schrieb:

SeppJ schrieb:

(Dir ist hoffentlich bewusst, dass dies nicht der einzige Einsatzzweck von Inlineassembler ist. Inlineassembler an sich ist schon noch äußerst wichtig)

Was denn z.B.?

Ich arbeite in einer Anwendung mit Fixed-Point-Arithmetik, und muss dort häufig Float-Werte in Fixed-Werte überführen (runden, nicht abschneiden). Das geht unter POSIX-Systemen wunderbar mit lrint . Unter Windows gibt es leider kein lrint . +0.5 und dann casten ist grausam langsam (die Funktion wird im Code extrem häufig ausgeführt). Daher benutze ich unter Windows folgendes kleines asm dafür:

inline long round(float val)
{
    long result;
    _asm
    {
        fld val
        fistp result
    }
    return result;
}

Das hat ca. 350% Zuwachs (auf einem Pentium M) an Leistung gebracht.

Edit: Wobei ich gerade sehe, dass dies bei MSVC 2008 wohl auch überflüssig ist. Da wird __ftol2_sse für die Konvertierung mittels Cast benutzt..

abc.w

camper schrieb:

Die einzig brauchbare Form von Assembler-swap sieht so aus (ist zudem sehr portabel):
void swap(int& a, int& b)
{
    asm( "" : "=x" (a), "=x" (b) : "1" (a), "0" (b));
}

Portabel

# g++ -c tmp.c
tmp.c: In function `void swap(int&, int&)':
tmp.c:3: error: impossible constraint in `asm'

Toll

camper

abc.w schrieb:

camper schrieb:
Die einzig brauchbare Form von Assembler-swap sieht so aus (ist zudem sehr portabel):
void swap(int& a, int& b)
{
    asm( "" : "=x" (a), "=x" (b) : "1" (a), "0" (b));
}
Portabel

Jedenfalls funktioniert es ohne Anpassung auf jeder Plattform, die von gcc unterstützt wird, da ja die Anweisung selbst keine Code emittiert.

abc.w schrieb:

# g++ -c tmp.c
tmp.c: In function `void swap(int&, int&)':
tmp.c:3: error: impossible constraint in `asm'

Toll

Falscher Code oder falscher Compiler. gcc-4.5.2 schluckt es und macht auch das Richtige damit. Die Fehlermeldung ist jedenfalls verdächtig unwahrscheinlich.

cfoobar

padreigh schrieb:

Mich wundert diese Assembler Interesse etwas - der Compiler macht doch auch nichts anderes als Assembler. Der wird wohl kaum Additionen und so in fünf Schritten machen ... Ich stand bisher auf dem Standpunkt das Assembler nur nützt wenn man Insiderwissen hat oder wirklich auf 99.8% statt 99.437% Performance aus ist? Und wenn man nicht misst oder deassembliert landet man schnell bei 99.02% weil man was weniger schlau macht als der Compiler? _Gerade_ für Grafikzeug, wäre es da nicht vorteilhafter wenn man immer wiederkehrende Rechnungn auf der GPU ausführt statt die CPU mit eigenem Assembler besser auslasten zu wollen?

Das Assemblerinteresse ist halt noch von früher da, dort habe ich so kleine Grafikdemos programmiert und da ging ohne Assembler gar nix. Das war aber auch nicht sonderlich schlimm, man hatte nur mehr Tipparbeit, aber von der Sprache her habe ich die Grundlagen nie wieder zu schnell lernen können, wie die von Assembler

Ne mir ist schon klar, dass man heute das kaum noch braucht, und die Compiler da bestimmt viel besser optimieren wie ich. Bei meinen Recherchen nach Algorithmen und deren Implementierung, bin ich halt immer wieder auf Funktionen mit Inline-Assembler gestoßen, also denke ich mir dass sich da doch noch eine Menge optimieren läßt. Ich glaube bei denen ging es auch nicht um ein paar Prozent, sondern gleich um 30% oder noch mehr.

Da ich einen Software-Renderer unter Windows schreiben will, brauche ich keine programmierbare GPU oder ein GUI-Framework das portabel ist. Da reicht C und WinAPI völlig aus, es dient eh nur meiner eigenen Neugier.

Gruß Chris

camper

abc.w schrieb:

# g++ -c tmp.c
tmp.c: In function `void swap(int&, int&)':
tmp.c:3: error: impossible constraint in `asm'

Toll

falscher Code. Es muss =g heißen.

inline void swap_rename(int& a, int& b)
{
  asm ("" : "=g"(a), "=g"(b) : "1"(a), "0"(b));
}

Mit NEOs Messroutine erhalte ich damit folgende Werte:

swap_cpp:               490 ms
swap_mov:               580 ms
swap_xchg:              580 ms
swap_rename:            480 ms

ohne Optimierung.

swap_cpp:               80 ms
swap_mov:               140 ms
swap_xchg:              110 ms
swap_rename:            0 ms

Mit -O2.

swap_cpp:               0 ms
swap_mov:               70 ms
swap_xchg:              80 ms
swap_rename:            0 ms

Mit -O2 und -funroll-loops.

NEO.PIXEL

Was ist jetzt der Unterschied von swap_rename zu swap_mov und swap_xchg?
Was passiert da genau?

camper

NEO.PIXEL schrieb:

Was ist jetzt der Unterschied von swap_rename zu swap_mov und swap_xchg?
Was passiert da genau?

Ich habe mal den Testcode etwas geändert, und mit einer realistischeren Anwendung (bubble-sort) kombiniert. Außerdem das clobber-Register für swap_mov hinzugefügt:

#include <iostream>
#include <algorithm>
#include <ctime>

#ifdef NOINLINE
void swap_cpp(int& a, int& b) __attribute__ ((noinline));
void swap_mov(int& a, int& b) __attribute__ ((noinline));
void swap_xchg(int& a, int& b) __attribute__ ((noinline));
void swap_rename(int& a, int& b) __attribute__ ((noinline));
#endif

void swap_cpp(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

void swap_mov(int& a, int& b)
{
    asm (
        "movl %%eax, %%ecx\n\t"
        "movl %%edx, %%eax\n\t"
        "movl %%ecx, %%edx\n\t"
           : "+a"(a), "+d"(b)
           :: "%ecx" );
}

void swap_xchg(int& a, int& b)
{
    asm (
        "xchgl %0, %1"
      : "+r"(a), "+r"(b) );
}

void swap_rename(int& a, int& b)
{
    asm (
        "## foo\n\t## bar"
      : "=rm"(a), "=rm"(b)
      : "1"(a), "0"(b) );
}

inline void show(const char* c, clock_t& s, clock_t& e)
{
    std::cout << c << ":\t\t" << (e-s)/(0.001*CLOCKS_PER_SEC) << " ms\n";
}

#define SORT(begin, end,f) \
    for ( int* p = end; p-- != begin; ) \
    { \
        for ( int* q = begin; q < p; ++q ) \
        { \
            if ( q[ 1 ] < q[ 0 ] ) \
                f( q[ 0 ], q[ 1 ] ); \
        } \
    } \

void fill(int* begin, int* end)
{
    for ( int i = end - begin ; begin != end; )
        *begin++ = --i;
}

int main()
{
    const unsigned L = 5e4;
    int* begin = new int[L];
    int* end = begin + L;
    clock_t c_start, c_end;

#define MEASURE(f) \
    fill( begin, end ); \
    c_start = clock(); \
    SORT( begin, end, f ); \
    c_end = clock(); \
    show( #f, c_start, c_end );

    MEASURE( std::swap )
    MEASURE( swap_cpp )
    MEASURE( swap_mov )
    MEASURE( swap_xchg )
    MEASURE( swap_rename )
    MEASURE( std::swap )

    delete [] begin;
    return 0;
}

Mit

g++ test.cpp -O3 --unroll-loops -march=atom -DNOINLINE -save-temps

übersetzt (4.5.2 gentoo 64-bit), sehen die Swapfunktionen so aus:

swap_cpp            swap_mov               swap_xchg               swap_rename
.cfi_startproc      .cfi_startproc         .cfi_startproc          .cfi_startproc
movl (%rdi), %eax   movl (%rdi), %eax      movl (%rdi), %edx       movl    (%rdi), %eax
movl (%rsi), %edx   movl (%rsi), %edx      movl (%rsi), %eax       movl    (%rsi), %edx
                    # 26 "test.cpp" 1      # 33 "test.cpp" 1       # 41 "test.cpp" 1
                        movl %eax, %ecx        xchgl %edx, %eax        ## foo
                        movl %edx, %eax                                ## bar
                        movl %ecx, %edx
                    # 0 "" 2               # 0 "" 2                # 0 "" 2
movl %edx, (%rdi)   movl %eax, (%rdi)      movl %edx, (%rdi)       movl    %edx, (%rsi)
movl %eax, (%rsi)   movl %edx, (%rsi)      movl %eax, (%rsi)       movl    %eax, (%rdi)
ret                 ret                    ret                     ret
.cfi_endproc        .cfi_endproc           .cfi_endproc            .cfi_endproc

Wie man leicht erkennt, erzeugen swap_cpp und swap_rename hier optimalen Code. Der Grund dafür liegt auf der Hand: sofern nicht die gesamte Assembleranweisung wegoptimiert wird, erzeugt sie immer zweierlei Art von Code: einmal den eigentlich explizit spezifizierten, als auch einen Prolog/Epilog um die angegebenen Ein-/Ausgabeoperanden in das Programm zu integrieren. Letzteres kann durch den Compiler optimiert werden (der weiß was dieser Code tut), zudem wird er möglicherweise kürzer oder ganz überflüssig, je weniger streng die angegeben constraints sind.
Liegt etwa ein Eingabeargument ohnehin zunächst einmal irgendwo im Speicher vor und ist ein Speicheroperand zulässig, so können irgenwelche mov-Befehle bzgl. dieses Operanden ganz vermieden werden. Dieser zusätzliche vom Compiler generierte Code is prinzipiell nicht zu vermeiden, und je kürzer der eigentliche Assemblercode ist, umso mehr fällt dieser Overhead ins Gewicht. Das ist einer der Hauptgründe, weshalb die Verwendung von inline-Assembler für elementare Funktionen in aller Regel keinen Gewinn bringt.

Bei anderen Formen von inline-Assembler (ms vc++ u.ä.) können keine Constraints angegeben werden und der Compiler hat ein rudimentäres Verständis für die verwendeten Assemblerbefehle. Das hat zwei Effekte: der zusätzlich erzeugte Code beschränkt sich im Grunde auf das Sichern und Wiederherstellen von Registerinhalten (daraus folgt dann auch, dass diesbzgl. kaum Optimierungspotential existiert) und der selbst geschriebene Code, soweit er von irgendwelchen Parametern abhängt, ist regelmäßig weniger effizient.