Subject: Re: Python and Lisp Test
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 31 Dec 2005 04:58:04 -0600
Newsgroups: comp.lang.lisp
Message-ID: <asGdnYgrw-yh-SvenZ2dnUVZ_tmdnZ2d@speakeasy.net>
Marcin 'Qrczak' Kowalczyk  <qrczak@knm.org.pl> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) writes:
| > That sounds really small to me. The literature I've read on generational
| > GCs with a "nursery" [e.g., Ungar, Appel, or especially Wilson et al...]
| > <http://www.cs.utexas.edu/users/oops/papers.html#caching-gen-gc>]
| > [suggests] making the nursery be roughly the size of the CPU's secondary
| > cache [but not larger].
| 
| I have 256kB of cache. While in this non-natural program increasing
| the young heap size helps (256kB is best), a more realistic program
| (a compiler compiling itself; actually 23 invocations, one for each
| module) is fastest with the young heap of 64kB: [results elided]
+---------------

Very interesting.  On the other hand, your results for each run
vary only 4-5% over the *very* wide range of nursery sizes. I'd
expect to see *much* larger variations [even if the minima were
at nursery sizes oter than I would expect], so I'm wondering if
the bottleneck is somewhere else entirely other than the GC or
cache pressure.

+---------------
| I doubt it should be made exactly the cache size. Since the program
| doesn't exclusively access objects it has just allocated, assuming
| some LRU policy most parts of the nursery would be wiped out of the
| cache just before they are read back during a GC.
+---------------

You have a point, but the optimal size probably depends very much
on the size and type of cache. I would expect to see direct-mapped
caches behave very differently than 2- or 4-way set-associative caches.
For the latter, I'd expect nurseries below 1/2 the cache size to
cause almost *no* thrashing with older objects. And for the direct-
mapped case, if the basic generational assumption is correct, even
with the nursery size as large as the cache size there should be
much less thrashing than you might think, since -- again, assuming
most new objects die very young -- at any point in time very little
of the nursery actually constains "live" objects.

+---------------
| > Also, be sure you keep the nursery in a fixed location...
| 
| It is kept in the same location...
+---------------

O.k., just checking...  ;-}  ;-}

+---------------
| (unless a single object to be allocated is larger; external memory
| like bignum digits and array contents doesn't count).
+---------------

Yes, of course. A lot of the papers I've read on nursery schemes
suggest not allocating "large" objects in the nursery at all
[where "large" is 1/64th to 1/8th the size of the nursery or more.]


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607