Two Threads Incrementing One Counter, Ten Million Times Each

The smallest program that loses an update, and the first thing it teaches is how hard it is to catch in the act.

java

Counter counter = new Counter();

Runnable job = () -> {
    for (int i = 0; i < n; i++) {
        counter.increment();
    }
};

Thread a = new Thread(job);
Thread b = new Thread(job);
a.start(); b.start();
a.join(); b.join();

System.out.println(counter.count);

Run with n at a thousand, then at a hundred thousand, then at ten million, three times each. On a machine with two cores this is what comes back.

The same program at three sizes, three runs each
Increments each	Expected	Run 1	Run 2	Run 3
1,000	2,000	2,000	2,000	2,000
100,000	200,000	200,000	200,000	200,000
10,000,000	20,000,000	20,000,000	20,000,000	10,238,769

Eight of those nine runs are correct, and the code is broken in every one of them. The two join calls guarantee both threads had finished before the total was read, so nothing was missed by measuring too early — the increments really were lost.

Almost half of them went, on the run that failed. That is the shape of a lost update: not a small drift, but one thread spending a long stretch writing values it computed from a number the other thread had already moved past.

So a test cannot show this code is correct, and can only ever fail to show it is wrong. That is what makes shared mutable state worth removing rather than worth testing.