> Reference counting is done every time an object is placed on the stack or passed to an external function.  If you add up all the increments and decrements its almost always more expensive for a non trivial program than simply collecting when its needed.  Not to mention the cyclical reference issue which is not a problem with other methods which actually 'collect'.

I don't see why passing a reference to a function requires the reference to be incremented.  I know this sounds redundant, but just pass the reference by reference.

> The 'stop the world' slowdown issue only happens when you allocate. Most time sensitive programs do not (have to) allocate when the sensitive stuff is going on anyhow.  Reference counting would be a big step backwards, imo.

How is it a step backwards when it adds capability and performance?  You can do more with reference counting than you can with single references. Further, you can use a sweep with reference counting just like with single references to eliminate circular references.  Java and C# both do this.  I think the sweep should be a compile option.

-Craig

> One of the goals of the D language is to make it simpler to implement a
> compiler
> than C++ (yet still high performance, and attractive to non-gurus). IMHO,
> at
> this early stage it would not be productive to "marry" the GC algorithm
> with the
> reference compiler, especially with a RefCount GC that requires non-gurus
> to
> avoid/hunt-down circular references.
>
> D is kind-of in a league of it's own here - a natively compiled,
> high-performance, imperitive language combining garbage collection with
> malloc/free and RAII that aims to be safer, simpler and more intuitive to
> use
> than C/++. The reference compiler and GC need to stay as flexible as
> possible
> IMHO.
>
> This is a good and timely discussion - glad you brought it up.

Perhaps reference counting, mark and sweep, etc. can be GC options.  Perhaps there can be different optional GC's for D.  I know that is asking a lot, but it would be very cool.  Then you could test one GC approach against another and evaluate the results.

-Craig

> Perhaps reference counting, mark and sweep, etc. can be GC options.
> Perhaps
> there can be different optional GC's for D.  I know that is asking a lot,
> but it would be very cool.  Then you could test one GC approach against
> another and evaluate the results.

It isn't hard to hack up phobos to plug in a different collector - you just need to obey the same API (roughly 6 functions or so I think) as the standard collector. I tried this last year with plugging in the boehm collector and testing out some of its features (like incremental collection). Poke around with the files in src/phobos/internal/gc. Plugging in a reference counting mechanism might be non-trivial, though, since the API is not the same as the standard collector (for example think about the role of destructors in the standard GC vs a reference-counted GC). If you do experiment with different collectors I'd be interested in hearing about what you discover.

In article <d1esok$1744$1@digitaldaemon.com>, Craig Black says...
>
>> One of the goals of the D language is to make it simpler to implement a
>> compiler
>> than C++ (yet still high performance, and attractive to non-gurus). IMHO,
>> at
>> this early stage it would not be productive to "marry" the GC algorithm
>> with the
>> reference compiler, especially with a RefCount GC that requires non-gurus
>> to
>> avoid/hunt-down circular references.
>>
>> D is kind-of in a league of it's own here - a natively compiled,
>> high-performance, imperitive language combining garbage collection with
>> malloc/free and RAII that aims to be safer, simpler and more intuitive to
>> use
>> than C/++. The reference compiler and GC need to stay as flexible as
>> possible
>> IMHO.
>>
>> This is a good and timely discussion - glad you brought it up.
>
>Perhaps reference counting, mark and sweep, etc. can be GC options.  Perhaps there can be different optional GC's for D.  I know that is asking a lot, but it would be very cool.  Then you could test one GC approach against another and evaluate the results.
>
>-Craig
>

That was one of the aims, I think, of the current GC interface design. 'Pluggable' GC's. Frankly, the hardest to plug-in would probably be ref. counting and I suspect that making the interface RC compatible wasn't a priority because vendors, computer science and even large-scale system architects (eg: Net) seem to be running away from RC GC schemes. Here's a great book on GC recommended by the creator of D (Walter Bright):

http://www.amazon.com/exec/obidos/ASIN/0471941484/qid=1111167957/sr=2-1/ref=pd_bbs_b_2_1/102-3668383-6538501

