Speicher sparen mit String Interning in Java

Attila Szegedis Vortrag über “lessons learned about the JVM” auf der QCon London überraschte mich, da 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

class Location {
	String city;
	String region;
	String countryCode;
	double long;
	double lat;
}

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:

class SharedLocation {
	String city;
	String region;
	String countryCode;
}
class Location {
	SharedLocation sharedLocation;
	double long;
	double lat;
}

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:

// OpenJDK 6 code
JVM_ENTRY(jstring, JVM_InternString(JNIEnv *env, jstring str))
  JVMWrapper("JVM_InternString");
  JvmtiVMObjectAllocEventCollector oam;
  if (str == NULL) return NULL;
  oop string = JNIHandles::resolve_non_null(str);
  oop result = StringTable::intern(string, CHECK_NULL);
  return (jstring) JNIHandles::make_local(env, result);
JVM_END
 
oop StringTable::intern(Handle string_or_null, jchar* name,
                        int len, TRAPS) {
  unsigned int hashValue = hash_string(name, len);
  int index = the_table()->hash_to_index(hashValue);
  oop string = the_table()->lookup(index, name, len, hashValue);
 
  // Found
  if (string != NULL) return string;
 
  // Otherwise, add to symbol to table
  return the_table()->basic_add(index, string_or_null, name, len,
                                hashValue, CHECK_NULL);
}

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:

String city = resultSet.getString(1);
String region = resultSet.getString(2);
String countryCode = resultSet.getString(3);
double city = resultSet.getDouble(4);
double city = resultSet.getDouble(5);
 
Location location = new Location(city.intern(), region.intern(), countryCode.intern(), long, lat);
allLocations.add(location);

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:

private static final int MAX = 40000000;
public static void main(String[] args) throws Exception {
	long t = System.currentTimeMillis();
	String[] arr = new String[MAX];
	for (int i = 0; i < MAX; i++) {
		arr[i] = new String(DB_DATA[i % 10]);
		// and: arr[i] = new String(DB_DATA[i % 10]).intern();
	}
	System.out.println((System.currentTimeMillis() - t) + "ms");
	System.gc();
	System.out.println(arr[0]);
}

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()

1519ms
[GC [PSYoungGen: 2359296K->393210K(2752512K)] 2359296K->2348002K(4707456K), 5.4071058 secs] [Times: user=8.84 sys=1.00, real=5.40 secs] 
[Full GC (System) [PSYoungGen: 393210K->392902K(2752512K)] [PSOldGen: 1954792K->1954823K(1954944K)] 2348002K->2347726K(4707456K) [PSPermGen: 2707K->2707K(21248K)], 5.3242785 secs] [Times: user=3.71 sys=0.20, real=5.32 secs] 
DE
Heap
 PSYoungGen      total 2752512K, used 440088K [0x0000000740000000, 0x0000000800000000, 0x0000000800000000)
  eden space 2359296K, 18% used [0x0000000740000000,0x000000075adc6360,0x00000007d0000000)
  from space 393216K, 0% used [0x00000007d0000000,0x00000007d0000000,0x00000007e8000000)
  to   space 393216K, 0% used [0x00000007e8000000,0x00000007e8000000,0x0000000800000000)
 PSOldGen        total 1954944K, used 1954823K [0x0000000680000000, 0x00000006f7520000, 0x0000000740000000)
  object space 1954944K, 99% used [0x0000000680000000,0x00000006f7501fd8,0x00000006f7520000)
 PSPermGen       total 21248K, used 2724K [0x000000067ae00000, 0x000000067c2c0000, 0x0000000680000000)
  object space 21248K, 12% used [0x000000067ae00000,0x000000067b0a93e0,0x000000067c2c0000)

Mit intern()

