Benchmarks

Üblicherweise ist es einfacher, ein korrektes Programm zu verschnellern, als ein effizientes Programm zu korrigieren. Daher ist es normalerweise sinnvoll, mit möglichst simplem und lesbarem Code zu starten. Sobald die Effizienz für den gegebenen Anwendungsfall ein Problem wird, ergibt die Detektion von Flaschenhälsen des Programms Sinn, bevor Maßnahmen zur Effizienzsteigerung ergriffen werden. Ansonsten ist die Gefahr groß, dass Programme unter großem Zeiteinsatz an Stellen optimiert werden, die keinen Einfluss auf den Anwendungsfall haben. Zeiten werden immer in Release-Builds gemessen. Debug-Builds sind üblicherweise signifikant langsamer und haben keine Relevanz für das in der Praxis eingesetzte Programm. Dabei muss man aufpassen, dass Optimierungen im Release-Build nicht den Code entfernen, dessen Ausführungszeit zu untersuchen ist, falls dieser aus dem Kontext separiert untersucht wird.

Profiling

Zum Entdecken von Flaschenhälsen bietet sich Profiling als Werkzeug an. Mit Profiling lassen sich für einen Programmdurchlauf die Programmabschnitte bestimmen, in denen am meisten Zeit verbaucht wurde. Unglücklicherweise ist mir für Rust kein betriebssystemunabhängiges, minimalinvasives Tool bekannt, mit dem man Programme einfach profilen könnte, z.B. im Gegensatz zu Python's sehr praktischem line_profiler.

Eine plattformunabhängie aber sehr invasive Variante ist die Verwendung von Counts. Um Counts zu verwenden, muss man im Code an interessanten Stellen Zeitmessungen unterbringen und per eprint! ausgeben. Counts kann dann verwendet werden um die Zeiten zu aggregieren.

Benchmarks

Wenn man Flaschenhälse identifiziert hat, befindet man sich vornehmlich in der Situation die Laufzeit \( t \) eines bestimmten Teilprogramms abschätzen und für verschiedene Veränderungen vergleichen zu wollen. Eine direkte Messung ist nicht möglich, da ein Programm immer im Kontext eines Betriebssystems läuft, in dem weitere Hintergrundprozesse am Werkeln sind. Was wir also messen können ist eine Zeit \( t_{\text{M}} \) die durch die Summe \[ t_{\text{M}} = t + t_{\text{N}} + t_{\text{O}} \] gegeben ist, wobei wir \( t_{\text{N}} \ge 0 \) als Rauschen (engl. noise) wahrnehmen, das durch Hintergundprozesse oder ähnliches verursacht wird. Benutzer von Hardware, die von einer zentralen IT-Abteilung verwaltet wird, können hier oft ein trauriges Lied von singen. Der letzte Term \( t_{\text{O}} \ge 0 \) ist der Overhead, den das Testen verursacht. Das heißt, die Dauer der Messung \( t_{\text{M}} \) ist immer größer als die oder gleich der eigentlich interessanten Zeit \( t \).

In Rust gibt es die externe Bibliothek Criterion. Externe Bibliotheken werden in Rust auch Crates genannt und sind das Thema eines späteren Kapitels. Um Criterion zu verwenden, fügen wir in unserer Cargo.toml die Zeilen

[dev-dependencies]
criterion = { version = "0.4", features = ["html_reports"] }

[[bench]]
name = "my_benchmark"
harness = false

ein. Mit dem Key features lässt sich Funktionalität von Crates ein oder ausschalten. Ob ein Crate über Features verfügt obliegt den Crate-Entwicklern und unterscheidet sich üblicherweise von Crate zu Crate. Das Criterion-Feature html_reports sorgt dafür, dass wir Plots unserer Benchmarks im target-Ordner finden. Als nächsten Schritt brauchen wir im Ordner benches eine Datei namens my_benchmarks.rs. Der Name der Datei muss dem Namen unter [[bench]] entsprechen. Beispielhaften Inhalt der Datei my_benchmarks.rs betrachten wir im Folgenden.

