Speicher sparen mit String Interning in Java

Attila Szegedis Vortrag über „lessons learned about the JVM “ überraschte mich insbesondere dadurch dass er relativ ausgiebig darauf einging, wie viel Speicher eigentlich durch Daten belegt wird. Dies ist für Enterprise Java Entwickler eher untypisch. Doch er hatte einige gute Anwendungsbeispiele aus seiner Zeit bei Twitter.

Speicherverbrauch von Daten

Frage: Wie viel Speicher benötigt eigentlich der String „Hello World“ ?
Antwort: 62/86 Bytes (32/64 bit Java)!
Dies teilt sich auf in 8/16 (Object Header für String) + 11 * 2 (Zeichen) + [8/16 (Object Header char Array) + 4 (array Länge) aufgefüllt auf 16/24] + 4 (Offset) + 4 (Count) + 4 (HashCode) + 4/8 (Referenz aufs char Array). [Auf 64Bit ist das String Objekt auf 40 aufgefüllt].

Das Problem

Stellen wir uns vor, wir haben jede Menge Locations, welche an unseren Tweets hängen und die Position des Users beschreiben. Die Implementierung könnte dann etwa so aussehen

Wenn wir nun alle Orte aller jemals gemachten Tweets laden, so ist klar, dass dies ziemlich viele String Objekte erzeugt. Und bei der Größe von Twitter ist es auch sehr wahrscheinlich, dass diese Strings zu einem großen Teil aus Duplikaten bestehen. Attila sagte in seinem Vortrag, dass diese Daten nicht in einen 32 GB Heap passten. Also ist die Frage: Wie bekommen wir die Daten kleiner, so das sie alle in den Speicher passen?

Schauen wir uns zwei Lösungen an, die sogar kombiniert werden können.

Attilas Lösung

Da es eine mehr oder weniger gut versteckte Abhängigkeit der Daten zueinander gibt kann man, sobald man sie entdeckt hat, den Speicherbedarf ohne technische Tricks reduzieren. Wir können eine einfache Normalisierung der Daten durchführen:

Dies ist eine elegante Lösung, da Städte selten ihre Region oder ihr Land wechseln. Diese Kombination ist also eigentlich immer eindeutig. Und diese Darstellung ist dennoch flexibel genug um Abweichungen abbilden zu können. Dies ist insbesondere bei von Benutzern eingegebenen Daten sinnvoll. Nach der Normalisierung belegen mehrere Tweets aus „Solingen, NRW, DE“ nur eine SharedLocation.
Jedoch würde „Ratingen, NRW, DE“ immer noch 3 weitere Strings im Speicher anlegen, anstatt nur den neuen „Ratingen“ zur erstellen. In dem Fall von Twitter hat nach diesem Refactoring die Datenmenge in 20GB Heap gepasst.

String Interning

Was aber, wenn man entweder das Modell nicht verändern kann (oder will), oder man in dem Fall von Twitter auch keine 20GB Heap gehabt hätte?
Die Antwort ist String Interning, was dafür sorgt, dass jeder String nur ein einziges Mal im Speicher bleibt.
Leider gibt es einige Verwirrung über den Sinn von String interning. Viele Entwickler fragen ob dies denn den Vergleich zweier Strings beschleunigt, da dann die Strings ja sogar identisch sind. Dies ist zwar der Fall (wie bei allen Objekten)

// java.lang.String
public boolean equals(Object anObject) {
  if (this == anObject) {
    return true;
  }
  //...
}

Jedoch ist die Performance von „equals“ nicht der Grund aus dem man Interning verwenden sollte. Es ist dafür gedacht Speicher zu sparen.

Verwendet String.intern() nur auf Strings die häufig vorkommen und auch nur um Speicher zu sparen

Die Effizienz von Interning ist durch das Verhältnis von Dubletten zu einmaligen Strings bestimmt. Und es hängt auch davon ab wie einfach der Code an den stringerzeugenden Stellen zu modifizieren ist.

Also, wie geht das nun?

String Interning verwendet eine Instanz eines Strings (der also schon im Heap existiert) und prüft ob eine identische Kopie in der StringTable existiert.
Diese StringTable ist so etwas wie ein HashSet das den String in der Permanent Generation speichert. Der alleinige Zweck dieser Table ist eine einzige Instanz pro Zeichenkette am Leben zu halten. Falls der String dort schon ist, wird diese Instanz zurückgeliefert. Ansonsten wird diese Zeichenkette dort gespeichert:

Als Ergebnis existiert jeder String nur ein Mal.

Interne Strings richtig verwendet

Die richtige Stelle zur Verwendung von String Interning ist der Ort an dem Zeichenketten aus externen Quellen, z.B. Datenbanken, gelesen werden. Alle Strings die bereits hartcodiert im Quelltext stehen werden durch den Compiler zu automatisch internen Strings.
Ein Beispiel sieht so aus:

Alle neu erstellten Location Objekte werden den internen String verwenden. Die temporären Strings werden anschließend durch die Garbage Collection entfernt.

Wie effektiv ist String Interning

Am besten verwendet man zur Bestimmung der Sinnhaftigkeit von Interning einen Heap Dump eines recht vollen Heaps. Es kann sogar einer von einem OutOfMemoryError sein.
Wenn man ihn dann in Eclipse MAT öffnet und den java.lang.String aus dem Histogram auswählt, kann man im Kontextmenü „Java Basics“ und „Group By Value“ wählen

Je nach Größe des Heaps kann dies nun eine lange Zeit dauern. Am Ende kommt ein Ergebnis wie dieses heraus, dass man entweder nach Anzahl Objekten oder nach Belegtem Speicher sortieren kann:

In dem Screenshot sieht man eine erstaunliche Menge von zwei Millionen leerer Strings! Diese belegen unglaubliche 130 MB Speicher. Als nächstes folgt JavaScript und diverse technische Strings, wie die keys die hier für Lokalisierung verwendet werden. Und es gibt auch einige fachlich motivierte Strings in hoher Anzahl.
Bei den fachlichen Strings lässt sich wahrscheinlich noch am einfachsten feststellen wo sie erstellt werden. Für alle Anderen müssten wir die Option „Merge shortest Path to GC Root“ verwenden um die Codestellen zu finden wo sie erzeugt werden.

Kompromisse

Warum macht man denn nicht aus allen Zeichenketten interne Strings? Weil es den Code verlangsamt! Hier ein kleines Beispiel:

Dieser Code erstellt stark referenzierte String Objekte. Am Schluss geben wir auch noch ein Element aus, da sonst das ganze Array „arr“ wegoptimiert werden könnte. Anschließend laden wir nur 10 verschieden Strings aus unserer Datenbank. Ich verwende hier „new String()“ um die temporären Strings zu simulieren. Am Schluss führe ich noch eine Garbage Collection durch, so das alle temporären Ojekte nicht betrachtet werden.

Diesen Code habe ich auf einem 64bit Windows, JDK 1.6.0_27, i5-2520M CPU mit 8GB Ram laufen lassen. Dazu habe ich die Parameter -XX:+PrintGCDetails -Xmx6G -Xmn3G gesetzt. Hier die Ausgaben:
Ohne intern()

Mit intern()

Wir sehen also, dass die Differenz durchaus signifikant ist. Mit intern() benötigte der Code 3,3 Sekunden länger. Jedoch war die Speicherersparnis enorm. Am Ende benötigten wir lediglich 253472K(250M) Speicher. Ohne intern() belegten die Strings ganze 2397635K (2.4G). Dies ist schon ein beachtlicher Unterschied und zeigt anschaulich welchen Effekt String.intern() zu welchem Preis haben kann.