4838ms
[GC [PSYoungGen: 2359296K->156506K(2752512K)] 2359296K->156506K(2757888K), 0.1962062 secs] [Times: user=0.69 sys=0.01, real=0.20 secs] 
[Full GC (System) [PSYoungGen: 156506K->156357K(2752512K)] [PSOldGen: 0K->18K(5376K)] 156506K->156376K(2757888K) [PSPermGen: 2708K->2708K(21248K)], 0.2576126 secs] [Times: user=0.25 sys=0.00, real=0.26 secs] 
DE
Heap
 PSYoungGen      total 2752512K, used 250729K [0x0000000740000000, 0x0000000800000000, 0x0000000800000000)
  eden space 2359296K, 10% used [0x0000000740000000,0x000000074f4da6f8,0x00000007d0000000)
  from space 393216K, 0% used [0x00000007d0000000,0x00000007d0000000,0x00000007e8000000)
  to   space 393216K, 0% used [0x00000007e8000000,0x00000007e8000000,0x0000000800000000)
 PSOldGen        total 5376K, used 18K [0x0000000680000000, 0x0000000680540000, 0x0000000740000000)
  object space 5376K, 0% used [0x0000000680000000,0x0000000680004b30,0x0000000680540000)
 PSPermGen       total 21248K, used 2725K [0x000000067ae00000, 0x000000067c2c0000, 0x0000000680000000)
  object space 21248K, 12% used [0x000000067ae00000,0x000000067b0a95d0,0x000000067c2c0000)

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.

  • Facebook
  • Delicious
  • Digg
  • StumbleUpon
  • Reddit
  • Blogger
  • LinkedIn
Fabian Lange

9 Antworten auf Speicher sparen mit String Interning in Java

  1. Der Code wird nicht nur langsamer, sondern “interne Strings” werden ja auch nicht mehr gelöscht. Wenn man da falsch optimiert, läuft man Gefahr es viel schlimmer zu machen.

    Die eigentlich interessante Frage hier: wieso werden so viele leere Stringinstanzen erzeugt und verbleiben offensichtlich auch referenziert im Speicher?

  2. Fabian Lange sagt:

    Hallo Michael,
    je nach JVM werden intere Strings auch Garbage Collected. Dafür müssen Sie allerdings tatsächlich Garbage sein (also nicht mehr stark/strong referenziert).
    In dem Screenshot sind es deshalb so viele leere Strings, weil hier eine Kundendatenbank im Speicher ist. Diese wurde über Hibernate aus der Datenbank gelesen und sehr viele String Felder haben keinen Wert. Deshalb gibt es halt so viele Leerstrings.

    Fabian

  3. Andrej Golovnin sagt:

    Hallo Michael, Hallo Fabian,

    seit Java 7 (Oracle JVM) werden interne String in dem normalen Java Heap Space angelegt (s. Bug #6962931). Zusätzlich wurde eine neue XX-Option (s. Bug #6962930) eingeführt: -XX:StringTableSize=hashTableSize. Über diese Option kann man jetzt die Größe des Hashtables für interne Strings festlegen. Der Default-Wert ist auf 1009 festgelegt. Für bestimmte Anwendungen kann es durchaus sinnvoll sein, die Größe des Hashtables zu verändern. S. Bug #6988220 für mehr Details.

    Gruß,
    Andrej

  4. di sagt:

    nice article. may be one of these days you can write something about Memory Footprint.there is so much inaccurate information out there , it is difficult to find out what is going on really.

  5. Simon sagt:

    Are interned strings eligible for collection at a full GC? Would it be wise to Intern uuid strings that are pk identities of entities with a long lived process?

  6. Jamie sagt:

    There’s also a non-permgen intern implementation available in the Guava libraries which provides weak/strong reference implementations.

    It also supports other immutable objects as well.

    Interface:
    http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/Interner.java

    and

    Implementations:
    http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/Interners.java

  7. B sagt:

    what is the difference ?
    String s1=new String(“abcde”);
    sop(s1);

    sop(s1.intern());

    am confused of string .,.

    • Fabian Lange sagt:

      if you use intern, your method sop might get a reference to s1, which would be the same, or if that “abcde” was already interned before, it would get a reference to that previously interned string instead and s1 would be garbage collected.

  8. This was a really nice article!
    I’ve been used String interning one project to lead with a search hit 1000 names per second with Red-Black Tree – O(log n) strategy on server side, with multiple threads managed with ExecutorService on thread pool .

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>