String Performance

String in Java is special, because its immutable particularity.
Immutable String is the cornerstone of Java Security and thread-safety, without it Java is brittle.

But immutable comes with price, whenever you "modify" String, you are actually creating a new one, and in most cases the old one becomes garbage. Thanks for Java's automatic garbage collection mechanism, programmers don't have to worry about those String garbages too much. But if you totally ignore them, or even abuse String api, your program will suffer from excessive GC.

In JDK's history, some efforts have been made to improve(to avoid) String garbages creation. JDK 1.0 added StringBuffer, JDK 1.5 added StringBuilder. StringBuffer and StringBuilder are same except StringBuilder is not thread-safe. Most String connecting operation are happened inside a method call which is under a single thread context, so no need to sync. So JDK's advice is whenever you need to connect String, try to use StringBuffer and StringBuilder, whenever you are in a single thread context, use StringBuilder rather than StringBuffer. Following this advice can improve performance compares to directly using String.concat() in most cases, but the real world cases sometimes can be complex. This advice can not give you the best performance gain. Today let's talk about String's connecting performance deeply, to help you completely understand this.

First, let's refute a rumor, some people says SB(StringBuffer and StringBuilder) is always better than String.concat(). This is wrong! sometime String.concat() can beat SB! We will prove this by an example.

Goal:
    Connect two Strings,
    String a = "abcdefghijklmnopq"; //length=17
    String b = "abcdefghijklmnopqr"; //length=18

Explanation:
    We are going to analyze garbage creation by different connecting solution. In our discuss, we will ignore input parameters(String a and b), even they become garbages, since they are not created by our code. We only count String's internal char[], since except that String's other states are very small, we can simply ignore them.

Solution 1:
    Use String.concat()
Code:
    String result = a.concat(b);
This is very simple, let's see JDK String source code to analyze what actually happens.

String source code:

public String concat(String str) {
    int otherLen = str.length();
    if (otherLen == 0) {
        return this;
    }
    char buf[] = new char[count + otherLen];
    getChars(0, count, buf, 0);
    str.getChars(0, otherLen, buf, count);
    return new String(0, count + otherLen, buf);
}

