JEXP                       JEXP

Microbenchmarks leicht gemacht

Während der letzen Jahre hat Aleksey Shipilev, ein Java Performance Experte bei Oracle als Teil des OpenJDK Projekts den "Java Microbenchmark Harness (JMH)" entwickelt. Dieses Microbenchmark-Tool erleichtert die Erstellung und Durchführung korrekter Benchmarks die nur wenige Operationen umfassen.

Normalerweise sind diese schwierig korrekt zu gestalten. Da der zu testende Code meist sehr schnell (in wenigen Nano- oder Mikrosekunden) ausgeführt wird, muss er oft wiederholt werden. Das macht man normalerweise in Schleifen mit Hundertausenden oder Millionen von Durchläufen.

Fallstricke für Mikrobenchmarks

Was kostet aber die Schleife selbst? Deren Laufzeit sollte man schon von der Gesamtlaufzeit abziehen. Und was ist mit Testdaten? Der Aufruf von Random sollte in diesen Schleifen tunlichst vermieden werden. Also vorher genügend große Felder mit Zufallswerten füllen und dann über Schleifenvariable modulo Feldgröße auf die Werte zugreifen.

Was ist mit Compiler-Optimierungen? Wird der Code innerhalb der Schleife wegoptimiert, weil seine Ergebnisse sowieso nicht genutzt werden? Oder seine Eingabewerte konstant sind? Also Summen aufaddieren oder Zuweisungen an Variablen ausserhalb der Schleife einbauen. Andere Optimierungen wie Loop-Unrolling für Schleifen oder On-Stack-Replacement (OSR) für das unmittelbare Ersetzen von Interpreter-Code durch kompilierten Code, sind auch prädestiniert dafür, Microbenchmarks zu verfälschen. Andere Optimierungen werden nur im Mikrobenchmarks aktiv, da der Compiler den einfacheren Code viel leichter analysieren kann. Im komplexeren Produktivcode wäre diese Analyse dagegen nicht erfolgreich.

Wann setzt eigentlich die Hotspot Compilierung ein? Der Sprung von interpretiertem Bytecode zu hochoptimiertem Code wird erst nach einigen (tausend) Zyklen durchgeführt. Hilfreich ist dazu der Kommandozeilenparameter (-XX:CompileThreshold=n, default ist 10000 für -server, 1500 für -client, sichtbar mit -XX:+PrintCompilation). Desweiteren ist Inlining (-XX:+PrintInlining) interessant, bis zu welcher Größe werden häufig aufgerufene Methoden in ihre Aufrufstellen platziert? (-XX:MaxInlineSize=n, standardmässig bis 35 bytes, es gibt auch noch: -XX:FreqInlineSize=n, das für besonders häufig aufgerufene Methoden noch eine zweite Schwelle angibt).

Da Hotspot erst nach 10000 Durchläufen zuschlägt, sollte man also den zu messenden Code vorher genügend oft (warm-)laufen lassen. Hotspot-Compilierung, Laden von Klassen und Erst-Initialisierung (z.b. für Konsolenausgaben) während der Messung verzerren das Ergebnis. Deren Abwesenheit kann man sicherstellen, wenn keine Ausgaben von -verbose:class und -XX:+PrintCompilation in diesem Zeitraum erscheinen.

Desweiteren ist ein einziger Durchlauf oft nicht ausreichend, um genügend Aussagekraft zu haben. Gerade auf Privatrechnern laufen zuviele Prozesse im Hintergrund, die sich negativ bemerkbar machen, besonders wegen paralleler und nicht-konstanter CPU- oder Speicherlast (IDE, Browser, Skype, Twitter Client, Hintergrundaktualisierungen, z.B. für die Desktop-Suche, Virenscanner usw.). Auch die Ausführung auf virtuellen, nicht dedizierten Maschinen in der Cloud liefert keine garantiert gleichen Ausführungszeiten.

Also sollte man die Mikrobenchmarks auf einen blanken Rechner durchführen, auf dem sonst nichts weiter läuft und man volle Kontrolle über CPU, RAM und Festplattenaktivitäten hat. Oder man lässt den Test entsprechend häufig laufen, und sammelt die Laufzeiten (nicht einfach den Mittelwert bilden), um sich ein Histogramm (wie z.B. mit Gil Tene’s [HdrHistogram]) ausgeben zu lassen, in dem die relevanten Perzentilen der Laufzeiten erkennbar sind.

