String Substring in Java

Strings sind in Java-Programmen allgegenwärtig. Jedoch hat sich die Implementierung der Klasse String in den letzten Jahren immer mal wieder geändert.

Ein Gastbeitrag von Dr. Heinz Kabutz und Sven Ruppert

Wenn in einer der ersten Versionen beispielsweise mehrere nicht konstante Strings zusammengefügt wurden, führte dies zu Aufrufen der Methode concat() oder der Verwendung der Klasse StringBuffer.

In Java 1.0 und 1.1 überprüfte die Methode hashCode() die Länge des Strings. War dieser zu lang, wurde nur jedes achte Element verwendet. Wenn man sich an dieser Stelle das Speicher-Layout ansieht, so stellt man fest, dass das nicht sonderlich effektiv war. In Java 2 wurde jedes Zeichen verwendet, und ab der Version 3 wurde der Hashcode dann gecached.

Nun könnte man annehmen, dass damit logischerweise ein großer Performancegewinn einhergehe. Leider ist das in produktiven Anwendungen aber nur recht selten der Fall. Verschärfend kommt hinzu, dass in den Fällen, in denen es einen Unterschied machen würde, die Möglichkeit besteht, das System extrem zu belasten, wenn der Hashcode 0 ist. Das liegt daran, dass in dem Fall jedes Mal der Hashcode wieder ausgerechnet werden muss. Wenn man eine Zeichenkombination findet, bei der ein Hashcode 0 ist, so kann man eine willkürliche Anzahl dieser Zeichen nacheinander schreiben, und am Ende kommt man immer wieder auf 0.

Wenn man nun eine Kombination von Zeichen hat, deren Hashcode null ergibt, kann man eine willkürliche Serie von long-Werten erzeugen. Das hat zur Folge, dass eine Operation wie hashCode(), die einen gespeicherten Wert verwendet, nun eine Komplexität von O(n) aufweisen wird.

In Java 7 wurde eine Lösung mit der Methode hash32() angeboten, die jedoch in Java 8 wieder entfernt wurde. Neulich – mein Co-Trainer Maurice Naftalin (Mastering of Lambdas) und ich (Dr. Heinz Kabutz) unterrichteten gerade zusammen unseren „Extreme Java 8“-Kurs, der sich mit Performance und Concurrency beschäftigt – dachte ich ein wenig über die Klasse String nach. Ich widme dieser Klasse immer ein wenig mehr Zeit, da sie beim Profiling meist unter den Top-Klassen zu finden ist, sehr häufig verwendet wird und aus diesem Grund einer hohen Aufmerksamkeit bedarf.

Von der Java-Version 1 bis zur Version 6 versucht die Implementierung der Klasse String das Erzeugen von Objekten mittels new char[] zu vermeiden. Unter anderem, indem ein Substring das bereits verwendete char-Array (char[]) wiederverwendet. Es wird lediglich ein anderer Offset und eine andere Länge verwendet. In der Klasse StringChars bspw. haben wir zwei Strings mit dem Inhalt “hello_world” und dem Substring “hello”. Diese verwenden dasselbe char-Array.

1import java.lang.reflect.*;
2 
3public class StringChars {
4  public static void main(String... args)
5      throws NoSuchFieldException, IllegalAccessException {
6    Field value = String.class.getDeclaredField("value");
7    value.setAccessible(true);
8 
9    String hello_world = "Hello world";
10    String hello = hello_world.substring(0, 5);
11    System.out.println(hello);
12 
13    System.out.println(value.get(hello_world));
14    System.out.println(value.get(hello));
15  }
16}

In Java 6 bekommen wir z. B. die Ausgabe

