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 effi