www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is there a modern GC for D?

reply "Robert Jacques" <sandford jhu.edu> writes:
Based on a thread on the DMD concurrency mailing list I've begun to get a  
sinking regarding the future of the garbage collector in D: most of the  
work in GC algorithms has gone into functional and (mostly) pure-OO  
languages, leaving a multi-paradigm systems programming language like D  
out in the cold. So far, I know mark-sweep and mark-region algorithms in  
either serial, parallel or thread-local forms should work. But based on  
Java we'd really like incremental, generational and/or concurrent options.  
So I'd like to ask people to help brainstorm some ideas.

Some things I've run into:
-structs/pointers/slices/etc make finding memory meta information, like  
mark-bits or ref-counts, non-trivial.
-C function calls and assembler blocks make code instrumentation  
questionable.
-Getting concurrent GC code correct is very hard. Boehm's algorithm, for  
instance, looks extremely racy.

Thanks!
Feb 09 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Robert Jacques wrote:
 Based on a thread on the DMD concurrency mailing list I've begun to get 
 a sinking regarding the future of the garbage collector in D: most of 
 the work in GC algorithms has gone into functional and (mostly) pure-OO 
 languages, leaving a multi-paradigm systems programming language like D 
 out in the cold. So far, I know mark-sweep and mark-region algorithms in 
 either serial, parallel or thread-local forms should work. But based on 
 Java we'd really like incremental, generational and/or concurrent 
 options. So I'd like to ask people to help brainstorm some ideas.
 
 Some things I've run into:
 -structs/pointers/slices/etc make finding memory meta information, like 
 mark-bits or ref-counts, non-trivial.
 -C function calls and assembler blocks make code instrumentation 
 questionable.
 -Getting concurrent GC code correct is very hard. Boehm's algorithm, for 
 instance, looks extremely racy.
 
 Thanks!

s/sinking/thinking/ http://www.youtube.com/watch?v=gmOTpIVxji8 :o) Andrei
Feb 09 2010
parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 10 Feb 2010 01:06:47 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Robert Jacques wrote:
 Based on a thread on the DMD concurrency mailing list I've begun to get  
 a sinking regarding the future of the garbage collector in D: most of  
 the work in GC algorithms has gone into functional and (mostly) pure-OO  
 languages, leaving a multi-paradigm systems programming language like D  
 out in the cold. So far, I know mark-sweep and mark-region algorithms  
 in either serial, parallel or thread-local forms should work. But based  
 on Java we'd really like incremental, generational and/or concurrent  
 options. So I'd like to ask people to help brainstorm some ideas.
  Some things I've run into:
 -structs/pointers/slices/etc make finding memory meta information, like  
 mark-bits or ref-counts, non-trivial.
 -C function calls and assembler blocks make code instrumentation  
 questionable.
 -Getting concurrent GC code correct is very hard. Boehm's algorithm,  
 for instance, looks extremely racy.
  Thanks!

s/sinking/thinking/ http://www.youtube.com/watch?v=gmOTpIVxji8 :o) Andrei

:) actually it should be a sinking feeling. Thanks for the laughs.
Feb 10 2010
prev sibling next sibling parent Justin Johansson <no spam.com> writes:
Robert Jacques wrote:
 Based on a thread on the DMD concurrency mailing list I've begun to get 
 a sinking regarding the future of the garbage collector in D: most of 
 the work in GC algorithms has gone into functional and (mostly) pure-OO 
 languages, leaving a multi-paradigm systems programming language like D 
 out in the cold. So far, I know mark-sweep and mark-region algorithms in 
 either serial, parallel or thread-local forms should work. But based on 
 Java we'd really like incremental, generational and/or concurrent 
 options. So I'd like to ask people to help brainstorm some ideas.
 
 Some things I've run into:
 -structs/pointers/slices/etc make finding memory meta information, like 
 mark-bits or ref-counts, non-trivial.
 -C function calls and assembler blocks make code instrumentation 
 questionable.
 -Getting concurrent GC code correct is very hard. Boehm's algorithm, for 
 instance, looks extremely racy.
 
 Thanks!

As my high school maths teacher used to say: Good question; next question. :-) Justin Johansson
Feb 10 2010
prev sibling next sibling parent reply Leandro Lucarella <llucax gmail.com> writes:
Robert Jacques, el 10 de febrero a las 01:03 me escribiste:
 -Getting concurrent GC code correct is very hard. Boehm's algorithm,
 for instance, looks extremely racy.

