"Craig Black" <cblack@ara.com> skrev i en meddelelse news:d1d0dg$21fn$1@digitaldaemon.com...
> Gotcha.  Well, if you want to improve performance, it might help to use reference counting, and completely remove the sweep.  I don't see any drawback to this approach, except that an extra integer must be included in each object.

In some cases it would inprove performance, and in some cases it will not. Constantly keeping the reference counts up-to-date are expensive too, and in many cases a garbage collector performs betters. There have been many studies on this subject, but I'm not sure of any final conclusion. There are many forms of garbage collection, and reference counting can be optimized too. For example, you don't need to adjust the reference count as long as you (the compiler) are sure the reference count does not reach zero. However, the major drawback of reference counting is its lack of ability to reclaim cyclic structures that are no longer used. So, the optimal solution depends on the application, and it might even be a combination. But the language is not targeted any single application. It needs to provide a good trade-off for most applications, and with the problem of cyclic references in mind, garbage collection seems a viable choice, and is proven to work well in other languages (with some exceptions).

Regards,
Martin

"Craig Black" <cblack@ara.com> wrote in message news:d1csh0$1t53$1@digitaldaemon.com...
>> The current D GC tries to reuse collected memory in-place before
>> allocating
>> another page, so it is pretty efficient with memory resources, which IMHO
>> will
>> probably also translate into faster running programs from start to
>> finish,
>> especially in high-load environments, etc. The current GC doesn't really
>> seem to
>> fragment that much, or at least when it does it's likely over contigous
>> blocks
>> in the same area of memory - which will likely be used the next time any
>> reasonable sized (<= 2K) object(s) are allocated.
>
> Let me get this straight.  The GC allocates units until it runs out of space.  When it runs out of space, it makes a pass (sweep) to collect units that have no reference.  Is this correct?
>

Well, it does a 'mark' then a 'sweep'. The mark sets a flag and the sweep acts on it. The whole reason the 'mark' is required is because of the 'circular reference' issue that has always been a problem with Ref. Counting. I suspect that having the ref. count updated repeatedly for every object could also end up being pretty expensive - each of those updates would always have to be sychronized for thread-safety.

Also, to do the ref. counting, you'd need the GC internals to be closely coupled with the compiler, which would make the latter harder to implement and make it really tough to 'plug-in' new GC code.

> If this is so, why is a sweep even required?  When a reference is set to zero, couldn't D just record that the unit is lost right then?  Why can't this be done deterministically?  Wouldn't this be faster?
>
>> On the other end, another advantage of the current design is that
>> auto-collection is attempted only when needed to fulfill a new request
>> for the
>> size of the object being allocated. This should make it suitable for
>> interactive
>> apps. (rather than some other type of 'stop-and-move-the-world'
>> algorithm).
>>
>> The price paid with the current D GC is speed of allocation of many small
>> objects in a tight loop. I'm wondering out loud here if maybe the best
>> all-around-gc strategy going forward would be to somehow optimize the
>> current
>> algorithm (or a type-aware one much like it) to allocate smaller objects
>> faster?
>> Ironically, the best way to do that may be to find some way to optimize
>> the
>> collection part of the cycle.
>>
>> Your idea in the OP would seem to nail the allocation speed problem, at
>> least
>> until the first full collection is needed. But as previously mentioned
>> we'd
>> almost certainly have to pay for it somewhere, like in longer GC related
>> pauses.
>
> I cannot deny that my approach could cause GC pauses when the buffers resize, but this would happen very infrequently.
>
>> A different set of eyes (yours) going through and profiling the current
>> GC code
>> may well be worth it.
>
> I would like to help however I can, but my understanding of the D's GC is elementary.  I don't currently understand why there even needs to be a "sweep".
>
> -Craig
> 

> In some cases it would inprove performance, and in some cases it will not. Constantly keeping the reference counts up-to-date are expensive too, and in many cases a garbage collector performs betters. There have been many studies on this subject, but I'm not sure of any final conclusion. There are many forms of garbage collection, and reference counting can be optimized too.  For example, you don't need to adjust the reference count as long as you (the compiler) are sure the reference count does not reach zero. However, the major drawback of reference counting is its lack of ability to reclaim cyclic structures that are no longer used. So, the optimal solution depends on the application, and it might even be a combination. But the language is not targeted any single application. It needs to provide a good trade-off for most applications, and with the problem of cyclic references in mind, garbage collection seems a viable choice, and is proven to work well in other languages (with some exceptions).
>
> Regards,
> Martin
>

I don't see the problem with updating a reference count when a reference changes.  This to me is a very small price to pay, along the same lines as D's initializing variables with default values.  Clue me in on how this could ever be a bottleneck.

Garbage collection on the other hand has a huge effect on performance.  We are not talking about incrementing or decrement a integer here.  This is evident by the fact that garbage collectors often cause applications to pause for a moment.  I'm not against garbage collection, but I don't think it's necessary if it's not compacting memory and enhancing performance.

