inline Fertigkeiten des compilers

Ichwerdennsonst

ich frage mich manchmal, wie gut der Compiler eine Funktion inline macht. Als Beispiel mal:

typedef struct __list {
    struct __list* next;
    struct __list* prev;
} list;
void list_remove(list* entry) {
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
}

void list_add(list* here, list* entry) {
    entry->next = here->next;
    entry->prev = here;

    here->next->prev = entry;
    here->next = entry;
}

void list_replace(list* eold, list* enew) {
    enew->next = eold->next;
    enew->prev = eold->prev;

    enew->next->prev = enew;
    enew->prev->next = enew;

    eold->next = eold;
    eold->prev = eold;
}

theoretisch könnten wir jetzt den code in list_replace ersetzten durch:

void list_replace(list* eold, list* enew) {
    list_add(eold,enew);
    list_remove(eold);
}

Das wäre übersichtlicher
Hätte aber einen Funktionsoverhead
Checkt der Compiler (z.B. gnu) das und macht das inline?
Oder sollte ich die inline Direktive verwenden?

Th69

Du kannst es einfach lokal mit der gcc-Option -S oder online mit dem C++ Compiler Explorer überprüfen (den entsprechenden C++ Compiler auswählen und schauen welcher Assemblercode dafür generiert wird - du kannst auch weitere Compileroptionen z.B. -O2 dort angeben).

Das Schlüsselwort inline sollte man nicht mehr zur Angabe der Optimierung verwenden, da es eine andere Bedeutung bekommen hat, s. inline specifier (unter "Explanation" ab "The original intent of the inline keyword...") - der deutsche Artikel zu inline hat leider noch die ursprüngliche Bedeutung beschrieben.

SeppJ

@Th69 sagte in inline Fertigkeiten des compilers:

Das Schlüsselwort inline sollte man nicht mehr zur Angabe der Optimierung verwenden, da es eine andere Bedeutung bekommen hat, s. inline specifier (unter "Explanation" ab "The original intent of the inline keyword...") - der deutsche Artikel zu inline hat leider noch die ursprüngliche Bedeutung beschrieben.

Auch wenn's ursprünglich im C++-Bereich gestellt wurde, ist wohl doch reines C gemeint vom Code her. Nicht das inline in C zwingend das bedeuten würde, dass die Funktion geinlined wird, aber das Verhalten bezüglich der Linkage hat subtile Unterschiede im Vergleich zu C++. Siehe die Erklärung für C in derselben Referenz: https://en.cppreference.com/w/c/language/inline

Tendenziell vertragen sich inlining und Pointer nicht so gut, besonders in C. Wenn du Th69s Rat folgst und ein bisschen herumspielst, wirst du sehen, dass ein optimierender Compiler zwar die Funktionen inlinen würde, aber der Code doch anders ausschaut, als wenn du die Funktionen selber inline schreibst. Das liegt an der Möglichkeit von Pointer Aliasing. Der Compiler muss hier annehmen, dass die Zeiger potentiell aufeinander zeigen könnten, und wenn man darüber Werte verändert, wird auf einmal die Reihenfolge der Operationen wichtig, und Optimierungen werden dadurch erschwert. Schau mal, was das restrict-Schlüsselwort macht (nur C, nicht C++, da in c++ nicht nötig). Die am besten optimierbarste Variante deines Codes sollte in diese Richtung gehen:

void list_replace(list* restrict eold, list* restrict enew) {
    list_add(eold,enew);
    list_remove(eold);
}

Vorausgesetzt, du kannst garantieren, dass hier kein Aliasing stattfindet. Wenn doch, dann passieren unerwartete Dinge.

hustbaer

@SeppJ sagte in inline Fertigkeiten des compilers:

Schau mal, was das restrict-Schlüsselwort macht (nur C, nicht C++, da in c++ nicht nötig).

Wieso sollte restrict in C++ nicht nötig sein? Da gibt's genau das selbe Problem, also dass der Compiler oft Optimierungen nicht machen kann, weil er nicht wissen kann ob Zeiger bzw. Referenzen vielleicht auf das selbe Objekt zeigen.

SeppJ

@hustbaer sagte in inline Fertigkeiten des compilers:

Wieso sollte restrict in C++ nicht nötig sein?

Weil ich die Aliasing-Regeln nicht mehr richtig im Kopf habe

Aber in C++ gibt's restrict halt nicht (außer als compilerspezifische Erweiterung).

hustbaer

Aber in C++ gibt's restrict halt nicht (außer als compilerspezifische Erweiterung).

Ja, das stimmt. Ist vielleicht schade. Oder auch nicht, ist halt eine Footgun weniger

Finnegan

@Ichwerdennsonst Ich habe aus Neugier mal Godbolt damit gefüttert.

Clang: https://godbolt.org/z/hPj5f6Gc9
GCC: https://godbolt.org/z/M1Tj1xn3Y

Wie erwartet inlinen beide Compiler die Funktionsaufrufe in der zweiten Variante von list_replace. Alles andere hätte mich bei einem solch noch relativ simplen Konstrukt gewundert.

