Debian Codegraph @

external/bdwgc/doc/scale.md

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