#![allow(unused)]
fn main() {
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use std::time::Duration;
use std::thread;
fn sleepy_func(n: u64) -> u64 {
    thread::sleep(Duration::from_millis(n));
    n
}

fn benchmark_sleepy(c: &mut Criterion) {
    c.bench_function("sleep", |b| b.iter(|| sleepy_func(black_box(20))));
}

criterion_group!(benches, benchmark_sleepy);
criterion_main!(benches);
}

Die Funktion criterion::black_box verhindert, dass der Compiler unsere Funktionsaufrufe wegoptimiert. Die Makros am Ende werden verwendet, um zu benchmarkende Funktionen zu registrieren, damit sie per

cargo bench

ausgeführt werden können. Criterion führt mehrere Läufe durch und erstellt Statistiken, die Ausreißer beachten. Die Philosophie hinter Criterion ist, dass zu benchmarkende Programme fast nie deterministisch seien. Determinismus impliziert, dass man das Minimum über mehrere Läufe oder wenigstens Statisitiken heranziehen sollte, die robust gegenüber Ausreißern sind, denn Abweichungen sind nur additives Rauschen. Man kann nicht durch zufällige Ereignisse auf dem Rechner ein verschnellertes Programm erwarten. Ob die Zufallselemente einer Ausführung wirklich relevant sind, oder ob ein Programm aus praktischer Sicht als deterministisch betrachtet werden sollte, hängt von der Anwendung ab. Beispielsweise hängt die Zeit einer Vektoralloktation von der aktuellen Konfiguration des Speichers ab oder die Zugriffszeit auf eine Hashmap vom Vorhanden sein einer Kollision ab. Diese Zeitunterschiede sind oft so gering sein, dass sie für die Anwendung völlig irrelevant sind. Ein im Hintergrund vom Betriebssystem gestartetes Programm beispielsweise auf einem von einer zentralen IT gesteuerten Windows PC kann jedoch bei Benchmarks durchaus signifikant dazwischen funken. Leider bietet Criterion nicht die Option, das Minimum zu verwenden. Dennoch ist Criterion ein komfortables Crate mit hilfreichen Funktionen zum Erstellen von Benchmarks. Beispielsweise merkt sich Criterion für uns den vorherigen Durchlauf als Baseline und und vergleicht den aktuellen Durchlauf damit. Man kann auch manuell Baselines definieren.

Im vorherigen Kapitel haben wir eine Aufgabe zum Erstellen einer VecMap gesehen. Um ihre Zugriffszeiten bewerten zu können, ist die HashMap eine sehr gut geeignete Baseline. Des Weiteren können wir mit Criterion unterschiedliche Implementierungen einer Funktion miteinander vergleichen. Dazu verwenden wir eine Gruppe.

#![allow(unused)]
fn main() {
use std::time::Duration;
use std::thread;
use criterion::{black_box, criterion_group, criterion_main, Criterion, BenchmarkId};
fn sleepy_func(n: u64) -> u64 {
    thread::sleep(Duration::from_millis(n));
    n
}
fn very_sleepy_func(n: u64) -> u64 {
    thread::sleep(Duration::from_millis(n * 2));
    2 * n
}
fn benchmark_sleepy(c: &mut Criterion) {
    let mut group = c.benchmark_group("sleepy_group");
    for n in [1, 5, 10] {
        group.bench_with_input(BenchmarkId::new("sleepy", n), &n, |b, n| {
            b.iter(|| sleepy_func(black_box(n)))
        });
        group.bench_with_input(BenchmarkId::new("very_sleepy", n), &n, |b, n| {
            b.iter(|| very_sleepy_func(black_box(n)))
        });
    }
}
}

Wenn wir nun cargo bench ausführen, finden wir unter target/criterion/sleepy_group/report eine index.html, in der für verschiedene Werte von n auf der x-Achse entsprechende Zeiten auf der y-Achse zu finden sind.

Aufgabe

Erstelle Benchmarks mit Criterion für Lese- und Schreibzugriffe auf die VecMap im Vergleich zur HashMap. Vergleiche verschieden große Maps für 5, 10, 30 und 100 Elemente.