Re: AW: [Caml-list] The tag bit

[Brian Hurt <bhurt@spnz.org>]

On Fri, 13 Aug 2004, Christophe Raffalli wrote:

> There is a less costly way to avoid the tag bit in integer: 
> "conservative GC": any int which happens to point in an alloccated block 
> (or only at the beginning if you do not consider C but ML) is considered 
> as a pointer. You will have very few wrong pointers (especially in the 
> second case). Moreover, array of int or float, or block of memory can be 
> tagged with a flag saying they do not old pointer.
> 
> The Boehm GC for C and C++ is very succefull to do that and very often 
> allow you to share data-structure in C as you would in ML (not caring 
> about who will release first the data) and gain both speed and memory.

This works well for languages like C/C++, where allocation is
(compartively) rare.  Ocaml programs allocate like crazy (most of the
stuff they allocate becomes garbage almost immediately, which is why they
don't take 300 terabytes of ram to run).  Cost of allocation is a very 
important number to Ocaml's performance.

The problem with Boehm-style conservative GC is that you can't do copying 
collection with it.  You're not *sure* if that word is an integer or a 
pointer, so you can't change it to move the object it's pointing to- you 
might be changing an integer, with catastrophic consequences for the 
program.  

With copying garbage collection, allocation is very, very fast.  Ocaml, on 
the x86, takes five simple instructions to allocate a block of memory (if 
you don't kick off a garbage collection).  So a high allocation rate isn't 
a big problem.  But this only works because Ocaml keeps the heap compact 
by moving objects around.  So allocating on the heap is not much slower 
than allocating on the stack- you just bump a pointer.  If you can't move 
objects around, the heap becomes fragmented- free and used blocks mixed 
together.  And you end up searching the heap for a free space when you 
want to allocate.  This isn't a problem if allocation is rare, but it's 
deadly for Ocaml.


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners