📊 statistics

The Right Call for Software Benchmarking: Consistent Decisions in Stateful Environments

Dieses Paper argumentiert, dass in zustandsbehafteten Computing-Umgebungen, in denen adaptive Mechanismen absolute Leistungsmessungen verfälschen, das Software-Benchmarking als ein Entscheidungsproblem neu definiert werden sollte, das darauf abzielt, das schnellste Programm durch Versuchsdesigns zu identifizieren, die konsistente Schätzungen von Leistungsdifferenzen anstelle von Absolutwerten liefern.

Ursprüngliche Autoren: Gábor Melis

Veröffentlicht 2026-06-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Gábor Melis

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Rennwagen-Ingenieur und versuchen herauszufinden, welcher von zwei neuen Motordesigns schneller ist. Sie nehmen beide mit auf eine Rennstrecke, aber es gibt ein Problem: Die Strecke selbst ist unberechenbar. Manchmal weht der Wind, manchmal ist der Asphalt heiß, manchmal rennt ein streunender Hund über die Ziellinie und manchmal weist die Zeitmessung einen Fehler auf. Dies sind die „zustandsabhängigen“ Faktoren, von denen das Paper spricht – Dinge, die man nicht vollständig kontrollieren oder vorhersagen kann.

Wenn Sie einfach Motor A fünfmal und dann Motor B fünfmal laufen lassen und die Ergebnisse mitteln, könnten Sie das falsche Ergebnis erhalten. Warum? Weil vielleicht während der Läufe von Motor A der Wind ruhig war und während Motor B ein Sturm tobte. Das „Rauschen“ der Umgebung hat Ihre Ergebnisse verzerrt.

Dieses Paper, geschrieben von Gábor Melis von Google DeepMind, argumenttiert, dass der Versuch, die absolute Geschwindigkeit eines einzelnen Programms in dieser chaotischen Welt zu messen, ein aussichtsloses Unterfangen ist. Stattdessen sollten wir aufhören zu messen, „wie schnell“ etwas ist, und uns stattdlich darauf konzentrieren, „welches schneller ist“.

Hier ist der Kern des Papers, unterteilt in einfache Konzepte:

1. Das Problem: Die „Täuschung“ der absoluten Geschwindigkeit

Das Paper sagt, dass der Versuch, in modernen Computern eine perfekte, absolute Zahl dafür zu bekommen, wie lange ein Programm benötigt, so ist, als würde man versuchen, die exakte Körpergröße einer Person zu messen, die auf einem Trampolin steht, während das Trampolin hüpft. Die Umgebung (das Trampolin) verändert sich basierend auf dem, was zuvor passiert ist.

Die Falle: Wenn Sie versuchen, Programm A zu messen und dann Programm B, könnte sich die „Stimmung“ des Computers (Cache, Temperatur, Hintergrundaufgaben) zwischen den beiden verändert haben.
Das Ergebnis: Ihre Messungen sind verzerrt. Sie können den absoluten Zahlen nicht trauen.

2. Die Lösung: Das „Direktrennen“ (Deltas)

Anstatt zu fragen: „Wie schnell ist Programm A?“ (was schwierig ist), fragen Sie lieber: „Ist Programm A schneller als Programm B?“ (was einfacher ist).

Die Analogie: Stellen Sie sich zwei Läufer auf einer schlammigen Rennbahn vor. Wenn der Schlamm tiefer wird, werden beide Läufer langsamer. Wenn Sie sie separat messen, könnten Sie denken, der zweite Läufer sei langsamer, weil der Schlamm schlimmer geworden ist. Aber wenn Sie sie zur gleichen Zeit (oder in einem eng miteinander verflochtenen Rennen) laufen lassen, beeinflusst der Schlamm sie gleichermaßen. Der Unterschied zwischen ihnen bleibt klar, selbst wenn die absoluten Zeiten chaotisch sind.
Die Behauptung des Papers: Indem man sich auf den Unterschied (das „Delta“) zwischen zwei Programmen konzentriert, die in demselben Experiment gemessen wurden, fällt das Rauschen der Umgebung weg. Man muss nicht wissen, warum der Computer langsam ist; man muss nur wissen, dass er für beide Programme gleichermaßen langsam war.