Circular references are indeed a problem with reference counting.  However, they can always be avoided if one is a careful programmer.  Thus, we have a trade-off between convenience and performance.  Since I am a careful programmer, and confident that I can avoid circular references, I would rather have the performance.  The GC sweep seems to be such a large price to pay just for handling circular references.

-Craig

> Well, it does a 'mark' then a 'sweep'. The mark sets a flag and the sweep acts on it. The whole reason the 'mark' is required is because of the 'circular reference' issue that has always been a problem with Ref. Counting. I suspect that having the ref. count updated repeatedly for every object could also end up being pretty expensive - each of those updates would always have to be sychronized for thread-safety.

I never understood why reference counting would be a performance problem. Incrementing and decrementing an integer can be performed rather quickly. Is sychronization the problem?  I do not know the performance overhead of synchronizing a method.

> Also, to do the ref. counting, you'd need the GC internals to be closely coupled with the compiler, which would make the latter harder to implement and make it really tough to 'plug-in' new GC code.

I disagree.  The compiler could be written to facilitate new GC stuff.  This is the beauty of modular and object-oriented programming.

-Craig

"Craig Black" <cblack@ara.com> skrev i en meddelelse news:d1d7va$28aa$1@digitaldaemon.com...
> I don't see the problem with updating a reference count when a reference changes.  This to me is a very small price to pay, along the same lines as D's initializing variables with default values.  Clue me in on how this could ever be a bottleneck.

I believe reference counting is more expensive than initialization because initialization is done once per object, whereas reference counting is done a potential endless number of times. Also, reference counting suffers from the locality-of-reference problem.

> Garbage collection on the other hand has a huge effect on performance.  We are not talking about incrementing or decrement a integer here.  This is evident by the fact that garbage collectors often cause applications to pause for a moment.  I'm not against garbage collection, but I don't think it's necessary if it's not compacting memory and enhancing performance.

It depends on the application. For example, a compiler that simply compiles its input and exit might never need a single collection, and have thereby eliminated the overhead completely. I suspect Walter to be a bit biased because of this combined with his background :-) Anyway, this example is as good as yours pointing in the opposite direction.

The problem with the pause is a problem for real-time applications, and a threading garbage collector can overcome that problem. So that is not really an issue.

> Circular references are indeed a problem with reference counting. However, they can always be avoided if one is a careful programmer.

Sure they can. But problems that are cyclic in nature, are best expressed using cyclic data structures. I would not consider it careful not to do that, but a hack to overcome some specific problem.

> Thus, we have a trade-off between convenience and performance.  Since I am a careful programmer, and confident that I can avoid circular references, I would rather have the performance.  The GC sweep seems to be such a large price to pay just for handling circular references.

Well, some feel that memory management is too important an issue to leave to the compiler. You seems to be one of them. Other feel that memory management is too important an issue to leave to the programmer. I don't have an oppinion on this if not confronted with a specific case, but using a garbage collector provides the best protection for the programmer for not shooting himself in the foot, and therefore is a good default choice within the language like D.

Regards,
Martin

"Craig Black" <cblack@ara.com> skrev i en meddelelse news:d1d1v5$22ri$1@digitaldaemon.com...
> Yes, similar to a copying GC, except that the objects are separated into buffers depending on the size of the object.  This facilitates easy compacting within buffers that is performed each time an object is deallocated.

It reminds me:

I believe that the BSD variants of UNIX uses a concept like this for malloc() and friends. Allocation sizes are rounded to the next power of two, and there is therefore only a small number of real allocation sizes, and a great potential for reuse. It is fast, but is also wastes 25% memory on average due to internal fragmentation.

Regards,
Martin

In article <d1d8ge$28qg$1@digitaldaemon.com>, Craig Black says...
>
>I never understood why reference counting would be a performance problem. Incrementing and decrementing an integer can be performed rather quickly. Is sychronization the problem?  I do not know the performance overhead of synchronizing a method.

Lock-based synchronization requires a couple hundred extra CPU cycles.  Lockless synchronization tends to have far less overhead, but still forces a cache sync between CPUs.

>> Also, to do the ref. counting, you'd need the GC internals to be closely coupled with the compiler, which would make the latter harder to implement and make it really tough to 'plug-in' new GC code.
>
>I disagree.  The compiler could be written to facilitate new GC stuff.  This is the beauty of modular and object-oriented programming.

The nice thing about reference counting is that performance is smoother over the run of the application, but I have a feeling the overall cost is comparable to a typical mark/scan garbage collector.  And reference counting is more complex to implement.  So long as an application can control the GC to some degree, I don't think having collection cycles should be an issue--you could always fire a time-bound collection cycle during an idle period.


Sean

