[plt-scheme] Collect-Garbage not enabled on Dr. Scheme?

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Tue Apr 7 15:43:49 EDT 2009

At Sun, 5 Apr 2009 19:40:52 +0300, emre berat nebioğlu wrote:
> "[Boehm, POPL'02]" Can someone explain this problem more clearly or
> can someone suggest anything because i wonder that problem.
> And mail said the problem is for for GUI program why is that ?

Suppose that your program allocates a bunch of little objects that
don't point to each other:

                                    .
    ----    ----     ----     ----  .   ----
   |    |  |    |   |    |   |    | .  |    |
    ----    ----     ----     ----  .   ----
                                    .
                        <<< GC-able . in use >>>
                                    .

And suppose further that the program stops using each object soon after
it's allocated. If the conservative collector accidentally holds onto 1
out of 5 objects that it should collect at any given then, that's not a
big problem. A GC will be triggered every time there are N objects
total, and roughly N/5 objects will hang around to the left of the
dotted line. You just have a constant overhead on your heap usage due
to imprecision.

Now, suppose instead that the objects can point to each other, and when
you allocate an object, you make the previous one point to the new one
to form a linked list:

                                    .
    ----    ----     ----     ----  .   ----
   |    |->|    |-->|    |-->|    |-.->|    |
    ----    ----     ----     ----  .   ----
                                    .
                        <<< GC-able . in use >>>
                                    .

Note that links don't go from the "in use" area to the "GC-able" area
(otherwise its wouldn't be GCable). Still, it now matters which objects
to the left of the dotted line a conservative GC accidentally retains.
An object far to the left of the picture references many other nodes,
so far more than N/5 nodes will remain to the left of the dotteed line
after a GC. That will make GCs less frequent, so that even more is
retained after the next GC, and so on.

This linked-list problem happens for threads in our system. It often
happens with GUIs, and DrScheme is a particularly extreme example. Each
time you click execute in DrScheme, a new thread is created. Swapping
out a thread captures the state of registers, and a register can easily
refer to the thread being swapped in. Even if DrScheme stops referring
to all the old threads, if the GC accidentally retains one of the
threads, it can easily hold on to many future threads, and so on.

If the programmer knows when threads die, then the problem is easily
solved by "zeroing out" the dead threads so they do not refer to other
threads. But we don't want to keep track of when threads die; relying
on GC lets us create simpler and more reliable synchronization
abstractions.



Posted on the users mailing list.