Many concurrent problems can be solved through a concurrent state machine. This leads to better scalability and in my case better memory utilization.

I learned this through an OutOfMemoryError exception. And this video from Dr. Cliff Click.

The problem: An OutOfMemoryError exception

Running my tool with the neo4j-analytics benchmark from the renaissance benchmark suite let to an OutOfMemoryError. By using the JVM arguments -XX:+HeapDumpOnOutOfMemoryError I generated a heap dump. The Eclipse memory analyzer showed that I was creating too many instances of the class com.vmlens.trace.agent.bootstrap.callback.state.ObjectState: More than forty-five thousand or two gigabytes RAM.

I added a field to each class to log the threads accessing the fields of this class. I created a new instance of com.vmlens.trace.agent.bootstrap.callback.state.ObjectState in the constructor of each class. And I updated the values from com.vmlens.trace.agent.bootstrap.callback.state.ObjectState using a synchronized block.

The solution: A concurrent state machine

A friend of mine told me about a video from Dr. Cliff Click. In it, Dr. Cliff Click shows how we can use state machines to implement a concurrent hash map. This was the solution: I can also use a concurrent state machine. The state machine starts with null, goes to SingleThreaded, and from there to MultiThreaded.

To implement the state machine I use the method compareAndSet from the class java.util.concurrent.atomic.AtomicReferenceFieldUpdater. This method lets you execute the two operations compare and set atomically. The method typically directly maps to a machine code instruction. Starting with JDK 9 you also can use java.lang.invoke.VarHandle instead of java.util.concurrent.atomic.AtomicReferenceFieldUpdater.

We need to retry the method compareAndSet until it succeeds. This retry loop is already implemented in the class java.util.concurrent.atomic.AtomicReferenceFieldUpdater in the method updateAndGet:

public final V updateAndGet(T obj, UnaryOperator<V> updateFunction) {
  V prev, next;
  do {
     prev = get(obj);
     next = updateFunction.apply(prev);
  } while (!compareAndSet(obj, prev, next));
  return next;
}

Using this method the source code of our state machine looks like this:

volatile State state = null;
private static final AtomicReferenceFieldUpdater STATE = 
	AtomicReferenceFieldUpdater.newUpdater(
	ObjectWithState.class, State.class, "state");
public void update(ObjectWithState object) {
  STATE.updateAndGet(object, (current) -> {
  if (current == null) {
   return new SingleThreaded(); 
  }
  return new MultiThreaded(current);
 });
}

Using the new way to store the data I now need three hundred megabytes instead of two gigabytes.

Updating multiple variables

There is currently no method to update multiple variables atomically. But often we can still use compareAndSet for multiple variables. When our state machine does not contain cycles and we access the next variable only when we reached a specific state, we still can use compareAndSet, even for multiple variables.

An example of this technique is the class java.util.concurrent.FutureTask. This class uses a state machine stored in the variable state. The dependent variable outcome is only read or written when we reached a specific state.

The states are documented in the JavaDoc of the class:

/*
* Possible state transitions:
* NEW -> COMPLETING -> NORMAL
* NEW -> COMPLETING -> EXCEPTIONAL
* NEW -> CANCELLED
* NEW -> INTERRUPTING -> INTERRUPTED
*/

The following shows the source code to update the variable outcome. We only update the variable outcome when we managed to set the state COMPLETING:

protected void set(V v) {
   if (STATE.compareAndSet(this, 
         NEW, COMPLETING)) {
     outcome = v;
     STATE.setRelease(this, 
        NORMAL); // final state
     finishCompletion();
   }
}

The static field STATE is a java.lang.invoke.VarHandle to call compareAndSet for the variable state.

Conclusion

After realizing that I was implementing a concurrent state machine, I was able to reduce the size from two gigabytes to three hundred megabytes. An algorithm using compareAndSet, which is used to implement the concurrent state machines, typically scale better than a lock-based algorithm. For example, for write operations, the concurrent hash map by Dr. Cliff Click scales better than the locked based java.util.concurrent.ConcurrentHashMap.