How do I prove programmatically that StringBuilder is not threadsafe?
Asked Answered
J

3

47

How do I prove programmatically that StringBuilder is not threadsafe?

I tried this, but it is not working:

public class Threadsafe {
    public static void main(String[] args) throws InterruptedException {
        long startdate = System.currentTimeMillis();

        MyThread1 mt1 = new MyThread1();
        Thread t = new Thread(mt1);
        MyThread2 mt2 = new MyThread2();
        Thread t0 = new Thread(mt2);
        t.start();
        t0.start();
        t.join();
        t0.join();
        long enddate = System.currentTimeMillis();
        long time = enddate - startdate;
        System.out.println(time);
    }

    String str = "aamir";
    StringBuilder sb = new StringBuilder(str);

    public void updateme() {
        sb.deleteCharAt(2);
        System.out.println(sb.toString());
    }

    public void displayme() {
        sb.append("b");
        System.out.println(sb.toString());
    }
}

class MyThread1 implements Runnable {
    Threadsafe sf = new Threadsafe();

    public void run() {
        sf.updateme();
    }
}

class MyThread2 implements Runnable {
    Threadsafe sf = new Threadsafe();

    public void run() {
        sf.displayme();
    }
}
Judy answered 1/2, 2018 at 8:37 Comment(10)
Just curious: why would you want to prove that something is not thread-safe?Bustard
Threadsafe sf = new Threadsafe() (in both your thread classes) => That means, your two threads are operating on different Threadsafe instances and thus on different StringBuilder instances!Jinny
coderanch.com/t/666742/java/…Sonorous
curl https://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html | grep "not safe for use by multiple threads" && echo "Not thread safe". It's documented not to be thread safe. You might not be able to prove it's not thread safe because the implementation might have changed so that it is; you shouldn't rely upon that property though, because there is no guarantee that it will continue to be thread-safe.Amateurish
@MickMnemonic Likely because some colleague claims their multithreaded code using StringBuilder is perfectly safe and the question author wants to prove them wrong.Shing
Make your StringBuilder static; that'll guarantee it's shared.Sprouse
One principal caveat: Concurrency problems tend to be elusive. You may not run into errors even though the class is not threadsafe. It's sometimes very hard to find such errors.Maritamaritain
@Philipp: Even more likely -- this is a homework problem that the OP actually attempted before asking about on StackOverflow (if so, good for you OP!)Sydneysydnor
@Shing I hope not. If something is not documented to be thread safe, it simply is not...Cohesion
To prove that it is not thread-safe requires you to inspect the implementation and give an example of two possible serialisations of operations on multiple threads that will give different results. You probably don't want to prove it isn't thread-safe.Summerlin
U
114

Problem

I am afraid the test you have written is incorrect.

The main requirement is to share the same StringBuilder instance between different threads. Whereas you are creating a StringBuilder object for each thread.

The problem is that a new Threadsafe() initialises a new StringBuilder():

class Threadsafe {
    ...
    StringBuilder sb = new StringBuilder(str);
    ...
}
class MyThread1 implements Runnable {
    Threadsafe sf = new Threadsafe();
    ...
}
class MyThread2 implements Runnable {
    Threadsafe sf = new Threadsafe();
    ...
}

Explanation

To prove the StringBuilder class is not thread-safe, you need to write a test where n threads (n > 1) append some stuff to the same instance simultaneously.

Being aware of the size of all the stuff you are going to append, you will be able to compare this value with the result of builder.toString().length():

final long SIZE = 1000;         // max stream size

final StringBuilder builder = Stream
        .generate(() -> "a")    // generate an infinite stream of "a"
        .limit(SIZE)            // make it finite
        .parallel()             // make it parallel
        .reduce(new StringBuilder(), StringBuilder::append, (b1, b2) -> b1);
                                // put each element in the builder

Assert.assertEquals(SIZE, builder.toString().length());

Since it is actually not thread-safe, you may have trouble getting the result.

An ArrayIndexOutOfBoundsException may be thrown because of the char[] AbstractStringBuilder#value array and the allocation mechanism which was not designed for multithreading use.

Test

Here is my JUnit 5 test which covers both StringBuilder and StringBuffer:

public class AbstractStringBuilderTest {

    @RepeatedTest(10000)
    public void testStringBuilder() {
        testAbstractStringBuilder(new StringBuilder(), StringBuilder::append);
    }

    @RepeatedTest(10000)
    public void testStringBuffer() {
        testAbstractStringBuilder(new StringBuffer(), StringBuffer::append);
    }

