What actual cause the StringBuilder fails in multi threading environment

Question

StringBuffer is synchronized but StringBuilder is not ! This has been discussed deeply at Difference between StringBuilder and StringBuffer.

There is an example code there (Answered by @NicolasZozol), which address two issues:

• compares the performance of these StringBuffer and StringBuilder
• shows the StringBuilder could fail in a multithread environment.

My question is about second part, exactly what makes it to go wrong?! When you run the code some times, the stack trace is displayed as below:

Exception in thread "pool-2-thread-2" java.lang.ArrayIndexOutOfBoundsException
    at java.lang.String.getChars(String.java:826)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:416)
    at java.lang.StringBuilder.append(StringBuilder.java:132)
    at java.lang.StringBuilder.append(StringBuilder.java:179)
    at java.lang.StringBuilder.append(StringBuilder.java:72)
    at test.SampleTest.AppendableRunnable.run(SampleTest.java:59)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
    at java.lang.Thread.run(Thread.java:722)

When I trace down the code I find that the class which actually throws the exception is: String.class at getChars method which calls System.arraycopy(value, srcBegin, dst, dstBegin, srcEnd - srcBegin); According to System.arraycopy javadoc:

Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by src to the destination array referenced by dest. The number of components copied is equal to the length argument. ....

IndexOutOfBoundsException - if copying would cause access of data outside array bounds.

For simplicity I have exactly paste the code here:

public class StringsPerf {

    public static void main(String[] args) {

        ThreadPoolExecutor executorService = (ThreadPoolExecutor) Executors.newFixedThreadPool(10);
        //With Buffer
        StringBuffer buffer = new StringBuffer();
        for (int i = 0 ; i < 10; i++){
            executorService.execute(new AppendableRunnable(buffer));
        }
        shutdownAndAwaitTermination(executorService);
        System.out.println(" Thread Buffer : "+ AppendableRunnable.time);

        //With Builder
        AppendableRunnable.time = 0;
        executorService = (ThreadPoolExecutor) Executors.newFixedThreadPool(10);
        StringBuilder builder = new StringBuilder();
        for (int i = 0 ; i < 10; i++){
            executorService.execute(new AppendableRunnable(builder));
        }
        shutdownAndAwaitTermination(executorService);
        System.out.println(" Thread Builder: "+ AppendableRunnable.time);

    }

   static void shutdownAndAwaitTermination(ExecutorService pool) {
        pool.shutdown(); // code reduced from Official Javadoc for Executors
        try {
            if (!pool.awaitTermination(60, TimeUnit.SECONDS)) {
                pool.shutdownNow();
                if (!pool.awaitTermination(60, TimeUnit.SECONDS))
                    System.err.println("Pool did not terminate");
            }
        } catch (Exception e) {}
    }
}

class AppendableRunnable<T extends Appendable> implements Runnable {

    static long time = 0;
    T appendable;
    public AppendableRunnable(T appendable){
        this.appendable = appendable;
    }

    @Override
    public void run(){
        long t0 = System.currentTimeMillis();
        for (int j = 0 ; j < 10000 ; j++){
            try {
                appendable.append("some string");
            } catch (IOException e) {}
        }
        time+=(System.currentTimeMillis() - t0);
    }
}

Can you please describe in more details (or with a sample) to show how multithread cause the System.arraycopy fails, ?! Or how the threads make invalid data passed to System.arraycopy ?!

Answer 1

This is how I understand it. You should go one step back and look at where getChars is called from in the AbstractStringBuilder append method:

public AbstractStringBuilder append(String str) {
    if (str == null) str = "null";
    int len = str.length();
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}

The ensureCapacity method will check that the attribute value is long enough to store the appended value and if not then it will resize accordingly.

Lets say 2 threads invoke this method on the same instance. Keep in mind that value and count is accessed by both threads. In this contrived scenario, say value is an array of size 5 and there are 2 characters in the array so count=2 (if you look at the length method you'll see that it returns count).

Thread 1 invokes append("ABC") which will call ensureCapacityInternal and value is big enough so it is not resized (requires size 5). Thread 1 pauses.

Thread 2 invokes append("DEF") which will call ensureCapacityInternal and value is big enough so it is not resized either (also requires size 5). Thread 2 pauses.

Thread 1 continues and calls str.getChars with no problems. It then calls count += len. Thread 1 pauses. Note that value now contains 5 characters and is length 5.

Thread 2 now continues and calls str.getChars. Remember that it uses the same value and same count as Thread 1. But now, count has increased and could potentially be greater than the size of value i.e. the destination index to copy is greater than the length of the array which causes IndexOutOfBoundsException when invoking the System.arraycopy within str.getChars. In our contrived scenario, count=5 and the size of value is 5 so when System.arraycopy is called, it cannot copy to the 6th position of an array that's length 5.

Answer 2

If you compare append method in both the classes i.e. StringBuilder and StringBuffer. You can find StringBuilder.append() is not synchronized where as StringBuffer.append() is synchronized.

// StringBuffer.append
public synchronized StringBuffer append(String str) {
    super.append(str);
    return this;
}

// StringBuilder.append
public StringBuilder append(String str) {
    super.append(str);
    return this;
}

So when you try to append "some string" using multiple threads.

In case of StringBuilder, ensureCapacityInternal() is called from different threads at the same time. This result in change of size based on previous value in both the call, and after that both the threads are appending "some string" causing ArrayIndexOutOfBoundsException.

Eg: String value is "some stringsome string". Now 2 threads want to append "some string". So both will call ensureCapacityInternal() method and which will result in increase in length if enough space is not available, But if there are 11 places remaining then it will not increment the size. Now two threads have called System.arraycopy with "some string" at the same time. And then both threads try to append "some string". So actual length increase should be 22, but char[] has 11 empty places inside it, resulting in ArrayIndexOutOfBoundsException.

In case of StringBuffer, append method is already synchronized, so this scenario won't arise.