Wie man schon sehen kann, wartet eine Menge Arbeit auf jeden, der einen verlässlichen Mikro-Laufzeittest durchführen wil. In der Präsentation [JmhPresentation] von Aleksey werden noch viele andere Aspekte genannt, die man bedenken sollte - nicht ohne Grund schürt er gewaltigen Respekt vor realistischen und nutzbaren Benchmark-Ansätzen.

Mit dem Java MicroBenchmarks Harness sollen zumindest einige dieser Fallstricke besser handhabbar werden. Grund genug, uns dieses Tool mal etwas genauer anzuschauen. Als Testcode nehme ich einige Routinen, die ich schon lange einmal testen wollte. Diese dienen der effizienteren Speicherung von großen Mengen von Long-Werten in einem Speicherbereich (z.b. byte-Array).

Java Measurement Harness

JMH kümmert sich viele Aspekte des Benchmarks: WarmUp, Starten von JVM’s und Threads, Zeitmessung, Sammeln von Statistiken, usw.

Anders als andere Benchmarks misst JMH standardmässig nicht, wie lange ein Stück Code läuft, sondern wie oft es in einer festen Zeitspanne ausgeführt werden kann. Wie andere Benchmarks ist JMH aber auch nicht vor Einflüssen aus der Umgebung oder anderen Hotspot-Aspekten gefeit, daher seien die Benchmark-Regeln aus [MBRegeln] noch einmal ans Herz gelegt.

JMH basiert auf Maven, es ist aber auch ein Ant-Task verfügbar. Der einfachste Weg mit JMH zu starten ist, sich ein Projekt mittels Maven-Archetype generieren zu lassen.

mvn archetype:generate \
          -DinteractiveMode=false \
          -DarchetypeGroupId=org.openjdk.jmh \
          -DarchetypeArtifactId=jmh-java-benchmark-archetype \
          -DgroupId=de.jexp \
          -DartifactId=jmh-example \
          -Dversion=1.0

Dabei ist zu beachten, dass der Package-Name auf die groupId gesetzt wird.

Mit jmh-exampe/src/main/java/de/jexp/MyBenchmark.java wird auch gleich ein Beispiel-Benchmark erzeugt, der noch recht spartanisch aussieht:

package de.jexp;

import org.openjdk.jmh.annotations.GenerateMicroBenchmark;

public class MyBenchmark {

    @GenerateMicroBenchmark
    public void testMethod() {
        // place your benchmarked code here
    }
}

Diesen kann man jetzt einfach per mvn clean install bauen lassen (dabei werden per Annotations-Prozessor die eigentlichen Test-Klassen generiert) und mittels java -jar target/microbenchmarks.jar ausführen lassen.

Die Ausgabe sollte dann so aussehen:

# Run progress: 0,00% complete, ETA 00:00:10
# VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0.jdk/Contents/Home/jre/bin/java
# VM options: <none>
# Fork: 1 of 1
# Warmup: 5 iterations, 1 s each
# Measurement: 5 iterations, 1 s each
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: de.jexp.MyBenchmark.testMethod
# Warmup Iteration   1: 3182454,485 ops/ms
...
# Warmup Iteration   5: 3260164,501 ops/ms
Iteration   1: 3230647,136 ops/ms
...
Iteration   5: 3167623,557 ops/ms

Result : 3215430,878 ±(99.9%) 140442,901 ops/ms
  Statistics: (min, avg, max) = (3167623,557, 3215430,878, 3248612,634), stdev = 36472,575
  Confidence interval (99.9%): [3074987,977, 3355873,779]

Benchmark                      Mode   Samples         Mean   Mean error    Units
d.j.MyBenchmark.testMethod    thrpt         5  3215430,878   140442,901   ops/ms

Die meisten Aspekte von JMH sind per Annotation konfigurierbar, hier ein typisches Set von Annotationen an der Mikrobenchmark-Klasse.

// Messung der Durchschnittslaufzeit (mehr dazu s.u.)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(MILLISECONDS)
@Warmup(iterations = 10, time = 1, timeUnit = SECONDS)
@Measurement(iterations = 20, time = 1, timeUnit = SECONDS)
@Fork(5)
// die Klasse wird pro Benchmark neu Erzeugt, alternativ Scope.Thread
@State(Scope.Benchmark)
@Threads(8)
class MyBenchmark {

    int a,b;

    // Initialisierung des Zustands (Resourcenfreigabe mit @TearDown)
    @Setup
    public void setup() {
        long now = System.currentTimeMillis();
        a=(int)now % 1000;
        b=(int)now / 1000;
    }

    // Erzwungenes Inlining
    @CompilerControl(CompilerControl.Mode.INLINE)
    private int plus(int a, int b) {
       return a + b;
    }

    // Testmethode
    @GenerateMicroBenchmark
    public int add(BlackHole bh) {
       // Rückgabe zur Vermeidung von Dead-Code-Elimination
       return plus(a,b);
    }
}

Aber auch ein manuelles Aufsetzen ist kein Problem. Einfach diese Abhängigkeiten deklarieren:

<dependencies>
    <dependency>
        <groupId>org.openjdk.jmh</groupId>
        <artifactId>jmh-core</artifactId>
        <version>0.5.5</version>
    </dependency>
    <dependency>
        <groupId>org.openjdk.jmh</groupId>
        <artifactId>jmh-generator-annprocess</artifactId>
        <version>0.5.5</version>
        <scope>provided</scope>
    </dependency>
</dependencies>

Beim Ausführen des Annotationsprozessors generiert JMH im target Verzeichnis diese Klassen:

generated-sources/annotations/[generated-sources/annotations/de/jexp/generated/MyBenchmark.java]

Das ist der Sourcecode für den eigentlichen Test. Dabei wird die Klasse mit vielen Zusatzvariablen und Methoden für Statistiken, Warmup usw. angereichert. Die meisten von ihnen sind mit viel Padding versehen, um Cacheline-Sharing auszuschliesen.

In target/classes/META-INF/CompilerHints, legt JMH fest, welche Methoden vom Compiler zum Inlining vorgesehen werden dürfen und welche nicht. Im Beispielfall sind das:

dontinline,de/jexp/generated/MyBenchmark.testMethod_Throughput_measurementLoop
dontinline,de/jexp/generated/MyBenchmark.testMethod_AverageTime_measurementLoop
dontinline,de/jexp/generated/MyBenchmark.testMethod_SampleTime_measurementLoop
dontinline,de/jexp/generated/MyBenchmark.testMethod_SingleShotTime
inline,de/jexp/MyBenchmark.testMethod
inline,org/openjdk/jmh/logic/BlackHole.clearSinks

Ausführen kann man das erzeugte JAR dann mittels:

// -wi=warmups, -i=iterations, -f=forks, -h=Hilfe (mit sehr vielen Optionen)
java -jar target/microbenchmarks.jar [ -wi 5 -i 5 -f 1]

Oder programmatisch, direkt aus der Klasse heraus:

public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
            .include(".*" + MyBenchmark.class.getSimpleName() + ".*")
            .warmupIterations(5)
            .measurementIterations(5)
            .threads(4)
            .forks(1)
            .build();

    new Runner(opt).run();
}

BenchMark-Modes:

JMH kennt verschiedene Modi zur Durchführung der Benchmarks. Sie können sowohl als Annotationen (@BenchmarkMode) an den Benchmarkklassen, als auch als Startparameter definiert werden. Im Einzelnen sind das:

Modus (Mode.) Beschreibung

Throughput

Misst die Anzahl der Operationen pro Zeiteinheit (siehe @Measurement(timeUnit))

AverageTime

Durchschnittlich Ausführungszeit einer Operation

SampleTime

Individuelle Zeiten werden erfasst für die Ermittlung von Perzentilen, Verteilungen usw.

SingleShotTime

Nur einmalige Messung, wenn z.b. der Sonderfall einer unoptimierten Ausführung betrachtet werden soll

AverageTime, SampleTime, ..

Modi können komma-separiert gelistet werden

All

Alle Modi zur Zeitmessung sind gleichzeitg aktiv

Testzustände

Mit @State(scope) werden Klassen annotiert, die als Zustandsobjekte für die Mikrobenchmarks genutzt werden sollen. Sie können in 3 verschiedenen Scopes definiert werden:

Scope Beschreibung

Scope.Benchmark

Zustand wird für den gesamten Benchmark geteilt, Setup- und TearDown-Methoden werden nur einmalig aufgerufen

Scope.Thread

Zustand wird pro Therad und auch im Thread erzeugt

Scope.Group

