Lost list element in a concurrency program

Question

This is a task from the book Head First Java, where the reader is asked to find out what happens in the following code block:

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

public class TwoThreadsWriting {
    public static void main(String[] args) {
        ExecutorService threadPool = Executors.newFixedThreadPool(2);
        Data data = new Data();
        threadPool.execute(()-> addLetterToData('a', data));
        threadPool.execute(()-> addLetterToData('A', data));
        threadPool.shutdown();
    }

    private static void addLetterToData(char letter, Data data) {
        for(int i = 0; i < 26; i++){
            data.addLetter(letter++);
            try {
                Thread.sleep(50);
            } catch (InterruptedException ignored) {}
        }
        System.out.println(Thread.currentThread().getName() + data.getLetters());
        System.out.println(Thread.currentThread().getName() + " size: " + data.getLetters().size());
    }
}
class Data {
    private final List<String> letters = new ArrayList<>();
    public List<String> getLetters() {return letters;}
    public void addLetter(char letter){
        letters.add(String.valueOf(letter));
    }
}

I expected that the output lists contain 52 characters like this

['a', 'A', 'b', 'B', ...]

But sometimes the number of elements is less than 52 and some characters are missing in letters, like here for example ('K' is missing):

pool-1-thread-2[A, a, B, b, c, C, d, D, e, E, f, F, G, g, H, h, i, I, J, j, k, L, l, m, M, N, n, O, o, p, P, q, Q, r, R, s, S, t, T, u, U, V, v, w, W, X, x, y, Y, Z, z]

pool-1-thread-1[A, a, B, b, c, C, d, D, e, E, f, F, G, g, H, h, i, I, J, j, k, L, l, m, M, N, n, O, o, p, P, q, Q, r, R, s, S, t, T, u, U, V, v, w, W, X, x, y, Y, Z, z]

pool-1-thread-2 size: 51
pool-1-thread-1 size: 51

I do not understand why this happens. I tried debugging it by printing the value of the local variable letter of addLetter but it only shows me that the 'K' was actually added.

I do know that this all happens solely due to using the non-thread-safe ArrayList or addLetter not being declared as synchronized, but I want to understand what's even happening here in the first place.

You have a data race, which is a common issue when working on concurrent threads. **Concurrency is hard**. — aled, May 16 '23 at 15:47
Re, "...what's even happening." You'd have to look at the source code for `ArrayList` to know what's _really_ happening. But why not start with one of those examples where two threads increment a counter variable, and some of the increments get lost? An `ArrayList` basically is an array with a counter variable that tells where to `add` the next item. — Solomon Slow, May 16 '23 at 15:53
Even looking at source won't clarify all of it, because in the absence of synchronization different optimizations like reordering of instructions are allowed. — Nathan Hughes, May 16 '23 at 16:34

score 1 · Answer 1 · edited May 16 '23 at 16:43

1

ArrayList is not thread-safe. If two threads try to call add() at the same time, anything might happen. From the Arraylist documentation:

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

edited May 16 '23 at 16:43

Basil Bourque

303,325
100
852
1,154

answered May 16 '23 at 15:57

fishinear

6,101
3
36
84

Lost list element in a concurrency program

1 Answers1