Interessant ist allerdings, dass beide Compiler in der "manuellen inline"-Funktion anscheinend anders mit SIMD-Registern vektorisieren. Clang macht in der ersten Variante offenbar noch ein read/write von/aus einem 128-bit SIMD-Register währen die inline-variante nur auf 64-Bit-Registern arbeitet. GCC verwendet in beiden Varianten SIMD-Instruktionen, allerdings jeweils auf eine etwas andere Weise.

Was davon wirklich effizienter ist, kann man denke ich ohne Microbenchmark nicht wirklich sagen. Ich würde allerdings darauf tippen, dass es bei Speicher- Reads und Writes kein großer Unterschied ist, ob man einen mit 128 oder zwei mit 64 Bits macht. Außer vielleicht eine kürzere Instruktions-Sequenz, die den Instruction Cache etwas weniger belastet.

Generell würde ich empfehlen, zunächst vor allem gut lesbaren Code zu schreiben (die zweite Variante) und mir solche Gedanken erst ganz am Schluss machen. Und das auch nur dann, wenn das Programm überhaupt relevante CPU-Zeit in den betreffenden Codestellen verbringt.

Auch sollte man bezüglich Optimierung bei dem Beispiel vielleicht auch zuerst einmal fragen, ob eine verkettete Liste überhaupt eine geeignete Datenstruktur ist. Die sind nämlich meist nicht sehr cache-freundlich (je nachdem wie der Speicher für die Nodes alloziert wurde) und man fährt bis zu einer überraschend großen Anzahl von Elementen oft besser, wenn man auf einem zusammenhängenden Speicherbereich (Array/Vector) arbeitet. Selbst wenn fürs Einfügen und Löschen dahinter liegende Elemente im Speicher verschoben werden müssen.

Ichwerdennsonst

Danke euch und sorry, ich habe die Antworten gerade erst gesehen
der code ist c, die Frage ist aber eher auf C++ bezogen, also der Code dient nur als Beispiel für auch deutlich komplexere Fälle. Deshalb kannst du das wieder zurück in die C++ Abteilung schieben?
Übrigens ist der Code aus einem CTF, das ich gerade zur Hand hatte (und das einigermaßen veranschaulichend aussah), also habe ich so generell meine Zweifel, ob das eine gute Art ist eine Liste zu implementieren

Ichwerdennsonst

Meinst du, dass die meisten Compiler bei jeder Funktion genau hinschauen, ob inline sinnvoll ist, unabhängig von der Komplexität?
Und wenn ich -o3 (bei gnu) als Option habe?
Ein restrict für c++ gibt es nicht?
Ich finde den Code, der die Funktionen verschachtelt auch deutlich übersichtlicher. Es wäre halt schön, trotzdem den Funktionscall zu vermeiden.

SeppJ

@Ichwerdennsonst sagte in inline Fertigkeiten des compilers:

Meinst du, dass die meisten Compiler bei jeder Funktion genau hinschauen, ob inline sinnvoll ist, unabhängig von der Komplexität?

Der Compiler ist gewiss nicht zu faul. "oh, ich habe schon 20 Funktionen analysiert und es ist Freitag Nachmittag, den Rest mache ich mal so husch husch".

Was wichtiger ist, dass der Compiler auch die Möglichkeit haben muss, die Funktion zu inlinen. Das heißt, er muss den Code der Funktion auch kennen, wenn er zu den Stellen kommt, wo die Funktion benutzt wird. Sonst kann er den Code dort schließlich nicht einsetzen. Und deswegen hat das inline Schlüsselwort die Bedeutung die es hat, denn mit inline kann man Funktionen auch in Headern definieren, ohne Probleme mit doppelten Definitionen zu bekommen. So hat man dann an jeder Stelle, wo die Funktion genutzt wird, auch automatisch den Code vorliegen, und der Compiler kann tun was er für richtig hält.

Prinzipiell gibt es auch Techniken für verzögertes Inlining zur Linkzeit, aber da muss man sich schon sehr speziell für auskennen, um das zu nutzen, wohingegen inline in Headern Kinderkram ist.

Und wenn ich -o3 (bei gnu) als Option habe?

Was sollte dann sein? Worauf bezieht sich deine Frage?

Ein restrict für c++ gibt es nicht?

Offiziell nein, aber viele Compiler haben inoffizielle Erweiterungen, die das gleiche tun. Die nennen das dann oft __restrict__ oder ähnlich. Musst du gucken. Und abschätzen, ob es Portabilitätsprobleme wert ist.

Ich finde den Code, der die Funktionen verschachtelt auch deutlich übersichtlicher. Es wäre halt schön, trotzdem den Funktionscall zu vermeiden.

Die Bilanz aus dem Thread ist doch, dass der Compiler das relativ trivial inlinen kann!?

Ichwerdennsonst

@SeppJ sagte in inline Fertigkeiten des compilers:

Die Bilanz aus dem Thread ist doch, dass der Compiler das relativ trivial inlinen kann!?

Das würde ich auch so sehen

@SeppJ sagte in inline Fertigkeiten des compilers:

Was sollte dann sein? Worauf bezieht sich deine Frage?

Das ist die Optimierungsoption auf höchster Stufe. Meine Frage ist, ob damit nochmal sehr genau nachgeschaut wird, ob sich nicht doch noch eine Funktion zum inlinen eignet.