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).

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

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);
  Thread main = Thread.currentThread();
  new Thread(() -> {
    synchronized (System.out) {
      phaser.arriveAndDeregister();
      while(main.getState() != Thread.State.BLOCKED)
        Thread.onSpinWait();
      list.remove(6);
    }
  }).start();
  phaser.arriveAndAwaitAdvance();
}

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

Comments

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)

Related Articles

Browse the Newsletter Archive