3. Die Strategie: „Shuffle“ vs. „Block“

Das Paper testet zwei Wege, diese direkten Duelle auszutragen, um sicherzustellen, dass der „Schlamm“ Sie nicht täuscht.

Die „Block“-Methode (Der alte Weg): Sie lassen Programm A 10 Mal laufen, dann Programm B 10 Mal.
- Der Fehler: Das Paper zeigt, dass dies riskant ist. Wenn sich der Zustand des Computers langsam ändert (wie eine Rennstrecke, die im Laufe der Zeit heißer wird), könnte Programm A einen „kühlen“ Start haben und Programm B ein „heißes“ Ende. Die Verzerrung verschwindet nicht, selbst wenn Sie es eine Million Mal laufen lassen. Es ist, als würde man den ersten Läufer am Morgen und den zweiten am Mittag laufen lassen.
Die „Randomisierte“ Methode (Der neue Weg): Sie werfen für jeden einzelnen Lauf eine Münze. Kopf: Laufe A. Zahl: Laufe B.
- Der Sieg: Dies ist die große Empfehlung des Papers. Durch das zufällige Mischen der Läufe stellen Sie sicher, dass jedes „Umgebungsrauschen“ (wie ein plötzlicher Temperaturanstieg) beide Programme in etwa gleichermaßen trifft. Selbst wenn das Rauschen hinterlistig ist und versucht zu betrügen, macht das zufällige Mischen es unmöglich, dass das Rauschen konsequent eines der Programme bevorzugt.

4. Die Garantie: „Wir wissen, dass wir recht haben“

Das Paper sagt nicht nur „versuchen Sie das“. Es nutzt Mathematik, um zu beweisen, dass, wenn Sie diese Methode des zufälligen Mischens verwenden:

Konsistenz: Wenn Sie das Experiment lange genug durchführen, werden Sie schließlich den wahren Gewinner finden, egal wie chaotisch der Computer ist.
Endliches Budget: Sie benötigen keine unendliche Zeit. Das Paper bietet einen Weg, um genau zu berechnen, wie viele Durchläufe Sie benötigen, um zum Beispiel zu 95 % sicher zu sein, dass Programm A schneller ist als Programm B.

5. Was ist mit anderen Methoden?

Das Paper untersucht auch andere populäre Wege, mit denen Software-Benchmarks durchgeführt werden, wie zum Beispiel „Paar-Benchmarking“ (A laufen lassen, dann B, dann A, dann B) oder die Verwendung von Bibliotheken wie Google Benchmark.

Das Urteil: Diese Methoden können zwar das „Zittern“ (die Varianz) in den Zahlen reduzieren, was die Ergebnisse glatter aussehen lässt. Das Paper argumentiert jedoch, dass sie das Bias (die Verzerrung) nicht beheben. Sie könnten immer noch den falschen Gewinner wählen, weil sie den langfristigen Drift des Computerzustands nicht berücksichtigen. Die Methode des zufälligen Mischens ist die einzige, die mathematisch robust gegen diese versteckten Tricks ist.

Zusammenfassung

Betrachten Sie Software-Benchmarking wie ein Spiel „Schere, Stein, Papier“, das in einem Raum gespielt wird, in dem das Licht ständig flackert.