"Martin M. Pedersen" <martin@moeller-pedersen.dk> wrote in message news:d1d9qd$2adb$1@digitaldaemon.com...
> "Craig Black" <cblack@ara.com> skrev i en meddelelse news:d1d7va$28aa$1@digitaldaemon.com...
>> I don't see the problem with updating a reference count when a reference changes.  This to me is a very small price to pay, along the same lines as D's initializing variables with default values.  Clue me in on how this could ever be a bottleneck.
>
> I believe reference counting is more expensive than initialization because initialization is done once per object, whereas reference counting is done a potential endless number of times. Also, reference counting suffers from the locality-of-reference problem.

I disagree, reference counting is not done that often.  Only when references are assigned or nullified.  However, I do see a potential issue with thread synchronization.  I just realized that reference counting must be synchronized to be thread safe, but I'm not sure how much this affects performance.  Do you know?

I'm not familiar with the term "locality-of reference".  Could you clue me in?

>> Garbage collection on the other hand has a huge effect on performance. We are not talking about incrementing or decrement a integer here.  This is evident by the fact that garbage collectors often cause applications to pause for a moment.  I'm not against garbage collection, but I don't think it's necessary if it's not compacting memory and enhancing performance.
>
> It depends on the application. For example, a compiler that simply compiles its input and exit might never need a single collection, and have thereby eliminated the overhead completely. I suspect Walter to be a bit biased because of this combined with his background :-) Anyway, this example is as good as yours pointing in the opposite direction.
>
> The problem with the pause is a problem for real-time applications, and a threading garbage collector can overcome that problem. So that is not really an issue.
>
>> Circular references are indeed a problem with reference counting. However, they can always be avoided if one is a careful programmer.
>
> Sure they can. But problems that are cyclic in nature, are best expressed using cyclic data structures. I would not consider it careful not to do that, but a hack to overcome some specific problem.

You can still use cyclic data structures.  Just be careful how you deallocate them. GC does not solve the problem of memory leak.  It only prevents dangling pointers.  Programmers must always be careful of potential memory leak issues, so requiring programmers to be aware of the problem of circular references is not that big of a deal IMO.

>> Thus, we have a trade-off between convenience and performance.  Since I am a careful programmer, and confident that I can avoid circular references, I would rather have the performance.  The GC sweep seems to be such a large price to pay just for handling circular references.
>
> Well, some feel that memory management is too important an issue to leave to the compiler. You seems to be one of them. Other feel that memory management is too important an issue to leave to the programmer. I don't have an oppinion on this if not confronted with a specific case, but using a garbage collector provides the best protection for the programmer for not shooting himself in the foot, and therefore is a good default choice within the language like D.

A matter of opinion.  Fair enough.

-Craig

In article <d1d8ge$28qg$1@digitaldaemon.com>, Craig Black says...
>
>> Well, it does a 'mark' then a 'sweep'. The mark sets a flag and the sweep acts on it. The whole reason the 'mark' is required is because of the 'circular reference' issue that has always been a problem with Ref. Counting. I suspect that having the ref. count updated repeatedly for every object could also end up being pretty expensive - each of those updates would always have to be sychronized for thread-safety.
>
>I never understood why reference counting would be a performance problem. Incrementing and decrementing an integer can be performed rather quickly. Is sychronization the problem?  I do not know the performance overhead of synchronizing a method.
>

Yes, this can be relatively expensive. In the Java world, I've often seen different recommendations on which classes/algorithms to use depending on if you need single-threaded speed or multi-threaded synchronization.

Not only that, but RC has to go on constantly as the state of any reference changes, which means that it's hard to ever get 'peak performance' without the GC mechanism getting in the way when using any kind of reference types. This means smooth operation (no noticable pauses of different length), but there is often some GC related overhead going on.

>> Also, to do the ref. counting, you'd need the GC internals to be closely coupled with the compiler, which would make the latter harder to implement and make it really tough to 'plug-in' new GC code.
>
>I disagree.  The compiler could be written to facilitate new GC stuff.  This is the beauty of modular and object-oriented programming.
>

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.

>-Craig
>
>

Craig Black wrote:

> "Martin M. Pedersen" <martin@moeller-pedersen.dk> wrote in message news:d1d9qd$2adb$1@digitaldaemon.com...
> 
>>"Craig Black" <cblack@ara.com> skrev i en meddelelse news:d1d7va$28aa$1@digitaldaemon.com...
>>
>>>I don't see the problem with updating a reference count when a reference changes.  This to me is a very small price to pay, along the same lines as D's initializing variables with default values.  Clue me in on how this could ever be a bottleneck.
>>
>>I believe reference counting is more expensive than initialization because initialization is done once per object, whereas reference counting is done a potential endless number of times. Also, reference counting suffers from the locality-of-reference problem.
> 
> 
> I disagree, reference counting is not done that often.  Only when references are assigned or nullified.  However, I do see a potential issue with thread synchronization.  I just realized that reference counting must be synchronized to be thread safe, but I'm not sure how much this affects performance.  Do you know?
> 

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'.

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.

-David