String-Verkettung
In Java gibt es zwei unterschiedliche Klassen String und StringBuilder zur Verarbeitung von Zeichenketten, deren prinzipielle Eigenschaften in Kapitel 11 erläutert wurden. Java-Anfänger verwenden meist hauptsächlich die Klasse String, denn sie stellt die meisten Methoden zur Zeichenkettenextraktion und -verarbeitung zur Verfügung und bietet mit dem +-Operator eine bequeme Möglichkeit, Zeichenketten miteinander zu verketten.
Daß diese Bequemlichkeit ihren Preis hat, zeigt folgender Programmausschnitt:
001 String s;
002 s = "";
003 for (int i = 0; i < 20000; ++i) {
004 s += "x";
005 }
Listing 50.1: Langsame String-Verkettung
Das Programmfragment hat die Aufgabe, einen String zu erstellen, der aus 20000 aneinandergereihten »x« besteht. Das ist zwar nicht sehr praxisnah, illustriert aber die häufig vorkommende Verwendung des +=-Operators auf Strings. Der obige Code ist sehr ineffizient, denn er läuft langsam und belastet das Laufzeitsystem durch 60000 temporäre Objekte, die alloziert und vom Garbage Collector wieder freigegeben werden müssen. Der Compiler übersetzt das Programmfragment etwa so:
001 String s;
002 s = "";
003 for (int i = 0; i < 20000; ++i) {
004 s = new StringBuilder(s).append("x").toString();
005 }
Listing 50.2: Wie der Java-Compiler String-Verkettungen übersetzt
Dieser Code ist in mehrfacher Hinsicht unglücklich. Pro Schleifendurchlauf wird ein temporäres StringBuilder-Objekt alloziert und mit dem zuvor erzeugten String initialisiert. Der Konstruktor von StringBuilder erzeugt ein internes Array (also eine weitere Objektinstanz), um die Zeichenkette zu speichern. Immerhin ist dieses Array 16 Byte größer als eigentlich erforderlich, so dass der nachfolgende Aufruf von append das Array nicht neu allozieren und die Zeichen umkopieren muss. Schließlich wird durch den Aufruf von toString ein neues String-Objekt erzeugt und s zugewiesen. Auf diese Weise werden pro Schleifendurchlauf drei temporäre Objekte erzeugt, und der Code ist durch das wiederholte Kopieren der Zeichen im Konstruktor von StringBuilder sehr ineffizient.
Eine eminente Verbesserung ergibt sich, wenn die Klasse StringBuilder und ihre Methode append direkt verwendet werden:
001 String s;
002 StringBuilder sb = new StringBuilder(1000);
003 for (int i = 0; i < 20000; ++i) {
004 sb.append("x");
005 }
006 s = sb.toString();
Listing 50.3: Performante String-Verkettungen mit StringBuilder.append
Hier wird zunächst ein StringBuilder erzeugt und mit einem 1000 Zeichen großen Puffer versehen. Da die StringBuilder-Klasse sich die Länge der gespeicherten Zeichenkette merkt, kann der Aufruf append("x") meist in konstanter Laufzeit erfolgen. Dabei ist ein Umkopieren nur dann erforderlich, wenn der interne Puffer nicht mehr genügend Platz bietet, um die an append übergebenen Daten zu übernehmen. In diesem Fall wird ein größeres Array alloziert und der Inhalt des bisherigen Puffers umkopiert. In der Summe ist die letzte Version etwa um den Faktor 10 schneller als die ersten beiden und erzeugt 60000 temporäre Objekte weniger.
Interessant ist dabei der Umfang der Puffervergrößerung, den das StringBuilder-Objekt vornimmt, denn er bestimmt, wann bei fortgesetztem Aufruf von append das nächste Mal umkopiert werden muss. Anders als beispielsweise bei der Klasse Vector, die einen veränderbaren Ladefaktor besitzt, verdoppelt sich die Größe eines StringBuilder-Objekts bei jeder Kapazitätserweiterung. Dadurch wird zwar möglicherweise mehr Speicher als nötig alloziert, aber die Anzahl der Kopiervorgänge wächst höchstens logarithmisch mit der Gesamtmenge der eingefügten Daten. In unserem Beispiel kann der interne Puffer zunächst 1000 Zeichen aufnehmen, wird beim nächsten Überlauf auf etwa 2000 Zeichen vergrößert, dann auf 4000, 8000, 16000 und schließlich auf 32000 Zeichen. Hätten wir die initiale Größe auf 20000 Zeichen gesetzt, wäre sogar überhaupt kein Kopiervorgang erforderlich geworden und das Programm hätte 12000 Zeichen weniger alloziert.
Bei der Verwendung der Operatoren + und += auf String-Objekten sollte man zusätzlich bedenken, dass deren Laufzeit nicht konstant ist (bzw. ausschließlich von der Länge des anzuhängenden Strings abhängt). Tatsächlich hängt sie auch stark von der Länge des Strings ab, an den angehängt werden soll, denn die Laufzeit eines Kopiervorgangs wächst nun einmal proportional zur Länge des zu kopierenden Objekts. Damit wächst das Laufzeitverhalten der Schleife in Listing 50.1 nicht linear, sondern annähernd quadratisch. Es verschlechtert sich also mit zunehmender Länge der Schleife überproportional.
)
