[ceph.git] / ceph / src / boost / tools / build / src / engine / boehm_gc / doc / scale.html

<HTML>
<HEAD>
<TITLE>Garbage collector scalability</TITLE>
</HEAD>
<BODY>
<H1>Garbage collector scalability</h1>
In its default configuration, the Boehm-Demers-Weiser garbage collector
is not thread-safe.  It can be made thread-safe for a number of environments
by building the collector with the appropriate
<TT>-D</tt><I>XXX</i><TT>-THREADS</tt> compilation
flag.  This has primarily two effects:
<OL>
<LI> It causes the garbage collector to stop all other threads when
it needs to see a consistent memory state.
<LI> It causes the collector to acquire a lock around essentially all
allocation and garbage collection activity.
</ol>
Since a single lock is used for all allocation-related activity, only one
thread can be allocating or collecting at one point.  This inherently
limits performance of multi-threaded applications on multiprocessors.
<P>
On most platforms, the allocator/collector lock is implemented as a
spin lock with exponential back-off.  Longer wait times are implemented
by yielding and/or sleeping.  If a collection is in progress, the pure
spinning stage is skipped.  This has the advantage that uncontested and
thus most uniprocessor lock acquisitions are very cheap.  It has the
disadvantage that the application may sleep for small periods of time
even when there is work to be done.  And threads may be unnecessarily
woken up for short periods.  Nonetheless, this scheme empirically
outperforms native queue-based mutual exclusion implementations in most
cases, sometimes drastically so.
<H2>Options for enhanced scalability</h2>
Version 6.0 of the collector adds two facilities to enhance collector
scalability on multiprocessors.  As of 6.0alpha1, these are supported 
only under Linux on X86 and IA64 processors, though ports to other
otherwise supported Pthreads platforms should be straightforward.
They are intended to be used together.
<UL>
<LI>
Building the collector with <TT>-DPARALLEL_MARK</tt> allows the collector to
run the mark phase in parallel in multiple threads, and thus on multiple
processors.  The mark phase typically consumes the large majority of the
collection time.  Thus this largely parallelizes the garbage collector
itself, though not the allocation process.  Currently the marking is
performed by the thread that triggered the collection, together with
<I>N</i>-1 dedicated
threads, where <I>N</i> is the number of processors detected by the collector.
The dedicated threads are created once at initialization time.
<P>
A second effect of this flag is to switch to a more concurrent
implementation of <TT>GC_malloc_many</tt>, so that free lists can be
built, and memory can be cleared, by more than one thread concurrently.
<LI>
Building the collector with -DTHREAD_LOCAL_ALLOC adds support for thread
local allocation.  It does not, by itself, cause thread local allocation
to be used.  It simply allows the use of the interface in 
<TT>gc_local_alloc.h</tt>.
<P>
Memory returned from thread-local allocators is completely interchangeable
with that returned by the standard allocators.  It may be used by other
threads.  The only difference is that, if the thread allocates enough
memory of a certain kind, it will build a thread-local free list for
objects of that kind, and allocate from that.  This greatly reduces
locking.  The thread-local free lists are refilled using 
<TT>GC_malloc_many</tt>.
<P>
An important side effect of this flag is to replace the default
spin-then-sleep lock to be replace by a spin-then-queue based implementation.
This <I>reduces performance</i> for the standard allocation functions,
though it usually improves performance when thread-local allocation is
used heavily, and thus the number of short-duration lock acquisitions
is greatly reduced.
</ul>
<P>
The easiest way to switch an application to thread-local allocation is to
<OL>
<LI> Define the macro <TT>GC_REDIRECT_TO_LOCAL</tt>,
and then include the <TT>gc.h</tt>
header in each client source file.
<LI> Invoke <TT>GC_thr_init()</tt> before any allocation.
<LI> Allocate using <TT>GC_MALLOC</tt>, <TT>GC_MALLOC_ATOMIC</tt>,
and/or <TT>GC_GCJ_MALLOC</tt>.
</ol>
<H2>The Parallel Marking Algorithm</h2>
We use an algorithm similar to
<A HREF="http://www.yl.is.s.u-tokyo.ac.jp/gc/">that developed by
Endo, Taura, and Yonezawa</a> at the University of Tokyo.
However, the data structures and implementation are different,
and represent a smaller change to the original collector source,
probably at the expense of extreme scalability.  Some of
the refinements they suggest, <I>e.g.</i> splitting large
objects, were also incorporated into out approach.
<P>
The global mark stack is transformed into a global work queue.
Unlike the usual case, it never shrinks during a mark phase.
The mark threads remove objects from the queue by copying them to a
local mark stack and changing the global descriptor to zero, indicating
that there is no more work to be done for this entry.
This removal
is done with no synchronization.  Thus it is possible for more than
one worker to remove the same entry, resulting in some work duplication.
<P>
The global work queue grows only if a marker thread decides to
return some of its local mark stack to the global one.  This
is done if the global queue appears to be running low, or if
the local stack is in danger of overflowing.  It does require
synchronization, but should be relatively rare.
<P>
The sequential marking code is reused to process local mark stacks.
Hence the amount of additional code required for parallel marking
is minimal.
<P>
It should be possible to use generational collection in the presence of the
parallel collector, by calling <TT>GC_enable_incremental()</tt>.
This does not result in fully incremental collection, since parallel mark
phases cannot currently be interrupted, and doing so may be too
expensive.
<P>
Gcj-style mark descriptors do not currently mix with the combination
of local allocation and incremental collection.  They should work correctly
with one or the other, but not both.
<P>
The number of marker threads is set on startup to the number of
available processors (or to the value of the <TT>GC_NPROCS</tt>
environment variable).  If only a single processor is detected,
parallel marking is disabled.
<P>
Note that setting GC_NPROCS to 1 also causes some lock acquisitions inside
the collector to immediately yield the processor instead of busy waiting
first.  In the case of a multiprocessor and a client with multiple
simultaneously runnable threads, this may have disastrous performance
consequences (e.g. a factor of 10 slowdown). 
<H2>Performance</h2>
We conducted some simple experiments with a version of
<A HREF="gc_bench.html">our GC benchmark</a> that was slightly modified to
run multiple concurrent client threads in the same address space.
Each client thread does the same work as the original benchmark, but they share
a heap.
This benchmark involves very little work outside of memory allocation.
This was run with GC 6.0alpha3 on a dual processor Pentium III/500 machine
under Linux 2.2.12.
<P>
Running with a thread-unsafe collector,  the benchmark ran in 9
seconds.  With the simple thread-safe collector,
built with <TT>-DLINUX_THREADS</tt>, the execution time
increased to 10.3 seconds, or 23.5 elapsed seconds with two clients.
(The times for the <TT>malloc</tt>/i<TT>free</tt> version
with glibc <TT>malloc</tt>
are 10.51 (standard library, pthreads not linked),
20.90 (one thread, pthreads linked),
and 24.55 seconds respectively. The benchmark favors a
garbage collector, since most objects are small.)
<P>
The following table gives execution times for the collector built
with parallel marking and thread-local allocation support
(<TT>-DGC_LINUX_THREADS -DPARALLEL_MARK -DTHREAD_LOCAL_ALLOC</tt>).  We tested
the client using either one or two marker threads, and running
one or two client threads.  Note that the client uses thread local
allocation exclusively.  With -DTHREAD_LOCAL_ALLOC the collector
switches to a locking strategy that is better tuned to less frequent
lock acquisition.  The standard allocation primitives thus peform
slightly worse than without -DTHREAD_LOCAL_ALLOC, and should be
avoided in time-critical code.
<P>
(The results using <TT>pthread_mutex_lock</tt>
directly for allocation locking would have been worse still, at
least for older versions of linuxthreads.
With THREAD_LOCAL_ALLOC, we first repeatedly try to acquire the
lock with pthread_mutex_try_lock(), busy_waiting between attempts.
After a fixed number of attempts, we use pthread_mutex_lock().)
<P>
These measurements do not use incremental collection, nor was prefetching
enabled in the marker.  We used the C version of the benchmark.
All measurements are in elapsed seconds on an unloaded machine.
<P>
<TABLE BORDER ALIGN="CENTER">
<TR><TH>Number of threads</th><TH>1 marker thread (secs.)</th>
<TH>2 marker threads (secs.)</th></tr>
<TR><TD>1 client</td><TD ALIGN="CENTER">10.45</td><TD ALIGN="CENTER">7.85</td>
<TR><TD>2 clients</td><TD ALIGN="CENTER">19.95</td><TD ALIGN="CENTER">12.3</td>
</table>
<PP>
The execution time for the single threaded case is slightly worse than with
simple locking.  However, even the single-threaded benchmark runs faster than
even the thread-unsafe version if a second processor is available.
The execution time for two clients with thread local allocation time is
only 1.4 times the sequential execution time for a single thread in a
thread-unsafe environment, even though it involves twice the client work.
That represents close to a
factor of 2 improvement over the 2 client case with the old collector.
The old collector clearly
still suffered from some contention overhead, in spite of the fact that the
locking scheme had been fairly well tuned.
<P>
Full linear speedup (i.e. the same execution time for 1 client on one
processor as 2 clients on 2 processors)
is probably not achievable on this kind of
hardware even with such a small number of processors,
since the memory system is
a major constraint for the garbage collector,
the processors usually share a single memory bus, and thus
the aggregate memory bandwidth does not increase in
proportion to the number of processors. 
<P>
These results are likely to be very sensitive to both hardware and OS
issues.  Preliminary experiments with an older Pentium Pro machine running
an older kernel were far less encouraging.

</body>
</html>
Commit	Line	Data
7c673cae FG	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. 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>