| 1 |
721 |
jeremybenn |
<HTML>
|
| 2 |
|
|
<HEAD>
|
| 3 |
|
|
<TITLE>Garbage collector scalability</TITLE>
|
| 4 |
|
|
</HEAD>
|
| 5 |
|
|
<BODY>
|
| 6 |
|
|
<H1>Garbage collector scalability</h1>
|
| 7 |
|
|
In its default configuration, the Boehm-Demers-Weiser garbage collector
|
| 8 |
|
|
is not thread-safe. It can be made thread-safe for a number of environments
|
| 9 |
|
|
by building the collector with the appropriate
|
| 10 |
|
|
<TT>-D</tt><I>XXX</i><TT>-THREADS</tt> compilation
|
| 11 |
|
|
flag. This has primarily two effects:
|
| 12 |
|
|
<OL>
|
| 13 |
|
|
<LI> It causes the garbage collector to stop all other threads when
|
| 14 |
|
|
it needs to see a consistent memory state.
|
| 15 |
|
|
<LI> It causes the collector to acquire a lock around essentially all
|
| 16 |
|
|
allocation and garbage collection activity.
|
| 17 |
|
|
</ol>
|
| 18 |
|
|
Since a single lock is used for all allocation-related activity, only one
|
| 19 |
|
|
thread can be allocating or collecting at one point. This inherently
|
| 20 |
|
|
limits performance of multi-threaded applications on multiprocessors.
|
| 21 |
|
|
<P>
|
| 22 |
|
|
On most platforms, the allocator/collector lock is implemented as a
|
| 23 |
|
|
spin lock with exponential back-off. Longer wait times are implemented
|
| 24 |
|
|
by yielding and/or sleeping. If a collection is in progress, the pure
|
| 25 |
|
|
spinning stage is skipped. This has the advantage that uncontested and
|
| 26 |
|
|
thus most uniprocessor lock acquisitions are very cheap. It has the
|
| 27 |
|
|
disadvantage that the application may sleep for small periods of time
|
| 28 |
|
|
even when there is work to be done. And threads may be unnecessarily
|
| 29 |
|
|
woken up for short periods. Nonetheless, this scheme empirically
|
| 30 |
|
|
outperforms native queue-based mutual exclusion implementations in most
|
| 31 |
|
|
cases, sometimes drastically so.
|
| 32 |
|
|
<H2>Options for enhanced scalability</h2>
|
| 33 |
|
|
Version 6.0 of the collector adds two facilities to enhance collector
|
| 34 |
|
|
scalability on multiprocessors. As of 6.0alpha1, these are supported
|
| 35 |
|
|
only under Linux on X86 and IA64 processors, though ports to other
|
| 36 |
|
|
otherwise supported Pthreads platforms should be straightforward.
|
| 37 |
|
|
They are intended to be used together.
|
| 38 |
|
|
<UL>
|
| 39 |
|
|
<LI>
|
| 40 |
|
|
Building the collector with <TT>-DPARALLEL_MARK</tt> allows the collector to
|
| 41 |
|
|
run the mark phase in parallel in multiple threads, and thus on multiple
|
| 42 |
|
|
processors. The mark phase typically consumes the large majority of the
|
| 43 |
|
|
collection time. Thus this largely parallelizes the garbage collector
|
| 44 |
|
|
itself, though not the allocation process. Currently the marking is
|
| 45 |
|
|
performed by the thread that triggered the collection, together with
|
| 46 |
|
|
<I>N</i>-1 dedicated
|
| 47 |
|
|
threads, where <I>N</i> is the number of processors detected by the collector.
|
| 48 |
|
|
The dedicated threads are created once at initialization time.
|
| 49 |
|
|
<P>
|
| 50 |
|
|
A second effect of this flag is to switch to a more concurrent
|
| 51 |
|
|
implementation of <TT>GC_malloc_many</tt>, so that free lists can be
|
| 52 |
|
|
built, and memory can be cleared, by more than one thread concurrently.
|
| 53 |
|
|
<LI>
|
| 54 |
|
|
Building the collector with -DTHREAD_LOCAL_ALLOC adds support for thread
|
| 55 |
|
|
local allocation. It does not, by itself, cause thread local allocation
|
| 56 |
|
|
to be used. It simply allows the use of the interface in
|
| 57 |
|
|
<TT>gc_local_alloc.h</tt>.
|
| 58 |
|
|
<P>
|
| 59 |
|
|
Memory returned from thread-local allocators is completely interchangeable
|
| 60 |
|
|
with that returned by the standard allocators. It may be used by other
|
| 61 |
|
|
threads. The only difference is that, if the thread allocates enough
|
| 62 |
|
|
memory of a certain kind, it will build a thread-local free list for
|
| 63 |
|
|
objects of that kind, and allocate from that. This greatly reduces
|
| 64 |
|
|
locking. The thread-local free lists are refilled using
|
| 65 |
|
|
<TT>GC_malloc_many</tt>.
|
| 66 |
|
|
<P>
|
| 67 |
|
|
An important side effect of this flag is to replace the default
|
| 68 |
|
|
spin-then-sleep lock to be replace by a spin-then-queue based implementation.
|
| 69 |
|
|
This <I>reduces performance</i> for the standard allocation functions,
|
| 70 |
|
|
though it usually improves performance when thread-local allocation is
|
| 71 |
|
|
used heavily, and thus the number of short-duration lock acquisitions
|
| 72 |
|
|
is greatly reduced.
|
| 73 |
|
|
</ul>
|
| 74 |
|
|
<P>
|
| 75 |
|
|
The easiest way to switch an application to thread-local allocation is to
|
| 76 |
|
|
<OL>
|
| 77 |
|
|
<LI> Define the macro <TT>GC_REDIRECT_TO_LOCAL</tt>,
|
| 78 |
|
|
and then include the <TT>gc.h</tt>
|
| 79 |
|
|
header in each client source file.
|
| 80 |
|
|
<LI> Invoke <TT>GC_thr_init()</tt> before any allocation.
|
| 81 |
|
|
<LI> Allocate using <TT>GC_MALLOC</tt>, <TT>GC_MALLOC_ATOMIC</tt>,
|
| 82 |
|
|
and/or <TT>GC_GCJ_MALLOC</tt>.
|
| 83 |
|
|
</ol>
|
| 84 |
|
|
<H2>The Parallel Marking Algorithm</h2>
|
| 85 |
|
|
We use an algorithm similar to
|
| 86 |
|
|
<A HREF="http://www.yl.is.s.u-tokyo.ac.jp/gc/">that developed by
|
| 87 |
|
|
Endo, Taura, and Yonezawa</a> at the University of Tokyo.
|
| 88 |
|
|
However, the data structures and implementation are different,
|
| 89 |
|
|
and represent a smaller change to the original collector source,
|
| 90 |
|
|
probably at the expense of extreme scalability. Some of
|
| 91 |
|
|
the refinements they suggest, <I>e.g.</i> splitting large
|
| 92 |
|
|
objects, were also incorporated into out approach.
|
| 93 |
|
|
<P>
|
| 94 |
|
|
The global mark stack is transformed into a global work queue.
|
| 95 |
|
|
Unlike the usual case, it never shrinks during a mark phase.
|
| 96 |
|
|
The mark threads remove objects from the queue by copying them to a
|
| 97 |
|
|
local mark stack and changing the global descriptor to zero, indicating
|
| 98 |
|
|
that there is no more work to be done for this entry.
|
| 99 |
|
|
This removal
|
| 100 |
|
|
is done with no synchronization. Thus it is possible for more than
|
| 101 |
|
|
one worker to remove the same entry, resulting in some work duplication.
|
| 102 |
|
|
<P>
|
| 103 |
|
|
The global work queue grows only if a marker thread decides to
|
| 104 |
|
|
return some of its local mark stack to the global one. This
|
| 105 |
|
|
is done if the global queue appears to be running low, or if
|
| 106 |
|
|
the local stack is in danger of overflowing. It does require
|
| 107 |
|
|
synchronization, but should be relatively rare.
|
| 108 |
|
|
<P>
|
| 109 |
|
|
The sequential marking code is reused to process local mark stacks.
|
| 110 |
|
|
Hence the amount of additional code required for parallel marking
|
| 111 |
|
|
is minimal.
|
| 112 |
|
|
<P>
|
| 113 |
|
|
It should be possible to use generational collection in the presence of the
|
| 114 |
|
|
parallel collector, by calling <TT>GC_enable_incremental()</tt>.
|
| 115 |
|
|
This does not result in fully incremental collection, since parallel mark
|
| 116 |
|
|
phases cannot currently be interrupted, and doing so may be too
|
| 117 |
|
|
expensive.
|
| 118 |
|
|
<P>
|
| 119 |
|
|
Gcj-style mark descriptors do not currently mix with the combination
|
| 120 |
|
|
of local allocation and incremental collection. They should work correctly
|
| 121 |
|
|
with one or the other, but not both.
|
| 122 |
|
|
<P>
|
| 123 |
|
|
The number of marker threads is set on startup to the number of
|
| 124 |
|
|
available processors (or to the value of the <TT>GC_NPROCS</tt>
|
| 125 |
|
|
environment variable). If only a single processor is detected,
|
| 126 |
|
|
parallel marking is disabled.
|
| 127 |
|
|
<P>
|
| 128 |
|
|
Note that setting GC_NPROCS to 1 also causes some lock acquisitions inside
|
| 129 |
|
|
the collector to immediately yield the processor instead of busy waiting
|
| 130 |
|
|
first. In the case of a multiprocessor and a client with multiple
|
| 131 |
|
|
simultaneously runnable threads, this may have disastrous performance
|
| 132 |
|
|
consequences (e.g. a factor of 10 slowdown).
|
| 133 |
|
|
<H2>Performance</h2>
|
| 134 |
|
|
We conducted some simple experiments with a version of
|
| 135 |
|
|
<A HREF="gc_bench.html">our GC benchmark</a> that was slightly modified to
|
| 136 |
|
|
run multiple concurrent client threads in the same address space.
|
| 137 |
|
|
Each client thread does the same work as the original benchmark, but they share
|
| 138 |
|
|
a heap.
|
| 139 |
|
|
This benchmark involves very little work outside of memory allocation.
|
| 140 |
|
|
This was run with GC 6.0alpha3 on a dual processor Pentium III/500 machine
|
| 141 |
|
|
under Linux 2.2.12.
|
| 142 |
|
|
<P>
|
| 143 |
|
|
Running with a thread-unsafe collector, the benchmark ran in 9
|
| 144 |
|
|
seconds. With the simple thread-safe collector,
|
| 145 |
|
|
built with <TT>-DLINUX_THREADS</tt>, the execution time
|
| 146 |
|
|
increased to 10.3 seconds, or 23.5 elapsed seconds with two clients.
|
| 147 |
|
|
(The times for the <TT>malloc</tt>/i<TT>free</tt> version
|
| 148 |
|
|
with glibc <TT>malloc</tt>
|
| 149 |
|
|
are 10.51 (standard library, pthreads not linked),
|
| 150 |
|
|
20.90 (one thread, pthreads linked),
|
| 151 |
|
|
and 24.55 seconds respectively. The benchmark favors a
|
| 152 |
|
|
garbage collector, since most objects are small.)
|
| 153 |
|
|
<P>
|
| 154 |
|
|
The following table gives execution times for the collector built
|
| 155 |
|
|
with parallel marking and thread-local allocation support
|
| 156 |
|
|
(<TT>-DGC_LINUX_THREADS -DPARALLEL_MARK -DTHREAD_LOCAL_ALLOC</tt>). We tested
|
| 157 |
|
|
the client using either one or two marker threads, and running
|
| 158 |
|
|
one or two client threads. Note that the client uses thread local
|
| 159 |
|
|
allocation exclusively. With -DTHREAD_LOCAL_ALLOC the collector
|
| 160 |
|
|
switches to a locking strategy that is better tuned to less frequent
|
| 161 |
|
|
lock acquisition. The standard allocation primitives thus peform
|
| 162 |
|
|
slightly worse than without -DTHREAD_LOCAL_ALLOC, and should be
|
| 163 |
|
|
avoided in time-critical code.
|
| 164 |
|
|
<P>
|
| 165 |
|
|
(The results using <TT>pthread_mutex_lock</tt>
|
| 166 |
|
|
directly for allocation locking would have been worse still, at
|
| 167 |
|
|
least for older versions of linuxthreads.
|
| 168 |
|
|
With THREAD_LOCAL_ALLOC, we first repeatedly try to acquire the
|
| 169 |
|
|
lock with pthread_mutex_try_lock(), busy_waiting between attempts.
|
| 170 |
|
|
After a fixed number of attempts, we use pthread_mutex_lock().)
|
| 171 |
|
|
<P>
|
| 172 |
|
|
These measurements do not use incremental collection, nor was prefetching
|
| 173 |
|
|
enabled in the marker. We used the C version of the benchmark.
|
| 174 |
|
|
All measurements are in elapsed seconds on an unloaded machine.
|
| 175 |
|
|
<P>
|
| 176 |
|
|
<TABLE BORDER ALIGN="CENTER">
|
| 177 |
|
|
<TR><TH>Number of threads</th><TH>1 marker thread (secs.)</th>
|
| 178 |
|
|
<TH>2 marker threads (secs.)</th></tr>
|
| 179 |
|
|
<TR><TD>1 client</td><TD ALIGN="CENTER">10.45</td><TD ALIGN="CENTER">7.85</td>
|
| 180 |
|
|
<TR><TD>2 clients</td><TD ALIGN="CENTER">19.95</td><TD ALIGN="CENTER">12.3</td>
|
| 181 |
|
|
</table>
|
| 182 |
|
|
<PP>
|
| 183 |
|
|
The execution time for the single threaded case is slightly worse than with
|
| 184 |
|
|
simple locking. However, even the single-threaded benchmark runs faster than
|
| 185 |
|
|
even the thread-unsafe version if a second processor is available.
|
| 186 |
|
|
The execution time for two clients with thread local allocation time is
|
| 187 |
|
|
only 1.4 times the sequential execution time for a single thread in a
|
| 188 |
|
|
thread-unsafe environment, even though it involves twice the client work.
|
| 189 |
|
|
That represents close to a
|
| 190 |
|
|
factor of 2 improvement over the 2 client case with the old collector.
|
| 191 |
|
|
The old collector clearly
|
| 192 |
|
|
still suffered from some contention overhead, in spite of the fact that the
|
| 193 |
|
|
locking scheme had been fairly well tuned.
|
| 194 |
|
|
<P>
|
| 195 |
|
|
Full linear speedup (i.e. the same execution time for 1 client on one
|
| 196 |
|
|
processor as 2 clients on 2 processors)
|
| 197 |
|
|
is probably not achievable on this kind of
|
| 198 |
|
|
hardware even with such a small number of processors,
|
| 199 |
|
|
since the memory system is
|
| 200 |
|
|
a major constraint for the garbage collector,
|
| 201 |
|
|
the processors usually share a single memory bus, and thus
|
| 202 |
|
|
the aggregate memory bandwidth does not increase in
|
| 203 |
|
|
proportion to the number of processors.
|
| 204 |
|
|
<P>
|
| 205 |
|
|
These results are likely to be very sensitive to both hardware and OS
|
| 206 |
|
|
issues. Preliminary experiments with an older Pentium Pro machine running
|
| 207 |
|
|
an older kernel were far less encouraging.
|
| 208 |
|
|
|
| 209 |
|
|
</body>
|
| 210 |
|
|
</html>
|
