www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - State of and plans for the garbage collector

reply Jonathan M Davis <jmdavisprog gmail.com> writes:
Okay. I really don't know much about garbage collectors, how they work, or what 
makes one particularly good or bad (other than the fact that it needs to be 
efficient execution-wise and manage memory wisely so that you don't use too
much 
of it or do anything else that would be an overall negative for performance). 
However, from the comments here - both recent and in the past - it's pretty 
clear that D's garbage collector is fairly outdated. I would assume that that 
would be negative for performance - certainly it would mean that significant 
improvements could be made.

So, my question is this: what are the plans for the garbage collector? Is the 
intention to continue to improve it bit by bit, to give it a major overhaul at 
some point, to outright replace it at a later date, or something else entirely?

If D is going to compete with C and C++, it needs to be highly efficient, and
if 
the garbage collector isn't up to snuff, that's going to be a big problem. I'm 
not looking to complain about the current garbage collector - I really don't 
know how good or bad it is - but if it is rather poor (as I've gotten the 
impresison that it is - at least in some respects - from various discussions on 
it here), then I'd assume that it needs a major overhaul or replacement at some 
point. So, are there any specific plans with regards to that, or is that just 
something that may be considered in the future?

- Jonathan M Davis
Jul 15 2010
next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Thu, 15 Jul 2010 10:18:38 +0300, Jonathan M Davis  
<jmdavisprog gmail.com> wrote:

 Okay. I really don't know much about garbage collectors, how they work,  
 or what makes one particularly good or bad (other than the fact that it  
 needs to be efficient execution-wise and manage memory wisely so that  
 you don't use too much of it or do anything else that would be an  
 overall negative for performance). However, from the comments here -  
 both recent and in the past - it's pretty clear that D's garbage  
 collector is fairly outdated. I would assume that that would be negative  
 for performance - certainly it would mean that significant improvements  
 could be made.

IMO the D GC isn't bad, it's just mediocre. (It could have been way worse.) I would like to use this opportunity to bring up a GC implementation written by Jeremie Pelletier, which seems to have gone mostly unnoticed when it was posted as a reply to D.announce: http://pastebin.com/f7a3b4c4a Aside from multiple optimizations across the board, this GC employs an interesting different strategy. The gist of it is that it iteratively destroys only objects that have no immediate references. In the case of long linked lists, this trades destruction complexity with scan complexity, which is a very good change - most times deeply-nested structures such as linked lists survive multiple generational cycles. Jeremie, if you're reading this: how goes your D2 runtime project? (I also have an unfinished generational GC lying around, which is still unknown if it's viable performance-wise - I should really try to finish it one day.) -- Best regards, Vladimir mailto:vladimir thecybershadow.net
Jul 15 2010
prev sibling next sibling parent Leandro Lucarella <luca llucax.com.ar> writes:
Jonathan M Davis, el 15 de julio a las 00:18 me escribiste:
 Okay. I really don't know much about garbage collectors, how they work, or
what 
 makes one particularly good or bad (other than the fact that it needs to be 
 efficient execution-wise and manage memory wisely so that you don't use too
much 
 of it or do anything else that would be an overall negative for performance). 
 However, from the comments here - both recent and in the past - it's pretty 
 clear that D's garbage collector is fairly outdated. I would assume that that 
 would be negative for performance - certainly it would mean that significant 
 improvements could be made.
 
 So, my question is this: what are the plans for the garbage collector? Is the 
 intention to continue to improve it bit by bit, to give it a major overhaul at 
 some point, to outright replace it at a later date, or something else entirely?
 
 If D is going to compete with C and C++, it needs to be highly efficient, and
if 
 the garbage collector isn't up to snuff, that's going to be a big problem. I'm 
 not looking to complain about the current garbage collector - I really don't 
 know how good or bad it is - but if it is rather poor (as I've gotten the 
 impresison that it is - at least in some respects - from various discussions
on 
 it here), then I'd assume that it needs a major overhaul or replacement at
some 
 point. So, are there any specific plans with regards to that, or is that just 
 something that may be considered in the future?

