Debian Codegraph @

gc/doc/scale.md

raw
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.