There is a very simple concurrent GC model using fork()[1]. This is Unix only though (and very dependent on how efficiently fork() is implemented in the OS). I'm working (very slowly :) on implementing a GC based on this algorithm. No races, almost no synchronization. If the OS uses COW when fork()ing (I guess every modern OS does that), the only drawback is the copying of changed pages. [1] Nonintrusive Cloning Garbage Collector with Stock Operating System Support. http://www.cs.purdue.edu/homes/grr/snapshot-gc.ps -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ----------------------------------------------------------------------
Feb 10 2010
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2010-02-12 18:08:09 -0500, "Robert Jacques" <sandford jhu.edu> said:

 On Wed, 10 Feb 2010 09:51:37 -0500, Leandro Lucarella 
 <llucax gmail.com>  wrote:
 
 There is a very simple concurrent GC model using fork()[1]. This is Unix  only
 though (and very dependent on how efficiently fork() is implemented in  the
 OS). I'm working (very slowly :) on implementing a GC based on this
 algorithm.
 
 No races, almost no synchronization. If the OS uses COW when fork()ing (I
 guess every modern OS does that), the only drawback is the copying of
 changed pages.
 
 [1] Nonintrusive Cloning Garbage Collector with Stock Operating System
     Support.
     http://www.cs.purdue.edu/homes/grr/snapshot-gc.ps
 

Cool. Hadn't thought of something so simple. I just watched a channel 9 blog (http://channel9.msdn.com/shows/Going%20Deep/Mark-Russinovich-Insi e-Windows-7-Redux/) and about half-way through they talk about new process reflection capabilities in Windows 7, which are an extension of fork, which they've had for a while (for posix compatibility, etc). Also, the PAGE_WRITECOPY protection should also allow this to work on Windows, at a finer grain.

It looks cool indeed. I was a little wary for ill effects at first, so I attempted to insert an innocuous: if (fork() == 0) { sleep(1); // do mark and sweep and return the result to the parent process. exit(0); } in a (single-threaded) Cocoa application. No ill effect found (as long as you don't forget the exit(0)). I wonder how it'd fly on Windows though, isn't process creation a little more heavyweight? -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 12 2010
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 10 Feb 2010 09:51:37 -0500, Leandro Lucarella <llucax gmail.com>  
wrote:

 Robert Jacques, el 10 de febrero a las 01:03 me escribiste:
 -Getting concurrent GC code correct is very hard. Boehm's algorithm,
 for instance, looks extremely racy.

There is a very simple concurrent GC model using fork()[1]. This is Unix only though (and very dependent on how efficiently fork() is implemented in the OS). I'm working (very slowly :) on implementing a GC based on this algorithm. No races, almost no synchronization. If the OS uses COW when fork()ing (I guess every modern OS does that), the only drawback is the copying of changed pages. [1] Nonintrusive Cloning Garbage Collector with Stock Operating System Support. http://www.cs.purdue.edu/homes/grr/snapshot-gc.ps

Cool. Hadn't thought of something so simple. I just watched a channel 9 blog (http://channel9.msdn.com/shows/Going%20Deep/Mark-Russinovich-Insi e-Windows-7-Redux/) and about half-way through they talk about new process reflection capabilities in Windows 7, which are an extension of fork, which they've had for a while (for posix compatibility, etc). Also, the PAGE_WRITECOPY protection should also allow this to work on Windows, at a finer grain.
Feb 12 2010
prev sibling parent Leandro Lucarella <llucax gmail.com> writes:
Michel Fortin, el 12 de febrero a las 19:47 me escribiste:
Cool. Hadn't thought of something so simple. I just watched a
channel 9  blog  (http://channel9.msdn.com/shows/Going%20Deep/Mark-Russinovich-Inside-Windows-7-Redux/)
and about half-way through they talk about new process reflection
capabilities in Windows 7, which are an extension of fork, which
they've  had for a while (for posix compatibility, etc). Also, the
PAGE_WRITECOPY  protection should also allow this to work on
Windows, at a finer grain.

It looks cool indeed. I was a little wary for ill effects at first, so I attempted to insert an innocuous: if (fork() == 0) { sleep(1); // do mark and sweep and return the result to the parent process. exit(0); } in a (single-threaded) Cocoa application. No ill effect found (as long as you don't forget the exit(0)). I wonder how it'd fly on Windows though, isn't process creation a little more heavyweight?

I know Linux is very fast at fork()ing, you can even use clone() directly to avoid copying file descriptor tables for example. Even more, you get all the threads stopped in the cloned process for free ;) -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ----------------------------------------------------------------------
Feb 13 2010