Der Stack Ist Dein Freund – Eine Nachbesprechung
Viele Leser haben uns gefragt, ob der Artikel „Der Stack ist dein Freund“ [1] ernst gemeint sei. Wir als aufklärende Bildungsorganisation im Bereich IT sehen uns zur Wahrheit verpflichtet, und selbstverständlich werden unsere Empfehlungen inhaltlich mehrfach durch unsere Fachexperten geprüft.
Auf unserer Seite machte sich nach derartigem Feedback eher Enttäuschung breit - Enttäuschung darüber, wie wenig Softwareentwickler heute noch über die Abläufe im Computer wissen. Um unsere Empfehlungen zu untermauern, haben wir ein Benchmarking arrangiert, um die alternativen zu unserer Empfehlung zu bewerten.
Unser Test-Setup⌗
Obwohl iccb.dev eine Non-Profit-Organisation ist, haben alle ehrenamtlichen Redakteure zusammengelegt und dabei weder Kosten noch Mühen gescheut. Mit ein wenig Stolz präsentieren wir unser Referenzsystem:
login@system:~> cat /proc/cpuinfo | grep 'model_name\|cpu_MHz\|cache\ \|MemTotal'
model name : Celeron (Coppermine)
cpu MHz : 567.879
cache size : 128 KB
MemTotal : 376328 kB
Unser Referenzsystem auf Linux-Basis hat eine CPU mit 567MHz mit 128kB Cache [2] und stolzen 384MB RAM - abzüglich Video-Buffer. Wir haben es also geschafft, aus den Spenden der ehrenamtlichen Redakteure ein System am Puls der Zeit zu bauen – inklusive einer Zeitreise ins Jahr 2001.
Selbstverständlich hätten wir lieber ein professionelles Windows-System bevorzugt. Aus uns unerklärlichen Gründen unterstützen aktuelle Windows-Versionen die uns zur Verfügung stehende Hardware heute nicht mehr. Auf unserer Hardware wird heute nur Linux unterstützt.
Wir wundern uns: warum hält jemand Software für solch einen Dinosaurier am Leben? Ist Open Source am Ende doch ein Hort von mittellosen Studenten in Selbsthilfe? Warum können sich vermeintlich schlaue Menschen, die sich in die relevante Linux-Entwicklung einmischen, keine halbwegs aktuellen Systeme leisten? Wird Linux von Menschen am Leben gehalten, die auf Grund ihrer mangelnden Qualifikation kaum ihre Miete zahlen können?
Wir haben daher bereits eine Sozialstudie über Contributer in Open Source gestartet, und wir sind gespannt auf die Ergebnisse.
Langsam ist nicht so schlimm⌗
Anfangs war die gesamte Redaktion bestürzt über das Test-Setup: Langsam, uralt, unprofessionelle Softwareumgebung. Nach einer Weile stellte sich jedoch ein Konsens ein: Wenn Software auf diesem PC-Misthaufen mit den im Artikel benannten Tricks relevant besser funktioniert, dann sollten wir das Ergebnis trotzdem publizieren! Wir haben also die Implementierungsalternativen nebeneinandergehalten. Und wir sind verblüfft.
Wie messen wir?⌗
Für die genaue Vermessung der Software benötigen wir ein besonders genaues Zeitinstrument. Seit geraumer Zeit hat x86 mit der RDTSC-Instruktion einen taktgenauen Zähler, der für unser Experiment ideal ist. Mit ein paar Intrinsics vermessen unseren Code wie folgt:
#include <x86intrin.h>
asm("CPUID") // clear pipeline etc.
int numCyclesAtStart = __rdtsc(); // start
// Code goes here
int numCyclesAtEnd = __rdtsc(); // end
int numCyclesForOverhead = __rdtsc() - numCyclesAtEnd; // measure the overhead
int cycles = numCyclesAtEnd – numCyclesAtStart – numCyclesForOverhead;
Wir sind uns bewusst, dass die Aufrufe von __rdtsc() einige CPU-Zyklen Overhead kosten. Wir implementieren den dritten Aufruf, um den Overhead zu vermessen. Für genauere Ergebnisse gibt es vom Prozessorhersteller Intel Anweisungen [3], wie man die zeitlichen Effekte von Out-of-Order-Execution und der Pipelines in den Griff bekommt. Unsere Hoffnung ist, dass die Ergebnisse so deutlich voneinander abweichen, dass die Restungenauigkeit unserer Messung vernachlässigbar ist.
Variante 1⌗
Zunächst versuchen wir es mit einem Struct auf dem Heap und Pointern:
typedef struct {
int a,b,c,d
} MyData;
MyData* init () {
return new MyData {7, 8, 9};
}
void calculate (MyData* d) {
d->d = d->a + d->b + d->c;
}
int main () {
MyData* data = init2();
calculate2(data);
}
Die Ausführung von main() auf unserem Referenzsystem benötigte in den Versuchsläufen konstant 334 Takte.
Variante 2⌗
In Variante 2 benutzen wir zwar weiterhin das Struct, doch statt Pointern reichen wir das Datenobjekt über den Stack zwischen den Aufrufen hin und her:
MyData init3 () {
return MyData {7, 8, 9};
}
MyData calculate3 (MyData d) {
d.d = d.a + d.b + d.c;
return d;
}
int main3 () {
MyData data = init3();
calculate3(data);
}
Wir sind verblüfft: Der Code benötigt nur noch 64 CPU-Zyklen, also 80% weniger Zeit. Eine verblüffende Verbesserung, die jedoch Stack-Speicher kostet. Wie man das Problem mangelnden Stack-Speichers behebt, haben wir in „Rekursion ist gut“[4] erörtert.
Variante 3⌗
In Variante 3 wenden wir unsere Empfehlung konsequent an und Vermessen die Ausführung auf unserem Referenzsystem.
void init () {
int a = 7, b = 8, c = 9; // allocate vars on stack
}
void calculate () {
int a, b, c, d; // reuse previously assigned values on stack
d = a + b + c;
}
int main (void) {
init();
calculate();
}
Die Ausführung von main() dauerte hier nur noch 27 Takte. Ein Faktor von über 10x liegt zwischen den Varianten 1 und 3. Neben der besseren Lesbarkeit also auch noch ein erheblicher Geschwindigkeitsgewinn? Wir schauen genauer hin.
Die Analyse⌗
Zunächst fällt auf, dass Variante 1 mit deutlichem Abstand hinterherhinkt. Der new()-Aufruf in Variante 1 kostet fast 300 Zyklen, um irgendwo auf dem leeren Heap eine ausreichende Speichermenge zu finden und als belegt zu taggen. Wir sind verblüfft, denn der Algorithmus zum Finden freier Stellen auf dem Heap sollte hier leichtes Spiel haben.
Wir sind etwas besorgt, da die Verwendung von new() in der heutigen Software-Entwicklung viel zu leichtfertig verwendet wird. Neben den ganzen Unsicherheiten, die man sich durch Pointer einhandelt, befürchten wir, dass heute massenhaft ineffizienter Code geschrieben wird. Alle Anstrengungen der Elektroingenieure bei den Chipherstellern werden offenbar zunichte gemacht.
Variante 2 kommt mit einem Bruchteil der Instruktionen aus, liegt mit 64 CPU-Zyklen aber immer noch 58% höher als Variante 3 mit nur 27 Takten. Wir haben das Assembly analysiert und festgestellt, dass durch unseren Trick zahlreiche Instruktionen für Parameterübergabe und Ergebnisrückgabe entfallen, die in Variante 2 die Daten lediglich hin- und wieder zurück kopiert haben, also redundant sind.
Zudem fällt der Registerdruck in der ohnehin mit Registern sparsam ausgestatteten x86-Architektur in Variante 3 erheblich geringer aus, so dass weniger temporäre Daten auf dem Stack zwischengesichert werden müssen.
Uns ist bei der Analyse aufgefallen, dass die Anzahl der mov-Instruktionen in Variante 1 und 2 außergewöhnlich hoch ist. Computer sind zu wertvoll, um nur Daten hin- und herzuschieben, wenn sie in dieser Zeit auch wertvollere Aufgaben verrichten könnten. Wir haben hierzu eine Studie in Auftrag gegeben, die untersuchen soll, wie viel sinnvolle Arbeit ein Computer heute überhaupt noch macht, und wie viel Computer heute nur noch mit sinnlosem Hin- und Zurückkopieren von Daten verbringen.
Fazit⌗
Wir sehen bei der Anwendung unserer Handlungsempfehlung nicht nur eine bessere Lesbarkeit des Codes, sondern auch eine bis zu zehnmal kürzere Ausführungszeit. Die Messdaten untermauern unsere Empfehlung, mit der wir zugleich die Hoffnung hegen, dass Entwickler wieder mehr Verständnis über die Abläufe auf Computern entwickeln.
Quellen: