generational garbage collection

[Arvind]

hello ppl,
i am trying to implement a garbage collector for c++ using the
generational algorithm applying mark-sweep to each generation.
i am unable to get any details about the algorithm. is it
necessary that the object allocated in each generation and the
generations themselves be in the form of contigious memory locations.

[Frank Chang]

Could you please tell us whether you are referring to managed C++(.NET)
or unmanaged C++? Thank you.

[Chris Theis]

"Arvind" <ar****@yahoo.c o.in> wrote in message
news:11******** **************@ g14g2000cwa.goo glegroups.com.. .

hello ppl,
i am trying to implement a garbage collector for c++ using the
generational algorithm applying mark-sweep to each generation.
i am unable to get any details about the algorithm. is it
necessary that the object allocated in each generation and the
generations themselves be in the form of contigious memory locations.

Looking into my crystal ball (www.google.com) immediately gives me the
following things you might consider interesting:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/
http://en.wikipedia.org/wiki/Automat...age_collection

HTH
chris

[Frank Chang]

Chris, Arvind is a renowed a computer science processor. He may already
know about the links you found, I think Arvind is looking for people
who have actually worked on C++ garbage collection in academia or
industry(i.e. MSFT). Thank you.

[Chris Theis]

"Frank Chang" <Fr**********@g mail.com> wrote in message
news:11******** **************@ g47g2000cwa.goo glegroups.com.. .

Chris, Arvind is a renowed a computer science processor. He may already
know about the links you found, I think Arvind is looking for people
who have actually worked on C++ garbage collection in academia or
industry(i.e. MSFT). Thank you.

Frank,

I acknowledge that Arvind is a renowned computer science expert in the field
of graph theory, quantum computing etc. However, he stated " i am unable to
get any details about the algorithm" which indicates that he has not found
the links. IMHO the forum might not be the best place to discuss a rather
intricate topic like garbage collection to the required detail. Therefore I
posted the links, which describe algorithms in detail to help him getting
started.

Cheers
Chris

[msalters]

Arvind schreef:

hello ppl,
i am trying to implement a garbage collector for c++ using the
generational algorithm applying mark-sweep to each generation.
i am unable to get any details about the algorithm. is it
necessary that the object allocated in each generation and the
generations themselves be in the form of contigious memory locations.

It seems to me the answer is obviously no. Why should it be? The usual
reason for a set of items to be contiguous is so one can easily find
a next item. Exactly how you define 'next' also defines 'contiguous'.
If you don't qualify it, you usually refer to the "natural" order, i.e.
increasing addresses.

So, in this context I assume you'd want to have a contiguous memory
block so you can find the next allocation. However, if the memory
allocator used a linked list, the physical representation would
probably be non-contiguous, but one could still find the next
allocation in the generation.

HTH,
Michiel Salters

[Chris Theis]

"Arvind" <ar****@yahoo.c o.in> wrote in message
news:11******** **************@ g14g2000cwa.goo glegroups.com.. .

hello ppl,
i am trying to implement a garbage collector for c++ using the
generational algorithm applying mark-sweep to each generation.
i am unable to get any details about the algorithm. is it
necessary that the object allocated in each generation and the
generations themselves be in the form of contigious memory locations.

For mark-sweep GC contiguous memory is not required. However, you might end
up with heavily fragmented memory (depending on your application) and this
could lead to slower reallocation. There are other approaches that
inherently move allocated objects and therefore will automatically result in
contiguous memory. I'd recommend to take a look at
http://www.iecc.com/gclist/GC-faq.html

HTH
Chris

[Frank Chang]

Chris, I apologize. You are right. It seems you know a lot about
garbage collection. Was this experience gained through industry or
school? Thank you.

[Frank Chang]

Chris Theis, I have two reservations about garbage collection in C++ .
The first set of reservations can be found in the link ,
http://www.cs.tut.fi/~warp/MicrosoftComparingLanguages.
The second reservation that the GC-LIST link does not address is the
issue of multiple threads running in a C++ program. How will GC-LIST
handle the memory allocated to each worker thread that is instantianted
when the worker threads finish their tasks? Thank you.

[Chris Theis]

"Frank Chang" <Fr**********@g mail.com> wrote in message
news:11******** **************@ g44g2000cwa.goo glegroups.com.. .

Chris Theis, I have two reservations about garbage collection in C++ .
The first set of reservations can be found in the link ,
http://www.cs.tut.fi/~warp/MicrosoftComparingLanguages.
The second reservation that the GC-LIST link does not address is the
issue of multiple threads running in a C++ program. How will GC-LIST
handle the memory allocated to each worker thread that is instantianted
when the worker threads finish their tasks? Thank you.

Dear Frank,

frankly I share your reservations about GC starting already at the
philosophical design point of view, which is followed by the technical
requirements and overhead that can become very tricky. This is especially
true for multi threading environments. There are different approaches for
this problem like for example safe-points. This means that all threads must
have reached a safe-point before the GC can start its work. However, this
might become a bottleneck as soon as threads with very different priority
levels are involved as it could cause serious delays. Other approaches
include breaking the problem down into single-thread contexts, etc.

You might probably take a look at the following page which hosts a fairly
large collection of papers covering GC thread problems etc.

http://research.sun.com/jtech/pubs/
http://www-128.ibm.com/developerwork...ry/i-garbage2/

HTH
Chris