Re: [Bug-apl] Boehm garbage collector

[David B. Lamkins]

I'll add to that:

The Boehm collector is in the family of "conservative" collectors.
Briefly, since there's no way to give the collector a precise list of
roots to the data structures in the heap (this is true, for example, of
pointers on the stack and in structures), the collector instead uses the
hueristic of testing the value of a machine word to see whether it
contains an address in the heap; if the word passes this test, it's
assumed to be a pointer.

A conservative GC therefore won't collect any object that's still live,
but it *may* hold onto chunks of memory that aren't actually live. (You
might have a scalar value, for example, that "looks like" a pointer.)
The end result is a space leak.

In practice, this is *usually* not a problem. I have seen production
systems, though, in which a conservative GC caused catastrophic space
leaks under the right (wrong) conditions.

A reference-counting collector won't have these problems. 

Additionally, the work done by a reference-counting collector is evenly
amortized over the execution of the program, whereas a mark-sweep
collector (like Boehm) causes a pause (sometimes significant, depending
upon circumstances of the size of the heap, state of the heap, speed of
the machine, etc.) at unpredictable intervals for collection.

A proper GC can be an attractive alternative to reference counting in
the case where there may be circularity in references. I don't believe
that circularity of references is an issue in APL, unless the
implementer has explicitly tried to do clever sharing optimizations.

On Thu, 2014-05-29 at 10:38 -0500, Blake McBride wrote:
> Dear Elias,
> 
> 
> I have experience with the Boehm collector and thought I would share
> some opinions.
> 
> 
> 1.  Since C/C++ was not designed with GC in mind, the Boehm collector
> is forced to take into account many very system specific factors.
>  These factors vary widely from system to system, and from system
> release to system release.  This means that, rather than portable
> code, you are maximally system dependent.  While that may be fine as
> long as the Boehm team continues to support their collector, all of
> your code will fall on its face the day they don't.  In other words,
> anything built with the Boehm collector will from then on be
> completely dependent on them.  The source code they provide, while
> complete, is pretty useless unless you understand all of the very
> system specific nuances of each system they support.  In other words,
> you can't support it yourself.
> 
> 
> 2.  A GC like Boehm would never be as fast as reference counting.
>  Reference counting, when possible, only does what it needs to do at
> the time it needs to do it.  A generic GC has to use up a specified
> amount of memory and then check everything.  I know generational GC's
> and concurrent GC's minimize some of this but it still takes time and
> their assumptions are rarely completely accurate so their function is
> reduced, i.e. _conservative_ collector.
> 
> 
> The Boehm collector is a great solution when you want to add GC to a
> system after-the-fact, or if you are unwilling to do the hard work
> yourself.  It seems to me that Jurgen has already done the hard work
> in a portable way.  I'd prefer not to mess with it, nor pepper the
> system with Boehm ifdefs.
> 
> 
> Just an opinion (from someone who has used the Boehm collector and has
> written my own collectors).
> 
> 
> Thanks.
> 
> 
> Blake
> 
> 
> 
> 
> 
> 
> 
> 
> On Thu, May 29, 2014 at 9:24 AM, Elias Mårtenson <address@hidden>
> wrote:
>         I've been playing around with the Boehm (Böhm, I suppose)
>         garbage collector, and it's pretty amazing. Jürgen, do you
>         have any experience with it?
>         
>         
>         Updating the GNU APL code to (conditionally, with a compiler
>         option) to support using the collector for at least Value
>         objects should be fairly simple. This would provide several
>         benefits:
>               * A performance improvement since there is no need to
>                 deal with the reference counter.
>               * Improved parallelism if one wants to expand threading
>                 beyond simply paralellising simple loops (no need to
>                 deal with race conditions when accessing the reference
>                 count)
>               * Provide a more solid ground when attempting to reduce
>                 excessive cloning (with the GC, once can simply share
>                 everything and clone before modification)
>         I was thinking of starting to implement this, but it would
>         take more than a few hours which means that I first would like
>         to hear your input on it before wasting my time.
>         
>         
>         Regards,
>         Elias
> 
>