Mess around with the phobos (D's runtime library) make files a little and you could get a minimal runtime that doesn't even include the GC - and you'd basically use class de/allocators and such to get a 'clean and lite' C++ if you wanted OOP and really light executables. That's another real good and pragmatic reason to not couple the GC with the compiler, especially if you want D to be attractive for use in real-time and/or embedded systems.

One of the terrific things about D is the variety in how to manage memory, which can be customized for the job at hand. Spending a huge amount of resources optimizing the GC becomes less important because its performance doesn't ever have to be a show-stopper, like it can be with Java and other GC-only languages. I you had to describe the intent behind the design of D with one word, the best would probably be "pragmatic".

http://digitalmars.com/d/memory.html

That said - I think a better GC is possible and should be written sooner rather than later (after D v1.0 is out that is) and - as you suggested - a variety of good GC's to choose from would of course be the best of all worlds.

- Dave

Craig Black wrote:
>>Reference counting is done every time an object is placed on the stack or passed to an external function.  If you add up all the increments and decrements its almost always more expensive for a non trivial program than simply collecting when its needed.  Not to mention the cyclical reference issue which is not a problem with other methods which actually 'collect'.
> 
> 
> I don't see why passing a reference to a function requires the reference to be incremented.  I know this sounds redundant, but just pass the reference by reference.
> 

Think arrays, slices and multithreaded programs.   If I access any part of an array of objects I must inc/dec references to the object I am accessing.  A Slice is even bigger kettle of fish.  I must addref to the array itself, then addref all the objects contained within.

Multithreaded race conditions for this sort of thing are well documented.  for a quick example:

// assume objectA.refs == 2
DecRef( objectA ); // objectA.refs == 1
<--- another thread jumps in, calls DecRef(objectA),  frees it
if ( Ref( objectA )==0 ) // whoops!
{
  free( objectA );
}

> 
>>The 'stop the world' slowdown issue only happens when you allocate. Most time sensitive programs do not (have to) allocate when the sensitive stuff is going on anyhow.  Reference counting would be a big step backwards, imo.
> 
> 
> How is it a step backwards when it adds capability and performance?  You can do more with reference counting than you can with single references. Further, you can use a sweep with reference counting just like with single references to eliminate circular references.  Java and C# both do this.  I think the sweep should be a compile option.
> 
> -Craig 
> 
> 
You say that you can use a sweep with reference counting?  Then what does it buy you?  If you include sweep options when memory runs out, then you still have to touch all the objects, but now have the IncRef/Deref cost all over the place (with its attached complexity).

How exactly does it add capability and performance?  As I posted a memory allocation is simply a heap pointer decrement (1 cycle).  With RC all references to an object entails +1 cycle minimum. Most programs have a fairly large set of 'stable' objects and smaller numbers of short-lived ones.  This is precisely why generational collectors exist.

A deallocation (currently) is 0 cycles if you let the collector call it for you when a collection occurs.  In C++ you _must_ call delete. In D the destructor could even be called in a deallocation thread.

Running short of memory will _always_ entail some performance cost(human and machine time), so I still don't see any improvement.

If reference counting is a good thing, don't you think it would be more widespread?

"Java and C# both do this."
Java has never used Reference counting. It was initially mark and sweep, now uses a generational(optional incremental) collector.

(Sorry if any of this sounds like flaming, its not intended)
-David

> You say that you can use a sweep with reference counting?  Then what does it buy you?  If you include sweep options when memory runs out, then you still have to touch all the objects, but now have the IncRef/Deref cost all over the place (with its attached complexity).
>
> How exactly does it add capability and performance?  As I posted a memory allocation is simply a heap pointer decrement (1 cycle).  With RC all references to an object entails +1 cycle minimum. Most programs have a fairly large set of 'stable' objects and smaller numbers of short-lived ones.  This is precisely why generational collectors exist.
>
> A deallocation (currently) is 0 cycles if you let the collector call it for you when a collection occurs.  In C++ you _must_ call delete. In D the destructor could even be called in a deallocation thread.
>
> Running short of memory will _always_ entail some performance cost(human and machine time), so I still don't see any improvement.
>
> If reference counting is a good thing, don't you think it would be more widespread?
>
> "Java and C# both do this."
> Java has never used Reference counting. It was initially mark and sweep,
> now uses a generational(optional incremental) collector.
>
> (Sorry if any of this sounds like flaming, its not intended)
> -David

No offence taken.  I find this conversation quite stimulating.  I'm learning a lot.  In fact, I take back most of what I said in the last post.  I thought about it, and Java and C# do NOT use reference counting.  But they allow multiple references to a single object.  They do so using a GC.

Does D support multiple references to a single object?  I am under the impression that you can only have a single reference to an object and if you want another reference then you have to make a copy.  I could be wrong about this, but if I am right, I think that this is limiting, especially when Java and C# both currently support multiple referencing.

I think I see now why reference counting is not used.  However, I still think GC can be improved using compacting.

-Craig

How hard do ya'll think it would be to implement a compacting GC?

-Craig

Ben - what were your experiences with the Boehm GC when you plugged it in (performance wise, etc..)?

Thanks,

- Dave

"Ben Hinkle" <bhinkle@mathworks.com> wrote in message news:d1etcr$17li$1@digitaldaemon.com...
>
>> Perhaps reference counting, mark and sweep, etc. can be GC options.
>> Perhaps
>> there can be different optional GC's for D.  I know that is asking a lot,
>> but it would be very cool.  Then you could test one GC approach against
>> another and evaluate the results.
>
> It isn't hard to hack up phobos to plug in a different collector - you just need to obey the same API (roughly 6 functions or so I think) as the standard collector. I tried this last year with plugging in the boehm collector and testing out some of its features (like incremental collection). Poke around with the files in src/phobos/internal/gc. Plugging in a reference counting mechanism might be non-trivial, though, since the API is not the same as the standard collector (for example think about the role of destructors in the standard GC vs a reference-counted GC). If you do experiment with different collectors I'd be interested in hearing about what you discover.
> 

"Dave" <Dave_member@pathlink.com> wrote in message news:d1fvsd$2lv1$1@digitaldaemon.com...
> Ben - what were your experiences with the Boehm GC when you plugged it in (performance wise, etc..)?
>
> Thanks,
>
> - Dave

I think Boehm did better on the test that came with boehm (something about allocating trees in a certain pattern) and dmd did better on the word-count tests or tests where I added and removed tons of items from an AA. I should dig that stuff up - assuming I can find it. There wasn't a clear winner from what I remember.

Note Ares would probably be a good place to look for a base for plug-n-play GC http://dsource.org/forums/viewforum.php?f=31

In article <d1g1c7$2nfi$1@digitaldaemon.com>, Ben Hinkle says...
>
>Note Ares would probably be a good place to look for a base for plug-n-play GC http://dsource.org/forums/viewforum.php?f=31

I've made no attempt to clean up the GC interface so far, but Ares does a decent job of separating the language support code, the GC, and the standard library into separate units.  If anyone has input on GC refinements please let me know, as it's a task I've been putting off :)  Also, my integration work turned up an odd bug that I'd like to see fixed (around line 1422 of gcx.d).


Sean