generational garbage collection

Discussion in 'C++' started by Arvind, Aug 25, 2005.

  1. Arvind

    Arvind Guest

    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.
     
    Arvind, Aug 25, 2005
    #1
    1. Advertising

  2. Arvind

    Frank Chang Guest

    Could you please tell us whether you are referring to managed C++(.NET)
    or unmanaged C++? Thank you.
     
    Frank Chang, Aug 25, 2005
    #2
    1. Advertising

  3. Arvind

    Chris Theis Guest

    "Arvind" <> wrote in message
    news:...
    > 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
     
    Chris Theis, Aug 25, 2005
    #3
  4. Arvind

    Frank Chang Guest

    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 Chang, Aug 25, 2005
    #4
  5. Arvind

    Chris Theis Guest

    "Frank Chang" <> wrote in message
    news:...
    > 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
     
    Chris Theis, Aug 25, 2005
    #5
  6. Arvind

    msalters Guest

    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
     
    msalters, Aug 25, 2005
    #6
  7. Arvind

    Chris Theis Guest

    "Arvind" <> wrote in message
    news:...
    > 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
     
    Chris Theis, Aug 25, 2005
    #7
  8. Arvind

    Frank Chang Guest

    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, Aug 25, 2005
    #8
  9. Arvind

    Frank Chang Guest

    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.
     
    Frank Chang, Aug 25, 2005
    #9
  10. Arvind

    Chris Theis Guest

    "Frank Chang" <> wrote in message
    news:...
    > 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
     
    Chris Theis, Aug 26, 2005
    #10
  11. Arvind

    Frank Chang Guest

    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, Aug 26, 2005
    #11
  12. Arvind

    Frank Chang Guest

    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.
     
    Frank Chang, Aug 26, 2005
    #12
  13. Arvind

    Chris Theis Guest

    "Frank Chang" <> wrote in message
    news:...
    > 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
     
    Chris Theis, Aug 26, 2005
    #13
  14. Arvind

    Frank Chang Guest

    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, Aug 26, 2005
    #14
  15. Arvind

    Frank Chang Guest

    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"
     
    Frank Chang, Aug 26, 2005
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Laser Lu

    Garbage Collection and Manage Code?

    Laser Lu, Jan 26, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    733
    Gaurav Khanna [C# MVP]
    Jan 27, 2004
  2. Replies:
    1
    Views:
    453
    mrstephengross
    Jul 25, 2005
  3. Øyvind Isaksen
    Replies:
    1
    Views:
    1,001
    Øyvind Isaksen
    May 18, 2007
  4. Carl Banks

    Generational Interfaces

    Carl Banks, Jan 26, 2008, in forum: Python
    Replies:
    5
    Views:
    285
  5. Borked Pseudo Mailed

    Interest in generational GC for Python

    Borked Pseudo Mailed, Apr 19, 2009, in forum: Python
    Replies:
    3
    Views:
    216
    Martin v. Löwis
    Apr 20, 2009
Loading...

Share This Page