Java: Set<Integer> und Memory-Overhead

von Hubert Schmid vom 2012-01-08

Ich habe diese Woche eine Auswertung mit Hilfe eines Java-Programms gemacht, und bin dabei in ein Speicherproblem gelaufen, das ich intuitiv erst bei größeren Datenmengen erwartet hätte. In diesem Artikel beschreibe ich kurz die eigentliche Aufgabenstellung, stelle die ursprüngliche Implementierung mit ihren Problemen vor und zeige schließlich, wie ich den Code angepasst habe, um damit sowohl den Speicherverbrauch als auch die Laufzeit um eine Größenordnung zu reduzieren.

Die Aufgabenstellung

Im Wesentlichen ging es um eine Tabelle in einer Datenbank, deren Einträge von mehreren anderen Tabellen über Fremdschlüsselbeziehung referenziert wurden. Mich interessierte dabei, wie groß die paarweise Überlappung der verschiedenen, referenzierenden Tabellen ist – beziehungsweise ob die referenzierenden Tabellen getrennte Einträge referenzieren und damit unabhängig voneinander sind. Dabeihabe ich ungefähr zehn Tabellen mit Fremdschlüsseln ausgewertet, die im Schnitt jeweils mehrere Millionen Einträge enthielten.

Zur Vereinfachung abstrahiere ich im Folgenden ein wenig von der konkreten Problemstellung. Statt einem ResultSet verwende ich ein einfaches Interface, dass ich Generator genannt habe, und deren get-Methode den Schlüssel zurückgibt (der bereits eindeutig ist). Die zehn Generatoren werden zusammen mit einem eindeutigen Namen in eine Map gepackt, und die Methode analyze wertet die Überdeckung paarweise aus. Der Datentyp Values dient dabei zunächst als Platzhalter für die eigentliche Implementierung.

interface Generator {
    boolean next();
    int get();
}

void analyze(Map<String, Generator> generators) {
    // explode generators
    Map<String, Values> exploded = new HashMap<String, Values>();
    for (Map.Entry<String, Generator> entry : generators.entrySet()) {
        exploded.put(entry.getKey(), explode(entry.getValue()));
    }
    // actual analysis
    for (Map.Entry<String, Values> lhs : exploded.entrySet()) {
        for (Map.Entry<String, Values> rhs : exploded.entrySet()) {
            int count = countCommonValues(lhs.getValue(), rhs.getValue());
            println(lhs.getKey() + " " + rhs.getKey() + " " + count);
        }
    }
}

Die erste Implementierung

Es ist naheliegend die Funktionalität mit Set<Integer> zu realisieren. Und genau das habe ich im ersten Anlauf gemacht. Im obigen Code muss dafür der Platzhalter Values durch Set<Integer> ersetzt werden. Und die beiden oben verwendeten Methoden könnten beispielsweise so aussehen:

Set<Integer> explode(Generator generator) {
    Set<Integer> result = new HashSet<Integer>();
    while (generator.next()) {
        result.add(generator.get());
    }
    return result;
}

int countCommonValues(Set<Integer> lhs, Set<Integer> rhs) {
    int result = 0;
    for (int value : lhs) {
        if (rhs.contains(value)) {
            ++result;
        }
    }
    return result;
}

Die zweite Methode hätte ich alternativ auch mit Hilfe von retainAll implementieren können. Die Implementierung wäre damit zwar kürzer gewesen, aber aufgrund der zusätzlichen Kopie auch langsamer.

Das Problem

In meinem Fall bestand das Problem darin, dass die JVM nach wenigen Sekunden Laufzeit mit einer Fehlermeldung abgebrochen ist, weil sie 50 mal mehr Rechenzeit für die Speicherbereinigung wie für die Ausführung des eigentlichen Codes verwendet hat. Dazu hat sie vorgeschlagen, ihr beim nächsten Start mehr Hauptspeicher zuzuweisen. In meinem Fall hat das allerdings nicht geholfen. Denn auch mit mehr Hauptspeicher hat die JVM die Arbeit nach kürzester Zeit mit der gleichen Fehlermeldung aufgeben. Und mit noch mehr zugewiesenem Hauptspeicher ist der Rechner an seine Speichergrenze gestoßen.

Offensichtlich benötigt die JVM für die Speicherung der 50 Millionen Ids mehr Speicher, als mein Rechner zu bieten hat. Das Problem dabei sind allerdings nicht die eigentlichen Nutzdaten. Denn wenn man diese aufaddiert, kommt man nur auf ungefähr 200 MB Hauptspeicherbedarf. Das Problem ist vielmehr der Overhead, der durch die Speicherung dieser Daten in Set<Integer> entsteht.

