gc for interactive apps
Tom Lord
I have long wanted to get around to building an incremental GC with
decent latency guarantees (presuming sufficient physical memory). The
performance goal here is for decent GUI interaction -- not anything
more tense than that.
The approach that makes sense to me intuitively is some form of
incremental mark&sweep.
So I have some questions:
1) Is my intuition correct that mark-n-sweep displays decent
locality? After all, allocation is most always from
roughly sequentually allocated memory unless and until the
process' live data exhibits complete entropy. Is it worth
the trouble to detect and exclude from allocation sparse
pages?
2) Do I want to amortize incremental foo with allocations?
or do I want to try to run GC in a separate thread?
Unfortunately, I can't think of anyone who might be able to answer
from experience. There's a ton o' interesting GC research.
There's GUI experience on fairly exotic hardware or on the old
smalltalk image. Aside from that:
3) Who's been in this space already? (Aside from GNU Emacs
and siblings which don't display GC behavior I'd care to
emulate).
When I say "gui", I'm using a short-hand, of course. Any app interacting
with users in human-scale real-time and crunching a lot of lisp code...
-t
Jeremy H. Brown
for automatic dynamic memory management" by Jones and Lin; see
http://www.cs.ukc.ac.uk/people/staff/rej/gc.html#Book
As a survey work, it summarizes work pertaining to most, if not all,
of your questions.
> 1) Is my intuition correct that mark-n-sweep displays decent
> locality? After all, allocation is most always from
> roughly sequentually allocated memory unless and until the
> process' live data exhibits complete entropy. Is it worth
> the trouble to detect and exclude from allocation sparse
> pages?
In addition to the Jones and Lin book, check out this paper by Dave Moon:
http://portal.acm.org/citation.cfm?id=802040&dl=ACM&coll=portal
Although it is talking about GC in the context of specialized hardware
(the Symbolics lisp machines), part of the discussion is about
implementing a copying GC that preserves locality. (It's also just
flat out one of my favorite papers --- very clear and well written.)
> 2) Do I want to amortize incremental foo with allocations?
> or do I want to try to run GC in a separate thread?
Both have advantages. Amortizing GC as part of allocation makes for
better realtime behavior --- as a programmer, you know that allocation
costs, and if you avoid it, you don't pay cycles for GC. On the other
hand, if you can put GC in another thread, it can exploit idle cycles
more effectively. The Symbolics machines used some of both; see above
paper, again.
> 3) Who's been in this space already? (Aside from GNU Emacs
> and siblings which don't display GC behavior I'd care to
> emulate).
Once again, I'd say Symbolics. Also maybe Sobalvarro's paper, "A
Lifetime-based Garbage Collector for LISP Systems on General-Purpose
Computers", at
ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1417.ps.Z
There's actually been a ton of research on incremental, background,
etc. GC, so this isn't even the tip of the iceberg, really...
Jeremy
Anton van Straaten
The GC FAQ: http://www.iecc.com/gclist/GC-faq.html
And of course c.l.s.'s own Will Clinger:
http://www.ccs.neu.edu/home/will/GC/index.html, whose radioactive decay gc
model is worth a look. It's not necessarily incremental, afaik, but it may
be more efficient.
And a bibliography categorized by technique:
http://www.memorymanagement.org/bib/gc.html
> I have long wanted to get around to building an incremental GC with
> decent latency guarantees (presuming sufficient physical memory). The
> performance goal here is for decent GUI interaction -- not anything
> more tense than that.
If you can get past the slave connotations :), Java VMs seem able to meet
this requirement, so you might look into the gc systems they use. I have no
idea how "incremental" they actually are, but Java IDEs that are implemented
in Java (e.g. Eclipse, NetBeans) can have rather large memory footprints
(10-50MB), and for the most part, gc is not noticeable when using them. I
work with Eclipse, and very occasionally, in long-running sessions, there's
a noticeable pause which I assume is due to gc. This seems quite acceptable
for an IDE, but obviously could be a problem for something with more
stringent real time requirements.
There's an overview of Java gc systems here:
http://gcc.gnu.org/java/papers/nosb.html
which also appeared in Dr.Dobbs:
http://www.ddj.com/documents/s=915/ddj9810a/9810a.html
> Unfortunately, I can't think of anyone who might be able to answer
> from experience. There's a ton o' interesting GC research.
> There's GUI experience on fairly exotic hardware or on the old
> smalltalk image. Aside from that:
>
> 3) Who's been in this space already?
Some commercial companies have been in this space. I once did a bit of
conversion work on what was billed as an incremental generation-scavenging
collector, which worked very well, for user applications with 2-4MB memory
footprints (not the upper limit of possibility, just typical of the apps in
question). However, I'm guessing you're interested in examples you can
borrow strategies from, i.e. open source, academic etc.?
Anton
Jeffrey Siegal
> 3) Who's been in this space already? (Aside from GNU Emacs
> and siblings which don't display GC behavior I'd care to
> emulate).
Java
David Rush
> 1) Is my intuition correct that mark-n-sweep displays decent
> locality?
My read of the literature seems to indicate anything you want to read
into it. Really. A *lot* depends on a particular applications
allocation behavior. Most papers seem to handwavingly theorize about
locality. I don't think anyone has actually collected enough data to
draw direct conclusions.
I may well be wrong, and my knowledge is rapidly getting out of date,
but then again this is usenet.
> 2) Do I want to amortize incremental foo with allocations?
> or do I want to try to run GC in a separate thread?
Again from the lit, there seems to be more published on separate GC
threads than on incremental algorithms. YMMV. You could probably
publish your results, either way.
> Unfortunately, I can't think of anyone who might be able to answer
> from experience. There's a ton o' interesting GC research.
Me neither. This is definitely on my RSN list, you know?
david rush
--
It is easier to introduce new complications than to resolve the old ones.
-- Neal Stephenson, in _Cryptognomicon_
William D Clinger
> I have long wanted to get around to building an incremental GC with
> decent latency guarantees (presuming sufficient physical memory). The
> performance goal here is for decent GUI interaction -- not anything
> more tense than that.
>
> The approach that makes sense to me intuitively is some form of
> incremental mark&sweep.
Okay. There's a large literature on that dating back to the 1960s.
You should be aware that incremental mark&sweep algorithms generally
give up a large constant factor in performance compared to modern
generational algorithms.
> 1) Is my intuition correct that mark-n-sweep displays decent
> locality?
Maybe. Incremental algorithms may have worse locality than
non-incremental, though, since they compete with the mutator for
cache.
> Is it worth
> the trouble to detect and exclude from allocation sparse
> pages?
That depends on what you mean by sparse. If you're allocating
from free lists, then it probably doesn't matter much unless your
application is actually paging, which means you're losing anyway.
If you're allocating from contiguous regions of memory, then you
probably want to use a compacting collector at least occasionally,
in which case you might as well allocate from empty pages. So I'm
not sure what you mean here.
> 2) Do I want to amortize incremental foo with allocations?
> or do I want to try to run GC in a separate thread?
Yes: either way, and you might even consider doing both. (E.g. see
our paper on concurrent refinement of remembered sets, presented at
this year's Usenix JVM conference.)
> 3) Who's been in this space already?
As has already been said: Java. Also Smalltalk. Also Common Lisp.
In the Scheme world, I believe Chez Scheme and Larceny have the best
garbage collectors, hands down, but both are generational, not
incremental. Nonetheless they would be adequate for most interactive
applications.
For some real data on garbage collection in the Scheme world, see
http://www.ccs.neu.edu/home/will/GC/ and read the three papers
listed in the references.
Will
Thant Tessman
[...]
> In the Scheme world, I believe Chez Scheme and Larceny have the best
> garbage collectors, hands down, but both are generational, not
> incremental. Nonetheless they would be adequate for most interactive
> applications.
When I used Chez Scheme as the scripting language for a real-time VR
implementation, the effects of GC were unnoticeable. Granted we
programmed in a style that tried to avoid making garbage, and the app
didn't spend a huge portion of its time in the Scheme side of things,
but when I say GC was unnoticeable, I mean it was completely
unnoticeable. And this was a 60-frames-a-second application.
-thant
William D Clinger
> but when I say GC was unnoticeable, I mean it was completely
> unnoticeable. And this was a 60-frames-a-second application.
Oh, yes. Apps like that tend to generate a lot of objects that
die within 17 msec. Let's model this with a tight loop that
repeatedly reverses a 125-element list (usually 1000 bytes).
On a 450 MHz SPARC, Larceny will cons more than 300 Mby per
second and will collect more than 300 times per second, but
each collection takes less than a millisecond, so less than
25% of the total execution time is spent in the collector.
(By the way, the mutator time for this benchmark works out
to 10 clock cycles per cons. That's for a REVERSE written
in Scheme and compiled directly to native code.)
MzScheme v100 conses o little over 20 Mby per second (using
the built-in REVERSE, which is hand-coded in C), and spends
over half its time in the collector. For this (admittedly
unrealistic) benchmark, the MzScheme collector is over 30
times as slow as Larceny's generational collector, and its
latency is hundreds or even thousands of times as bad as
Larceny's. (BTW, after subtracting the gc time, we find
that MzScheme's hand-coded C is about 10 times as slow as
Larceny's compiled Scheme.)
I'll provide the source code below so people can use this as
a reality check for their collectors. For more realistic
gc benchmarks, see http://www.ccs.neu.edu/home/will/GC/ .
Will
; Calls f on x, n times.
(define (call-n-times n f x)
(if (zero? n)
'done
(begin (f x)
(call-n-times (- n 1) f x))))
(define (reverse-benchmark megabytes)
(define (reverse1 x)
(define (loop x y)
(if (null? x)
y
(loop (cdr x)
(cons (car x) y))))
(loop x '()))
(let ((n (quotient (* (expt 2 20) megabytes)
1000))
(x (vector->list (make-vector 125 0)))
(mby (number->string megabytes)))
; Use the library version of reverse.
(run-benchmark (string-append "reverse:" mby)
(lambda () (call-n-times n reverse x)))
; Use the local version of reverse, above.
(run-benchmark (string-append "reverse1:" mby)
(lambda () (call-n-times n reverse1 x)))
n))
Hans-J. Boehm
news:b84e9a9f.0210...@posting.google.com...
> On a 450 MHz SPARC, Larceny will cons more than 300 Mby per
> second and will collect more than 300 times per second, but
> each collection takes less than a millisecond, so less than
> 25% of the total execution time is spent in the collector.
> (By the way, the mutator time for this benchmark works out
> to 10 clock cycles per cons. That's for a REVERSE written
> in Scheme and compiled directly to native code.)
>
> MzScheme v100 conses o little over 20 Mby per second (using
> the built-in REVERSE, which is hand-coded in C), and spends
> over half its time in the collector. For this (admittedly
> unrealistic) benchmark, the MzScheme collector is over 30
> times as slow as Larceny's generational collector, and its
> latency is hundreds or even thousands of times as bad as
> Larceny's. (BTW, after subtracting the gc time, we find
> that MzScheme's hand-coded C is about 10 times as slow as
> Larceny's compiled Scheme.)
Will -
It would be worth trying to understand this a little bit more. I tried this
on a 266MHz PII (512K cache) with an approximate C equivalent of your
benchmark, and a current version of my collector. By your metric, I also
get roughly 21.6MB/sec cons rate. (I built the collector so that 8 byte
cons cells are really 8 bytes.) That's also distributed into 360
collections per second. If I increase the heap size from the default 64K to
1 MB, that goes up to 31 MB/sec. The top two routines in the profile are:
1) The allocation routine which removes an entry from a free list (30%,
could be reduced by inlining, etc.)
2) The routine that builds the free list in a page by writing zeros and
pointers in a tight loop (23%)
On this same machine, a simple gcc compiled loop that just initializes 1MB
of memory a word at a time has a throughput of about 122MB/sec. Thus I
claim you're unlikely to exceed 122MB/sec cons rate on my machine, unless
you manage to stay within the cache, which doesn't seem likely for real
applications. This seems to suggest that either:
- MzScheme could do something better, or
- There's a large architecture dependency here.
Hans
William D Clinger
> It would be worth trying to understand this a little bit more. I tried this
> on a 266MHz PII (512K cache) with an approximate C equivalent of your
> benchmark, and a current version of my collector. By your metric, I also
> get roughly 21.6MB/sec cons rate. (I built the collector so that 8 byte
> cons cells are really 8 bytes.) That's also distributed into 360
> collections per second. If I increase the heap size from the default 64K to
> 1 MB, that goes up to 31 MB/sec. The top two routines in the profile are:
>
> 1) The allocation routine which removes an entry from a free list (30%,
> could be reduced by inlining, etc.)
> 2) The routine that builds the free list in a page by writing zeros and
> pointers in a tight loop (23%)
This just points out the importance of fast allocation for
allocation-intensive programs. Your profiling shows that over
half of the time is spent doing things that Larceny doesn't
have to do. Here is the (inlined) SPARC code for the cons
operation in that benchmark, as implemented in Larceny:
76 add %etop, 8, %etop
80 subcc %etop, %stkp, %g0
84 ble,a #100
88 st %r6, [ %etop - 8 ]
92 jmpl %globals + 1040, %o7 ! morecore
96 add %o7, -24, %o7
100 st %r2, [ %etop - 4 ]
104 sub %etop, 7, %r2
That's just 6 dynamic instructions. (Instructions 92 and 96
are rarely executed. When they are executed, they trigger a
garbage collection.)
> On this same machine, a simple gcc compiled loop that just initializes 1MB
> of memory a word at a time has a throughput of about 122MB/sec. Thus I
> claim you're unlikely to exceed 122MB/sec cons rate on my machine,
That sounds about right to me. On my machine, the benchmark
I gave stays entirely within the 4 Mby L2 cache---I wrote it
to derive an upper bound on allocator/gc performance, not to
estimate typical performance. Your machine has only a 512K
cache, and its clock speed is about 60% the clock speed of my
machine, so it shouldn't be surprising that my machine is over
two and a half times as fast as yours for that loop.
> unless
> you manage to stay within the cache, which doesn't seem likely for real
> applications.
Actually, I think there are quite a few real applications
that rarely miss the cache. For example, I know that my
Scheme compiler's live storage rarely exceeds 4 Mby.
> This seems to suggest that either:
>
> - MzScheme could do something better, or
>
> - There's a large architecture dependency here.
Actually, your numbers show that MzScheme can't do much better
unless it changes the allocator, and your analysis shows that
it can't improve the allocator much without changing the
garbage collector.
I agree with the architecture dependency. Big caches rule.
Will
Jeffrey Siegal
Did you mean Larceny here? Above, MzScheme is reported at 20 MB/sec.
> - There's a large architecture dependency here.
This is probably the case. My vague recollection from that era was that
SPARCs had much better memory bandwidth. Possibly bigger cache as well.
Hans-J. Boehm
> Hans-J. Boehm wrote:
> > 1) The allocation routine which removes an entry from a free list (30%,
> > could be reduced by inlining, etc.)
> > 2) The routine that builds the free list in a page by writing zeros and
> > pointers in a tight loop (23%)
>
> This just points out the importance of fast allocation for
> allocation-intensive programs. Your profiling shows that over
> half of the time is spent doing things that Larceny doesn't
> have to do.
> That's just 6 dynamic instructions.
seen, instructions are often the wrong thing to count, though.
Especially with suboptimal scheduling, such as what's usually done by
gcc, memory references, even L2 or L3 cache hits, usually seem to be
the real issue. In the PII/266 case, the most of the time seems to go
into a few store instructions (see below).
Fundamentally, you have the advantage that you're touching memory only
once, whereas our collector/allocator touches it twice. In the PII/266
case, the various store instructions account for the Lion's share of
the cost, presumably because the processor's write buffer fills up.
If the heap doesn't fit in the cache, this difference largely
disappears, since much of the cost comes from the initial store to
each cache line. In our case, the second set of stores is then
relatively cheap, since the line is nearly certain to still be in at
least L2 cache.
Another difference that's hard to factor out here is that you
presumably control the calling convention, and hence can keep the
allocation and limit pointers in registers. Our standard allocator
has to completely reload the analogous state from global locations.
>
> > On this same machine, a simple gcc compiled loop that just initializes 1MB
> > of memory a word at a time has a throughput of about 122MB/sec. Thus I
> > claim you're unlikely to exceed 122MB/sec cons rate on my machine,
>
> That sounds about right to me. On my machine, the benchmark
> I gave stays entirely within the 4 Mby L2 cache---I wrote it
> to derive an upper bound on allocator/gc performance, not to
> estimate typical performance. Your machine has only a 512K
> cache, and its clock speed is about 60% the clock speed of my
> machine, so it shouldn't be surprising that my machine is over
> two and a half times as fast as yours for that loop.
Right. But if we assume that this is only an allocation/collection
issue, then my machine is faster in terms of cons rate for our
allocator. This is what makes me suspicious that MzScheme could do
better.
>
> > unless
> > you manage to stay within the cache, which doesn't seem likely for real
> > applications.
>
> Actually, I think there are quite a few real applications
> that rarely miss the cache. For example, I know that my
> Scheme compiler's live storage rarely exceeds 4 Mby.
I agree that it depends on the application. But everything I've heard
suggests that large Java web applications, for example, are generally
run with even the nursery much larger than the cache. That also seems
to be true for SPECjbb, eventhough the application is not that huge
(Sun's most recent 8 processor run uses a fixed 3.9GB heap, much of
which seems to be in the nursery. The other vendor results are
generally similar.)
>
> > This seems to suggest that either:
> >
> > - MzScheme could do something better, or
> >
> > - There's a large architecture dependency here.
>
> Actually, your numbers show that MzScheme can't do much better
> unless it changes the allocator, and your analysis shows that
> it can't improve the allocator much without changing the
> garbage collector.
My interpretation is that MzScheme can probably do significantly
better, though it probably would not be able get to closer than a
factor of two to Larceny on this benchmark.
I tried the experiment again, using the GC_CONS macro provided in the
collector distribution, and inlining the cons function. (This is a
bit ugly in terms of binary compatibility issues, since it potentially
introduces GC version dependencies into .o files. But that seems to
be par for the course here.)
In that case I get slightly over 60MB/sec on the Pentium II/266 with a
300KB heap, which should fit entirely into the 512K L2 cache. This is
for the C version of your benchmark. If I rerun my "clear memory"
test entirely in L2 cache, it manages about 180MB/sec. That implies
that at most a factor of 3 improvement is possible on this machine.
And a nonnegligible portion of the execution time has nothing to do
with cons, so that seem to be optimistic.
(Remember this is an ancient machine. The numbers on Itanium2/1GHz are
700 MB/sec conses with GC_CONS (300KB heap, 3MB L3 cache) about
5GB/sec for the naive fill operation. That's with 8 byte pointers and
16 byte cons cells. There appears to be more headroom there, but I
also suspect it would be hard for Larceny to get close to the fill
rate here.)
Hans
William D Clinger
> I agree that it depends on the application. But everything I've heard
> suggests that large Java web applications, for example, are generally
> run with even the nursery much larger than the cache. That also seems
> to be true for SPECjbb, even though the application is not that huge
> (Sun's most recent 8 processor run uses a fixed 3.9GB heap, much of
> which seems to be in the nursery. The other vendor results are
> generally similar.)
We talked about this in Pittsburgh, but I'll repeat my response for
the newsgroup. I think these enormous nurseries are a way for users
to cope with a mismatch between the application and younger-first
generational garbage collection. Increasing the nursery size of a
conventional 3-generational younger-first collector makes it behave
a little more like Larceny's 3ROF collector.
By the way, the numbers I posted for Larceny were for the default
3-generational younger-first collector, but the 2YF and 3ROF
collectors would have performed the same on that benchmark.
Will
Anton van Straaten
> I think these enormous nurseries are a way for users
> to cope with a mismatch between the application and younger-first
> generational garbage collection. Increasing the nursery size of a
> conventional 3-generational younger-first collector makes it behave
> a little more like Larceny's 3ROF collector.
Mightn't these large nurseries, and younger-first collection, actually be
appropriate for many Java database web apps? With these apps, developers
often try hard to make sure that most objects are short-lived, and don't
survive beyond a single HTTP transaction. The exceptions would be "session"
objects which in many cases, don't really contain much information. Since
there's only one such object per active user, the total population of
session objects and the objects they refer to should be quite small. It
seems like this pattern would result in enormous nurseries and tiny older
generations.
A major exception to the above would be when objects are cached by Java
between transactions. Not all web apps do this, though.
Anton
Sander Vesik
> Will Clinger wrote:
>> I think these enormous nurseries are a way for users
>> to cope with a mismatch between the application and younger-first
>> generational garbage collection. Increasing the nursery size of a
>> conventional 3-generational younger-first collector makes it behave
>> a little more like Larceny's 3ROF collector.
>
> Mightn't these large nurseries, and younger-first collection, actually be
> appropriate for many Java database web apps? With these apps, developers
> often try hard to make sure that most objects are short-lived, and don't
> survive beyond a single HTTP transaction. The exceptions would be "session"
> objects which in many cases, don't really contain much information. Since
> there's only one such object per active user, the total population of
> session objects and the objects they refer to should be quite small. It
> seems like this pattern would result in enormous nurseries and tiny older
> generations.
It could also be benchmarketing to an extent - figure out the optimal
sizes for this benchmark and then use them. Its nottotally a bad thing
as peopel using it in real life can do the same optimisation in principle.
>
> A major exception to the above would be when objects are cached by Java
> between transactions. Not all web apps do this, though.
>
> Anton
>
>
>
--
Sander
+++ Out of cheese error +++
William D Clinger
> Mightn't these large nurseries, and younger-first collection, actually be
> appropriate for many Java database web apps? With these apps, developers
> often try hard to make sure that most objects are short-lived, and don't
> survive beyond a single HTTP transaction. The exceptions would be "session"
> objects which in many cases, don't really contain much information. Since
> there's only one such object per active user, the total population of
> session objects and the objects they refer to should be quite small.
For this kind of app, I think a 4ROF collector would work pretty well.
The gcold benchmark was written to resemble a web app that behaves much as
you describe, except that it has a large, slowly mutating database in-heap.
Larceny's 3ROF collector trounces Larceny's 2YF and 3YF collectors on the
gcold benchmark.
By the way, Larceny's non-generational stop-and-copy collector trounces
Larceny's 3ROF collector on the gcold benchmark, but only when the heap
is large compared to the peak live data. (That is, only when the inverse
load factor is large.)
So a simpler conclusion is that the Java community's widespread use of
enormous nurseries probably reflects the existence of many important
applications for which, at high inverse load factors, non-generational
stop-and-copy collection performs better than non-generational mark and
sweep or conventional younger-first generational collectors.
Most of my recent research on garbage collection can be seen as attempts
to design practical generational collectors that work well when the
long-lived objects have the kind of queue-like lifetimes that are common
in web apps and many other server-like applications.
Will