doc/scale.html

   1 <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.  Before GC version 7.0, it did not, by itself, cause
  56 thread local allocation to be used.  It simply allowed the use of the
  57 interface in <TT>gc_local_alloc.h</tt>.  Since version 7.0, this causes
  58 GC_malloc, GC_malloc_atomic, and GC_gcj_malloc to be redefined to perform
  59 thread-local allocation.
  60 <P>
  61 Memory returned from thread-local allocators is completely interchangeable
  62 with that returned by the standard allocators.  It may be used by other
  63 threads.  The only difference is that, if the thread allocates enough
  64 memory of a certain kind, it will build a thread-local free list for
  65 objects of that kind, and allocate from that.  This greatly reduces
  66 locking.  The thread-local free lists are refilled using
  67 <TT>GC_malloc_many</tt>.
  68 <P>
  69 An important side effect of this flag is to replace the default
  70 spin-then-sleep lock to be replace by a spin-then-queue based implementation.
  71 This <I>reduces performance</i> for the standard allocation functions,
  72 though it usually improves performance when thread-local allocation is
  73 used heavily, and thus the number of short-duration lock acquisitions
  74 is greatly reduced.
  75 </ul>
  76 <P>
  77 The easiest way to switch an application to thread-local allocation
  78 in a pre-version-7.0 collector was to
  79 <OL>
  80 <LI> Define the macro <TT>GC_REDIRECT_TO_LOCAL</tt>,
  81 and then include the <TT>gc.h</tt>
  82 header in each client source file.
  83 <LI> Invoke <TT>GC_thr_init()</tt> before any allocation.
  84 <LI> Allocate using <TT>GC_MALLOC</tt>, <TT>GC_MALLOC_ATOMIC</tt>,
  85 and/or <TT>GC_GCJ_MALLOC</tt>.
  86 </ol>
  87 <H2>The Parallel Marking Algorithm</h2>
  88 We use an algorithm similar to
  89 <A HREF="http://www.yl.is.s.u-tokyo.ac.jp/gc/">that developed by
  90 Endo, Taura, and Yonezawa</a> at the University of Tokyo.
  91 However, the data structures and implementation are different,
  92 and represent a smaller change to the original collector source,
  93 probably at the expense of extreme scalability.  Some of
  94 the refinements they suggest, <I>e.g.</i> splitting large
  95 objects, were also incorporated into out approach.
  96 <P>
  97 The global mark stack is transformed into a global work queue.
  98 Unlike the usual case, it never shrinks during a mark phase.
  99 The mark threads remove objects from the queue by copying them to a
 100 local mark stack and changing the global descriptor to zero, indicating
 101 that there is no more work to be done for this entry.
 102 This removal
 103 is done with no synchronization.  Thus it is possible for more than
 104 one worker to remove the same entry, resulting in some work duplication.
 105 <P>
 106 The global work queue grows only if a marker thread decides to
 107 return some of its local mark stack to the global one.  This
 108 is done if the global queue appears to be running low, or if
 109 the local stack is in danger of overflowing.  It does require
 110 synchronization, but should be relatively rare.
 111 <P>
 112 The sequential marking code is reused to process local mark stacks.
 113 Hence the amount of additional code required for parallel marking
 114 is minimal.
 115 <P>
 116 It should be possible to use generational collection in the presence of the
 117 parallel collector, by calling <TT>GC_enable_incremental()</tt>.
 118 This does not result in fully incremental collection, since parallel mark
 119 phases cannot currently be interrupted, and doing so may be too
 120 expensive.
 121 <P>
 122 Gcj-style mark descriptors do not currently mix with the combination
 123 of local allocation and incremental collection.  They should work correctly
 124 with one or the other, but not both.
 125 <P>
 126 The number of marker threads is set on startup to the number of
 127 available processors (or to the value of the <TT>GC_NPROCS</tt>
 128 environment variable).  If only a single processor is detected,
 129 parallel marking is disabled.
 130 <P>
 131 Note that setting GC_NPROCS to 1 also causes some lock acquisitions inside
 132 the collector to immediately yield the processor instead of busy waiting
 133 first.  In the case of a multiprocessor and a client with multiple
 134 simultaneously runnable threads, this may have disastrous performance
 135 consequences (e.g. a factor of 10 slowdown).
 136 <H2>Performance</h2>
 137 We conducted some simple experiments with a version of
 138 <A HREF="gc_bench.html">our GC benchmark</a> that was slightly modified to
 139 run multiple concurrent client threads in the same address space.
 140 Each client thread does the same work as the original benchmark, but they share
 141 a heap.
 142 This benchmark involves very little work outside of memory allocation.
 143 This was run with GC 6.0alpha3 on a dual processor Pentium III/500 machine
 144 under Linux 2.2.12.
 145 <P>
 146 Running with a thread-unsafe collector,  the benchmark ran in 9
 147 seconds.  With the simple thread-safe collector,
 148 built with <TT>-DLINUX_THREADS</tt>, the execution time
 149 increased to 10.3 seconds, or 23.5 elapsed seconds with two clients.
 150 (The times for the <TT>malloc</tt>/i<TT>free</tt> version
 151 with glibc <TT>malloc</tt>
 152 are 10.51 (standard library, pthreads not linked),
 153 20.90 (one thread, pthreads linked),
 154 and 24.55 seconds respectively. The benchmark favors a
 155 garbage collector, since most objects are small.)
 156 <P>
 157 The following table gives execution times for the collector built
 158 with parallel marking and thread-local allocation support
 159 (<TT>-DGC_LINUX_THREADS -DPARALLEL_MARK -DTHREAD_LOCAL_ALLOC</tt>).  We tested
 160 the client using either one or two marker threads, and running
 161 one or two client threads.  Note that the client uses thread local
 162 allocation exclusively.  With -DTHREAD_LOCAL_ALLOC the collector
 163 switches to a locking strategy that is better tuned to less frequent
 164 lock acquisition.  The standard allocation primitives thus peform
 165 slightly worse than without -DTHREAD_LOCAL_ALLOC, and should be
 166 avoided in time-critical code.
 167 <P>
 168 (The results using <TT>pthread_mutex_lock</tt>
 169 directly for allocation locking would have been worse still, at
 170 least for older versions of linuxthreads.
 171 With THREAD_LOCAL_ALLOC, we first repeatedly try to acquire the
 172 lock with pthread_mutex_try_lock(), busy_waiting between attempts.
 173 After a fixed number of attempts, we use pthread_mutex_lock().)
 174 <P>
 175 These measurements do not use incremental collection, nor was prefetching
 176 enabled in the marker.  We used the C version of the benchmark.
 177 All measurements are in elapsed seconds on an unloaded machine.
 178 <P>
 179 <TABLE BORDER ALIGN="CENTER">
 180 <TR><TH>Number of threads</th><TH>1 marker thread (secs.)</th>
 181 <TH>2 marker threads (secs.)</th></tr>
 182 <TR><TD>1 client</td><TD ALIGN="CENTER">10.45</td><TD ALIGN="CENTER">7.85</td>
 183 <TR><TD>2 clients</td><TD ALIGN="CENTER">19.95</td><TD ALIGN="CENTER">12.3</td>
 184 </table>
 185 <PP>
 186 The execution time for the single threaded case is slightly worse than with
 187 simple locking.  However, even the single-threaded benchmark runs faster than
 188 even the thread-unsafe version if a second processor is available.
 189 The execution time for two clients with thread local allocation time is
 190 only 1.4 times the sequential execution time for a single thread in a
 191 thread-unsafe environment, even though it involves twice the client work.
 192 That represents close to a
 193 factor of 2 improvement over the 2 client case with the old collector.
 194 The old collector clearly
 195 still suffered from some contention overhead, in spite of the fact that the
 196 locking scheme had been fairly well tuned.
 197 <P>
 198 Full linear speedup (i.e. the same execution time for 1 client on one
 199 processor as 2 clients on 2 processors)
 200 is probably not achievable on this kind of
 201 hardware even with such a small number of processors,
 202 since the memory system is
 203 a major constraint for the garbage collector,
 204 the processors usually share a single memory bus, and thus
 205 the aggregate memory bandwidth does not increase in
 206 proportion to the number of processors.
 207 <P>
 208 These results are likely to be very sensitive to both hardware and OS
 209 issues.  Preliminary experiments with an older Pentium Pro machine running
 210 an older kernel were far less encouraging.
 211
 212 </body>
 213 </html>