Exploring Time-Space trade-offs for "synchronized" in Lilliput

[Dave Dice]

Abstract : In the context of project Lilliput, which attempts to reduce the size of object header in the HotSpot Java Virtual Machine (JVM), we explore a curated set of synchronization algorithms. Each of the algorithms could serve as a potential replacement implementation for the “synchronized” construct in HotSpot. Collectively, the algorithms illuminate trade-offs in space-time properties.

The key design decisions are where to locate synchronization metadata (monitor fields), how to map from an object to those fields, and the lifecycle of the monitor information.

The readers is assumed to be familiar with current HotSpot implementation of “synchronized” as well as the Compact Java Monitors (CJM) design (https://arxiv.org/abs/2102.04188)

Dave

p.s.,

Don’t expect any surprises regarding performance — common sense and intuition prevail.  As you’d expect, the more involved ”synchronized" is with the header word, the more performance we can squeeze out, albeit at a cost in complexity.

Note that I narrowed the space of solutions to cover only those that avoid the need for deferred deflation, as monitor accretion and deflation policies remain a continuing problem in HotSpot.

Finally, for reference, performance data is included for pthread_mutex operations and ReentrantLock.