241Concurrency Puzzle - System.arraycopy()

Author: Dr. Heinz M. KabutzDate: 2016-09-29Java Version: 6Category: Concurrency

Abstract: "Friends don't let friends write low-level concurrency by themselves." -@karianna. Here is your chance to participate in a global code review puzzle to figure out what's going on in some synchronized code.

Welcome to the 241st edition of The Java(tm) Specialists' Newsletter, sent to you from Chorafakia, Crete. The evening before our JCrete conference began, I stumbled whilst jogging, badly spraining my left foot. I panicked. Seventy guests from 25 countries were waiting for me. Each of them hand-picked. We had excursions to go on. Remote beaches. Ancient ruins to explore. So I copied my son's basketball coach: ice spray to reduce the swelling as quickly as possible. Instructions were in Greek. But how hard could it be? Aim. Spray. Done. Except I really should have read them. I gave myself such a bad burn that two months later my physiotherapist is still shaking his head at me. The fall was relatively minor. The burn wasn't. Always read the instructions! Same is true for writing concurrent code. You can get seriously burned without realizing it. Your code might work on your laptop, but fail on the server.

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

Concurrency Puzzle - System.arraycopy()

We had a fun exchange on Twitter recently about how important peer reviews are for concurrency code. It is very easy to make mistakes, even for experienced programmers. Writing concurrency code is a bit like cave diving. Only an amateur would think he's capable enough to go alone.

My good friend Jack Shirazi sent me some fun code he had hacked together. It being Jack of JavaPerformanceTuning.com, he obviously knew that the bottleneck was object creation, not contention. He was also aware that the threading was incorrect. However, in his thought experiment, he found a very interesting case of early writes by System.arraycopy(), due to cache lines, threads being moved between cores, flushing, etc. I think I'll just let him explain:

"I was playing around with separate read and write (monitor) locks for an example I'm thinking about, and I came across this concurrency failure that I couldn't explain. (If you're not interested that's fine, it's just an oddity from an incorrect implementation so not really that useful). The class is attached. Basically it would be a thread-safe stripped down arraylist-ish class for ints if I used one lock, but I was trying to understand where the concurrency failure would occur if read threads and write threads use different locks.

"And what I see is that the read thread very occasionally sees an empty array element, after it has definitely been populated. I'm not surprised that it sees a corrupt state, but I can't figure out how that particular corrupt state can occur. Maybe I'm just trying to put too much effort into understanding a definitely wrong implementation. A couple of things I tried: as an Object array (rather than an int array), I get the same failure (it sees a null); without the remove() method, again I see it, just less often.

"It almost seems like the System arraycopy sets an empty array that it copies data into (feasible), which would be fine within the synchronized block, you wouldn't see any effect, but it's like that empty array leaks out into "main" memory before the synchronized block completes, and the reading thread sees that..

"My best guess is that the write thread is busy writing and it writes to the L1 cache, first emptying the line, then before it writes the data, it gets suspended (lots of GC happening); the read thread is also suspended in a read; when the threads are re-started the OS starts the read thread on that core where the write was suspended, and since there was no flush from the write thread to invalidate the memory contents of the cache, then read thread assumes it is valid and just uses that empty value." - Jack Shirazi

Back to Heinz :-) I ran the code below on my MacBookPro Retina Display and it did not give the output he was experiencing. I then ran it on my 2-4-1 (8 core) server running JavaSpecialists.eu and there I could see that indeed, sometimes get() return 0 when it clearly shouldn't. Thus, you might need to run this on various hardware until you can reproduce it.

Instead of just providing a detailed explanation, I thought it would be more fun if you got into the cave of concurrent coding with us and tried to figure out how System.arraycopy() could sometimes do early writes and thus leak uninitialized arrays into the reader threads. Perhaps look at the C code of System.arraycopy() or use JITWatch to examine the generated machine code? The first person to send me the correct explanation gets a mention in my next newsletter. If you are subscribed to my newsletter via email, then simply respond to this email. If not, please sign up here and respond to the welcome email. Hurry, there are another hundred thousand Java programmers reading this with you, eager to become immortalized in The Java(tm) Specialists' Newsletter :-) A second challenge for those who are asleep at this time is to send me a solution that uses StampedLock. For extra points, upgrade the lock in the remove() method.

import java.util.*;

public class MyArrayList {
  private final Object READ_LOCK = new Object();
  private final Object WRITE_LOCK = new Object();
  private int[] arr = new int[10];
  private int size = 0;

  public int size() {
    synchronized (READ_LOCK) {
      return size;
    }
  }

  public int get(int index) {
    synchronized (READ_LOCK) {
      rangeCheck(index);
      return arr[index];
    }
  }

  public boolean add(int e) {
    synchronized (WRITE_LOCK) {
      if (size + 1 > arr.length)
        arr = Arrays.copyOf(arr, size + 10);

      arr[size++] = e;
      return true;
    }
  }

  public int remove(int index) {
    synchronized (WRITE_LOCK) {
      rangeCheck(index);

      int oldValue = arr[index];

      int numMoved = size - index - 1;
      if (numMoved > 0)
        System.arraycopy(arr, index + 1,
            arr, index, numMoved);
      arr[--size] = 0;

      return oldValue;
    }
  }

  private void rangeCheck(int index) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index: " + index + ", Size: " + size);
  }

  public static void main(String[] args) {
    for (int i = 0; i < 100000; i++) {
      MyArrayList list = new MyArrayList();
      new Thread(new Main(list, true)).start();
      new Thread(new Main(list, false)).start();
      new Thread(new Main(list, false)).start();
    }
  }

  static class Main implements Runnable {
    MyArrayList list;
    boolean update;

    public Main(MyArrayList list,
                boolean update) {
      this.list = list;
      this.update = update;
    }

    @Override
    public void run() {
      if (update) {
        for (int i = 1; i < 1000; i++) {
          list.add(i);
        }
        for (int i = 1; i < 250; i++) {
          list.remove(7);
        }
      } else {
        // wait until we're certain
        // index 6 has a value
        while (list.size() < 7) {}
        for (int i = 1; i < 1000; i++) {
          int x;
          if ((x = list.get(6)) != 7) {
            System.out.println(x +
                " and " + list.size());
          }
        }
      }
    }
  }
}

Disclaimer: Jack Shirazi very kindly allowed me to republish his email and code. The class he sent me was a thought experiment and not indicative of what he usually writes :-) I do know exactly what is going on and why, since it is explained in detail in Chapter 2 of my course Extreme Java - Concurrency and Performance. I'm sure many of you will figure it out too, but please be a good sport and don't publish your ideas until we have announced the winner. Patience, patience, patience :-)

Kind regards

Heinz

P.S. If you haven't already signed up to Jack Shirazi's monthly newsletter yet, I would strongly urge you to. Here is a link: Java Performance Tuning News

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