Zustand wird für eine Gruppe von Benchmarks geteilt, diese müssen dann auch mit derselben @Group("name") Annotation bezeichnet sein

Innerhalb der Zustandsklassen können @Setup- und @TearDown-Methoden für den Lebenszyklus, besonders für das Resourcenmanagement genutzt werden. Selbst die Testklasse kann mit @State annotiert werden und dient dann diesem Zweck.

// Zustand für den ganzen Benchmark, effektiv zwischen Threads geteilt
@State(Scope.Benchmark)
static class MyState {
    int a=23;
    int b=12;
    int c=0;
}

// Zustand pro Thread, so kein Sharing / konkurrierender Zugriff
@State(Scope.Thread)
static class MyThreadState {
    double answer=42d;
}

@GenerateMicroBenchmark
public void add(MyState state, MyThreadState state2) {
    state.c = state.a + state2.b;
}

State-Objekte werden nach Bedarf erzeugt, sind aber in den angegebenen Scopes gültig. Die Erzeugung erfolgt im Benchmark-Thread, so dass z.B. ThreadLocals korrekt zugeordnet sind und bleiben.

Für die Vermeidung der Eliminierung von ungenutztem Code, kann man Ergebnisse z.b. von der Test-Methode zurückgeben lassen oder sich einen BlackHole Parameter übergeben lassen, der beliebige Objekte konsumieren kann und damit für den Compiler eine Weiterverwendung der berechneten Ergebnisse darstellt.

Konkretes Beispiel

Wie schon angekündigt, beschäftigt der Code, den ich mir genauer anschauen wollte mit der effizienten Speicherung von Long Werten in einem ByteBuffer. Das ist z.B. notwendig wenn man größere Mengen von Long-IDs aufeinanderfolgend abspeichern will, aber nur sowenig Speicher wie möglich nutzen möchte. Normalerweise belegt jeder Long-Wert 8 Bytes, so dass eine Million Long-Werte 8 Millionen Bytes belegen. Wenn man diesen Wert auf die Hälfte oder weniger reduzieren kann, spart das eine Menge.

Es gibt viele verschiedene Ideen zur Kompression, zwei die ich mir genauer angeschaut habe, sind:

  • Speicherung der relevanten Bytes pro Long, d.h. alle nicht-Null Bytes und deren Anzahl, reduziert die Speichernutzung auf ca 3.4 Bytes pro Long in meinem Anwendungsfall

  • Speicherung des relevanten Anteils als aufeinanderfolgende Fragmente, die in einem High-Bit festhalten ob noch weiterer Block kommt oder ob der aktuelle der letzte ist. Die Anzahl muss somit nicht gespeichert werden aber man hat nur 7 Bit pro Block zur Verfügung, siehe [Variable Length Quantity]

  • Falls der VLQ Ansatz auch negative Zahlen speichern können soll, muss er diese Information irgendwo ablegen, so dass nur 6 statt 7 Bit zur Informationsspeicherung pro Block zur Verfügung stehen

Zum Vergleich habe ich noch eine Variante hinzugefügt, die die Long-Werte einfach direkt im Puffer ablegt ohne Kompression.

All diese LongEncoder implementieren dieses Interface:

public interface LongEncoder {
    int encode( ByteBuffer target, long value );
    int size( long value );
    long decode( ByteBuffer source );
}

Die individuellen Implementierungen sind zu lang zum Abdrucken und enthalten nur langweiligen Code mit vielen Bit-Operationen, daher hier ist nur die einfache Vergleichsvariante:

public class StoringLongEncoder implements LongEncoder {

    public int encode(ByteBuffer target, long value) {
        target.putLong(value);
        return 8;
    }

    public int size(long value) {
        return 8;
    }

    public long decode(ByteBuffer source) {
        return source.getLong();
    }
}

Um die verschiedenen Encoder zu testen, habe ich als Use-case das Speichern und Lesen inkrementell wachsender Werte genutzt. Ausgehend von einem Startwert (z.B. 7) der pro Durchlauf mit 11 multipliziert wird, hat jeder MicroBenchmark, eine Encoding, Decoding und Vergleichsoperation.

Der Benchmark sieht also wie folgt aus:

buffer.rewind();
encoder.encode(buffer, value);

buffer.rewind();
long decoded = encoder.decode(buffer);

if (decoded != value) throw new AssertionError("Incorrectly decoded, original: "+ value+" != decoded: "+ decoded);
value*=11;

