GCC Compiler-Optimierungen: Zerlegung eines Benchmarks

Die Idee zu diesem Beitrag stammt aus einem anderen Blogpost, in dem die Leistung eines kleinen Benchmarks in C, Go und Python verglichen wurde. Das überraschende Ergebnis in diesem Blog war, dass die Go-Implementierung viel besser abschnitt als die C-Version. Der Benchmark war ein einfaches Programm, das ein Kommandozeilenargument nahm und die Summe aller ganzen Zahlen bis zu diesem Argument berechnete. Ich wollte sehen, was los war, also habe ich versucht, es lokal auszuführen und tatsächlich, wenn es mit einem Parameter von 100.000.000 aufgerufen wurde, brauchte die C-Implementierung 0,259 Sekunden und die Go-Version nur 0,140 Sekunden. Die C-Version des Benchmarks sieht wie folgt aus: [code language="c"] #include <stdio.h> #include <stdio.h> #include <stdlib.h> main(int argc, char *argv[]) { int arg1 = 1; arg1 = atoi(argv[1]); long a; long sum = 0; /* für Schleifenausführung */ for( a = 0; a < arg1; a++ ) { sum += a; } printf("sum: %ldn", sum); return 0; } [/code] Im Blog wurde vorgeschlagen, einige Optimierungsflags für die Kompilierung des C-Programms zu verwenden, also habe ich es versucht: [code language="bash"] gcc -O3 bench.c -o bench -march=native [/code] Das O3-Flag weist gcc an, seine aggressivsten Optimierungsstrategien zu verwenden, und march=native weist ihn an, bei der Kompilierung in Maschinencode die Vorteile der lokalen CPU-Version zu nutzen. Dies hatte einen ziemlich dramatischen Effekt: Statt 0,259 Sekunden benötigte das gesamte Programm jetzt nur noch 0,001 Sekunden! Und der Wert blieb so niedrig, als ich den Parameter auf 1.000.000.000 erhöhte. Es scheint also, dass der Compiler unser Programm so umgeschrieben hat, dass es nur noch konstante Zeit benötigt.Um herauszufinden, was diese erstaunliche Beschleunigung verursacht hat, kompilierte ich erneut mit dem Flag -S, um den Assemblercode zu erhalten. Hier ist er, einschließlich einiger Kommentare, die die Anweisungen erklären: [code language="c"] .section __TEXT,__text,regular,pure_instructions .macosx_version_min 10, 10 .globl _main .align 4, 0x90 _main: ## @main .cfi_startproc ## BB#0: pushq %rbp Ltmp0: .cfi_def_cfa_offset 16 Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp2: .cfi_def_cfa_register %rbp movq 8(%rsi), %rdi callq _atoi ; Konvertiert das Argument in eine ganze Zahl, stellt das Ergebnis in ax xorl %esi, %esi testl %eax, %eax jle LBB0_2 ; Überspringen Sie die Berechnung, wenn ax 0 ist ## BB#1: ## %.lr.ph cltq ; die nächsten paar Zeilen stellen die for-Schleife dar: leaq -1(%rax), %rdx ; dx = ax - 1 leaq -2(%rax), %rcx ; cx = ax - 2 mulxq %rcx, %rcx, %rdx ; cx = cx * dx shldq $63, %rcx, %rdx ; dx = cx / 2 leaq -1(%rax,%rdx), %rsi ; si = dx + ax - 1 LBB0_2: leaq L_.str(%rip), %rdi ; fertig, wandelt das Ergebnis in einen String um xorl %eax, %eax callq _printf ; und drucken Sie es xorl %eax, %eax popq %rbp retq .cfi_endproc .section __TEXT,__cstring,cstring_literals L_.str: ## @.str .asciz "Summe: %ldn" .unterabschnitte_über_symbole [/code] Der Compiler hat die for-Schleife in eine einzige Berechnung umgewandelt: (ax - 1) * (ax-2) / 2 + ax - 1, die vereinfacht werden kann zu: ax * (ax + 1) / 2 Dies ist die bekannte Formel für eine Teilsumme einer arithmetischen Folge mit ax Elementen. Gcc hat erkannt, dass unsere Schleife in eine einzige Operation umgeschrieben werden kann! Außerdem werden unterwegs einige Mikrooptimierungen vorgenommen. Um zum Beispiel dx = ax - 1 zu berechnen, werden die Zeilen: [code language="c"] mov %rax, %rdx dec %rdx [/code] hätte den Zweck erfüllt. Der Compiler hat sich jedoch dafür entschieden, dies mit einer einzigen Anweisung zu tun: [code language="c"] leaq -1(%rax), %rdx [/code] Diese Anweisung war ursprünglich für die Manipulation von Adresszeigern mit Offsets gedacht, aber sie kann auch für einfache 64-Bit-Additionen verwendet werden. Auf modernen CPUs ist sie schneller als die beiden separaten Befehle und spart einen Befehl. Ein weiterer Compiler-Trick ist die folgende Zeile: [code language="c"] shldq $63, %rcx, %rdx [/code] Die Anweisung shld führt eine Linksverschiebung des zweiten Operanden rcx durch und die Überlaufbits werden in den dritten Operanden, rdx, verschoben. Durch die Linksverschiebung des 64-Bit-Registers rcx um 63 Positionen nach rdx wird effektiv eine Ganzzahldivision durch 2 an rcx durchgeführt, wobei das Ergebnis in rdx landet. Dies spart wieder einen Befehl, aber dieses Mal ist das Ergebnis genauso schnell wie das Verschieben von rcx nach rdx und die anschließende Division von rdx durch 2 (durch eine Rechtsverschiebung). Schlussfolgerung Die Schlussfolgerung: Es ist schwierig, einen angemessenen Benchmark zu schreiben, die Leistung von Sprachen zu vergleichen und moderne Compiler sind erstaunlich clever. Eine offene Frage bleibt für mich, welche Art von Algorithmus der Compiler verwendet, um die Art unserer for-Schleife zu erkennen. Verwendet er eine einfache Heuristik oder ist unsere for-Schleife ein Spezialfall einer allgemeinen Klasse von Schleifen, die vereinfacht werden können?