Path: utzoo!attcan!uunet!lll-winken!sun-barr!decwrl!shelby!neon!carcoar!wilson From: wilson@carcoar.Stanford.EDU (Paul Wilson) Newsgroups: comp.object Subject: Re: Garbage collection -- difficulty, cost, generality Summary: interpreters flatter gc's Message-ID: <1990Mar19.181029.14823@Neon.Stanford.EDU> Date: 19 Mar 90 18:10:29 GMT References: <1990Mar13.011146.6019@Neon.Stanford.EDU> <2356@syma.sussex.ac.uk> <4836@vanuata.cs.glasgow.ac.uk> <1990Mar15.232035.147@Neon.Stanford.EDU> <4862@vanuata.cs.glasgow.ac.uk> Sender: news@Neon.Stanford.EDU (USENET News System) Reply-To: wilson@carcoar.Stanford.EDU (Paul Wilson) Organization: U. of Illinois at Chicago (UIC, *not* UofC or UIUC) Lines: 121 In article <4862@vanuata.cs.glasgow.ac.uk> jack@cs.glasgow.ac.uk (Jack Campin) writes: > >wilson@carcoar.Stanford.EDU (Paul Wilson) wrote: >> jack@cs.glasgow.ac.uk (Jack Campin) writes: >>> aarons@syma.sussex.ac.uk (Aaron Sloman) wrote: >>>> wilson@carcoar.Stanford.EDU (Paul Wilson) writes: >>>>> Don't expect a fast language on stock hardware to have gc speed costs of >>>>> less than about 10% on average. >>>> [Poplog] varied between 1.5% and 3.2%. >>> PS-algol uses about 2.9% according to some measurements done a couple of >>> years ago. > >> Questions: > >> 1) how fast is PS-Algol, flat out? Less-than-great code quality can >> flatter gc performance. > >Very fast for an interpreted language. Much better than any Smalltalk I've >seen (Smalltalk is probably the closest familiar programming environment). Okay, that makes sense. Not to demean either Smalltalk or PS-Algol (two languages I like a lot), but this doesn't sound really fast, by my standards. I'm thinking of things like T (the object-oriented extended Scheme from Yale) and commercial Common Lisps, which have optimizing native-code compilers. (Though I'm actually unclear on current CL speeds.) Self seems to be approaching this kind of performance, and the techniques involved should work at least as well for future-generation Smalltalks. And the fast implementations should get even faster over time. GC's will have to keep up. I'd guess that if your worked at it, a good native-code compiled PS-Algol would run several times as fast, and your gc costs, as a percentage of run time, would be several times higher. This may or may not be a big issue for PS-Algol, depending on whether typical applications are compute- bound or I/O bound. >There is a much faster native-code-generated version used by ICL on their >mainframes; I don't have any performance figures on this (that I can give >out, anyway). Maybe comparable to a good interpreted Lisp, but that's >guesswork. I wasn't surprised that Poplog led to similar figures on >something; anyone got a nice closure-bashing benchmark that we could try >in Smalltalk, Scheme, Poplog and PS-algol to firm this up a bit? There's a closure-intensive benchmark or two in the appendix to David Kranz' thesis on Orbit (the T Compiler) from Yale. I don't know whether that's the right thing to test, though. It's hard to come up with a fair closure benchmark that will work across languages. In some languages you might use closures in certain situations, but in others you might not, even if they're available. For example, in vanilla Scheme (or PS-Algol) you might use closures to implement objects (which can get you in trouble performance-wise -- there's another subtle interaction with generational gc's). But in T, a full object system is provided, so you'd use that instead. >> 2) what kind of gc was used? > >Sliding compaction; Deutsch-Schorr-Waite or Morris, I forget which. I take it this is not a generational gc, though you're probably treating the persistent store as a kind of separate entity. Also, for programs with a lot of live data at gc time, sliding compaction, etc., can be pretty slow -- several passes over the data. > Later >versions add a feature that makes a big difference: sometimes treating >read-only persistent objects as garbage (you can always get them back from >disk later if this is wrong). This can reduce heap size drastically. That seems very reasonable. >> 3) what kind of programs were used for testing? > >Recompiling the compiler. Depending on your compiler, this may or may not be a reasonable test. For our bytecode compiler, our generational gc is extremely effective. If hte first generation is of reasonable size, nothing except the actual generated code (and associated data structures like literal frames) survives to be advanced out of the first generation. When the compiler starts compiling modules instead of just independent procedures, we expect the copying costs to go up significantly. (At a gc, we'll typically have some intermediate data structures of a whole module to copy, as well as those involved in compiling a single procedure.) Further in this direction is Lucid's Common Lisp compiler, which may have a *megabyte* of inter- procedural analysis goop lying around when doing an optimized system build. For that kind of "serious" stuff you'd want a serious generational gc. >> 4) did this involve persistent objects? > >Yes, but that doesn't make much difference to in-core gc, except for the >point mentioned in 2). The garbage collector only needs to test bit 31 of >a 4-byte address to tell persistent and virtual-memory pointers apart. >Persistent storage garbage collection is a different kettle of ballgames. >Time for a lunchbreak with our persistent store (~100 MB of data, gc >running on fast Suns). Only done every few weeks. I seem to recall that PS-Algol used to have a rather strange allocation/gc scheme, with objects allocated in areas by type for locality reasons. Were any locality effects ever measured? (Also, I seem to recall someone saying that there was a possibility of storage leaks in the P-store, under certain circumstances, or something like that. Is the same scheme in use, or has it been modified?) >-- >-- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank >Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home >JANET: jack@cs.glasgow.ac.uk BANG!net: via mcvax and ukc FAX: 041 330 4913 >INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp -- Paul Paul R. Wilson Software Systems Laboratory lab ph.: (312) 996-9216 U. of Illin. at C. EECS Dept. (M/C 154) wilson@bert.eecs.uic.edu Box 4348 Chicago,IL 60680 Paul R. Wilson Software Systems Laboratory lab ph.: (312) 996-9216 U. of Illin. at C. EECS Dept. (M/C 154) wilson@bert.eecs.uic.edu Box 4348 Chicago,IL 60680