> All of this would allow for a moving GC, but the GC would still be somewhat conservative because type information would still not be available for the stack (unless the app contained debug information, perhaps).

Is there a way to provide type information for the stack without hindering performance too badly?  Obviously it will be better if the GC has as much information as possible.

-Craig

bearophile wrote:
> Robert Fraser:
>> I've been wanting for a while to implement a different GC for D taking into account some of the stuff talked about in a few papers I read on non-moving GCs. IMO, D's GCs (Tango & Phobos) are pretty basic, they don't do any sort of sexy trickery.
> 
> I can see people in this newsgroup don't like to try to adapt already written code. Is this some bad from of NIH (Not Invented Here) syndrome? Maybe you can just take a 5-10-years old GC and adapt it, so we can avoid other 10 years of development and have a better GC soon (from your and other's comments I presume the Java GC can't be adapted to D, but other GCs may be found).
> 
> Note that ShedSkin uses the Bohem GC:
> http://www.hpl.hp.com/personal/Hans_Boehm/gc/
> From various tests it seems faster than the Phobos GC. Can't it be copied inside Phobos? It's well refined, well debugged, it doesn't leak, it has something like ten years of development, articles written on it, it's used often, etc. And it can be used from C too.
> 
> Bye,
> bearophile

I know it could be relatively easily plugged into Tango since Tango has a pluggable GC interface

bearophile wrote:
> Robert Fraser:
>> I've been wanting for a while to implement a different GC for D taking into account some of the stuff talked about in a few papers I read on non-moving GCs. IMO, D's GCs (Tango & Phobos) are pretty basic, they don't do any sort of sexy trickery.
> 
> I can see people in this newsgroup don't like to try to adapt already written code. Is this some bad from of NIH (Not Invented Here) syndrome? Maybe you can just take a 5-10-years old GC and adapt it, so we can avoid other 10 years of development and have a better GC soon (from your and other's comments I presume the Java GC can't be adapted to D, but other GCs may be found).
> 
> Note that ShedSkin uses the Bohem GC:
> http://www.hpl.hp.com/personal/Hans_Boehm/gc/
> From various tests it seems faster than the Phobos GC. Can't it be copied inside Phobos? It's well refined, well debugged, it doesn't leak, it has something like ten years of development, articles written on it, it's used often, etc. And it can be used from C too.

It would be trivial to plug the Boehm GC into Tango.  However, I'm not sure how much performance would benefit.  IIRC someone tested the Boehm GC with D a while back and it was actually slower than the one Walter wrote.


Sean

bearophile a écrit :
> Robert Fraser:
>> I've been wanting for a while to implement a different GC for D
>> taking into account some of the stuff talked about in a few papers
>> I read on non-moving GCs. IMO, D's GCs (Tango & Phobos) are pretty
>> basic, they don't do any sort of sexy trickery.
> 
> I can see people in this newsgroup don't like to try to adapt already
> written code. Is this some bad from of NIH (Not Invented Here)
> syndrome? Maybe you can just take a 5-10-years old GC and adapt it,
> so we can avoid other 10 years of development and have a better GC
> soon (from your and other's comments I presume the Java GC can't be
> adapted to D, but other GCs may be found).
> 
> Note that ShedSkin uses the Bohem GC: http://www.hpl.hp.com/personal/Hans_Boehm/gc/ From various tests it
> seems faster than the Phobos GC. Can't it be copied inside Phobos?
> It's well refined, well debugged, it doesn't leak,

I doubt that it truly doesn't leak: conservative GC may always leak depending on your program..

> it has something
> like ten years of development, articles written on it, it's used
> often, etc. And it can be used from C too.
> 
> Bye, bearophile

For the rest I agree: reuse is nice.

Regards,
renoX

On Mon, 10 Dec 2007 23:12:38 +0200, Sean Kelly <sean@f4.ca> wrote:

> The void[] thing is a language decision, not a runtime decision.  The runtimes for Phobos and Tango rely on TypeInfo.flags & 1 to determine whether a particular type contains pointers.  More exact type info for precise scanning would likely require a compiler change as well, since this would have to be added to TypeInfo.  All of this would allow for a moving GC, but the GC would still be somewhat conservative because type information would still not be available for the stack (unless the app contained debug information, perhaps).  So basically, any blocks pointed to from a location whose type is unknown, the block would effectively be pinned.

Ah, right.

Also, providing type information for the stack has already been discussed here. It's partially possible to do without much execution time overhead by storing the stack layout of a function's stack frame for every point in code somewhere. This requires that the GC have access to every stack frame in every thread, though - and it can't be done with a stack trace, because of non-D functions that D code might call.

Hmm. What if every time before D code calls non-D code, it saves a pointer to its stack frame into thread local storage (saving the previous pointer beforehand)? Then it would be possible for the GC to trace the function stack.

I think that this is definitely doable, but requires some thinking and work (and perhaps code change) :)

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com

Robert Fraser, el 10 de diciembre a las 13:32 me escribiste:
> Vladimir Panteleev wrote:
> >On Mon, 10 Dec 2007 22:48:00 +0200, Robert Fraser <fraserofthenight@gmail.com> wrote:
> >>FWIW, I don't think non-moving GCs will ever be able to outperform a well-tuned generational collector. But I'm not exactly in the know about these things, so I may be wrong.
> >I'm not sure if generational collectors are moving GCs, but since you're comparing them to non-moving GCs I'll add that a moving GC needs full knowledge of type information to work properly. While confusing an integer for a pointer may be a forgiveable mistake for non-moving GCs, it's not for a moving GC. I think D isn't ready for that yet (especially considered that both Phobos and Tango maintainers/users insist on void[] being a type that's allowed to hold pointers).
> 
> How would you make a non-moving generational GC? Isn't the idea of the generational GC that long-lived objects are moved into a separate part of memory?