1Hello
2[C@721cdeff
3[C@721cdeff

In Java 7 und Java 8 erhalten wir hingegen die folgende Ausgabe:

1Hello
2[C@49476842
3[C@78308db1

Der Grund für die Änderung

Es zeigte sich, dass Entwickler zu oft die Methode substring() verwenden, um Speicher zu sparen. Nehmen wir an, es gibt einen String von der Größe 1 MB. Allerdings benötigen wir lediglich die ersten 5 KB. Wenn wir nun einen Substring erzeugen und annehmen, der Rest würde verworfen, irren wir uns. Und zwar deshalb, weil der neue String das darunter liegende char-Array verwendet. Demnach kann der Garbage Collector nichts freigeben, und es wird kein Speicher weniger verwendet. Um genau dieses zu erreichen, muss man das folgende Idiom verwenden.

Wir erzeugen einen neuen String, indem wir einen leeren String mit dem Substring mittels + konkatenieren.

1String hello = "" + hello_world.substring(0, 5);

Im Verlauf unseres Kurses merkte der Kunde an, dass er ein sehr großes Problem mit dem neuen Java-7- und Java-8-Ansatz habe. In der Vergangenheit wurde davon ausgegangen, dass das Erzeugen von Substrings wenig Garbage erzeugt. Nun jedoch sind die Kosten sehr hoch. Um herauszufinden, wie viele Bytes genau erzeugt werden, schrieb ich eine kleine Klasse mit dem Namen Memory. Dort verwendete ich ein eher unbekanntes Feature der Klasse ThreadMXBean. Dieses wird Inhalt eines zukünftigen Newsletters sein.

1import javax.management.*;
2import java.lang.management.*;
3 
4public class Memory {
5  public static long threadAllocatedBytes() {
6    try {
7      return (Long) ManagementFactory.getPlatformMBeanServer()
8          .invoke(
9              new ObjectName(
10                  ManagementFactory.THREAD_MXBEAN_NAME),
11              "getThreadAllocatedBytes",
12              new Object[]{Thread.currentThread().getId()},
13              new String[]{long.class.getName()}
14          );
15    } catch (Exception e) {
16      throw new IllegalArgumentException(e);
17    }
18  }
19}

Nehmen wir an, dass wir einen großen String haben. Diesen wollen wir in kleinere Stücke zerteilen.

1import java.util.*;
2 
3public class LargeString {
4  public static void main(String... args) {
5    char[] largeText = new char[10 * 1000 * 1000];
6    Arrays.fill(largeText, 'A');
7    String superString = new String(largeText);
8 
9    long bytes = Memory.threadAllocatedBytes();
10    String[] subStrings = new String[largeText.length / 1000];
11    for (int i = 0; i < subStrings.length; i++) {
12      subStrings[i] = superString.substring(
13          i * 1000, i * 1000 + 1000);
14    }
15    bytes = Memory.threadAllocatedBytes() - bytes;
16    System.out.printf("%,d%n", bytes);
17  }
18}

In Java 6 werden durch die Klasse LargeString 360.984 Bytes erzeugt. In Java 7 jedoch steigt der Verbrauch auf 20.411.536 Bytes. Die Differenz ist sehr deutlich. Probieren Sie es einfach mal auf Ihrer Maschine aus.

Wenn wir nun in Java 6 Speicher einsparen möchten, müssen wir unsere eigene String-Klasse implementieren. Das ist nicht so anstrengend, wie eventuell befürchtet, wenn wir das CharSequence-Interface verwenden. Hier möchte ich anmerken, dass diese Implementierung SubbableString nicht threadsafe ist. Um das zu verdeutlichen, wurde die Annotation von Brian Goetz @NotThreadSafe als Kommentar verwendet.

1//@NotThreadSafe
2public class SubbableString implements CharSequence {
3  private final char[] value;
4  private final int offset;
5  private final int count;
6 
7  public SubbableString(char[] value) {
8    this(value, 0, value.length);
9  }
10 
11  private SubbableString(char[] value, int offset, int count) {
12    this.value = value;
13    this.offset = offset;
14    this.count = count;
15  }
16 
17  public int length() {
18    return count;
19  }
20 
21  public String toString() {
22    return new String(value, offset, count);
23  }
24 
25  public char charAt(int index) {
26    if (index < 0 || index >= count)
27      throw new StringIndexOutOfBoundsException(index);
28    return value[index + count];
29  }
30 
31  public CharSequence subSequence(int start, int end) {
32    if (start < 0) {
33      throw new StringIndexOutOfBoundsException(start);
34    }
35    if (end > count) {
36      throw new StringIndexOutOfBoundsException(end);
37    }
38    if (start > end) {
39      throw new StringIndexOutOfBoundsException(end - start);
40    }
41    return (start == 0 && end == count) ? this :
42        new SubbableString(value, offset + start, end - start);
43  }
44}

Wenn wir nun diese Verbesserung verwenden, benötigen wir unter Java 6 bis Java 8 281.000 Bytes. Unter Java 7 und Java 8 ergibt dies eine Verbesserung um den Faktor 72.

Abschließend möchte ich bitten, dies im Hinterkopf zu behalten, wenn eine Migration von Java 6 auf Java 8 ansteht. Ich weiß, dass zu viele meiner Kunden bei Java 6 stehengeblieben sind, da sie keine Argumente für eine Finanzierung der Migration gefunden haben. Abgesehen von den syntaktischen Vorzügen in Java 7 und Java 8 ist es ratsam, die Bugs aus Java 6 loszuwerden. Je schneller, desto besser.

Dieser Beitrag ist eine autorisierte Übersetzung des Java Specialist Newsletters Nr. 230 von Dr. Heinz Kabutz . Deutsche Fassung von Sven Ruppert .

Vom 8.-11. Dezember gibt Dr. Heinz Kabutz am codecentric-Standort Düsseldorf seinen bewährten „Java Specialists Master Course“. Mehr Informationen und eine Kursbeschreibung befinden sich auf der entsprechenden Schulungsseite .