I'm working on a concurrent GC, things are going really slow, but I plan to give it more attention this months, and I hope it will be finished (finished in my own terms, as it is my thesis) by the end of the year. I would like to explore merging the precise scanning patch and some other optimizations, collection strategies, but I'm not sure I will have the time (probably not). I'm not sure how it would turn out, even when I'm doing regular benchmarks to ensure, at least, that the current performance is not degraded (I didn't started doing the collection concurrently). One more note: I'm working with D1, but using the Tango runtime, so I guess it should be not to hard to port to D2. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ---------------------------------------------------------------------- Every day 21 new born babies will be given to the wrong parents
Jul 15 2010
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Thu, 15 Jul 2010 04:28:43 -0400, Vladimir Panteleev  
<vladimir thecybershadow.net> wrote:

 On Thu, 15 Jul 2010 10:18:38 +0300, Jonathan M Davis  
 <jmdavisprog gmail.com> wrote:

 Okay. I really don't know much about garbage collectors, how they work,  
 or what makes one particularly good or bad (other than the fact that it  
 needs to be efficient execution-wise and manage memory wisely so that  
 you don't use too much of it or do anything else that would be an  
 overall negative for performance). However, from the comments here -  
 both recent and in the past - it's pretty clear that D's garbage  
 collector is fairly outdated. I would assume that that would be  
 negative for performance - certainly it would mean that significant  
 improvements could be made.

IMO the D GC isn't bad, it's just mediocre. (It could have been way worse.) I would like to use this opportunity to bring up a GC implementation written by Jeremie Pelletier, which seems to have gone mostly unnoticed when it was posted as a reply to D.announce: http://pastebin.com/f7a3b4c4a Aside from multiple optimizations across the board, this GC employs an interesting different strategy. The gist of it is that it iteratively destroys only objects that have no immediate references. In the case of long linked lists, this trades destruction complexity with scan complexity, which is a very good change - most times deeply-nested structures such as linked lists survive multiple generational cycles.

Wouldn't that mean it can't handle cycles?
 Jeremie, if you're reading this: how goes your D2 runtime project?

 (I also have an unfinished generational GC lying around, which is still  
 unknown if it's viable performance-wise - I should really try to finish  
 it one day.)

Jul 15 2010
prev sibling next sibling parent reply Bane <branimir.milosavljevic gmail.com> writes:
If I had to chose one topic with most bitchin' on this newsgroup I have
impression it would be the one about GC. They usually goes from 'GC managed
programs are slow, D ain't good enough', to 'language X has better GC than D',
to ' GC that D has is bad at Z'.

Why not make D summer of code - write your own GC optimized for special case of
XYZ, send it, bundle all up in D with compiler switch '--useGC=XYZ'. That is
only way to really compare what is best for special case.

 Okay. I really don't know much about garbage collectors, how they work, or
what 
 makes one particularly good or bad (other than the fact that it needs to be 
 efficient execution-wise and manage memory wisely so that you don't use too
much 
 of it or do anything else that would be an overall negative for performance). 
 However, from the comments here - both recent and in the past - it's pretty 
 clear that D's garbage collector is fairly outdated. I would assume that that 
 would be negative for performance - certainly it would mean that significant 
 improvements could be made.
 
 So, my question is this: what are the plans for the garbage collector? Is the 
 intention to continue to improve it bit by bit, to give it a major overhaul at 
 some point, to outright replace it at a later date, or something else entirely?
 
 If D is going to compete with C and C++, it needs to be highly efficient, and
if 
 the garbage collector isn't up to snuff, that's going to be a big problem. I'm 
 not looking to complain about the current garbage collector - I really don't 
 know how good or bad it is - but if it is rather poor (as I've gotten the 
 impresison that it is - at least in some respects - from various discussions
on 
 it here), then I'd assume that it needs a major overhaul or replacement at
some 
 point. So, are there any specific plans with regards to that, or is that just 
 something that may be considered in the future?
 
 - Jonathan M Davis

Jul 15 2010
parent reply Bane <branimir.milosavljevic gmail.com> writes:
Anyway, I'm here bitching myself :) Just want to say that idea to have more
than one GC type to chose when compiling would be very interesting thing, if
single implementation can't be good for all cases.

 If I had to chose one topic with most bitchin' on this newsgroup I have
impression it would be the one about GC. They usually goes from 'GC managed
programs are slow, D ain't good enough', to 'language X has better GC than D',
to ' GC that D has is bad at Z'.
 
 Why not make D summer of code - write your own GC optimized for special case
of XYZ, send it, bundle all up in D with compiler switch '--useGC=XYZ'. That is
only way to really compare what is best for special case.
 

Jul 15 2010
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Bane (branimir.milosavljevic gmail.com)'s article
 Anyway, I'm here bitching myself :) Just want to say that idea to have more
than

implementation can't be good for all cases.
 If I had to chose one topic with most bitchin' on this newsgroup I have


programs are slow, D ain't good enough', to 'language X has better GC than D', to ' GC that D has is bad at Z'.
 Why not make D summer of code - write your own GC optimized for special case


only way to really compare what is best for special case.


If/when we have enough manpower to write/maintain multiple GC's, here are some GC designs that can be either optimizations or pessimizations depending on use case: 1. Precise heap scanning (i.e. in the absence of copying/heap compaction). If you allocate mostly small objects, you're probably very seldom bitten by false pointers and the O(1) overhead per block needed to store type info may be significant. If you allocate mostly large objects, you've probably been eaten alive by false pointers and the O(1) per block overhead is negligible to you. 2. Concurrent collection. If you use threads for concurreny/latency reasons, this can be a boon. If you use threads for parallelism/throughput reasons, or write single-threaded code, this is a complete waste. 3. Thread local allocators. Quite simply, it's a space-speed tradeoff, and it depends which is more important to you.
Jul 15 2010
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Leandro Lucarella (luca llucax.com.ar)'s article
 dsimcha, el 15 de julio a las 19:23 me escribiste:
 == Quote from Bane (branimir.milosavljevic gmail.com)'s article
 Anyway, I'm here bitching myself :) Just want to say that idea to have more
than

implementation can't be good for all cases.
 If I had to chose one topic with most bitchin' on this newsgroup I have


programs are slow, D ain't good enough', to 'language X has better GC than D', to ' GC that D has is bad at Z'.
 Why not make D summer of code - write your own GC optimized for special case


only way to really compare what is best for special case.


If/when we have enough manpower to write/maintain multiple GC's, here are some GC designs that can be either optimizations or pessimizations depending on use case: 1. Precise heap scanning (i.e. in the absence of copying/heap compaction). If you allocate mostly small objects, you're probably very seldom bitten by false pointers and the O(1) overhead per block needed to store type info may be significant. If you allocate mostly large objects, you've probably been eaten alive by false pointers and the O(1) per block overhead is negligible to you. 2. Concurrent collection. If you use threads for concurreny/latency reasons, this can be a boon. If you use threads for parallelism/throughput reasons, or write single-threaded code, this is a complete waste.

multi-threaded and uses more than 1 core. In that case, a concurrent GC could improve the overall performance of the application.

In theory. I thought that in practice concurrent GC's (I'm not talking about the case of thread-local heaps) are always slower throughput-wise than stop-the-world.
Jul 15 2010
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Thu, 15 Jul 2010 21:34:36 +0300, Bane  
<branimir.milosavljevic gmail.com> wrote:

 Why not make D summer of code - write your own GC optimized for special  
 case of XYZ, send it, bundle all up in D with compiler switch  
 '--useGC=XYZ'. That is only way to really compare what is best for  
 special case.

