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.