Re: Interview with Alan Kay

From: Duane Rettig (duane_at_franz.com)
Date: 02/27/05 

Date: 27 Feb 2005 00:54:17 -0800

Dave Roberts <dave-remove@remove-findinglisp.com> writes:

> Duane Rettig <duane@franz.com> writes:

> > For GC support, the real problem to solve is fast forwarding of
> > pointers that have moved.
>
> If you could design GC from scratch, would you do a copying collector?
> They are popular with current systems, particularly generational GC
> systems, but there is clearly overhead there.

Well, Generational GCs are not garbage collectors, they are actually
garbage _leavers_. They collect live data, and leave the garbage.
They work efficiently because of the actual tendency of most garbage
to become unreferenced early in its lifetime. Therefore, a higher
percentage of garbage is present in a first generation than in any
successive generation, and thus collecting the live data is going
to be more efficient than collecting the garbage and leaving the
live data uncopied. [Another nicety of collecting live data is that
the "marking" of the data a live no longer needs a bit to be set
for that data; if the data has moved, then that also becomes the
indicator that the data is live.] Once the number of generations
is high enough, it no longer is as useful to collect data, and
perhaps it becomes less efficient to continue to move live data
around at that time (though it is still easier to identify live
data than dead, so live-data-collection might still be worthwhile
even in older generations, though there are these tradeoffs). So
yes, when I talk about forwarding, I am assuming a copying portion
of a garbage collector, probably in a very young generation.

> > Traps being as expensive as they are,
> > it might be worthwhile to allow for a mechanism within the MMU itself,
> > along with data fetching hardware, to allow pages to be set up to
> > automatically be forwarded _without_ entering a trap.
>
> Could you do this at page granularity? Most of the copying GCs I have
> seen make this a per-object forwarding.

Per-object is mandatory. It is a question of how the forwarding can
be set up. If a simple trap per-page can be made (which is easy to
do; simply set up the page without read or write access, and when a
read or a write is done, then a trap occurs) then software in the trap
handler can look up current forwards in tables in order to know (per
object) where the forwarded address is. So at the trap level, it
would be per page, but as far as the application is concerned, it is
just referencing an address and is getting its current location,
regardless of where that is.

If the MMU were sufficiently intricate, and didn't demand to work on
a page basis, then it could be configured to automatically forward
pointers regardless of what page they were on. This is unlikely to
occur on modern, paged architectures, though.

> > This would allow
> > memory reads and stores to be indirected only when the page is being
> > cleaned out, as opposed to a true indirecting memory set and reference
> > technology that would _always_ go through an extra indirection; that
> > would work fine enough, but memory reads would be more than twice
> > as slow (not only two memory references, but second one being dependent
> > on the first, so the pipeline would stall often). This slowdown can be
> > tolerated if it is only required on pages that are being worked on by
> > the gc, but not if it is the basic operation for every memory read and
> > write.
>
> Ah, I think I see. So you set a bit that says that this page is in
> old-space.

Not quite. You set a bit that says that this page is one which may
have forwarded pointers. Where the page is is irrelevant, though
it is actually more likely to be in a newspace than an oldspace.

    Then, whenever you do a memory read to that page, you
> automatically check for a forwarding pointer in hardware and use that
> instead. Objects that have moved require the extra
> indirection. Objects that have yet to be copied are simply referenced
> where they lay. Am I getting that right?

Yes.

> > The reason I talk about traps rather than this indirection technique
> > is that it is more likely to occur, because less hardware would be
> > involved (and it is thus more general). Operating systems can indeed
> > do relatively fast trap handling, as long as the context switch isn't
> > hevyweight (or unless there is no context switch at all). Saving of
> > context, including MMX and XMM registers on Pentium and AMD hardware,
> > is one of the reasons why context switches are in fact so heavyweight.
> > One possible solution is that Calling Conventions could be created
> > for such trap handlers which allow for only certain registers to be
> > used; these could be installed in a non-context-switching first-level
> > trap-handler, if compiled properly, and user-level manipulation of
> > the pointers done that way. I don't know, however, what the security
> > concerns would be; they are likely to be non-nil...
>
> Yup. Optimization frequently cuts across the security boundary. There
> are a few ways to make this better, but the cost is always higher than
> if you didn't have to worry about it.
>
> Anyway, thanks for the answer.

No problem. 

-- 
Duane Rettig    duane@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182

Relevant Pages

  • Re: Form not being garbage collected
    ... >From the code snippet you pasted, we could say there is no memory leak ... collecting to occur. ... you found that the main form of your app always not get garbage ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Is garbage collection here yet?
    ... clean up afterwards i.e. collecting the garbage. ... If you clean up afterwards, it's not leaking, right? ... Ok, to rephrase it, you let garbage accumulate. ... before the next line of tcl code gets excuted. ...
    (comp.lang.tcl)
  • Re: Garbage collectable pinned arrays!
    ... As I understand it, pinning is an attribute of the *reference*, not ... it doesn't make sense for a pinned object to be garbage ... But collecting the object and ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Argument list too long (keep reading, its not the FAQ)
    ... > Are you sure your commands aren't collecting some garbage that adds to ... As I log the commands, I can check that there is no garbage ... wget's argument and start crawling. ...
    (comp.lang.perl.misc)