Running on Java 16-ea+15-631 (Preview)

# 283Four Billion Changes

##### Author: Dr Heinz M. KabutzDate: 2020-08-28Java Version: 9+Category: Tips and Tricks

Abstract: A nice puzzle to brighten your day - how can we make the Iterator think that the List has not been changed?

Welcome to the 283rd edition of The Java(tm) Specialists' Newsletter, sent to you from the beautiful Island of Crete. We have had a rather odd summer. Warm weather, of course, but few tourists. Chania looks like it does in winter, just warmer. The beaches are void of organized sun umbrellas. Cretans, famous for their hospitality, are cautious of outsiders. But this too will pass.

I am speaking at the JVM Community Virtual Conference in Nigeria tomorrow (29th August) (more info here).

### Four Billion Changes

A few days ago, I tweeted a #Java puzzle, asking how we could let an iterator continue to work, even after its collection had changed.

Here is the puzzle code:

```import java.util.*;

public class ListSurprise {
public static void main(String[] args) {
// Make ListSurprise print 3.14159
System.setSecurityManager(new SecurityManager());
List<Integer> numbers = new ArrayList<>();
Collections.addAll(numbers, 3, 1, 4, 1, 5, 5, 9);
Iterator<Integer> it = numbers.iterator();
System.out.print(it.next()); // 3
System.out.print('.');
System.out.print(it.next()); // 1
System.out.print(it.next()); // 4
System.out.print(it.next()); // 1
System.out.print(it.next()); // 5
doSomething(numbers); // should make the next output be 9
System.out.println(it.next());
if (!numbers.equals(List.of(3, 1, 4, 1, 5, 9)))
throw new AssertionError();
}

private static void doSomething(List<Integer> list) {
// how???
}
}
```

The `modCount` field in `AbstractList` helps to discover concurrent updates to a list. Whenever the list is changed, the `modCount` is also incremented. When the `Iterator` is created, it makes a copy of the current `modCount`. If this changes during iteration, then the backing list must have changed. However, if we remove an item with the iterator itself, then the iterator's `expectedModCount` is also changed to match the list's `modCount`. The trick is thus to remove the element at index 5, and to then change the list another 4294967295 times, thus looping the `int` back to the starting point. My friend Olivier Croisier wrote about this trick ten years ago. Here is what it would look like:

```private static void doSomething(List<Integer> list) {
// Remove element at index 5 and modify list 4 billion times
list.remove(5);
for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
((ArrayList<Integer>) list).trimToSize();
}
}
```

The `trimToSize()` method increments the `modCount` even if it does not really change the structure of the list. It is thus a fairly quicky way of spinning the `modCount` back to its original value.

Another interesting approach was with threads. The `list.set()` method does not increment `modCount`, since it does not change the structure of the list. Furthermore, when we look at `System.out.println(it.next());`, it is tempting to read from left to right. However, we all know that `it.next()` is executed first and then the `System.out.println()`. The second solution spawns a thread that synchronizes on `System.out`, thus preventing the main thread from continuing until we have removed the element at index 6.

I saw several solutions following similar approaches using `Thread.sleep()`. Here is mine, using Phaser and a spin loop that monitors the main thread's state. Once it is BLOCKED, we continue with removing the last element.

```private static void doSomething(List<Integer> list) {
// Set item 5 to 9; block main thread as we remove last item
list.set(5, 9);
Phaser phaser = new Phaser(2);
synchronized (System.out) {
phaser.arriveAndDeregister();
list.remove(6);
}
}).start();
}
```

The third approach was even more obscure. We take advantage of type erasure to insert a magical object into the list. When `toString()` is called, which would be after the call to `it.next()`, but before the call to `System.out.println()`, we remove `this`, leaving behind the desired list of `Integer` objects.

```private static void doSomething(List<Integer> list) {
// Replace 5 with object that removes itself and returns "9"
((List)list).set(5, new Object() {
public String toString() {
list.remove(this);
return "9";
}
});
}
```

The first and third solutions would work even with a stricter security manager installed. The second might not, since it is possible to prevent thread construction.

Here is one more that is the simplest solution, but also one that I like the least:

```private static void doSomething(List<Integer> list) {
// Println 9 and exit
System.out.println(9);
System.exit(0);
}
```

Deep reflection was not possible due to the security manager, although one of my respondents set up a policy file to allow that.

The lesson to learn from this is that the `ConcurrentModificationException` is best-effort. It might happen if a collection is modified, but we can also see other strange behaviour. We need to eradicate this exception from our systems.

Kind regards from Crete

Heinz

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

When you load these comments, you'll be connected to Disqus. Privacy Statement.

### Related Articles

Java Champion, author of the Javaspecialists Newsletter, conference speaking regular... About Heinz

#### Superpack 2020

Our entire Java Specialists Training in one huge bundle more...
##### Java Training

We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.

##### Java Consulting

We can help make your Java application run faster and trouble-shoot concurrency and performance bugs...

##### Java Emergency?

If your system is down, we will review it for 15 minutes and give you our findings for just 1 € without any obligation.