    private <T extends CharSequence> void testAbstractStringBuilder(T builder, BiFunction<T, ? super String, T> accumulator) {
        final long SIZE = 1000;
        final Supplier<String> GENERATOR = () -> "a";

        final CharSequence sequence = Stream
                .generate(GENERATOR)
                .parallel()
                .limit(SIZE)
                .reduce(builder, accumulator, (b1, b2) -> b1);

         Assertions.assertEquals(
                SIZE * GENERATOR.get().length(),    // expected
                sequence.toString().length()        // actual
         );
    }

}

Results

AbstractStringBuilderTest.testStringBuilder: 
    10000 total, 165 error, 5988 failed, 3847 passed.

AbstractStringBuilderTest.testStringBuffer:
    10000 total, 10000 passed.
Ushaushant answered 1/2, 2018 at 10:11 Comment(5)
Wow, that's a much higher rate of errors and failures than I would have expected in the StringBuilder case. What a nice demonstration.Petrel
Good idea using a parallel stream instead of using threads directly. That makes the test much shorter.Intimidate
@JohnBollinger on my system, the failure rate is even higher, >9900Commonalty
@Holger, I also was surprised to see such a low failure rate, did you use any JVM flags?Ushaushant
@AndrewTobilko no, just 64bit JVM on Windows with 8 cores; no special setup.Commonalty
F
18

Much simpler:

StringBuilder sb = new StringBuilder();
IntStream.range(0, 10)
         .parallel()
         .peek(sb::append) // don't do this! just to prove a point...
         .boxed()
         .collect(Collectors.toList());

if (sb.toString().length() != 10) {
    System.out.println(sb.toString());
}

There will be no order of the digits (they will not be 012... and so on), but this is something you don't care about. All you care is that not all the digits from range [0..10] where added to StringBuilder.

On the other hand if you replace StringBuilder with StringBuffer, you will always get 10 elements in that buffer (but out of order).

Foregut answered 1/2, 2018 at 9:24 Comment(3)
While this may work, it misses an explanation why OP's code did prove the opposite.Whensoever
OP only asked for a proof; OP never asked why their code didn't workThreeply
@WordsLikeJared: true, but that explanation makes it a better answer. See the highly upvoted answer by AndrewWhensoever
T
11

Consider the following test.

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class NotThreadSafe {

    private static final int CHARS_PER_THREAD = 1_000_000;
    private static final int NUMBER_OF_THREADS = 4;

    private StringBuilder builder;

    @Before
    public void setUp() {
        builder = new StringBuilder();
    }

    @Test
    public void testStringBuilder() throws ExecutionException, InterruptedException {
        Runnable appender = () -> {
            for (int i = 0; i < CHARS_PER_THREAD; i++) {
                builder.append('A');
            }
        };
        ExecutorService executorService = Executors.newFixedThreadPool(NUMBER_OF_THREADS);
        List<Future<?>> futures = new ArrayList<>();
        for (int i = 0; i < NUMBER_OF_THREADS; i++) {
            futures.add(executorService.submit(appender));
        }
        for (Future<?> future : futures) {
            future.get();
        }
        executorService.shutdown();
        String builtString = builder.toString();
        Assert.assertEquals(CHARS_PER_THREAD * NUMBER_OF_THREADS, builtString.length());
    }
}

This is intended to prove that StringBuilder is not thread-safe by proof by contradiction method. When run, it always throws exception like following:

java.util.concurrent.ExecutionException: java.lang.ArrayIndexOutOfBoundsException: 73726

    at java.util.concurrent.FutureTask.report(FutureTask.java:122)
    at java.util.concurrent.FutureTask.get(FutureTask.java:192)
    at NotThreadSafe.testStringBuilder(NotThreadSafe.java:37)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
    at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
    at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
    at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:68)
    at com.intellij.rt.execution.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:47)
    at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:242)
    at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:70)
Caused by: java.lang.ArrayIndexOutOfBoundsException: 73726
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:650)
    at java.lang.StringBuilder.append(StringBuilder.java:202)
    at NotThreadSafe.lambda$testStringBuilder$0(NotThreadSafe.java:28)
    at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
    at java.util.concurrent.FutureTask.run(FutureTask.java:266)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
    at java.lang.Thread.run(Thread.java:748)

Therefore, StringBuilder is broken when used by multiple threads.

Thaumaturge answered 1/2, 2018 at 9:2 Comment(3)
While this may work, it misses an explanation why OP's code did prove the opposite.Whensoever
@ThomasWeller The question asked in the title is how to proof that it is broken, not why the code from the op demonstrates the problemDelafuente
@Ferrybig: true, but that explanation makes it a better answer. See the highly upvoted answer by AndrewWhensoever

© 2022 - 2024 — McMap. All rights reserved.