F
Sieht für mich bei grobem überfliegen einigermaßen okay aus für nen simplen Benchmark. Ich bin allerdings etwas unglücklich darüber, wie in deinem Code vermieden wird, dass der Compiler den gesamten Algorithmus via Constant Folding direkt zur Compile-Zeit ausführt. Ich denke das ist lediglich ein "Unfall" dass er nicht direkt die sortierten Arrays als "Compiler-Optimierung" erzeugt:
size_t arr[n];
Ein nicht-initialisiertes Array. Dessen Inhalt ist nicht für den Compiler vorhersehbar.
und
void fill(size_t a[])
{
for (size_t i = 0; i < n; i++)
{
a[i] = my_rand(i + a[0], 51);
}
}
Hier verwendest du einen solchen unvorhersehbaren Wert (a[0]) um einen Random-Seed zu berechnen (du kannst ja mal probeweise ein memset(arr, 0, sizeof(arr)); einbauen. Gut möglich dass das zu überraschenden Ergebnissen führt ).
Ich würde empfehlen, das etwas sauberer und besser reproduzierbar zu lösen, z.B. so:
volatile size_t seed = 123;
size_t random_value = seed;
void fill(size_t a[]) {
for (size_t i = 0; i < n; i++) {
random_value = my_rand(random_value, 51);
a[i] = random_value;
}
}
volatile macht hier seed effektiv zu so einem unvorhersehbaren Wert, indem es Compiler-Optimierungen verbietet, die annehmen, dass seed bei der Zuweisung immer noch den Wert 123 hat, auch wenn es tatsächlich immer noch 123 ist. Das verhindert im weiteren verlauf ebenfalls alle Optimierungen, die darauf aufbauen.
random_value = seed; vor jedem benchmark-Test zu setzen wäre auch nicht verkehrt. Das würde dafür sorgen, dass alle Algorithmen mit den selben Arrays arbeiten.
Nun zu den Benchmarks:
@Lennox sagte in Funktion optimieren:
Ich denke, für den Use-Case kann man selbst mit -O3 nicht mehr herausholen...
Ich hoffe deine benchmarks sind auch bereits alle mit -O3 kompiliert. Sonst sind die Ergebnisse nämlich wenig aussagekräftig. Bei `-O0" z.B. wäre es keine große Kunst den Compiler mit handgeschriebenem Assembler zu schlagen.
Zu dem Assembler-Code selbst kann ich nichts sagen. Ich finde AT&T-Syntax leider unlesbar und habe auch nicht den Nerv das komplett zu analysieren. Es sieht allerdings bereits von der Länge her umständlicher aus, als das was der Compiler vermutlich mit -O3 aus deinem zuerst geposteten Algorithmus macht: https://godbolt.org/z/9PGE7jdT8.
Vielleicht kannst du beschreiben, was deine Optimierungs-Ideen waren und sicherstellen, dass der Compiler die nicht ohnehin schon mit -O3 umsetzt.
Wenn dein Assembler-Code tatsächlich äquivalent ist und der C-Code mit -O3 kompiliert wurde und der benchmark auch konsistent einen Vorteil für deine Assembler-Implementierung ausweist (manchmal sind das auch Cache-Effekte oder der OS-Scheduler spielt da mit rein) dann würde mich auch interessieren, woran das liegt. Das wäre ja schon ein signifikanter Unterschied. Ich gehe aber erstmal davon aus, dass du wahrscheinlich nicht exakt das gemessen hast, was du eigentlich wolltest (fill ist unter anderem auch noch mit drin als Komponente in den Timings).