Für einen direkteren Test der Algorithmen wäre es ggf. sinnvoll den ByteBuffer wegzulassen und direkt auf ein Byte-Array (oder gar nicht) zu schreiben. Aber ich wollte sie ja nur im Vergleich sehen.

Aber der Puffer und der inkrementierende Wert führen dazu, dass wir das @State Feature von JMH zeigen können. Wie schon erwähnt werden mit @State annotierte Klassen von JMH den Benchmarkmethoden als Parameter übergeben und dabei im richtigen Scope (Benchmark, Thread, Group) erzeugt und bereitgestellt.

In unserem Fall sind das dann Subklassen von LongEncoderHolder, die die beiden Attribute (Buffer und Wert), sowie die Operationen kapseln:

public static class LongEncoderHolder {
    private final LongEncoder encoder;
    ByteBuffer buffer = ByteBuffer.allocate(1000);
    long value = 7;

    public LongEncoderHolder(LongEncoder encoder) {
        this.encoder = encoder;
    }

	@CompilerControl(CompilerControl.Mode.INLINE)
    public int encode() {
        buffer.rewind();
        return encoder.encode(buffer, value);
    }

	@CompilerControl(CompilerControl.Mode.INLINE)
    public long decode() {
        buffer.rewind();
        long decoded = encoder.decode(buffer);
        if (decoded != value) throw
          new AssertionError("Incorrectly decoded, original: "
                             + value+" != decoded: "+decoded);
        return decoded;
    }

	@CompilerControl(CompilerControl.Mode.INLINE)
    void nextValue() {
        value*=11;
    }
}

Die konkrete Holder Subklasse pro Encoder sieht so aus:

@State(value = Scope.Thread)
public static class SignedLongEncoderHolder extends LongEncoderHolder {
    public SignedLongEncoderHolder() {
        super(new SignedLongBase128Encoder());
    }
}

Diese Holder-Klassen sind sicher von der Polymorphismus-Deoptimierung von Hotspot beeinflusst, aber ein testweises Inlining der Klassen hat keine signifikaten Unterschiede aufgezeigt.

Alternativ kann man den Zustand auch direkt im Benchmark ablegen, dann kann dieser mit @State(scope) annotiert werden und entsprechende Methoden für @Setup und @TearDown des Zustands enthalten. Man hätte dann eine Superklasse für den Benchmark und entsprechende Subklassen pro Encoder-Typ (siehe [JMH-Objectpool]).

Der eigentliche Benchmarkcode sieht dann so aus:

@GenerateMicroBenchmark
public long testSimpleLongEncoder(SimpleLongEncoderHolder longEncoder) {
    longEncoder.encode();
    long decoded = longEncoder.decode();
    longEncoder.nextValue();
    return decoded;
}

Bei der Ausführung erhalte ich folgende Werte, die mich doch etwas überrascht haben.

Benchmark                                             Mode   Samples         Mean   Mean error    Units
d.j.IdCompressionBenchmark.testSignedEncoder         thrpt         5    20714,543     2963,493   ops/ms
d.j.IdCompressionBenchmark.testSimpleLongEncoder     thrpt         5    19996,335     4542,521   ops/ms
d.j.IdCompressionBenchmark.testStoringLongEncoder    thrpt         5    75018,281     9012,319   ops/ms
d.j.IdCompressionBenchmark.testUnsignedEncoder       thrpt         5    38905,226     5379,667   ops/ms

Ich hätte vermutet, dass der SimpleLongEncoder der schnellste der Kompressionsalgorithmen ist, da er vergleichsweise wenige Operationen enthält. Der notwendige doppelte Zugriff (inkl Repositionierung) auf den Puffer für das Ablegen der Anzahl scheint sich hier negativ bemerkbar zu machen.

Ich habe auch noch ein paar andere Ideen, wie ich diesen Ansatz beschleunigen könnte, ein Ziel wäre es an 75% der Leistung des reinen Speicherns heranzukommen. Dagegen ist der VLQ-Encoder für positive Werte überraschend schnell trotz notwendigem Bitshifting und Rekombination von Blöcken.

Eine spannende Ausgangssituation, um weiter an der Performanceoptimierung zu arbeiten. Danke JMH.

Ressourcen

Last updated 2014-03-26 13:10:00 CET
Impressum - Twitter - GitHub - StackOverflow - LinkedIn