String(int offset, int count, char value[]) {
    this.value = value;
    this.offset = offset;
    this.count = count;
}

    This piece of code creates a new char[] whose length equals a.length() + b.length(), then copys a's and b's content to the new char[], finally creates a new String from the char[]. You need to pay attention to the constructor, it only has package accessibility, it directly uses the passed in char[] as its internal char[], does not do any copy protection. This constructor has to be package visible, otherwise user may use this constructor to break String's immutable.(Modify the char[] after uses it to create a String.) JDK's code guarantees no one will modify the char[] passed to this constructor.

    In this whole process, we do not create any garbage(As we said, a and b are parameters, not created by you, so we don't count them). So we are good

Solution 2:
    Use SB.append(), let's use StringBuilder as a demo, it is the same thing for StringBuffer.
Code:
    String result = new StringBuilder().append(a).append(b).toString();

This code looks more complex than String.concat(), but how about the performance? Let's analyze it by 4 steps, new StringBuilder(), append(a), append(b) and toString().
First, new StringBuilder().
See StringBuilder source code:
public StringBuilder() {
    super(16);
}
AbstractStringBuilder(int capacity) {
    value = new char[capacity];
}
We create a chat[] whose size is 16, no garbage created so far.

Second, append(a).
See source code:
public StringBuilder append(String str) {
    super.append(str);
    return this;
}
public AbstractStringBuilder append(String str) {
    if (str == null) str = "null";
    int len = str.length();
    if (len == 0) return this;
    int newCount = count + len;
    if (newCount > value.length)
        expandCapacity(newCount);
    str.getChars(0, len, value, count);
    count = newCount;
    return this;
}
void expandCapacity(int minimumCapacity) {
    int newCapacity = (value.length + 1) * 2;
    if (newCapacity < 0) {
        newCapacity = Integer.MAX_VALUE;
    } else if (minimumCapacity > newCapacity) {
        newCapacity = minimumCapacity;
    }
    value = Arrays.copyOf(value, newCapacity);
}
    This piece of code ensures the capacity first, which creates a new char[] whose size is 34, then causes the old 16 char[] becomes garbage. Check point 1, we create 1st garbage char[], size 16.

Third, append(b).
Same logic, ensures the capacity first, which creates a new char[] whose size is 70, then cause the old 34 char[] becomes garbage. Check point 2, we create 2nd garbage char[], size 34.

Finally, toString().

See source code:
public String toString() {
    // Create a copy, don't share the array
    return new String(value, 0, count);
}
public String(char value[], int offset, int count) {
    if (offset < 0) {
        throw new StringIndexOutOfBoundsException(offset);
    }
    if (count < 0) {
        throw new StringIndexOutOfBoundsException(count);
    }
    // Note: offset or count might be near -1>>>1.
    if (offset > value.length - count) {
        throw new StringIndexOutOfBoundsException(offset + count);
    }
    this.offset = 0;
    this.count = count;
    this.value = Arrays.copyOfRange(value, offset, offset+count);
}
    You should pay attention to this String constructor, it is public, so it has to do a copy protection, otherwise user may break String's immutable. But it creats our 3rd garbage, whose size is 70.

So totally we create 3 garbage objects, total size is 16+34+70=120 chars! Java is using Unicode-16, which means 240 bytes!

One thing can makes SB better, change the code to:
String result = new StringBuilder(a.length() + b.length()).append(a).append(b).toString();
Calculate it yourself, we create only one waste object whose size is 17 + 18 = 35, it is still bad, isn't it?

Compare to String.concat(), SB creates a lot of garbages(Anything bigger than 0 compares to 0 is infinity!), and as you can see SB has much more stack calls than String.concat().
With further analyze(do it yourself) you will find out, when connecting less than 4 Strings(Not including 4), String.concat() is much better than SB.

Ok, so when we are connecting more than 3 Strings(Not including 3), we should simply use SB, rigth?
Not exactly!

SB has an inherent problem, it uses a growing internal char[] to append new Strings, whenever you append new String, and SB reaches its capability, it grows. After that it has a bigger char[], the old one becomes a garbage. If we tell SB exactly how long the final result would be, it will save a lot growing garbages. But it is not easy to predict!

Compare to predict final String's length, predict the number of Strings you are going to connect is much more easier. So we can cache the Strings you want to connect, then at the last point(you call toString()) calculate the final String's length accurately, use this length to create a SB for connecting Strings, this can save a lot of garbages. Even though sometimes we still not able to predict how many Strings going to connect, we can use a growing String[] to cache Strings, since the String[] is much more smaller than the original char[](Most String contains more than 1 char in real world case.), a growing String[] is much more cheaper than growing char[]. This is exactly how our StringBundler works.

public StringBundler() {
    _array = new String[_DEFAULT_ARRAY_CAPACITY]; // _DEFAULT_ARRAY_CAPACITY = 16
}
public StringBundler(int arrayCapacity) {
    if (arrayCapacity <= 0) {
        throw new IllegalArgumentException();
    }
    _array = new String[arrayCapacity];
}
You can create a StringBundler with default array capacity which is 16 or give it required array capacity.
Whenever you call append(), you are not actually appending, the String is only cached in the array.
public StringBundler append(String s) {
    if (s == null) {
        s = StringPool.NULL;
    }
    if (_arrayIndex >= _array.length) {
        expandCapacity();
    }
    _array[_arrayIndex++] = s;
    return this;
}
If you are reaching the capacity, the internal String[] will grow.
protected void expandCapacity() {
    String[] newArray = new String[_array.length << 1];
    System.arraycopy(_array, 0, newArray, 0, _array.length);
    _array = newArray;
}
Expand the String[] is much cheaper than char[]. Because String[] is smaller, and grows less othen than char[].
When you finish all appending, call toString() to get the final result.
public String toString() {
    if (_arrayIndex == 0) {
        return StringPool.BLANK;
    }
    String s = null;
    if (_arrayIndex <= 3) {
        s = _array[0];
        for (int i = 1; i < _arrayIndex; i++) {
            s = s.concat(_array[i]);
        }
    }
    else {
        int length = 0;
        for (int i = 0; i < _arrayIndex; i++) {
            length += _array[i].length();
        }
        StringBuilder sb = new StringBuilder(length);
        for (int i = 0; i < _arrayIndex; i++) {
            sb.append(_array[i]);
        }
        s = sb.toString();
    }
    return s;
}

If the String number is less than 4(not including 4), it will use String.concat() to connect the String, otherwise it will caculate the final result's length first, then create a StringBuilder with this length, use this StringBuilder to connect Strings.

I suggest you to use String.concat() directly when you are sure about you only need to connect less than 4 Strings, even though StringBundler can do this for you, why bother to introduce the unneeded String[] and stack calls?

For more detail about StringBuilder see support.liferay.com/browse/LPS-6072

Ok, enough explanation, it is time to see the benchmark result, that the numbers tell you how much performance we can improve by using StringBundler!

We will compare performance for String.concat(), StringBuffer, StringBuilder, StringBundler with default init-capacity, StringBundler with explicit init-capacity.
The comparison includes two parts:

1. Time consume for getting the same amount of job done.
2. Garbage creation for getting the same amount of job done.

In the test all String length()==17, we connect Strings from 72 to 2, for each number we run 100K times.
For 1) we only take result between 40 to 2, because the jvm warn up may impact the result.
For 2) we take the whole range, since jvm warn up won't impact the total garbage generating number.

