Re: "The Little Lisper"

From: Hans-J. Boehm (Hans_Boehm_at_hp.com)
Date: 04/21/04 

Date: 21 Apr 2004 12:11:54 -0700

dave_a_fisher@yahoo.com (David Fisher) wrote in message news:<14030ca9.0404161420.5e3e7945@posting.google.com>...
>
> In fact, when you know how conservative GC works, such examples
> immediately spring to mind:
>
> 1. Implement a list-based queue. keep it at around 1000-element length
> (for example), run random floats "through" it. Observe your PLT
> eventually sending your computer to the swapping hell (unless heap
> limits are set, in which case it will just fail to allocate)
>
> 2. If you don't like "random", replace it with some "meaningful"
> numerics.
>
> 3. If you don't like "queue", replace it with lists, stacks or
> doubly-linked lists that are temporarily grown inside some loop, and
> then completely discarded (only to stay in memory _forever_, with some
> probability)
>
This is all discussed quite thoroughly in my paper:

``Bounding Space Usage of Conservative Garbage Collectors'',
Proceedings of the 2002 ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Languages, Jan. 2002, pp. 93-100.

There are two distinct reasons for conservative collection to leak
unbounded amounts of space:

1) The number of pointer misidentifications itself is unbounded. This
generally can't happen unless the heap itself is traced
conservatively. Some clients of our collector do that, some don't.
It's useful to be able to do this, but for Scheme or Java objects,
it's typically also fairly easily avoidable. (E.g. gcj avoids it.)

2) You create data structures which contain unbounded pointer chains.
Linked queues and lazily evaluated lists seem to be the canonical, and
basically only, examples of this. You do need to manually avoid these
in conservatively collected applications. (They also don't get along
well with some other GC techniques, e.g. anything that involves a very
rarely or never collected generation.) This is a property that's
quite amenable to analysis. And the paper contains an algorithm for
testing it with modest overhead.

I think the above examples actually won't work well. Version 1 will
work (i.e. blow up) if you instead fill a large live array with random
numbers which are replaced periodically. (If they're constant, the
black-listing algorithm in the collector is likely to handle the
problem.) Version 3 won't work, unless you have a very large heap in
relation to your address space, and the heap is traced conservatively.
 Queues are far worse than anything else. (See the paper for proofs.)

Hans

Relevant Pages

  • Re: RAD vs. performance
    ... ref counting is very prone to stalls whereas OCaml's ... errm, I don't keep inverse references or anything, only a count (gathering ... state is used by the mark/sweep collector ('grey' is a conventional holdover ... the initial heap size is 512kB, so this is an overhead of about 64kB ...
    (comp.lang.misc)
  • Re: How to create virtual machine?
    ... How garbage collectors gets roots from local variables? ... For this there is the heap. ... either memory copying (like in a copy collector or compacting collector), ... Since the C compiler is free to emit code that computes the LHS L-val ...
    (comp.lang.c)
  • Re: to dispose or not ?
    ... The dotNet garbage collector is, at it's heart, a move to another heap style collector for the Gen0 and Gen1 heaps and a mark/sweep/compact collector for the Gen2 heap. ... Setting an object to Nothing simply releases the reference from the variable to the object in the heap. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Smart Pointers: Is there something similar to smart pointers in C?
    ... "kinda" work. ... The garbage collector scans the heap and stack and registers for things ... struct to a system API, the GC probably won't see the struct address, ...
    (comp.lang.c)