Re: Ada GC (was about Java VM)

Dave Lloyd <dave@occl-cam.demon.co.uk> writes:


>But more importantly, Ada is type-secure
>and so a well-optimised GC can be incorporated --- in stark contrast
>to the inefficient conservative GCs bolted onto C (or worse,
>reference-counting GCs on a C subset). It is vital for a good
>mark-and-sweep or generational copying GC to know the types of all
>valid storage and the kernel set of pointers (the identifiers on the
>stack in A68/Ada/F90, the symbol bindings in Lisp).


The tradeoffs aren't that simple.


Zhong Shao and I spent some time trying to infer type information from
C programs to speed up those "inefficient" conservative collectors for
C. Our collector now has hooks to supply the type information
explicitly. But the automatic inference part of this never made it
into the standard collector version. And as far as I know nobody has
used what is there. The basic reason is that it doesn't help very
much, even after careful tweaking of the associated collector code.
You do get a benefit from limiting the statically allocated memory
scanned by the collector, and from informing the collector of objects
which are entirely pointerfree. Type information beyond that seems to
be less valuable.


The basic reason for this is that most nonpointers are conspicuously
not pointers, and can be dismissed by a conservative collector in at
most 5 instructions or so. That's comparable to the amount of time
required by a nonconservative collector to decide not to scan a field.


Based on measurements by Vincent Delacour, type information would help
more if you could also know that non-nil pointers always point to the
garbage collected heap (as might be true in an Ada implementation).
But this isn't free. It typically forces significant numbers of
constants, etc. to be copied to the heap, solely to preserve this
invariant. If you're not really careful, this doesn't do anything
good to your working set size. It also increases the number of
essentially permanent objects that your collector has to deal with in
the heap. I don't know whether it's a net performance win or loss.
(I would guess it loses if you're close to the paging threshold, and
wins otherwise. It's basically a time-space tradeoff.)


Type information also allows you to use a copying collector for young
objects, thus greatly decreasing the cost of allocating many
short-lived objects in languages with few updates of existing objects.
There is some evidence that it might also help some for languages with
C or Ada allocation behavior. But I don't think that case is
completely convincing yet.


Of course, type-secure languages have other substantial advantages,
and I'm all in favor of languages with at least a type-safe core. But
(expected case) GC performance seems to be a more subtle issue.


And one more nit: Ada is type secure only in the absence of explicit
deallocation.


Hans-J. Boehm
(boehm@parc.xerox.com)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.