Arraylets, Schism, and Z-Rays

Garbage collection is a Good Thing™ -- few software engineers will dispute that. But garbage collection is a real pain for real-time software engineering. The problem is that GC cycles sometimes lead to pauses of unpredictable length in the program's execution.

One possible approach to that is putting a cap on object sizes: for any given size limit, we can calculate a maximal incurred GC pause time, thereby yielding predictability. This works real nicely... until you reach the problem of arrays. Arrays, by their very nature, can be of arbitrary sizes, and will mock any limit you put on object sizes.

An interesting solution to the unbound size of arrays is representing them, internally, as multiple, independent memory blocks, called arraylets. These were introduced in Bacon, Cheng, and Rajan's paper from POPL '03: A Real-Time Garbage Collector with Low Overhead and Consistent Utilization. The idea is rather straightforward: an array now consists of a "spine", which is an array of pointers to smaller array parts. The array lookup operation a[i], which was previously a simple calculation and a single dereferencing (i.e., deref(a + i * sizeof(T)), where a is of type T[]), is now a more complex operation, involving two dereferences: deref(deref(base + i / elements_per_arraylet) + (i % elements_per_arraylet) * sizeof(T)). The first dereferencing finds the relevant arraylet's location, the second finds the desired element at index i inside that arraylet.

While the new lookup code is still O(1), it does introduce a significant loss of efficiency. Still, it also gives us back control over the GC's performance. As was shown by Bacon et al., the result can be used in real-time systems.

In PLDI '10, two papers continue this research trend: Pizlo et al.'s Schism: Fragmentation-Tolerant Real-Time Garbage Collector focus on improving the GC algorithm where arraylets are used. The authors implement a new GC, "Schism/CMR", in the Fiji VM, that reaches 65% of Sun's JDK throughput, while being fragmentation-tolerant. (Lack of fragmentation tolerance implies a risk that long-running programs will eventually fail. From personal experience I can attend that this risk is very real, and that finding and debugging a memory fragmentation issue in a non-GC environment, namely C++, can be significantly harder than finding a memory leak. A previous effort, CMR, reached 84% of the JDK's throughput but was not fragmentation-tolerant.)

I found the second paper to be closer to my personal field of interest. Sartor et al.'s Z-Rays: Divide Arrays and Conquer Speed and Flexibility discusses a set of incremental, yet significant, enhancements to the basic arraylet concept. These include:

• Separate memory region. Since arraylets are all of identical size (i.e., if the type is larger, there are fewer objects per arraylet), this greatly simplifies the memory management of arraylets.
• First-N optimization. The authors show that, empirically, nearly 90% of array access operations use the first 4KB of the array. By storing this prefix in the array object itself, alongside the spine (rather than in an arraylet), they were able to reduce the performance overhead of using arraylets by half.
• Lazy allocation and zero compression. Arrays in Java are initialized to all-zero (or all-null). Z-Rays are initialized by having all new arrays point to a global, immutable zero arraylet; actual arraylets are allocated lazily, on the first write operation. And whenever an arraylet is detected (during GC) to be all-zero, it is released, and the spine pointer is set to point to the shared zero arraylet.
• Fast array copy and copy-on-write, taking advantage of the Z-Ray structure to optimize the library call arraycopy. Since many higher-level operations depend on arraycopy (e.g., insertion to and deletion from an ArrayList), this can be highly beneficial.

All in call, the authors reach a 14.5% overhead compared to using standard arrays (this cannot really be compared to the results of Pizlo et al., since different benchmark suites are used). More interestingly, the authors hint that a final optimization that they did not carry out could yield even better results -- possibly to the extent of being faster than a naive, continuousness array implementation! The idea is the improve the JIT compiler so that it becomes aware of arraylets, and reduces the number of arraylet lookups when scanning an array serially (a very common operation). When going over indexes 0 to size-1, there's no need to find the arraylet with every iteration, but rather only every elements_per_arraylet iterations. While array lookup remains slower than with naive arrays, the GC time savings apparently more than compensate for that.

Of course, this is mostly an unfounded speculation; we should now await a follow-up research, by the same authors or by others, that will carry out this optimization and report the results. Still, I find it absolutely fascinating how existing Java programs (real-time or otherwise) can possibly be enhanced by optimizing such a basic facet of the JVM -- something which was generally considered too basic to optimize. The benefits of managed environments keep on piling.