Removing GC Synchronisation

1. Problem & Motivation

Java server applications typically exhibit distinctive characteristics: they are usually long-running, heavily multi-threaded, require very large heaps, are executed on large multiprocessors, load classes dynamically and demand that the garbage collector [jone96] provide good throughput and low pause times.

Garbage collection is based on the notion of liveness by reachability from a set of known locations, the roots. Unless the stack is scanned conservatively [boeh88], the mutator¹ must emit stack maps [diwa92,ages98] that describe which slots in a stack frame hold roots. Because stack maps are typically updated only at certain GC points (method calls, backward branches, etc.) in order to reduce storage overheads, it is only safe to collect when the stack map is up-to-date, i.e. at a GC point.

This scheme works well for single-threaded programs as all allocation requests are GC safe points. In a multi-threaded environment, however, we must ensure that all threads are at GC safe points before a collection can continue (even concurrent systems must `stop the world' briefly to synchronise). Unless every instruction is a GC point [stic99], each mutator thread must be rolled forward to a GC point (either by polling or code patching [ages98a]). The cost of this synchronisation in heavily multi-threaded environments is considerable. For example, thread suspension in the VolanoMark client [volano01], a client-server chat application that uses thousands of threads, incurs up to 23% of total time spent in GC (see Table 1).

• The analysis is based on Ruf-Steensgard [ruf00, stee00] but can classify objects even in presence of incomplete knowledge;
• The system requires neither synchronisation nor locks for local collections (in contrast to [stee00]);
• It does not use a write-barrier that may do an unbounded work (in contrast to [doma02)]);
• It is safe in the presence of dynamic class loading; and
• It has been incorporated into a production JVM, Sun's RJVM² [whit98].

2. Background & Related Work

Most work on synchronisation has focussed on mutator-mutator synchronisation [blan99, bogd99, choi99, whal99, ruf00, aldr99, aldr03], elimination of allocator-allocator contention through local allocation blocks [whit98, dimp00, ossi02)] or collector-collector synchronisation to allow multiple collector threads to be run in parallel on each processor [ossi02]. Ageson compares polling and code patching techniques for rolling threads forward to GC points [ages98a]. Stichnoth et al. [stic99] show how stack maps can be compressed sufficiently to allow any instruction to be a GC point.

In contrast, our work uses static analysis and a novel heap organisation to allow independent collection of thread-specific heaps without any synchronisation: it does not require all collector threads to rendezvous, nor does it require any locks to copy objects. In contrast, Steensgard [stee00] (upon whose escape analysis ours is based) initiates collection of all thread-specific heaps simultaneously through a global rendezvous, only after which may all threads start collection of their thread-specific heap. A global lock must also be acquired if a thread copies an object in the shared heap. Furthermore, Steensgard's system is embedded in a native code compiler rather than one that supports dynamic class loading.

A run-time alternative is to use a write barrier to trap any write of a reference to a local object into the shared heap and to mark the object as global. Marking may either take the form of setting a bit (in the object's header or a bitmap) or of copying the object out of the thread-specific region into a global heap region. The former is faster but risks fragmentation by leaving global objects in local regions [doma02.] The latter, conversely, involves a potentially costly copy operation but maintains the strict partition between local and global objects and preserves object locality. Neither technique bounds the work done by the write-barrier.

Finally, we note that systems that use non-pre-emptive threads [alpe99, alpe00] typically only switch thread contexts at GC points and hence never need to roll mutator threads forward before collection can start. Nevertheless, object segregation would allow such JVMs to collect threads independently.

3. Heap Layout

3.1 Closed Systems

int foo (int x) { 
    Thing t = new Thing(x); 
    return t.bar();
}

void foo () { 
    Thing t = new Thing();
    Stuff.s = t;
}

3.2 Dynamic Class Loading

void foo (Mumble m) { 
    Thing t = new Thing(x);
    m.wibble(t);
}

In summary, our analysis proves that, provided no further classes are loaded, OL objects cannot be reached by other than their allocating thread. However, should further classes be loaded, an OL object (and its transitive closure under the points-to relation) may become reachable by other threads. L, objects on the other hand, can never escape their allocating thread. The points-to invariants are:     Inv.1     No references from an object in one thread's heaplet into another thread's heaplet.       Inv.2     No references from a shared, G object to any object in a local heaplet.       Inv.3     No references from any OL object to any object in an L heaplet.

3.3 Non-conforming Classes

Because our analysis guarantees that there are neither G-OL, G-L nor OL-L references, we can collect a thread's L heaplet independently of all other heaplets, and its OL heaplet independently of the shared heap and of other threads. In practice, we usually collect a thread's L and OL together, independently of other threads. Only the shared heap requires a global thread rendezvous before it can be collected.

However, suppose that the loading of a new class allows an object o allocated at a site s (and o's transitive closure, o*) to change from OL to G. We call such a class non-conforming. All objects in o* must have been allocated in the same OL heaplet T_OL as o or in the shared heap. Because we do not maintain any record of which site allocated which object, we must treat all objects in T_OL as global. T_OL can no longer be collected independently but instead is treated as if it were part of the shared heap, H. Furthermore, any thread T_i that invokes allocation at this site s must be treated in the same way: all T_i,OL become global.

We justify this design decision as follows. Our collector is designed for long-running server applications. We expect analysis to be delayed until most classes have been loaded so that it can take advantage of as much knowledge of the program as possible. This reduces the chance of loading a non-conforming class in the future. We expect most classes that might be loaded to conform. It is unusual for a sub-class to allow an object to escape its thread (for example, by allocating it to a static field) when its parent did not. The worst-case outcome is that there were no L heaplets and that all OL heaplets become global. But this case is simply the status quo: a single shared heap.

4. Analysis

Our analysis is a development of Ruf's and Steensgard's algorithms for synchronisation removal [ruf00, stee00]. We group potentially aliased expressions into equivalence classes and construct polymorphic method summaries (method contexts) that can be reused at different call sites. The algorithm is thus context-sensitive and flow-insensitive: it does not require iteration to a fixed point. Although, in the worst-case, time and space complexity is exponential, Ruf demonstrates that these analyses are fast in practice.

Unlike Ruf-Steensgard, our algorithm is compositional: any class loaded after a partial analysis of a snapshot of the program is also analysed for conformance (i.e. that no execution of any method of this class could infringe the pointer-direction invariants) and incorporated into the system. Support for dynamic class loading is achieved by presuming fields and method parameters to be OL rather than L (unless proven otherwise). Consequently, our analysis deems only those objects that do not escape their allocating method (and thus are stack allocatable) to be L. Our current conformance check is very simple: we accept the class as conforming if and only if its method contexts are identical to those of the class that it over-rides (if any).

4.1 Specialisation

Thing t = new Thing();
t.f = Mumble.g; //g is global
foo(t);

void foo (Thing t) {
  bar(t.f);
}

Specialisation has consequences for a class' constant pool and its vtable. Both are of a fixed size, determined at class load time, but our specialisations increase the size of the pool and add further entries to the vtable. To accommodate this, we provide a second, shadow constant pool that is only used by our specialisations. Note that the shadow constant pool is guaranteed to be fully resolved. Calls to specialised methods are also handled through a shadow vtable. The cost of specialisation is thus an increase in space. Currently, we also require extra indirections for method calls but planned compiler modifications will remove these.

Finally, there is a trade-off between performing analysis earlier or later. Analysis is performed by a background thread. The sooner analysis is complete, the fewer objects that turn out to be thread-local are allocated in the shared heap. On the other hand, the later the analysis is performed, the more complete is our information (as more classes have been loaded and analysed). Thus fewer objects have to be allocated conservatively as thread-escaping. A closed system faces none of these issues as it has complete knowledge of all classes; no L objects need be allocated in the shared heap in a closed system.

5. GC Implementation

Our heap comprises one shared heap and one heaplet per thread, including the main thread. The root set for the collection of a region is those locations, outside that region, that hold a reference to an object inside that region. Roots include registers, stack, globals and objects in other regions holding inter-region references. Local, thread-specific heaplets may be collected independently of each other and without collecting the shared heap as their roots are only found within that thread's stack (and registers). Thus, when a request for allocation into a thread-local heaplet cannot be satisfied, only the thread making the request need be blocked while its heaplets are collected. The invariants above allow an object to be moved by the collector as no reference to that object can be held in any object that might be accessed by another thread. Neither global rendezvous, tricolour marking nor locks are required to allow a local collection to be performed. On the other hand, collection of the shared heap does require the usual global rendezvous. All threads must be stopped since objects in the shared heap may escape the thread that allocated them. Not only may there may be references to shared objects from outside the shared heap but shared objects may be reachable from more than one thread.

It is important that space in the heap be divided appropriately between the shared heap and the thread-specific heaplets. It would, for example, be inappropriate to divide the heap equally between each heaplet and the shared heap unless the pattern of memory demands of each thread were similar. Furthermore, it is probably desirable in most environments to avoid the situation in which all threads exhaust their heaplet simultaneously; although we still do not need to synchronise, all mutator threads would be stopped.

At the lowest level, the heap is constructed from local allocation blocks (LABs), each of 4KB. When a thread runs out of space, it requests one or more new LABs from the LAB-manager. Assuming that this request can be satisfied, the thread has the exclusive right to allocate objects in that (those) LAB(s). Most allocation is therefore linear, fast and synchronisation-free. This scheme also allows heaplets to grow dynamically, making better use of available space, rather than being constrained to a fixed size. We expect this scheme to respond well to program phase changes [wils95] since garbage collecting a heaplet compacts it into fewer LABs.

A heaplet is a list of LABs. Our analysis requires that heaplets either be collected by their owning thread (if they do not contain any shared objects) or with the shared heap⁴ in a stop-the-world collection. The heaplet's header indicates whether the heaplet is L, OL or G. Each thread can collect its L and OL heaplets independently of other threads. However, dynamic class loading may mean that objects allocated in a thread's OL heaplet can no longer be guaranteed not to be shared. In this case, it is the responsibility of the loader to set the header of the OL heaplets of each affected thread to G. G heaplets are collected only by stop-the-world collection.

Objects allocated by sites later determined to be L or OL will be placed in the shared heap if they are allocated before the analysis is run. These objects may refer to objects placed in the same thread's L or OL heaplet after the analysis has run. However, this does not break invariant Inv.2 and is safe for the following reasons. Although allocated in the shared heap, the object cannot be reached by any thread other than the one that is blocked. Whenever the shared heap is collected, so are all local heaplets. Thus, inter-heaplet references can be safely updated. On the other hand, any local object that was placed in the shared heap must be treated as a root of its thread's local collection. For reasons of simplicity of implementation and because we have many more heap regions than any RJVM heap configuration, we use remsets rather than card-tables [jone96] to detect inter-region references. We have found the size of these sets to be very small.

The collectors can move local objects allocated in the shared heap. At collection time, a thread T's remset is examined. Each entry must refer to an L or OL object that was placed in the shared heap. Furthermore, any other reference to this object must be from other objects local to this thread. It is therefore safe to move these objects out of the shared heap. If an object o contains a reference to an object in T_L, then o must be local and can be moved to T_L. Otherwise, o is either L or OL: in either case, it is safe to move o to T_OL. Any future write of a T_L-pointer to an object moved into T_OL must be trapped and added to T's remset in a similar fashion. This is necessary to allow T_L to continue to be collected independently even after the loading of a class has caused T_OL to be treated as global.

Over the shared-heap/local-heaplets structure, we lay a generational organisation. The design of this generational system is orthogonal to the design of the shared/local structure. The shared heap and the local heaplets each have two generations. However, other generational configurations are possible. For example, the system might be configured to have just a single, shared, old generation, rather than one old generation per thread.

6. Evaluation

The benchmarks used were the VolanoMark Client and Server [volano01], a client-server chat application, and SPECjbb2000 [specjbb], which emulates a 3-tier business system. Volano Client used 1024 connections (2048 threads) and SPECjbb2000 used 4 warehouses, each running 4 threads. All benchmarks were run on a lightly loaded Sun Ultra 60, with two 450 MHz UltraSPARC-II processors sharing 512 Mbytes of memory, running the Solaris 8 operating system.

Table 3 shows the number of classes and methods (total and fraction resolved in the snapshot), the number of L, OL and G allocation sites, the number of methods specialised, the code size (original and increase for both bytecode and compiled code) and the analysis time (and start time) for each benchmark.

The snapshot tactic resolves almost all methods despite capturing a smaller fraction of classes (but note that these benchmark applications typically load small reporting classes at the end of the run). The number of L and OL allocation sites is encouraging but we have yet to measure volume or space rental of objects allocated. Analysis times are acceptable for long-running server applications but very susceptible to the number of threads running (as the analysis runs in a separate background thread). However, code size is increased significantly; it may be better to profile methods and only specialise those that allocate heavily.

7. Future Work

At the time of writing, the implementation of the analysis and the collector is complete and run-time experiments are about to start.

We plan a number of improvements to the system. The collector should move thread-local objects allocated in the shared heap (before analysis) to their own heaplet whenever they are discovered in the heaplet's remset. Methods in dynamically loaded classes are only assumed to conform if their method contexts are identical to those of already loaded methods. Better conformance rules for dynamically loaded classes are almost certainly possible. Efficient use of the heap by many heaplets will be vital. We intend to investigate better GC triggers than simply `heap full'. We intend to remove the additional indirections required by calls to specialised methods (through shadow vtables).

Above all, this system offers a wide design space for garbage collection policy. For example, how rapidly and to what size should heaplets be expanded? The simplest growth policy is to expand heaplets by one LAB at a time. However, it might be better to allow memory-greedy threads to expand more rapidly in order to reduce LAB-manager synchronisation overhead. It is also important to decide when to collect and what to collect. Again, a simple solution may be allow heaplets to grow without restraint and to collect a heaplet only when the heap is full. However, as we noted above, this policy is likely to cause all threads to collect at about the same time - when the heap is full. It may be better to force a thread to collect (by denying a request for a LAB) when its volume of allocation since its last collection has exceed a threshold [zorn89]. Assuming a mix of thread behaviours, such a policy will reduce the tendency of all threads to collect simultaneously. A variation on this solution is to favour threads that are more active. Suppose the thread mix consists of a number of threads with growing memory footprints and other threads that have more stationary footprints. Rather than force the growing threads to collect repeatedly (which may offer comparatively small returns if the thread is constructing a large data structure - a commonly observed behaviour), it may be better to force collection of threads whose growth phase has stopped (by denying LAB allocation requests). Similarly, denial of LAB requests may be used to ensure that no thread remains uncollected for long periods of time. Other collection policies based on a thread's allocation and collection history are possible.

8. Conclusion

Acknowledgements

Footnotes

References

Copyright © 2003 University of Kent at Canterbury
Published by the Computing Laboratory,
University of Kent, Canterbury, Kent CT2 7NF, UK