Why is StringBuilder much faster than String?

Question

Why is StringBuilder much faster than string concatenation using the + operator? Even though that the + operator internally is implemented using either StringBuffer or StringBuilder.

public void shortConcatenation(){
    long startTime = System.currentTimeMillis();
    while (System.currentTimeMillis() - startTime <= 1000){

        character += "Y";
    }

    System.out.println("short: " + character.length());
}

//// using String builder

 public void shortConcatenation2(){
    long startTime = System.currentTimeMillis();
    StringBuilder sb = new StringBuilder();
    while (System.currentTimeMillis() - startTime <= 1000){

        sb.append("Y");
    }
    System.out.println("string builder short: " + sb.length());
}

_{I know that there are a lot of similar questions posted here, but these don't really answer my question.}

Suu

If those don't answer your question, neither will any here. – Verne

What evidence do you have to support the assertion that StringBuilder is much faster than string concatenation using the + operator? – Ashcraft

I have written a code that uses both "+" operator and StringBuilder. Please have a look at it and try to run it to see the result – Suu

Note that your way of measuring the time is heavily flawed. You can not do something like that in a language like Java because of JVM, JIT and GC. Your measurement consists of probably 90% just sideeffects. I have seen it many times already that someone made a measurement like this with the outcome of 10ms vs 100ms and concluded that the first must be faster, although it was actually a lot slower in practice. You have to use a framework like JMH to get useable results. – Wifeless

#2971815 – Cementite

Answer 1

Do you understand how it works internally?

Every time you do stringA += stringB; a new string is created an assigned to stringA, so it will consume memory (a new string instance!) and time (copy the old string + new characters of the other string).

StringBuilder will use an array of characters internally and when you use the .append() method it will do several things:

• check if there are any free space for the string to append
• again some internal checks and run a System.arraycopy to copy the characters of the string in the array.

Personally, I think the allocation of a new string every time (creating a new instance of string, put the string, etc.) could be very expensive in terms of memory and speed (in while/for, etc. especially).

In your example, use a StringBuilder is better, but if you need (example) something simple like a .toString(),

public String toString() {
    return StringA + " - " + StringB;
}

makes no differences (well, in this case it is better you avoid StringBuilder overhead which is useless here).

Scapolite

Answer 2

Strings in Java are immutable. This means that methods that operate on strings cannot ever change the value of a string. String concatenation using += works by allocating memory for an entirely new string that is the concatenation of the two previous ones, and replacing the reference with this new string. Each new concatenation requires the construction of an entirely new String object.

In contrast, the StringBuilder and StringBuffer classes are implemented as a mutable sequence of characters. This means that as you append new Strings or characters onto a StringBuilder, it simply updates its internal array to reflect the changes you've made. This means that new memory is only allocated when the string grows past the buffer already existing in a StringBuilder.

Sword

Answer 3

I can list a very nice example for understanding the same (I mean I felt it's a nice example). Check the code here taken from a LeetCode problem: https://leetcode.com/problems/remove-outermost-parentheses/

1: Using String

public String removeOuterParentheses(String S) {

    String a = "";
    int num = 0;
    for(int i=0; i < S.length()-1; i++) {
        if(S.charAt(i) == '(' && num++ > 0) {
            a += "(";
        }
        if(S.charAt(i) == ')' && num-- > 1) {
            a += ")";
        }
    }
    return a;
}

And now, using StringBuilder.

public String removeOuterParentheses(String S) {

    StringBuilder sb = new StringBuilder();

    int a = 0;
    for(char ch : S.toCharArray()) {
        if(ch == '(' && a++ > 0) sb.append('(');
        if(ch == ')' && a-- > 1) sb.append(')');
    }
    return sb.toString();
}

The performance of both varies by a huge margin. The first submission uses String while the latter one uses StringBuilder.

As explained above the theory is the same. String by property is immutable and synchronous,i.e. its state cannot be changed. The second, for example, is expensive owing to the creation of a new memory allocation whenever a concatenation function or "+" is used. It will consume a lot of heap and in return be slower. In comparison StringBuilder is mutable, it will only append and not create an overload on the memory consumed.

Meaghanmeagher

Answer 4

The problem is that you implemented a more efficient version with StringBuilder than the compiler would. Try

while (System.currentTimeMillis() - startTime <= 1000) {
    character = new StringBuilder(character).append("Y").toString();
}

That will give you a similar result to +=. The problem is that the compiler isn't necessarily smart enough to realize that instead of repeatedly casting to StringBuilder and back to String, it could do everything with the same StringBuilder. As others have already noted, using a single StringBuilder is going to be much faster, as it only has to allocate memory occasionally.

The += version may still do more optimizations than that one. But it will act more like that than your version. Consider

sb = new StringBuilder();
while (System.currentTimeMillis() - startTime <= 1000) {
    sb.append("Y");
    character = sb.toString();
}

Almost the same as your version but as slow as creating a new StringBuilder on every iteration. Apparently it's the toString that slows things down.

Coltson