| 1 |
# Garbage collector scalability |
| 2 |
|
| 3 |
If Makefile.direct is used, in its default configuration the |
| 4 |
Boehm-Demers-Weiser garbage collector is not thread-safe. Generally, it can be |
| 5 |
made thread-safe by building the collector with `-DGC_THREADS` compilation |
| 6 |
flag. This has primarily the following effects: |
| 7 |
|
| 8 |
1. It causes the garbage collector to stop all other threads when it needs |
| 9 |
to see a consistent memory state. It intercepts thread creation and |
| 10 |
termination events to maintain a list of client threads to be stopped when |
| 11 |
needed. |
| 12 |
2. It causes the collector to acquire a lock around essentially all |
| 13 |
allocation and garbage collection activity. Since a single lock is used for |
| 14 |
all allocation-related activity, only one thread can be allocating |
| 15 |
or collecting at one point. This inherently limits performance |
| 16 |
of multi-threaded applications on multiprocessors. |
| 17 |
|
| 18 |
On most platforms, the allocator/collector lock is implemented as a spin lock |
| 19 |
with exponential back-off. Longer wait times are implemented by yielding |
| 20 |
and/or sleeping. If a collection is in progress, the pure spinning stage |
| 21 |
is skipped. This has the uncontested advantage that most uniprocessor lock |
| 22 |
acquisitions are very cheap. It has the disadvantage that the application may |
| 23 |
sleep for small periods of time even when there is work to be done. And |
| 24 |
threads may be unnecessarily woken up for short periods. Nonetheless, this |
| 25 |
scheme empirically outperforms native queue-based mutual exclusion |
| 26 |
implementations in most cases, sometimes drastically so. |
| 27 |
|
| 28 |
## Options for enhanced scalability |
| 29 |
|
| 30 |
The collector uses two facilities to enhance collector scalability on |
| 31 |
multiprocessors. They are intended to be used together. (The following refers |
| 32 |
to Makefile.direct again.) |
| 33 |
|
| 34 |
* Building the collector with `-DPARALLEL_MARK` allows the collector to run |
| 35 |
the mark phase in parallel in multiple threads, and thus on multiple |
| 36 |
processors (or processor cores). The mark phase typically consumes the large |
| 37 |
majority of the collection time. Thus, this largely parallelizes the garbage |
| 38 |
collector itself, though not the allocation process. Currently the marking |
| 39 |
is performed by the thread that triggered the collection, together with |
| 40 |
_N_ - 1 dedicated threads, where _N_ is the number of processors (cores) |
| 41 |
detected by the collector. The dedicated marker threads are created when the |
| 42 |
client calls `GC_start_mark_threads()` or when the client starts the first |
| 43 |
non-main thread after the GC initialization (or after fork operation in |
| 44 |
a child process). Another effect of this flag is to switch to a more |
| 45 |
concurrent implementation of `GC_malloc_many`, so that free lists can be |
| 46 |
built and memory can be cleared by more than one thread concurrently. |
| 47 |
* Building the collector with `-DTHREAD_LOCAL_ALLOC` adds support for |
| 48 |
thread-local allocation. This causes `GC_malloc` (actually `GC_malloc_kind`) |
| 49 |
and `GC_gcj_malloc` to be redefined to perform thread-local allocation. |
| 50 |
|
| 51 |
Memory returned from thread-local allocators is completely interchangeable |
| 52 |
with that returned by the standard allocators. It may be used by other |
| 53 |
threads. The only difference is that, if the thread allocates enough memory |
| 54 |
of a certain kind, it will build a thread-local free list for objects of that |
| 55 |
kind, and allocate from that. This greatly reduces locking. The thread-local |
| 56 |
free lists are refilled using `GC_malloc_many`. |
| 57 |
|
| 58 |
An important side effect of this flag is to replace the default |
| 59 |
spin-then-sleep lock to be replaced by a spin-then-queue based implementation. |
| 60 |
This _reduces performance_ for the standard allocation functions, though |
| 61 |
it usually improves performance when thread-local allocation is used heavily, |
| 62 |
and, thus, the number of short-duration lock acquisitions is greatly reduced. |
| 63 |
|
| 64 |
## The Parallel Marking Algorithm |
| 65 |
|
| 66 |
We use an algorithm similar to |
| 67 |
[that developed by Endo, Taura, and Yonezawa](http://www.yl.is.s.u-tokyo.ac.jp/gc/) |
| 68 |
at the University of Tokyo. However, the data structures and implementation |
| 69 |
are different, and represent a smaller change to the original collector |
| 70 |
source, probably at the expense of extreme scalability. Some of the |
| 71 |
refinements they suggest, e.g. splitting large objects, were also incorporated |
| 72 |
into our approach. |
| 73 |
|
| 74 |
The global mark stack is transformed into a global work queue. Unlike the |
| 75 |
usual case, it never shrinks during a mark phase. The mark threads remove |
| 76 |
objects from the queue by copying them to a local mark stack and changing the |
| 77 |
global descriptor to zero, indicating that there is no more work to be done |
| 78 |
for this entry. This removal is done with no synchronization. Thus it is |
| 79 |
possible for more than one worker to remove the same entry, resulting in some |
| 80 |
work duplication. |
| 81 |
|
| 82 |
The global work queue grows only if a marker thread decides to return some |
| 83 |
of its local mark stack to the global one. This is done if the global queue |
| 84 |
appears to be running low, or if the local stack is in danger of overflowing. |
| 85 |
It does require synchronization, but should be relatively rare. |
| 86 |
|
| 87 |
The sequential marking code is reused to process local mark stacks. Hence the |
| 88 |
amount of additional code required for parallel marking is minimal. |
| 89 |
|
| 90 |
It should be possible to use incremental/generational collection in the |
| 91 |
presence of the parallel collector by calling `GC_enable_incremental`, but |
| 92 |
the current implementation does not allow interruption of the parallel marker, |
| 93 |
so the latter is mostly avoided if the client sets the collection time limit. |
| 94 |
|
| 95 |
Gcj-style mark descriptors do not currently mix with the combination of local |
| 96 |
allocation and incremental collection. They should work correctly with one or |
| 97 |
the other, but not both. |
| 98 |
|
| 99 |
The number of marker threads is set on startup to the number of available |
| 100 |
processor cores (or to the value of either `GC_MARKERS` or `GC_NPROCS` |
| 101 |
environment variable, if provided). If only a single processor is detected, |
| 102 |
parallel marking is disabled. |
| 103 |
|
| 104 |
Note that setting `GC_NPROCS` to 1 also causes some lock acquisitions inside |
| 105 |
the collector to immediately yield the processor instead of busy waiting |
| 106 |
first. In the case of a multiprocessor and a client with multiple |
| 107 |
simultaneously runnable threads, this may have disastrous performance |
| 108 |
consequences (e.g. a factor of 10 slowdown). |
| 109 |
|
| 110 |
## Performance |
| 111 |
|
| 112 |
We conducted some simple experiments with a version of |
| 113 |
[our GC benchmark](http://www.hboehm.info/gc/gc_bench/) that was slightly |
| 114 |
modified to run multiple concurrent client threads in the same address space. |
| 115 |
Each client thread does the same work as the original benchmark, but they |
| 116 |
share a heap. This benchmark involves very little work outside of memory |
| 117 |
allocation. This was run with an ancient GC (released in 2000) on a dual |
| 118 |
processor Pentium III/500 machine under Linux 2.2.12. |
| 119 |
|
| 120 |
Running with a thread-unsafe collector, the benchmark ran in 9 seconds. With |
| 121 |
the simple thread-safe collector, built with `-DGC_THREADS`, the execution |
| 122 |
time increased to 10.3 seconds, or 23.5 elapsed seconds with two clients. (The |
| 123 |
times for the `malloc`/`free` version with glibc `malloc` are 10.51 (standard |
| 124 |
library, pthreads not linked), 20.90 (one thread, pthreads linked), and 24.55 |
| 125 |
seconds, respectively. The benchmark favors a garbage collector, since most |
| 126 |
objects are small.) |
| 127 |
|
| 128 |
The following table gives execution times for the collector built with |
| 129 |
parallel marking and thread-local allocation support |
| 130 |
(`-DGC_THREADS -DPARALLEL_MARK -DTHREAD_LOCAL_ALLOC`). We tested the client |
| 131 |
using either one or two marker threads, and running one or two client threads. |
| 132 |
Note that the client uses thread local allocation exclusively. With |
| 133 |
`-DTHREAD_LOCAL_ALLOC` the collector switches to a locking strategy that |
| 134 |
is better tuned to less frequent lock acquisition. The standard allocation |
| 135 |
primitives thus perform slightly worse than without `-DTHREAD_LOCAL_ALLOC`, |
| 136 |
and should be avoided in time-critical code. |
| 137 |
|
| 138 |
(The results using `pthread_mutex_lock` directly for allocation locking would |
| 139 |
have been worse still, at least for older versions of linuxthreads. With |
| 140 |
`-DTHREAD_LOCAL_ALLOC`, we first repeatedly try to acquire the lock with |
| 141 |
`pthread_mutex_try_lock`, busy-waiting between attempts. After a fixed number |
| 142 |
of attempts, we use `pthread_mutex_lock`.) |
| 143 |
|
| 144 |
These measurements do not use incremental collection, nor was prefetching |
| 145 |
enabled in the marker. We used the C version of the benchmark. All |
| 146 |
measurements are in elapsed seconds on an unloaded machine. |
| 147 |
|
| 148 |
Number of client threads| 1 marker thread (secs.)| 2 marker threads (secs.) |
| 149 |
---|------|----- |
| 150 |
1| 10.45| 7.85 |
| 151 |
2| 19.95| 12.3 |
| 152 |
|
| 153 |
The execution time for the single threaded case is slightly worse than with |
| 154 |
simple locking. However, even the single-threaded benchmark runs faster than |
| 155 |
even the thread-unsafe version if a second processor is available. The |
| 156 |
execution time for two clients with thread local allocation time is only 1.4 |
| 157 |
times the sequential execution time for a single thread in a thread-unsafe |
| 158 |
environment, even though it involves twice the client work. That represents |
| 159 |
close to a factor of 2 improvement over the 2 client case with the old |
| 160 |
collector. The old collector clearly still suffered from some contention |
| 161 |
overhead, in spite of the fact that the locking scheme had been fairly well |
| 162 |
tuned. |
| 163 |
|
| 164 |
Full linear speedup (i.e. the same execution time for 1 client on one |
| 165 |
processor as 2 clients on 2 processors) is probably not achievable on this |
| 166 |
kind of hardware even with such a small number of processors, since the memory |
| 167 |
system is a major constraint for the garbage collector, the processors usually |
| 168 |
share a single memory bus, and thus the aggregate memory bandwidth does not |
| 169 |
increase in proportion to the number of processors (cores). |
| 170 |
|
| 171 |
These results are likely to be very sensitive to both hardware and OS issues. |
| 172 |
Preliminary experiments with an older Pentium Pro machine running an older |
| 173 |
kernel were far less encouraging. |