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

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

[Ennals, Robert]

Unfortunately, conservative GC is incompatible with copying collection (which I believe is what O'Caml uses - though I may be wrong).


With a copying collector, data is allocated sequentially in a nursery buffer, and the collector periodically moves the reachable data to a new area area of memory, fixing up all pointers to point to new locations.

The advantage of this approach is that allocation on the heap is very cheap - just return the current position of the heap pointer, and increment it by the object size.

The downside is that one must know for certain whether or not an object is a pointer - as pointers will be changed when the data they point to is moved.


Regarding the block-based approach: as others have mentioned - this approach is entirely practical, and is indeed the approach taken by several other compiler implementations (including GHC), however anecdotal evidence suggests that the bit tagging approach makes GC faster.


> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr [mailto:owner-caml-
> list@pauillac.inria.fr] On Behalf Of Christophe Raffalli
> Sent: 13 August 2004 13:59
> To: Jacques Garrigue
> Cc: Christoph.Bauer@lms-gmbh.de; caml-list@inria.fr
> Subject: Re: AW: [Caml-list] The tag bit
> 
> 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.
> 
> Does anyone have  a comparison between two identical GC except one
> should have a tag bit and the other be conservative ?
> 
> The cost of conservative GC is the test to know if an int is pointing in
> (or at the beginning) of an allocated block which require for instance a
> hashtbl of allocated blocks by adress ranges. I don't know if the gain
> for arithmetic + easier C interface would compensate the lost in the GC
> for a real GC like Caml's.
> 
> 
> --
> Christophe Raffalli
> Université de Savoie
> Batiment Le Chablais, bureau 21
> 73376 Le Bourget-du-Lac Cedex
> 
> tél: (33) 4 79 75 81 03
> fax: (33) 4 79 75 87 42
> mail: Christophe.Raffalli@univ-savoie.fr
> www: http://www.lama.univ-savoie.fr/~RAFFALLI
> ---------------------------------------------
> IMPORTANT: this mail is signed using PGP/MIME
> At least Enigmail/Mozilla, mutt or evolution
> can check this signature
> ---------------------------------------------
> 
> -------------------
> 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

-------------------
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

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

[Ennals, Robert]

Do mostly copying collectors actually solve the problem Andreas was
discussing?

My impression was that mostly copying collectors are only really useful
when the vast majority of pointers are tagged. If all pointers into a
block are tagged, then the block is copied (just as it would be in a
copying collector); however if there are some ambiguous pointers into a
block (e.g. from within some C code you have linked to) then that block
is "pinned" into position, and must remain pinned until there are no
ambiguous pointers into it.

Thus, my impression was the mostly copying collection is great if one
has a language that uses tagged pointers, but wishes it to share GC-ed
objects with a language that doesn't understand tags, but that it
wouldn't really buy you anything in a situation where nothing was tagged
(which is what I think people were proposing).


Of course, I may be talking complete rubbish here - this isn't really my
field. Please feel free to tell me that I've completely misunderstood
everything.


-Rob

> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr [mailto:owner-caml-
> list@pauillac.inria.fr] On Behalf Of T. Kurt Bond
> Sent: 13 August 2004 15:33
> To: Andreas Rossberg
> Cc: caml-list@inria.fr
> Subject: Re: AW: [Caml-list] The tag bit
> 
> Andreas Rossberg writes:
> > AFAIK, a conservative collector is not allowed to move anything.
Hence
> > it is inherently incompatible with compacting and generational GC,
like
> > used in OCaml (and highly desirable).
> 
> Joel F. Bartlett's 1988 paper "Compacting garbage collection with
> ambiguous roots" describes a conservative "mostly copying" compacting
> GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up
> Generations and C++" descibes a generation variation.  Frederick Smith
> and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable
> Alternative to Conservative Mark-Sweep" describes an improved variant
> that they compared with the BDW by using both with the TIL/C ML
> compiler.  Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe
> a GC in their 1998 paper "A Customisable Memory Management Framework
> for C++" that uses mostly copying GC for the default heap.
> 
> --
> T. Kurt Bond, tkb@tkb.mpl.com
> 
> -------------------
> 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

-------------------
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

AW: [Caml-list] The tag bit

[Bauer, Christoph]

[-- Attachment #1: Type: text/plain, Size: 902 bytes --]


>     Well, I can see several reasons :
>   * processors like powers of two, especially when it comes 
> to the size 
> of a memory address, because of cache issues, so you'd better 
> make it 32 
> or 64 words than 33 or 65.
>   * If the tag bit can be anywhere in a word you have to spend extra 
> time to extract it, whereas when it is at a fixed place, 
> especially LSB 
> or MSB, it is very cheap and easy.
>   * You would need two registers to access a value and its 
> tag instead 
> of one, and registers are very precious, at least on IA-32 
> architectures.

But who needs the tag bit? Only the garbage collector. Maybe it's
an advantage to see 32 tag bits as a whole, e.g. the question
"does the block contains any pointer" can be calculated bit-parallel.
Anyway the garbage collector could works on blocks and needs 
just one additional memory access per block.

Regards,
Christoph Bauer

[-- Attachment #2: Type: text/html, Size: 1807 bytes --]

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

[Jacques Garrigue]

From: "Bauer, Christoph" <Christoph.Bauer@lms-gmbh.de>
> But who needs the tag bit? Only the garbage collector. Maybe it's
> an advantage to see 32 tag bits as a whole, e.g. the question
> "does the block contains any pointer" can be calculated bit-parallel.
> Anyway the garbage collector could works on blocks and needs 
> just one additional memory access per block.

But who works in your program?
The garbage collector!
Do some profiling, and you will be surprised at how much time is used
collecting garbage in a perfectly sane program.
No surprise here: in symbolic programming, you are generating garbage
all the time. In the old lisp days, people talked of the mutator (your
program) and the collector, emphasizing that they are almost equal.
And you wouldn't give 1 bit for your brother, doing all the dirty
work? :-)

More seriously, it may be that your idea of blocks could be made to
work, but it's not going to be easy. For instance, what do you do when
manipulating data between registers? Looks like it would mean updating
some special register every time you do a move operation. This could
generate heaps of code.
GC is such an old field that I suppose all weird approaches have
already been studied in the litterature.

Jacques Garrigue

-------------------
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

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

[Christophe Raffalli]

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.

Does anyone have  a comparison between two identical GC except one 
should have a tag bit and the other be conservative ?

The cost of conservative GC is the test to know if an int is pointing in 
(or at the beginning) of an allocated block which require for instance a 
hashtbl of allocated blocks by adress ranges. I don't know if the gain 
for arithmetic + easier C interface would compensate the lost in the GC 
for a real GC like Caml's.


--
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

-------------------
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

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

[Andreas Rossberg]

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.

AFAIK, a conservative collector is not allowed to move anything. Hence 
it is inherently incompatible with compacting and generational GC, like 
used in OCaml (and highly desirable).

Cheers,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Let's get rid of those possible thingies!  -- TB

-------------------
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

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

[T. Kurt Bond]

Andreas Rossberg writes:
> AFAIK, a conservative collector is not allowed to move anything. Hence 
> it is inherently incompatible with compacting and generational GC, like 
> used in OCaml (and highly desirable).

Joel F. Bartlett's 1988 paper "Compacting garbage collection with
ambiguous roots" describes a conservative "mostly copying" compacting
GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up
Generations and C++" descibes a generation variation.  Frederick Smith
and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable
Alternative to Conservative Mark-Sweep" describes an improved variant
that they compared with the BDW by using both with the TIL/C ML
compiler.  Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe
a GC in their 1998 paper "A Customisable Memory Management Framework
for C++" that uses mostly copying GC for the default heap.

-- 
T. Kurt Bond, tkb@tkb.mpl.com

-------------------
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

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

[Ville-Pertti Keinonen]

T. Kurt Bond wrote:

>Joel F. Bartlett's 1988 paper "Compacting garbage collection with
>ambiguous roots" describes a conservative "mostly copying" compacting
>GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up
>Generations and C++" descibes a generation variation.  Frederick Smith
>and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable
>Alternative to Conservative Mark-Sweep" describes an improved variant
>that they compared with the BDW by using both with the TIL/C ML
>compiler.  Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe
>a GC in their 1998 paper "A Customisable Memory Management Framework
>for C++" that uses mostly copying GC for the default heap.
>  
>
Don't forget G. May Yip's "Incremental, generational mostly-copying 
garbage collection in uncooperative environments".  :)

Obviously, all of these variations are subject to the problem mentioned 
by others - movable pointers must be tagged or otherwise identifiable.

I've implemented a variation of the algorithm described in G. May Yip's 
thesis - it works nicely, but my impression of the technique is that it 
inevitably has far more processing overhead than OCaml's collector (even 
without the incremental aspect).  However, it may be worthwile for some 
applications (incremental, supports a mixed environment of arbitrary 
C/C++ code that may refer to the heap of another language that does tag 
(non-)pointers).

The thing with garbage collection is that while it's often obviously a 
good solution, for some specific requirements no garbage collector seems 
"quite right", and you have to either give up on the idea of garbage 
collection or use a massively customized algorithm.

OCaml's collector is impressive - it's not (properly) incremental or 
real-time, but fast, precise, compacting and very good for a lot of 
practical purposes.  From Xavier's papers, we can see that quite a bit 
of testing and tuning has gone into it.

-------------------
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

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

[skaller]

On Fri, 2004-08-13 at 22:58, Christophe Raffalli wrote:

> Does anyone have  a comparison between two identical GC except one 
> should have a tag bit and the other be conservative ?

The Boehm collector is quite efficient: if you compare it
to hand written encodings such as reference counting
for example.

The main problem with it is that it has to 'stop the world'
whilst it is doing its thing, and so isn't useful for
real time applications such as a game where you can easily
pay 20% of all CPU for the GC -- but you simply can't freeze
up the game for 10 seconds every few minutes.

The Ocaml generational collector is likely to be much better
at this -- some of the workload is spread over time, and
the remaining major collection when needed will also be
faster, and can be called manually at appropriate points.

A second point is -- Boehm cannot defragment memory.
Ocaml can (although the compaction is 'world stop').

So .. i don't think the 'overall CPU use' of the two collector
kinds is actually what you need to compare: the real time
performance and/or ability to operate with C/C++ code
are the likely issues.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Christophe Raffalli]

skaller wrote:
> On Fri, 2004-08-13 at 22:58, Christophe Raffalli wrote:
> 
> 
>>Does anyone have  a comparison between two identical GC except one 
>>should have a tag bit and the other be conservative ?
> 
> 
> The Boehm collector is quite efficient: if you compare it
> to hand written encodings such as reference counting
> for example.
> 
> The main problem with it is that it has to 'stop the world'
> whilst it is doing its thing, and so isn't useful for
> real time applications such as a game where you can easily
> pay 20% of all CPU for the GC -- but you simply can't freeze
> up the game for 10 seconds every few minutes.
> 
> The Ocaml generational collector is likely to be much better
> at this -- some of the workload is spread over time, and
> the remaining major collection when needed will also be
> faster, and can be called manually at appropriate points.
> 
> A second point is -- Boehm cannot defragment memory.
> Ocaml can (although the compaction is 'world stop').
> 
> So .. i don't think the 'overall CPU use' of the two collector
> kinds is actually what you need to compare: the real time
> performance and/or ability to operate with C/C++ code
> are the likely issues.
> 
> 
It is not true, on some configuration (including intel I think) Boehm's 
GC can be incremental. At least the documentation say so.
-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

-------------------
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

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

[Brian Hurt]

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