Dynamic string concatenation by example, 3900 times more expensive than StringBuilder

The significant cost associated with using the String concatenation operator, and need to use a StringBuilder instead of a String to store the interim object under construction, is well known. In this post, we start by firstly presenting eye opening results from some performance tests to quantify why one needs to consider the cost of String concatenation, we then take a look under the hood to see why dynamic String concatenation is so inefficient.

Performance Tests: Does Concatenating n Strings Really Take Time Quadratic in n?

Joshua Bloch, in Effective Java, advises that using the concatenation operator repeatedly to concatenate n strings requires time quadratic in n due to strings being immutable and the need to copy the contents of both strings when performing a concatenation operation.

In terms of Big O notation, the above means O(n²) or O-n-squared, which is disastrous time wise. To see just how disastrous, here are the results of 4 runs of a simple test, the 5th run was stopped since I was not willing to wait approximately 40 seconds squared.

Number concatenations

+/ms StringBuider.append/ms
100 0 0
1000 22 0
10 000 306 1
100 000 39 259 10

The results show an exponential increase in time when looking at the concatenation time column and since big O time estimates are not exact, one can say yes, concatenating n strings really does take time quadratic in n.

If you’d like to run the tests on your machine, please find the simple program used below.

public class StringConcatenationPerformance {

	public static void main(String[] args) {

        final String base = getBaseString();
        int CONCATENATIONS = 1000;

        long startTime = System.currentTimeMillis();

        String result = base;

        for(int i = 0; i < CONCATENATIONS ; i++) {
            result = result + "b";
        }

        long estimatedTime = System.currentTimeMillis() - startTime;

        System.out.println(result.length());
        System.out.println(estimatedTime);

        startTime = System.currentTimeMillis();
        StringBuilder builder = new StringBuilder(base);
        for(int i = 0; i < CONCATENATIONS ; i++) {
            builder.append("b");
        }
        estimatedTime = System.currentTimeMillis() - startTime;
        System.out.println(builder.toString().length());
        System.out.println(estimatedTime);

    }

    private static String getBaseString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 1000; i++) {
            builder.append("a");
        }
        return builder.toString();
    }

}

String Concatenation: Under The Hood

Eyal Lupu has kindly done the hard work of opening the hood, meaning that he used the javap utility (java class file disassembler) to look at the generated byte code of a concatenation loop.

His results show that the following:

String result = "";
for (int t=0; t<10000; ++t ) {
 result = result + getSomeString();
}

Results, in effect, in the following:

String result = "";
for (int t=0; t<10000; ++t ) {
 result = new StringBuilder(String.valueOf(result)).append(getSomeString()).toString();
}

The above created 10 000 Strings on the heap, 10 000 StringBuilder objects, then there is the additional cost of, within StringBuilder.append, allocating an array large enough to fit our characters and copying characters from the old smaller array to the larger array.

References

  1. Under the Hood of Java Strings Concatenating Performance, Eyal Lupu
  2. java String concatenation, Tom Hawtin
  3. Effective Java, Second Edition, Joshua Bloch, Item 51: Beware the performance of string concatenation
  4. Java String Concatenation, Joseph Kulandai
  5. Stivlo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s