BTW, We use follow JVM parameter to generate gc log:
-XX:+UseSerialGC -Xloggc:gc.log -XX:+PrintGCDetails

We use SerialGC to eliminate multi-processors' influence.

The following picture show the time consume comparison:

From the picture you can see:

1. String.concat() is the best when connecting 2 or 3 Strings
2. StringBunlder is better than SB in general.
3. StringBuilder is better than StringBuffer(because it saves a lot of unneed sync)

For 3) we may discuss it deeply in later blogs, there are a lot of similar cases in our code and JDK, a lot of sync protection are not necessary(at least in some cases), like JDK's io package. If we bypass these unneed sync, we can improve performance.

We analyze the gc log(gc log can't give 100% accurately garbage number, but it can show you the trend)

String.concat()	229858963K
StringBuffer	34608271K
StringBuilder	34608144K
StringBundler with default init-capacity	21214863K
StringBundler with explicit init-capacity	19562434K

 

From the statistics number you can see, StringBundler does save you a lot of String garbages.

My final advice is:

1. Use String.concat() when you connect only 2 or 3 Strings.
2. Use StringBuilder/StringBuffer when you connect more than 3(not including 3) Strings and you can predict the final result's length accurately.
3. Use StringBunlder when you connect more than 3(not including 3) Strings but you can not predict the final result's length.
4. Give StringBunlder an explicit init capacity when you can predict it.

If you are lazy, just use StringBunlder, it is the best choice for most cases, for other case even though it is not the best choice, it still performs well enough.

[Ray Augé]

I'm sure glad you're on our team Shuyang!

Great stuff!

[Shuyang Zhou]

Thanks Ray

[Alexander Chow]

What a great optimisation! Excellent job Shuyang!

[Bavithra Rajendran]

Very Informative !
Thanks.

[Jonas Yuan]

Nice work. Thank you, Shuyang!

[Sandeep Nair]

Awesome possum!!!

[Bing Ran]

Nice stuff! Will use it in Japid(http://github.com/branaway/Japid), my template engine for the Play framework for max throughput.

[Shuyang Zhou]

Glad to know my stuff can help your product
You may also interested in the unsync IO blog. I guess a template engine must do some stream processing.

[(You)]

[...] String Concatenation Performance vs. String Builder/Buffer and how Liferay 6 achieved a speedup by not using S.B. [that much] – StringBuilder/Buffer has lot of overhead and thus String.concat or... [...] Read More

[James Lefeu]

I'm curious whether the benchmarks would change much if we used strings of size 2 or strings of size 300.

[Pavel Savinov]

Nice article Shuyang!
String in Java is very "interesting" class indeed. As one more step of Liferay Strings optimizations we could also replace all direct substring invocations, like that: String strutsPath = strutsAction.substring(...)
wrapping them into new String constructor to save more memory...

[Pavel Savinov]

Oops, out-of-date comment