Java: Set<Integer> und Memory-Overhead
von Hubert Schmid vom 2012-01-08
Ich habe diese Woche eine kleine 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 werde ich kurz die eigentliche Aufgabenstellung motivieren, die ursprüngliche Implementierung und ihre Probleme vorstellen und schließlich zeigen, wie ich den Code angepasst habe, um damit sowohl den Speicherverbrauch als auch die Laufzeit um einen Faktor 10 zu reduzieren.Die AufgabenstellungEs ist nicht unüblich, dass Datenbanken von mehreren, abgrenzbaren Teilsystemen genutzt werden. Und ich habe mich für eine bestimmte Tabelle in so einer Datenbank interessiert, deren Einträge von mehreren Teilsystemen über Fremdschlüssel referenziert werden.Mich interessierte dabei, welche Teilsysteme sich Zeilen in der fraglichen Tabelle teilen beziehungsweise welche Systeme zeilenweise unabhängig sind. Dabei habe ich ungefähr 10 Foreign-Key-Tabellen mit im Schnitt mehreren Millionen unterschiedlichen Schlüssel ausgewertet.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> first : exploded.entrySet()) {
for (Map.Entry<String, Values> second : exploded.entrySet()) {
int count = countCommonValues(first.getValue(), second.getValue());
System.out.println(first.getKey() + " " + second.getKey() + " " + count);
}
}
}Die erste ImplementierungIch finde es relativ naheliegend die Funktionalität mit Set<Integer> zu realisieren. Und genau das habe ich auch 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 zwar kürzer gewesen, aber dafür auch langsamer aufgrund der kompletten Kopie einer großen Set-Datenstruktur.Das ProblemIn meinem Fall war das Problem ganz konkret, dass nach einigen Sekunden Laufzeit die JVM mit der Fehlermeldung abgebrochen ist, dass sie 50 mal so viel Rechenzeit für die Speicherbereinigung als für die Ausführung des eigentlichen Codes benötigt, und daher keine Lust mehr hat.Ganz konkret hat sie auch noch vorgeschlagen, ihr beim nächsten Start mehr Hauptspeicher zuzuweisen. In meinem Fall hat das allerdings nicht geholfen. Denn auch mit mehr Hauptspeicher hat sie die Arbeit nach wenigen Sekunden 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 die belegen nur ungefähr 200 MB Hauptspeicher. 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, dass diese Grenze so nahe liegt.Die LösungEine einfache Alternative wäre gewesen, dass Programm einfach auf einem Rechner laufen zu lassen, der zehnmal so viel Hauptspeicher hat. Leider hatte ich diese Möglichkeit in diesem Augenblick nicht. Stattdessen habe ich das Set<Integer> durch eine andere und wesentlich effizientere Datenstruktur ersetzt.Für diese Aufgabe wäre es viel zu zeitaufwendig gewesen, eine bessere und alternative Datenstruktur für Set<Integer> zu schreiben. Aber das war auch gar nicht notwendig. Denn die Anforderungen an die Datenstruktur sind in diesem Beispiel minimal. Daher war es mir möglich, in wenigen Minuten die notwendige Funktionalität genau für meinen Anwendungsfall zu imlementieren.Wenn man primitive Datentypen in Java effizient speichern will, dann muss man den Objekt-Overhead reduzieren. Dazu speichert man einfach mehrere Werte in einem Objekt - und am einfachsten nimmt man dazu ein Array. Im ursprünglichen Algorithmus ersetze ich also einfach den Platzhalter Values durch int[], und 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 Implementierung für Set<Integer> dadurch nicht signifikant komplexer geworden. Wichtig ist noch der Aufruf von Arrays.sort. Denn erst durch die Eigenschaft der Sortierung kann ich den Schnitt zweier Arrays effizient bestimmen. Und die Implementierung der zweiten Methode ist damit ebenfalls relativ einfach.int countCommonValues(int[] lhs, int[] rhs) {
int result = 0;
for (int value : lhs) {
if (Arrays.binarySearch(rhs, value) >= 0) {
++result;
}
}
return result;
}Die Methode sieht für Set<Integer> und int[] praktisch identisch aus, und ist auch fast genauso effizient. Genau lässt sich letzterer Punkt allerdings nicht feststellen, denn im ersten Fall hängt er von Verteilung der Elements im HashSet ab. Um aber sicher zu gehen und den Code in jeder Hinsicht performanter zu machen, kann man stattdessen auch den richtigen Schnittalgorithmus verwenden.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 neue Implementierung mit der alternativen Datenstruktur weniger als 8% der ursprünglichen Implementierung. Und auch die Laufzeit hat sich um den Faktor 6.5 verbessert. Das war mehr als ausreichend, um meine ursprüngliche Auswertung abzuschließen.Das FazitIch 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 das aus zwei Gründen: Erstens sind in vielen Fällen die Kosten vernachlässigbar, die durch den Hauptspeicherverbrauch verursacht. Und zweitens: Selbst wenn das so ist, dann 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 dieses Beispiel ebenfalls zeigen sollte.