In D1, the garbage collector is actually compiled to a stand-alone library, but then it's statically linked into Phobos. If you edit the Phobos makefile a bit, you should then be able to specify the GC .lib to link to on the compiler/linker command-line. In D2 it looks like the GC is clumped together with the runtime. -- Best regards, Vladimir mailto:vladimir thecybershadow.net
Jul 15 2010
prev sibling next sibling parent Leandro Lucarella <luca llucax.com.ar> writes:
Bane, el 15 de julio a las 14:34 me escribiste:
 If I had to chose one topic with most bitchin' on this newsgroup
 I have impression it would be the one about GC. They usually goes from
 'GC managed programs are slow, D ain't good enough', to 'language
 X has better GC than D', to ' GC that D has is bad at Z'.
 
 Why not make D summer of code - write your own GC optimized for
 special case of XYZ, send it, bundle all up in D with compiler switch
 '--useGC=XYZ'. That is only way to really compare what is best for
 special case.

The GC I'm working on is configurable at startup (runtime) via environment variables. The idea is to be able to tune the GC for different programs without even recompiling. I already made the actual compile time options for memory stomping and sentinel configurable at runtime and it works great, there is no noticeable performance penalty when you don't use them either. I think this is really the way to go. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ---------------------------------------------------------------------- Los pobres buscan su destino. Acá está; ¿no lo ven? -- Emilio Vaporeso. Marzo de 1914
Jul 15 2010
prev sibling next sibling parent Leandro Lucarella <luca llucax.com.ar> writes:
dsimcha, el 15 de julio a las 19:23 me escribiste:
 == Quote from Bane (branimir.milosavljevic gmail.com)'s article
 Anyway, I'm here bitching myself :) Just want to say that idea to have more
