Saturday 7 July 2012

Item 51: Beware the performance of string concatenation


The string concatenation operator (+) is a convenient way to combine a few strings into one. It is fine for generating a single line of output or for constructing the string representation of a small, fixed-size object, but it does not scale. Using the string concatenation operator repeatedly to concatenate n strings requires time quadratic in n. It is an unfortunate consequence of the fact that strings are immutable (Item 15). When two strings are concatenated, the contents of both are copied.

For example, consider the following method that constructs a string representation of a billing statement by repeatedly concatenating a line for each item:

// Inappropriate use of string concatenation - Performs horribly!
public String statement() {
String result = "";
for (int i = 0; i < numItems(); i++)
result += lineForItem(i); // String concatenation
return result;
}

This method performs abysmally if the number of items is large. To achieve acceptable performance, use a StringBuilder in place of a String to store the statement under construction. (The StringBuilder class, added in release 1.5, is an unsynchronized replacement for StringBuffer, which is now obsolete.)

public String statement() {
StringBuilder b = new StringBuilder(numItems() * LINE_WIDTH);
for (int i = 0; i < numItems(); i++)
b.append(lineForItem(i));
return b.toString();
}

The difference in performance is dramatic. If numItems returns 100 and lineForItem returns a constant 80-character string, the second method is eightyfive times faster than the first on my machine. Because the first method is quadratic in the number of items and the second is linear, the performance difference is even more dramatic for larger numbers of items. Note that the second method preallocates a StringBuilder large enough to hold the result. Even if it is detuned to use a default-sized StringBuilder, it is still fifty times faster.

The moral is simple: don’t use the string concatenation operator to combine more than a few strings unless performance is irrelevant. Use StringBuilder’s append method instead. Alternatively, use a character array, or process the strings one at a time instead of combining them.


Reference: Effective Java 2nd Edition by Joshua Bloch