Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[jsa@alexandria (Jon S Anthony)]

In article <dewar.846422447@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Someone (I lost track) gave as an advantage of garbage collection:
> 
> >    > Pro: ...
> >    >  Faster - allocations can be _much_ faster and collections can be
> >    >  much more efficient than good ol' "free".

That would be me...


> I agree on the allocation, but the free claim is dubious, it depends on
> a lot of factors. A true GC, as opposed to a conservative GC, can be
> made to run in time proportional to the amount of non-garbage (see for
> example the description of the SPITBOL collector in SP&E 1977 article
> by Dewar and McCann), so if you have a LOT of garbage this can be true.

Actually, you can do much better in practice if you use a generational
scheme (where you don't waste time on stuff that will typically not
become garbage).  So, even if you don't have a lot of garbage, and
have a lot of non-garbage, this can be true (it really depends more on
how much "quickly [but not instantly] dying" things you generate - not
the total amount of non-dying things...)


> But if you are doing lots of GC's then you can end up spending a lot of
> time freeing a little stuff (ttrue of conservative GC as well of course).

This is not particularly accurate in the context of generational
schemes.


> On the other hand, it is quite possible to make free quite efficient.
> I wrote the collector for the x86 Alsys compiler (I don't know if the
> TSP ObjectAda still uses it or not), and it had the property that
> free was a single instruction that was generated in line.

Well, 1) I used "can" specifically because I didn't want to assert
"are".  2) If you never need to collect, you will not even execute 1
instruction the entire run (let alone 1 for each free).  3) You can
write such very efficient "free"s even within the language - just roll
your own allocator (which is what I believe happens in real-time
contexts actually requiring "heap" style allocation).  4) we were not
talking about these sort of special "free"s...

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com