Not exactly. Generation GCs are a particular case of parition based GCs. Their main feature is the posibility to perform a partial collection, instead of a full collection, making pause times smaller and, maybe increasing the cost/benefit ratio (recover as much as memory with the less processing time cost). You can make some tricks to avoid moving stuff (which might not be that performant, specially for generational collectors, but it can be done, and with some other types of partitional collectors could be very natural).

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
La máquina de la moneda, mirá como te queda!
	-- Sidharta Kiwi

Robert Fraser wrote:

> Vladimir Panteleev wrote:
>> On Mon, 10 Dec 2007 22:48:00 +0200, Robert Fraser <fraserofthenight@gmail.com> wrote:
>> 
>>> FWIW, I don't think non-moving GCs will ever be able to outperform a well-tuned generational collector. But I'm not exactly in the know about these things, so I may be wrong.
>> 
>> I'm not sure if generational collectors are moving GCs, but since you're comparing them to non-moving GCs I'll add that a moving GC needs full knowledge of type information to work properly. While confusing an integer for a pointer may be a forgiveable mistake for non-moving GCs, it's not for a moving GC. I think D isn't ready for that yet (especially considered that both Phobos and Tango maintainers/users insist on void[] being a type that's allowed to hold pointers).
>> 
> 
> How would you make a non-moving generational GC? Isn't the idea of the generational GC that long-lived objects are moved into a separate part of memory?

I don't believe so.  According to the all-knowing Wikipedia entry on GCs, generational GCs are frequently implemented by using difference sections of memory for each generation.  However, this doesn't seem to be necessary. The only things that "generational" GC implies is that memory chunks are lumped into difference categories according to age- the older ones are scanned less often.  Cross-generational references have to be given special attention, however.  I could see a D GC being generational yet non-moving by storing a generation marker at the begining of a memory chunk or some such such scheme instead of partitioning memory by age.

IANA GC expert, however, so please correct me if I'm wrong.

-- 
~John Demme
me@teqdruid.com

On Mon, 10 Dec 2007 21:34:20 -0000, Robert Fraser <fraserofthenight@gmail.com> wrote:

> bearophile wrote:
>> Robert Fraser:
>>> I've been wanting for a while to implement a different GC for D taking into account some of the stuff talked about in a few papers I read on non-moving GCs. IMO, D's GCs (Tango & Phobos) are pretty basic, they don't do any sort of sexy trickery.
>>  I can see people in this newsgroup don't like to try to adapt already written code. Is this some bad from of NIH (Not Invented Here) syndrome? Maybe you can just take a 5-10-years old GC and adapt it, so we can avoid other 10 years of development and have a better GC soon (from your and other's comments I presume the Java GC can't be adapted to D, but other GCs may be found).
>>  Note that ShedSkin uses the Bohem GC:
>> http://www.hpl.hp.com/personal/Hans_Boehm/gc/
>> From various tests it seems faster than the Phobos GC. Can't it be copied inside Phobos? It's well refined, well debugged, it doesn't leak, it has something like ten years of development, articles written on it, it's used often, etc. And it can be used from C too.
>>  Bye,
>> bearophile
>
> I know it could be relatively easily plugged into Tango since Tango has a pluggable GC interface

I thought D in general was supposed to have a pluggable GC interface. Isn't it
part of the language spec?

Bruce Adams wrote:
> On Mon, 10 Dec 2007 21:34:20 -0000, Robert Fraser <fraserofthenight@gmail.com> wrote:
> 
>> bearophile wrote:
>>> Robert Fraser:
>>>> I've been wanting for a while to implement a different GC for D taking into account some of the stuff talked about in a few papers I read on non-moving GCs. IMO, D's GCs (Tango & Phobos) are pretty basic, they don't do any sort of sexy trickery.
>>>  I can see people in this newsgroup don't like to try to adapt already written code. Is this some bad from of NIH (Not Invented Here) syndrome? Maybe you can just take a 5-10-years old GC and adapt it, so we can avoid other 10 years of development and have a better GC soon (from your and other's comments I presume the Java GC can't be adapted to D, but other GCs may be found).
>>>  Note that ShedSkin uses the Bohem GC:
>>> http://www.hpl.hp.com/personal/Hans_Boehm/gc/
>>> From various tests it seems faster than the Phobos GC. Can't it be copied inside Phobos? It's well refined, well debugged, it doesn't leak, it has something like ten years of development, articles written on it, it's used often, etc. And it can be used from C too.
>>>  Bye,
>>> bearophile
>>
>> I know it could be relatively easily plugged into Tango since Tango has a pluggable GC interface
> 
> I thought D in general was supposed to have a pluggable GC interface. Isn't it
> part of the language spec?

I don't think so.  The GC in Phobos does have some code in place that looks like it is meant to support run-time pluggability though.


Sean

bearophile Wrote:

> This tiny benchmark focus on GC performance and shows similar results to the "binary trees" benchmark I have shown here few weeks ago, but it's quite shorter, so it may be more useful. <

bearophile Wrote:

> This tiny benchmark focus on GC performance and shows similar results to the "binary trees" benchmark I have shown here few weeks ago, but it's quite shorter, so it may be more useful. <

On a Pentium 4 @ 3.00GHz the obj_test_ss.py version ran in the range 7.36 sec. to 7.54 sec. in three tests. The times are comparable to those of a P3 @ 500 Mhz. Maybe a bit slower: 6*7.54=45.24.

I would have thought that compiled C or D would be many times faster than shown in the test, but my expertise is slim in this area.

Jim Jennings