Alter Weg: Messen Sie, wie lange man braucht, um Schere zu spielen, und messen Sie dann Stein. Das flackernde Licht könnte Stein langsamer aussehen lassen, nur weil das Licht in diesem Moment schlecht war.
Neuer Weg (Dieses Paper): Spielen Sie Schere und Stein in derselben Runde und wechseln Sie dabei zufällig, wer zuerst dran ist. Das flackernde Licht beeinflusst beide gleichermaßen. Sie können klar sehen, wer die Runde gewonnen hat, auch wenn Sie nicht genau sagen können, wie lange die Runde gedauert hat.

Das Paper kommt zu dem Schluss, dass wir, um bessere Software (wie Compiler oder Datenbanken) zu bauen, aufhören müssen, perfekter absoluter Zahlen nachzujagen, und stattdin diese „randomisierten direkten Duelle“ nutzen müssen, um die wahren Gewinner zu finden.

Technisches Resümee: Die richtige Entscheidung beim Software-Benchmarking

1. Problemstellung

Moderne Computersysteme verlassen sich stark auf zustandsbehaftete Mechanismen (z. B. CPU-Temperatur-Throttling, Cache-Zustände, OS-Scheduling und konkurrierende Workloads), um die Leistung zu optimieren. Während diese Mechanismen die Effizienz verbessern, führen sie temporale Abhängigkeiten zwischen sequenziellen Messungen ein. Infolgedessen erzeugt der unkontrollierte Zustand der Umgebung einen „Confounder“ (Störfaktor), der naive Schätzer der absoluten Programperformance (z. B. durchschnittliche Laufzeit) verzerrt und inkonsistent macht.

Das Paper argumentiert, dass es in solchen zustandsbehafteten Umgebungen theoretisch unmöglich ist, den absoluten Verlust (Kosten) eines einzelnen Programms zu schätzen, ohne starke, oft nicht verifizierbare Annahmen über die zugrunde liegenden Dynamiken der Umgebung zu treffen. Traditionelle Benchmarking-Methoden, die auf absoluten Zahlen oder einfacher Mittelwertbildung basieren, versagen, da der unkontrollierte Zustand $U$ die Messungen auf eine Weise beeinflusst, die nicht modelliert oder kontrolliert werden kann, was zu irreführenden Optimierungsentscheidungen führt.

2. Methodik und Framework

2.1 Formalisierung als Entscheidungsproblem

Die Autoren definieren Software-Benchmarking nicht als Schätzproblem der absoluten Performance, sondern als ein Entscheidungsproblem: das Identifizieren des schnellsten Programms innerhalb einer Menge $\mathcal{F}$ unter einer gegebenen Konfiguration $c$ .

Ziel: Finde $\arg \min_{f \in \mathcal{F}} l(f)$ , wobei $l(f)$ der erwartete Verlust ist.
Zentrale Erkenntnis: Während die Schätzung des absoluten Verlusts $l(f)$ durch unkontrollierte Zustände verzerrt wird, kann die Schätzung der Performance-Differenz (Delta) zwischen zwei Programmen, $\delta(f, g) = l(f) - l(g)$ , unverzerrt sein, wenn das Umgebungsrauschen beide Programme ähnlich beeinflusst. Dies beruht auf einer ceteris paribus-Annahme („alles andere bleibt gleich“): Unkontrolliertes Rauschen beeinflusst den Verlust additiv (oder multiplikativ im Log-Raum) und einheitlich über alle Programme in der Menge.

2.2 Messmodell

Das Paper postuliert ein generatives Modell, bei dem:

Ein unkontrollierter Zustand $U$ über die Zeit evolviert.
Ein Programm $F_i$ basierend auf vorherigen Beobachtungen ausgewählt wird.
Die beobachtete Laufzeit $T_i$ eine Funktion der wahren Laufzeit und des aktuellen unkontrollierten Zustands ist.
Der Zustand $U$ unobserviert ist und seine Verteilung unbekannt ist.

2.3 Experimentelle Designs

Um eine konsistente Schätzung von Deltas zu erreichen, schlägt das Paper zwei primäre Experiment-Designs vor, die Symmetrie nutzen, um Bias zu eliminieren:

Delta-Designs ( $\mathcal{D}_\Delta$ ): Eine allgemeine Klasse von Designs, bei denen die Wahl des nächsten Programms nur von vorherigen Entscheidungen abhängt (nicht vom unobservierten Zustand) und eine Wahrscheinlichkeit von Null für alle Programme ausschließt.
Blockierte Experimente ( $\beta$ ): Programme werden in Blöcken ausgeführt, in denen jedes Programm eine gleiche Anzahl von Malen innerhalb des Blocks erscheint (Ziehen ohne Zurücklegen). Das Paper analysiert sowohl Single-Block- als auch Multi-Block-Designs.
- Ergebnis: Konstante Blockgrößen können zu asymptatischer Verzerrung führen, da die Ausführungsreihenfolge innerhalb eines festen Blocks Korrelationen mit dem sich entwickelnden Zustand erzeugt.
- Lösung: Wachsende Blockgrößen (bei denen die Blockgröße mit der Gesamtzahl der Durchläufe steigt) sind erforderlich, um asymptotische Konsistenz und verschwindenden Bias zu gewährleisten.
Einfache Randomisierte Experimente ( $\alpha$ ): Programme werden für jeden Durchlauf unabhängig und gleichverteilt zufällig ausgewählt (Ziehen mit Zurücklegen).
- Ergebnis: Dieses Design erreicht die optimale asymptotische Rate von $O(n^{-1/2})$ für das Rauschdifferenzial, selbst unter adversariellen, autokorrelierten Umgebungsrauschen, ohne die komplexe Blockstruktur zu benötigen.

2.4 Entscheidungsregel

Das Paper definiert eine Entscheidungsregel, die ein Programm $f^*$ auswählt, wenn das geschätzte Delta $\hat{\delta}(f^*, g)$ für alle Wettbewerber $g$ hinreichend negativ ist, basierend auf einer einseitigen Konfidenzgrenze.

Die Regel verwendet adversarielle Rausch-Envelopes, um Finite-Sample-Garantien zu bieten, ohne eine spezifische Rauschverteilung vorauszusetzen.
Es unterscheidet zwischen „Pre-Data“ (Frequentist) und „Post-Data“ (Bayesian) Perspektiven und wählt einen frequentistischen Pre-Data-Ansatz, um Robustheit gegenüber unbekannten Umgebungsdynamiken zu gewährleisten.

3. Zentrale Beiträge

Formalisierung des Benchmarking als Entscheidungsproblem: Das Paper formalisiert die Aufgabe, das schnellste Programm unter einem allgemeinen, intransaktablen Messmodell zu finden, und verlagert den Fokus von der absoluten Schätzung auf die relative Entscheidungsfindung.
Die „Täuschung“ (Mirage) der absoluten Performance: Es zeigt auf, dass die konsistente Schätzung absoluter Performance-Werte in zustandsbehafteten Umgebungen unrealistische Annahmen (z. B. stationäre Verteilungen des Zustands, Zero-Mean Random Walks) erfordert.
Delta-basierte Methodik: Es schlägt vor, sich auf Performance-Differenziale ( $\delta$ ) statt auf absolute Werte zu konzentrieren. Unter der Annahme, dass unkontrollierte Zustände alle Programme einheitlich beeinflussen, heben sich programmspezifische Biases im Delta auf.
Experiment-Designs mit Garantien:
- Es führt Blockierte und Einfache Randomisierte Designs ein, die konsistente Schätzer für Kontraste zulassen.
- Es beweist, dass Einfache Randomisierte Designs ( $\alpha$ ) die optimale asymptotische Konvergenzrate ( $O(n^{-1/2})$ ) erreichen und robust gegenüber adversariellem Rauschen sind.
- Es analysiert Blockierte Designs ( $\beta$ ) und zeigt, dass diese zwar die Varianz reduzieren können, aber wachsende Blockgrößen benötigen, um eine asymptatische Verzerrung zu vermeiden.
Finite-Sample-Garantien: Das Paper liefert Dynamic-Programming (DP)-Formulierungen und analytische Approximationen (Martingale und Asymmetrisch), um die minimale Anzahl an Durchläufen zu berechnen, die erforderlich sind, um eine spezifische Performance-Differenz mit einem gegebenen Konfidenzniveau zu detektieren.