than

implementation can't be good for all cases.
 If I had to chose one topic with most bitchin' on this newsgroup I have


programs are slow, D ain't good enough', to 'language X has better GC than D', to ' GC that D has is bad at Z'.
 Why not make D summer of code - write your own GC optimized for special case


only way to really compare what is best for special case.


If/when we have enough manpower to write/maintain multiple GC's, here are some GC designs that can be either optimizations or pessimizations depending on use case: 1. Precise heap scanning (i.e. in the absence of copying/heap compaction). If you allocate mostly small objects, you're probably very seldom bitten by false pointers and the O(1) overhead per block needed to store type info may be significant. If you allocate mostly large objects, you've probably been eaten alive by false pointers and the O(1) per block overhead is negligible to you. 2. Concurrent collection. If you use threads for concurreny/latency reasons, this can be a boon. If you use threads for parallelism/throughput reasons, or write single-threaded code, this is a complete waste.

Not completely, if you have a multi-core, suddenly your program becomes multi-threaded and uses more than 1 core. In that case, a concurrent GC could improve the overall performance of the application. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ---------------------------------------------------------------------- - Tata Dios lo creó a usté solamente pa despertar al pueblo y fecundar las gayinas. - Otro constrasentido divino... Quieren que yo salga de joda con las hembras y después quieren que madrugue. -- Inodoro Pereyra y un gallo
Jul 15 2010
prev sibling parent Michael Rynn <michaelrynn optusnet.com.au> writes:
On Thu, 15 Jul 2010 00:18:38 -0700, Jonathan M Davis wrote:

 Okay. I really don't know much about garbage collectors, how they work,
 or what makes one particularly good or bad

Me too. But its a central part of the D langauge, its design and runtime. Even though D programmmers can replace allocators and do manual memory management, I would like to know if anyone has tried to do this in a big way. Without GC, programming with the DPL would be a different beast. It would seem to me that type information, GC design, memory allocation schemes are by dependence necessarily integrated together to try to get efficient performance. There must be loads of academic research projects done on this already, that would show what the trade-offs are. The first thing I notice is that memory blocks allocated by GC are either marked as either needing to be checked or are not checked at all. As far as I know there is no futher refining meta data, for instance a list of 32/64 bit offsets which can be excluded or included for being pointers to data. Such a list would be of the form [offset-array length, exclusive/inclusive], offset1, offset2, offsetn. Its slower code to walk through such list than the method of the current GC, which from my remembrance of an earlier newsgroup post, just bit-ands every value to see if looks like a memory aligned address or not. Having the option of a more careful check may resolve the residual cases. There is a trade off between the amount of information available to the GC, and how effective it will be. More information also means a cost of attaching another pointer for the information to each memory block type, with implications on how the memory blocks might be pooled. I read that the .NET garbage collector uses much more complete metadata stored in the assembly to know what part of objects contain addresses. I am sure its a state of the art GC, but I know nothing of its guts. So the GC depends on how the D compiler may compile in a accessible memory descriptor it to each typeinfo, type allocation pool, and integrate this into the runtime allocation design and memory block scanning. This gives the GC an option of resolving the harder cases of false pointers for objects not released by the conservative scan which does not use type information. Without the type information, the GC and memory allocation experimenter is limited to a reduced subset of models and algorithms, and so the possibility of having a choice of something better than the Boehm conservative collector (I think it actually can use some form of meta data), is restricted. -->= -->=
Jul 18 2010