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]

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/Automatic_garbage_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]

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]

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]

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/developerworks/ibm/library/i-garbage2/

HTH
Chris

 

[Frank Chang]

Chris, let me try again. The last post didn't make it through. Thank
you for explaining safe-points, There is also a good discussion about
safe-points in the link http:/www/ieec.com/gclist/GC-faq.html , Thread
Safety, you provided yesterday. However, the FAQ does not discuss how
the GC-LIst project releases the memory allocated by threads back to
the operating system. Even in managed C++(.NET) , John Skeets writes:
"It's normal for memory not to be released to the OS for potentially a
very long time, and sometimes never. The important thing is that the
memory becomes available as far as .NET is concerned."
I read your links about how IBM resolved GC thread problems in
Java . Given the differences between Java and unmanaged C++, do you
think the Java GC thread solutions can be applied to unmanaged C++?

 

[Frank Chang]

Chris, If this post appears twice it is because my browser crashed. I
read your link http://www.ieec.com.gclist/GC-faq.html . This article
contains a section, Thread Support, which discusees safe-points.
However, the thread support section does not contain a discussion about
how the GC-List unmanaged C++ garbage collection policy handles
releasing the memory allocated by multiple threads back to the
operating system after the threads have finished their tasks. Even in
managed C++(.NET), I believe it may be true that the memory released by
threads is released to the .NET "VM" rather than the operating system.
I scanned the link concerning Java garbage collection which you
provided but I am not sure if Arvind can apply those same solutions to
unmanaged C++ garbage collection.
I read Arvind's web page about his current research interests. It
is interesting to read. Evidently, Arvind has started two companies
since 2000. I just don't think it would be a good idea to start a
company built around an unmanaged C++ garbage collection framework.
The total revenues of this hypothetical company would be a lot less
than the cost of R&D required to build such a product. Also, it is
uncertain how the unmanaged C++ community react to such a product once
it were introduced. Thank you.

 

[Chris Theis]

Chris, If this post appears twice it is because my browser crashed. I
read your link http://www.ieec.com.gclist/GC-faq.html . This article
contains a section, Thread Support, which discusees safe-points.
However, the thread support section does not contain a discussion about
how the GC-List unmanaged C++ garbage collection policy handles
releasing the memory allocated by multiple threads back to the
operating system after the threads have finished their tasks. Even in
managed C++(.NET), I believe it may be true that the memory released by
threads is released to the .NET "VM" rather than the operating system.
I scanned the link concerning Java garbage collection which you
provided but I am not sure if Arvind can apply those same solutions to
unmanaged C++ garbage collection.
I read Arvind's web page about his current research interests. It
is interesting to read. Evidently, Arvind has started two companies
since 2000. I just don't think it would be a good idea to start a
company built around an unmanaged C++ garbage collection framework.
The total revenues of this hypothetical company would be a lot less
than the cost of R&D required to build such a product. Also, it is
uncertain how the unmanaged C++ community react to such a product once
it were introduced. Thank you.

Hi Frank,

GC-list is rather a discussion/knowledge base than an actual implementation.
Releasing memory from the GC to the OS is implementation dependent and also
a philosophical question. It can be argued whether it is a good idea to
immediately return memory to the OS pool, but in IMHO for most applications
it is not such a hot idea. If you have a lot of short-lived threads it will
pay off to keep control over the memory, however for long lived threads the
situation can be different. AFAIK many GC implementations delay the release
to the OS as long as possible.

I also think the .NET handles it that way but you might check Mike Zintels
blog for this (http://blogs.msdn.com/mikezintel/default.aspx).
It actually makes sens that the .NET VM is the instance taking care of the
memory for the whole .NET framework as it allows for better control. I
actually would be very cautious investing my money in the R&D for a new
unmanaged C++ GC as there are quite sophisticated open source
implementations already available, but this is a rather personal opinion and
I certainly do not want to discourage anybody from doing this. There is
certainly large room for improvement on the technical side, but I have my
reservations regarding the economical aspects of such an undertaking.

Anyway, you normally can apply the basic ideas of the Java GC also to an
unmanaged C++ GC, but naturally you'll run into big difference regarding the
interfacing. In Java (and C#) the memory management is done mostly under the
hood, whereas in unmanaged C++ it will be the developer who will have to
interface with the GC at some point or the other.

HTH
Chris

 

[Frank Chang]

Chris: I never meant to infer that GC-LIST was an implementation . I
referred to it as a policy. I apologize for the confusion. The biggest
difference between Java, C# and managed C++(.NET) is that they have an
virtual machine layered on top of the operating system. From all your
links including
http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html, I see no
mention of the fact that garbage collection in unmanaged C++ would use
a virtual machine. For example, gnu has a garbage collection option but
I don't believe they have also built a virtual machine. Therefore, in
unmanaged C++ GC , the memory allocated by threads should be released
to the operating system. Also , could you please tell me why there is a
difference between short-lived threads and long-lived threads?

 

[Frank Chang]

Chris, Sorry for the typo : It should read:

The biggest difference between Java, C# and managed C++(.NET)
versus unmanaged C++ is that Java, C#, managed C++ all have an virtual
machine layered on top of the operating system.

I think you alluded to this in your last post,
"In Java (and C#) the memory management is done mostly under the
hood, whereas in unmanaged C++ it will be the developer who will have
to interface with the GC at some point or the other"