Meinen Messungen zufolge liegt der Overhead in diesem Fall über einem Faktor 12. Verursacht wird er hauptsächlich durch das Boxing des int in einem Integer sowie durch den zusätzlichen Overhead, den jedes Element in einem HashSet mit sich bringt. Und obwohl mir das alles im Voraus bewusst war, so hat es mich doch ein wenig überrascht, wie schnell diese Grenze erreicht wird.

Die Lösung

Eine pragmatische Alternative wäre gewesen, dass Programm einfach auf einem Rechner mit deutlich mehr Hauptspeicher laufen zu lassen. Leider hatte ich diese Möglichkeit in diesem Augenblick nicht. Daher habe ich mich dazu entschieden, Set<Integer> durch eine eigene und wesentlich effizientere Datenstruktur zu ersetzen.

Solche Entscheidungen sollten wohl überlegt sein. Denn im Allgemeinen steckt hinter einer Datenstruktur wie Set<T> verhältnismäßig viel Arbeit, die gerne unterschätzt wird. In meinem Fall ist die Situation hingegen einfach: Die Anforderungen und der Funktionsumfang sind so gering, dass die Aufgabe in wenigen Minuten erledigt ist.

Um primitive Datentypen in Java effizient zu speichern, muss in erster Linie der Objekt-Overhead reduziert werden. Das heißt das Verhältnis zwischen primitiven Werten und Objekten wird erhöht, und am einfachsten nimmt man dafür ein Array. Tatsächlich ist der erste Schritt, im ursprünglichen Algorithmus den Platzhalter Values durch ein sortiertes Array int[] zu ersetzen. Die Implementierung der explode-Methode sieht damit so aus:

Values explode(Generator generator) {
    int[] result = new int[0];
    for (int size = 0; generator.next(); ++size) {
        if (size >= result.length) {
            // exponential growth
            result = Arrays.copyOf(result, result.length + size + 1);
        }
        result[size] = generator.get();
    }
    // trim to actual size
    result = Arrays.copyOf(result, size);
    Arrays.sort(result);
    return result;
}

Bemerkenswerterweise ist die Methode im Vergleich zur vorherigen Implementierung kaum komplexer geworden. Wichtig ist das exponentielle Wachstum des Arrays, wodurch der Gesamtaufwand linear bleibt. Außerdem wird das Array erst am Ende sortiert, nachdem es vollständig befüllt wurde. Aufgrund der Sortierung lässt sich die zweite Methode nun einfach wie folgt implementieren:

int countCommonValues(int[] lhs, int[] rhs) {
    int result = 0;
    for (int value : lhs) {
        if (Arrays.binarySearch(rhs, value) >= 0) {
            ++result;
        }
    }
    return result;
}

Die Methode ist gleich aufgebaut wie die entsprechende Methode für Set<Integer>, und die Implementierung ist sehr effizient. Asymptotisch betrachtet ist sie jedoch langsamer als bei der Verwendung eines HashSet – zumindest unter der Annahme, dass die Elemente hinreichend gleichmäßig verteilt werden.

Der verwendete Algorithmus ist allerdings nicht optimal. Ich habe ihn eingesetzt, weil er einfach zu implementieren ist, da die Standard-Bibliothek eine passende Hilfsfunktion enthält. Wesentlich effizienter ist hingegen ein Schnittalgorithmus, der die Sortierung beider Arrays ausnutzt und damit mit linearer Zeitkomplexität die Anzahl der gemeinsamen Elemente berechnet.

int countCommonValues(int[] lhs, int[] rhs) {
    int result = 0;
    int p = 0;
    int q = 0;
    while (p < lhs.length && q < rhs.length) {
        if (lhs[p] < rhs[q]) {
            ++p;
        } else if (lhs[p] > rhs[q]) {
            ++q;
        } else {
            ++result;
            ++p;
            ++q;
        }
    }
    return result;
}

Im Ergebnis benötigt die letzte Implementierung weniger als 8% des Speichers der ursprünglichen Implementierung. Und auch die Laufzeit hat sich in meinen Messungen um Faktor 6.5 verbessert. Das war weit mehr als ausreichend, um meine ursprüngliche Auswertung abzuschließen.

Das Fazit

Ich glaube, es ist allseits bekannt und akzeptiert, dass Java mit Hauptspeicher nicht gerade sparsam umgeht. Und dieses Beispiel hat es in einem extremen Fall nochmals gezeigt. Trotzdem sollte man deswegen nicht in Panik verfallen – und zwar aus zwei Gründen: Erstens sind in vielen Fällen die Kosten vernachlässigbar, die durch den Hauptspeicherverbrauch verursacht werden. Und zweitens: Selbst wenn das so ist, hat man in der Regel auch in Java die Möglichkeit, sehr gezielt die größten Verschwender ausfindig zu machen und gezielt zu beseitigen – wie in diesem Beispiel.