javaconcurrencyconcatenationatomicreference

Concat new characters to StringBuilder object atomically


My problem is:

I have class:

public class AtomicStringBuilder {
    private final AtomicReference<StringBuilder> sbRef;
}

I need to add new characters to StringBuilder concurrently and atomically. But problem is, only last 128 characters should be in this object. I can't use StringBuffer, because operation should be non-blocking.

So,there are two operations:

First: check if StringBuilder already has 128 chars.

Second: if it has not -> add new char, if it has -> delete first char and add new char.

Is there a way to make this two or three operations atomic?

I made this method, but it doesn't work:

public void append(String string) {
        this.sbRef.getAndUpdate(ref -> {
            if (ref.length() < 128) {
                ref.append(string);
            } else {
                ref.append(string).delete(0, ref.length() - 128);
            }
            return ref;
        });
    }

For testing I created this method:

public void test() {
AtomicStringBuilder atomicStringBuilder = new AtomicStringBuilder();
Random random = new Random();
Stream<Integer> infiniteStream = Stream.iterate(0, i -> random.nextInt(10));

infiniteStream.parallel()
.limit(100000)
.forEach(integer -> atomicStringBuilder.append(String.valueOf(integer)));

assertEquals(128, atomicStringBuilder.getSb().get().length());
}

This is not a real prolem, I can change AtomicReference with anything else which will work. The task is to create operation that will be lock-free and without race conditions


Solution

  • Here's a solution with immutable Strings.

    If you use AtomicReference you need to return a new reference rather than mutating the object the reference points to. Atomically comparing the current and expected value of the reference is the only way to know that it hasn't been updated by another thread.

    getAndUpdate does this:

    1. get the current reference
    2. apply the lambda to the reference, getting a new reference
    3. if the current reference hasn't changed, atomically set it to the new reference, otherwise go back to 1.
    public class App {
        static class AtomicStringBuilder {
            public final AtomicInteger counter = new AtomicInteger();
    
            public final AtomicReference<String> sbRef = new AtomicReference<>("");
    
            public void append(String string) {
                this.sbRef.getAndUpdate(ref -> {
                    counter.getAndIncrement();
                    if (ref.length() < 128) {
                        return ref + string;
                    } else {
                        String s = ref + string;
                        return s.substring(s.length() - 128);
                    }
                });
            }
        }
    
        static void test() {
            AtomicStringBuilder atomicStringBuilder = new AtomicStringBuilder();
            Random random = new Random();
            Stream<Integer> infiniteStream = Stream.iterate(0, i -> random.nextInt(10));
    
            infiniteStream.parallel()
                    .limit(100000)
                    .forEach(integer -> atomicStringBuilder.append(String.valueOf(integer)));
    
            if (128 != atomicStringBuilder.sbRef.get().length()) {
                System.out.println("failed ");
            }
            System.out.println(atomicStringBuilder.sbRef.get());
            System.out.println(atomicStringBuilder.counter.get());
        }
    
        public static void main(String[] args) {
            test();
        }
    }
    

    I've added a counter to the lambda. The value it shows after running this program will be more than 100,000, because concurrent updates forced retries.