4. Ergebnisse und Validierung

Theoretische Schranken: Die Autoren beweisen, dass für Simple Randomized Designs die Rauschdifferenz $\bar{E}_f - \bar{E}_g$ eine Ordnung von $O_p(n^{-1/2})$ aufweist, was der Rate von unabhängigem Rauschen trotz der Anwesenheit von zustandsbehaftetem, korreliertem Umgebungsrauschen entspricht.
Bias-Analyse: Es wird gezeigt, dass Designs mit konstanten Blockgrößen in bestimmten Szenarien (z. B. wenn der unkontrollierte Zustand von der Sequenz der Programme abhängt) asymptatisch verzerrt sind. Wachsende Blockgrößen sind notwendig, um diesen Bias zu eliminieren.
Empirische Validierung:
- Das Paper validiert analytische Approximationen gegen Dynamic-Programming (DP)-Simulationen für Worst-Case-Konfidenz.
- Die Ergebnisse zeigen, dass die Asymmetrische Approximation eine engere Schranke bietet als die Martingale-Approximation für den Fall von zwei Programmen.
- Experimente bestätigen die $O(n^{-1/2})$ Skalierungsbeziehung: Eine Halbierung des Detektionsschwellenwerts erfordert etwa eine Vervierfachung der Anzahl der Durchläufe.
- Das Einfache Randomisierte ( $\alpha$ ) Design erreicht konsistent eine nicht-null Konfidenz mit weniger Durchläufen als das Blockierte ( $\beta$ ) Design, insbesondere bei niedrigeren Detektionsschwellen, da letzteres anfällig für aus festen Blockstrukturen extrahierte Informationen ist.

5. Bedeutung und Ansprüche

Das Paper beansprucht, eine robuste Methodik für das Benchmarking mit begrenztem Budget in zustandsbehafteten Umgebungen bereitzustellen. Durch die Priorisierung von Performance-Differenzialen gegenüber absoluten Maßen und die Nutzung spezifischer Experiment-Designs (insbesondere einfacher Randomisierung) können Entwickler:

Konsistente Entscheidungen darüber treffen, welches Programm am schnellsten ist, selbst wenn die zugrunde liegenden Umgebungsdynamiken unbekannt und unkontrolliert sind.
Probabilistische Garantien für ihre Entscheidungen in Finite-Sample-Regimen erhalten, wodurch die Fallstricke verzerrter absoluter Schätzer vermieden werden.
Die Entwicklung von performance-sensitiver Software (Compiler, ML-Frameworks, Datenbanken) beschleunigen, indem sie die zuverlässige Detektion kleiner Performance-Unterschiede ermöglichen, die sonst durch Systemzustandsrauschen verborgen blieben.

Die Autoren stellen explizit klar, dass ihr Ansatz nicht versucht, komplexe Systemdynamiken (wie thermische Regler) zu dekonstruieren, sondern statetliche Symmetrie und Randomisierung nutzt, um diese Dynamiken für die Entscheidung „welches ist schneller“ irrelevant zu machen. Sie räumen ein, dass ihre Methode zwar die Stichproben-Effizienz und Entscheidungszuverlässigkeit verbessert, aber auf der Annahme beruht, dass unkontrollierte Zustände alle verglichenen Programme ähnlich beeinflussen; falls diese Annahme verletzt wird (z. B. durch programmspezifische Hardware-Interaktionen), sind zusätzliche Kontrollen erforderlich.