www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - draft proposal for ref counting in D

reply Walter Bright <newshound2 digitalmars.com> writes:
This is an email conversation we had last summer. It's of general interest, so 
reposted here with permission. We didn't reach any conclusions, but there's a 
lot of good stuff in here, and it's particularly relevant to other recent
threads.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
This is based on n.g. discussions and ideas from you guys. I'll redo it as a
DIP 
if it passes the smoke test from y'all.

----------------------------------------------------------------------
     Adding Reference Counting to D

D currently supports manual memory management and generalized GC.
Unfortunately, 
the pausing
and memory consumption inherent in GC is not acceptable for many programs, and 
manual
memory management is error-prone, tedious, and unsafe. A third style, reference 
counting (RC),
addresses this. Common implementations are COM's AddRef/Release, Objective-C's
ARC,
and C++'s shared_ptr<>.

None of these three schemes are guaranteed memory-safe, they all require the 
programmer
to conform to a protocol (even O-C's ARC). Stepping outside of the protocol 
results in
memory corruption. A D implementation must make it possible to use ref counted 
objects
in code marked as  safe, although it will be necessary for the implementation
of 
those
objects to be unsafe.

Some aspects of a D implementation are inevitable:

1. Avoid any requirement for more pointer types. This would cause drastic 
increases in
complexity for both the compiler and the user. It may make generic code much 
more difficult
to write.

2. Decay of a ref-counted pointer to a non-ref-counted pointer is unsafe, and 
can only
be allowed (in  safe code) in circumstances where it can be statically proven
to 
be safe.

3. A ref counted object is inherently a reference type, not a value type.

4. The compiler needs to know about ref counted types.


==Proposal==

If a class contains the following methods, in either itself or a base class, it
is
an RC class:


     T AddRef();
     T Release();

An RC class is like a regular D class with these additional semantics:

1. In  safe code, casting (implicit or explicit) to a base class that does not
have both AddRef() and Release() is an error.

2. Initialization of a class reference causes a call to AddRef().

3. Assignment to a class reference causes a call to Release() on its original
value
and AddRef() on the new value.

4. Null checks are done before calling any AddRef() or Release().

5. Upon scope exit of all RC variables or temporaries, a call to Release() is 
performed,
analogously to the destruction of struct variables and temporaries.

6. If a class or struct contains RC fields, calls to Release() for those fields
will
be added to the destructor, and a destructor will be created if one doesn't 
exist already.

7. If a closure is created that contains RC fields, either a compile time error 
will be
generated or a destructor will be created for it.

8. Explicit calls to AddRef/Release will not be allowed in  safe code.

9. A call to AddRef() will be added to any argument passed as a parameter.

10. Function returns have an AddRef() already done to the return value.

11. The compiler can elide any AddRef()/Release() calls it can prove are
redundant.

12. AddRef() is not called when passed as the implicit 'this' reference.

13. Taking the address of, or passing by reference, any fields of an RC object
is not allowed in  safe code. Passing by reference an RC field is allowed.

14. RC objects will still be allocated on the GC heap - this means that a normal
GC run will reap RC objects that are in a cycle, and RC objects will get 
automatically
scanned for heap references with no additional action required by the user.


==Existing Code==

D COM objects already have AddRef() and Release(). This proposal should not
break
that code, it'll just mean that there will be extra AddRef()/Release calls made.
Calling AddRef()/Release() should never have been allowed in  safe code anyway.

Any other existing uses of AddRef()/Release() will break.

==Arrays==

Built-in arrays have no place to put a reference count. Ref counted arrays
would 
hence
become a library type, based on a ref counted class with overloaded operators
for
the array operations.

==Results==

This is a very flexible approach, allowing for support of general RC objects,
as 
well
as specific support for COM objects and Objective-C ARC. AddRef()/Release()'s 
implementation
is entirely up to the user or library writer.

 safe code can be guaranteed to be memory safe, as long as AddRef()/Release() 
are correctly
implemented.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

Looks like a good start.

A few things:

1. Proposal point 3, you need to AddRef first, THEN Release the original.
Reason 
being, you could be assigning a reference the same value as before. In this 
case, if you decrement *first*, you will decrement the reference, which might 
reduce it to 0, and free the object before you increment.  In most cases, the 
AddRef and Release are elided, so it's not bad if you do this.

I wonder if it's not a good idea to have a RefAssign function that takes two RC 
objects and does a check to see if they are the same before doing AddRef and 
Release to help with this issue. Calls where the compiler can prove they are
the 
same value can be elided.

2. AddRef and Release should be treated not as function calls, but as
callables. 
That is, if for some reason AddRef and Release should be aliases, this does not 
detract from the solution. Only requirement should be that they cannot be UFCS, 
as that doesn't make any sense (one cannot add reference counting after the
fact 
to an object).

I'm thinking of the Objective-C objects, whose functions are "release" and 
"retain". It would be good to use the names Objective-C coders are used to.

3. Objective-C ARC uses a mechanism called auto-release pools that help cut
down 
on the release/retain calls. It works like this:

 autoreleasepool {  // create a new pool
      NSString *str = [NSString stringWithFormat: "an int: %d", 1];
       autoreleasepool { // create a new pool on the "pool stack"
            NSDate *date = [NSDate date];
            {
                NSDate *date2 = [NSDate date];
            }
      } // auto-release date and date2
} // auto-release str

In this way, it's not the pointer going out of scope that releases the object, 
it's the release pool going out of scope that releases the object. These
release 
pools themselves are simply RC objects that call release on all their objects 
(in fact, prior to the  autoreleasepool directive, you had to manually create 
and destroy these pools).

The benefit of this model is that basically, inside a pool, you can move around 
auto-released objects at will, pass them into functions, return them from 
functions, etc, without having to retain or release them for each assignment. 
It's kind of like a mini-GC.

It works by convention, that any function that returns a RC object:

if it's called 'new...' or 'init...' or 'alloc...' or 'copy...', then the
object 
is assumed returned with it's retain count incremented on behalf of the calling 
scope. This means, if you assign it to a member variable, for instance, you do 
not have to retain the object again, and if it goes out of scope, you must call 
release on it.

All other functions return 'auto-released' objects, or objects which have
queued 
in the latest auto release pool. The compiler knows this and can elide more of 
the releases and retains.

Would this be a mechanism that's worth putting in? I think it goes really well 
with something like TempAlloc.  I don't think we should use convention,
though...

-Steve
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 1:19 PM, Steven Schveighoffer wrote:
 Looks like a good start.

 A few things:

 1. Proposal point 3, you need to AddRef first, THEN Release the original. 

this case, if you decrement *first*, you will decrement the reference, which might reduce it to 0, and free the object before you increment. In most cases, the AddRef and Release are elided, so it's not bad if you do this. Yeah, I got that backwards, and I should know better.
 I wonder if it's not a good idea to have a RefAssign function that takes two 

Release to help with this issue. Calls where the compiler can prove they are the same value can be elided. I'd like to see how far we get with just AddRef/Release first, and getting the semantics of them right first.
 2. AddRef and Release should be treated not as function calls, but as 

this does not detract from the solution. Yes, just like the names for Ranges are used.
   Only requirement should be that they cannot be UFCS, as that doesn't make 

That would be covered by disallowing explicit calls to AddRef/Release in safe code.
 I'm thinking of the Objective-C objects, whose functions are "release" and 

AddRef/Release are the COM names. It's trivial to have one wrap the other. I picked AddRef/Release because I'm familiar with their semantics, and am not with O-C.
 3. Objective-C ARC uses a mechanism called auto-release pools that help cut 

  autoreleasepool {  // create a new pool
       NSString *str = [NSString stringWithFormat: "an int: %d", 1];
        autoreleasepool { // create a new pool on the "pool stack"
             NSDate *date = [NSDate date];
             {
                 NSDate *date2 = [NSDate date];
             }
       } // auto-release date and date2
 } // auto-release str

 In this way, it's not the pointer going out of scope that releases the 

release pools themselves are simply RC objects that call release on all their objects (in fact, prior to the autoreleasepool directive, you had to manually create and destroy these pools).
 The benefit of this model is that basically, inside a pool, you can move 

functions, etc, without having to retain or release them for each assignment. It's kind of like a mini-GC.
 It works by convention, that any function that returns a RC object:

 if it's called 'new...' or 'init...' or 'alloc...' or 'copy...', then the 

calling scope. This means, if you assign it to a member variable, for instance, you do not have to retain the object again, and if it goes out of scope, you must call release on it.
 All other functions return 'auto-released' objects, or objects which have 

more of the releases and retains.
 Would this be a mechanism that's worth putting in? I think it goes really 

though... I agree with not relying on convention. But also reserving the new*, init*, alloc* and copy* namespaces seems excessive for D. As for autoreleasepool, it is relying on a convention that its fields are not leaking. I don't see how we can enforce this.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
I have overlooked addressing what happens when you pass an RC ref to a pure 
function. Is the pure function allowed to call AddRef()/Release()? Not sure.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

That's a resounding yes.

Consider that this is allowed:

class X {}

struct S
{
    X foo;
    void setFoo(X newfoo) pure {foo = newfoo;}
}

If X is ref-counted, you HAVE to increment the ref count.

The only issue here is, ref counting may have to access global data.  But we 
already have exceptions for memory management, even for strong-pure functions.

-Steve

On Jun 25, 2013, at 4:48 PM, Walter Bright wrote:

 I have overlooked addressing what happens when you pass an RC ref to a pure 

Oct 09 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:


On Jun 25, 2013, at 4:44 PM, Walter Bright wrote:

 On 6/25/2013 1:19 PM, Steven Schveighoffer wrote:
 Would this be a mechanism that's worth putting in? I think it goes really 


though...
 I agree with not relying on convention. But also reserving the new*, init*, 

 As for autoreleasepool, it is relying on a convention that its fields are not 

I don't think the autoreleasepool is relying on convention, it's simply giving the compiler a way to elide careful tracking of temporaries' reference counts. It was definitely of more use when manual reference counting was done, because one only had to worry about retaining non-temporary data in that case. But the compiler can make the same optimizations (and does in the ARC version of Objective-C). Consider the following code: NSString *str = [NSString stringWithFormat: "%d", 5]; // translating to D, that would be something like: NSString str = NSString.stringWithFormat("%d", 5); stringWithFormat is a class method that gives you back a temporary string. You are not asserting ownership, you are just assigning to a variable. Now, if you wanted to do some fancy stuff with str, we could do: { NSString str2; { NSString str = NSString.stringWithFormat("%d", 5); if(condition) str2 = str; if(otherCondition) { NSString str3 = str; str = NSString.stringWithFormat("%d", 6); } } str2 = str; } Now, in all this mess, how is the compiler to sort out the AddRefs and Releases? Most likely, it will end up adding more than it needs to. But with autorelease pool, it's like you did this: AutoReleasePool arp; { NSString str2; { NSString str = NSString.stringWithFormat("%d", 5); arp.add(str); if(condition) str2 = str; if(otherCondition) { NSString str3 = str; str = NSString.stringWithFormat("%d", 6); arp.add(str); } } str2 = str; } arp.drain(); // releases both strings used, don't care what now-out-of-scope variables Essentially, they are only retained when created, and because they go out of scope, they are no longer needed. The compiler can surmise that because the fields aren't leaving the scope, it doesn't have to retain them. If it does see that, it adds a retain. Then, it can release them all at once. In fact, this could be done automatically, but you have to allocate a place to put these 'scheduled for release' things. In Cocoa, the main event loop has an auto release pool, and you can add them manually wherever you wish for more fine-grained memory management (that is, if you wanted to free objects before you left the event loop). Note that in Objective-C, they use those naming conventions to determine whether an object is auto-released or not. But we could make sure it's *always* auto-released, as we don't have the historical requirements that Objective-C has. The question is, does it make sense to use this technique to "lump together" deallocations instead of conservatively calling retain/release wherever you assign variables (like C++ shared_ptr)? And a further question is whether the compiler should pick those points, or whether they should be picked manually. -Steve
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
If autoreleasepull is just a handy way to lump together Release() calls, then 
that is quite unnecessary if the compiler inserts calls to Release() 
automatically. If it is, instead, a promise that members of autoreleasepull do 
not leak references outside of that object, then this is very problematic for D 
to guarantee such - and guarantee it it must. I.e. it's "escape analysis" in 
another disguise.

I think the compiler should pick where to put the Release() calls, that is the 
whole point of ARC. If the compiler can do sufficient escape analysis to 
determine that the calls can be elided, so much the better.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On Jun 25, 2013, at 5:28 PM, Walter Bright wrote:

 If autoreleasepull is just a handy way to lump together Release() calls, then 

automatically. If it is, instead, a promise that members of autoreleasepull do not leak references outside of that object, then this is very problematic for D to guarantee such - and guarantee it it must. I.e. it's "escape analysis" in another disguise.
 I think the compiler should pick where to put the Release() calls, that is 

determine that the calls can be elided, so much the better. I'm not sure exactly what is required for ARC to guarantee proper memory management (whether it requires flow-analysis or not), but it seems to work quite well for Objective-C. I think it helps minimize the expensive release/retain calls when you can just say "oh, someone else will clean that up later", just like you can with a GC. It might be good for someone who knows the ARC eliding techniques that clang uses to explain how they work. We certainly shouldn't ignore those techniques. -Steve
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 2:47 PM, Steven Schveighoffer wrote:
 I'm not sure exactly what is required for ARC to guarantee proper memory 

quite well for Objective-C. I think it helps minimize the expensive release/retain calls when you can just say "oh, someone else will clean that up later", just like you can with a GC.
 It might be good for someone who knows the ARC eliding techniques that clang 


Also remember that O-C doesn't guarantee memory safety, so they are freed from some of the constraints we operate under. They can say "don't do that", we can't. C++ shared_ptr<> is memory safe as long as you don't escape a pointer - and no C++ compiler checks for that. COM is also memory safe as long as you carefully follow the conventions - and again, no C++ compiler checks it.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
 On 6/25/2013 2:47 PM, Steven Schveighoffer wrote:
 I'm not sure exactly what is required for ARC to guarantee proper memory 


quite well for Objective-C. I think it helps minimize the expensive release/retain calls when you can just say "oh, someone else will clean that up later", just like you can with a GC.
 It might be good for someone who knows the ARC eliding techniques that clang 



Also remember that O-C doesn't guarantee memory safety, so they are freed

can't. I'm not sure that it doesn't. At least when we are talking about object references. The only thing clang complains about is when you try to call any memory management manually, or if you disobey the naming conventions. -Steve
Oct 09 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 25-juin-2013 à 17:20, Steven Schveighoffer a écrit :

 On Jun 25, 2013, at 4:44 PM, Walter Bright wrote:

 On 6/25/2013 1:19 PM, Steven Schveighoffer wrote:
 Would this be a mechanism that's worth putting in? I think it goes really 



though...
 I agree with not relying on convention. But also reserving the new*, init*, 


 As for autoreleasepool, it is relying on a convention that its fields are 


 I don't think the autoreleasepool is relying on convention, it's simply 

counts. Not at all. Autorelease pools were useful at a time before ARC so you wouldn't have to think of releasing manually every object called functions were returned to you. Instead, most functions would return autoreleased object and you'd only have to retain those objects you were storing elsewhere. Nowadays, with ARC, we still have them but that's mostly for interoperability already existing code. Most functions still return autoreleased objects because that's the convention, and breaking that convention would cause objects to be retained or released to many times. So we still need autorelease pools. But ARC is hard at work[^1] behind the scene to reduce the number of those autoreleased objects. So no, we shouldn't introduce autorelease pools to D... well, except maybe for the part were we want interoperability with Objective-C (because we have no choice). And finally, there's nothing unsafe with autorelease pools as long as you don't keep an unretained reference to an autoreleased object when the pool drains. Making sure you have no unretained reference is ARC's job, so with ARC it should not be no problem. [^1]: One clever trick ARC does is inside the implicit call to objc_returnAutoreleased it adds at the end of an autoreleasing function, the runtime checks to see if the return address points to an instruction that'll call objc_retain on that same pointer. If that's the case, it skips the autorelease and also skip objc_retain and goes to the next instruction directly. Of course if the convention was always to return object retained, none of this would be needed. I saw that explained on a WWDC video a couple of years back.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 25, 2013, at 9:31 PM, Michel Fortin wrote:

 Le 25-juin-2013 à 17:20, Steven Schveighoffer a écrit :

 I don't think the autoreleasepool is relying on convention, it's simply 


counts.
 Not at all. Autorelease pools were useful at a time before ARC so you 

returned to you. Instead, most functions would return autoreleased object and you'd only have to retain those objects you were storing elsewhere. Having used MRC, I appreciate what autoreleasepool did, but I thought of it being also as a kind of blanket way to allow the compiler to remove extra retains/releases in ARC. Is it not advantageous to release a whole pool of objects vs. releasing them individually during execution? All releases and retains are atomic, so I figured one could do some optimization when it's all lumped together. I find the autorelease pools very GC-like -- you don't have to worry who uses or forgets the reference, it's kept in memory until you don't need it. Anyway, everything I know about Obj-C ARC I learned from my iOS 5 book :) So don't take me as an expert. -Steve
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 25-juin-2013 à 21:40, Steven Schveighoffer a écrit :

 On Jun 25, 2013, at 9:31 PM, Michel Fortin wrote:

 Not at all. Autorelease pools were useful at a time before ARC so you 


returned to you. Instead, most functions would return autoreleased object and you'd only have to retain those objects you were storing elsewhere.
 Having used MRC, I appreciate what autoreleasepool did, but I thought of it 

retains/releases in ARC.
 Is it not advantageous to release a whole pool of objects vs. releasing them 

figured one could do some optimization when it's all lumped together. I haven't done any benchmarking, but I'd have to assume it is more advantageous to just return objects retained since Apple went to great lengths to make sure this can happen even when the convention is to return autoreleased. There's no question it also simplifies the compiler. It's much easier to reason about pairs of retain/release than retain/autorelease.
 I find the autorelease pools very GC-like -- you don't have to worry who uses 

The concept was truly great, no doubt about that.
Oct 09 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 6:31 PM, Michel Fortin wrote:
 And finally, there's nothing unsafe with autorelease pools as long as you 

Well, that's exactly the issue - an escaping reference.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 25, 2013, at 11:04 PM, Walter Bright wrote:

 On 6/25/2013 6:31 PM, Michel Fortin wrote:
 And finally, there's nothing unsafe with autorelease pools as long as you 


 Well, that's exactly the issue - an escaping reference.

Read the next sentence after your quote though: "Making sure you have no unretained reference is ARC's job, so with ARC it should not be no problem." So with ARC, it's not unsafe. I think that was the ultimate point. -Steve
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 8:08 PM, Steven Schveighoffer wrote:
 On Jun 25, 2013, at 11:04 PM, Walter Bright wrote:

 On 6/25/2013 6:31 PM, Michel Fortin wrote:
 And finally, there's nothing unsafe with autorelease pools as long as you 



 Well, that's exactly the issue - an escaping reference.

"Making sure you have no unretained reference is ARC's job, so with ARC it

 So with ARC, it's not unsafe.  I think that was the ultimate point.

Yes, I read the next sentence. What it means to me is that autorelease pools add nothing when ARC is implemented - no optimizations, either. Either that or I don't understand how ARC figures out that there are no escaping references without doing things like runtime checks.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 26, 2013, at 12:10 AM, Walter Bright wrote:

 On 6/25/2013 8:08 PM, Steven Schveighoffer wrote:
 On Jun 25, 2013, at 11:04 PM, Walter Bright wrote:

 On 6/25/2013 6:31 PM, Michel Fortin wrote:
 And finally, there's nothing unsafe with autorelease pools as long as you 




 Well, that's exactly the issue - an escaping reference.

"Making sure you have no unretained reference is ARC's job, so with ARC it


 So with ARC, it's not unsafe.  I think that was the ultimate point.

Yes, I read the next sentence. What it means to me is that autorelease pools

don't understand how ARC figures out that there are no escaping references without doing things like runtime checks. OK, it sounded like you were saying still that Objective C with ARC didn't have memory safety. I'm no longer arguing about autorelease, I defer to Michel on that. I clearly didn't understand that autorelease doesn't provide any benefits for ARC, it's just there for compatibility. -Steve
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 9:13 PM, Steven Schveighoffer wrote:
 OK, it sounded like you were saying still that Objective C with ARC didn't 

My initial first pass read of: http://clang.llvm.org/docs/AutomaticReferenceCounting.html indicates that ARC does not guarantee memory safety. There are a number of "undefined" behaviors when the O-C programmer does not follow the rules.
Oct 09 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:

Where are the benchmarks that show that this is a good idea in 
some real situations? This is the essential first step.


 If a class contains the following methods, in either itself or 
 a base class, it is
 an RC class:


     T AddRef();
     T Release();

What if a programmer adds only one of those two? Currently if you add only part of the hashing protocol (or you bork a function signature) the compiler often gives no errors. What are the plans for coalescing and optimizing away some reference counts updates? Bye, bearophile
Oct 09 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/11/13 10:28 AM, bearophile wrote:
 What are the plans for coalescing and optimizing away some reference
 counts updates?

There is now a discussion and paper on optimizing a reference counter: http://lambda-the-ultimate.org/node/4825 Bye, bearophile

Yes, I think that's great work. Andrei
Oct 11 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 9 October 2013 at 22:31:34 UTC, Walter Bright wrote:
 ==Arrays==

 Built-in arrays have no place to put a reference count. Ref 
 counted arrays would hence
 become a library type, based on a ref counted class with 
 overloaded operators for
 the array operations.

You'll soon see the roadblock here with templates and type qualifiers. const(A!T) and A!const(T) has nothing to do with each other as far as the compiler is concerned, and no we have no way around this ATM.
Oct 09 2013
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 What are the plans for coalescing and optimizing away some 
 reference counts updates?

There is now a discussion and paper on optimizing a reference counter: http://lambda-the-ultimate.org/node/4825 Bye, bearophile
Oct 11 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Updated incorporating Steven's suggestion, and some comments about 
shared/const/mutable/purity.

-------------------------------------------------------------

     Adding Reference Counting to D

D currently supports manual memory management and generalized GC.
Unfortunately, 
the pausing
and memory consumption inherent in GC is not acceptable for many programs, and 
manual
memory management is error-prone, tedious, and unsafe. A third style, reference 
counting (RC),
addresses this. Common implementations are COM's AddRef/Release, Objective-C's
ARC,
and C++'s shared_ptr<>.

None of these three schemes are guaranteed memory-safe, they all require the 
programmer
to conform to a protocol (even O-C's ARC). Stepping outside of the protocol 
results in
memory corruption. A D implementation must make it possible to use ref counted 
objects
in code marked as  safe, although it will be necessary for the implementation
of 
those
objects to be unsafe.

Some aspects of a D implementation are inevitable:

1. Avoid any requirement for more pointer types. This would cause drastic 
increases in
complexity for both the compiler and the user. It may make generic code much 
more difficult
to write.

2. Decay of a ref-counted pointer to a non-ref-counted pointer is unsafe, and 
can only
be allowed (in  safe code) in circumstances where it can be statically proven
to 
be safe.

3. A ref counted object is inherently a reference type, not a value type.

4. The compiler needs to know about ref counted types.


==Proposal==

If a class contains the following methods, in either itself or a base class, it
is
an RC class:


     T AddRef();
     T Release();

An RC class is like a regular D class with these additional semantics:

1. In  safe code, casting (implicit or explicit) to a base class that does not
have both AddRef() and Release() is an error.

2. Initialization of a class reference causes a call to AddRef().

3. Assignment to a class reference causes a call to AddRef() on the new value
followed by a call to Release() on its original value.

4. Null checks are done before calling any AddRef() or Release().

5. Upon scope exit of all RC variables or temporaries, a call to Release() is 
performed,
analogously to the destruction of struct variables and temporaries.

6. If a class or struct contains RC fields, calls to Release() for those fields
will
be added to the destructor, and a destructor will be created if one doesn't 
exist already.

7. If a closure is created that contains RC fields, either a compile time error 
will be
generated or a destructor will be created for it.

8. Explicit calls to AddRef/Release will not be allowed in  safe code.

9. A call to AddRef() will be added to any argument passed as a parameter.

10. Function returns have an AddRef() already done to the return value.

11. The compiler can elide any AddRef()/Release() calls it can prove are
redundant.

12. AddRef() is not called when passed as the implicit 'this' reference.

13. Taking the address of, or passing by reference, any fields of an RC object
is not allowed in  safe code. Passing by reference an RC field is allowed.

14. RC objects will still be allocated on the GC heap - this means that a normal
GC run will reap RC objects that are in a cycle, and RC objects will get 
automatically
scanned for heap references with no additional action required by the user.

15. The class implementor will be responsible for deciding whether or not to
support
sharing. Casting to shared is already disallowed in  safe code, so this is only
viable in system code.

16. RC objects cannot be const or immutable.

17. Can RC objects be arguments to pure functions?

==Existing Code==

D COM objects already have AddRef() and Release(). This proposal should not
break
that code, it'll just mean that there will be extra AddRef()/Release calls made.
Calling AddRef()/Release() should never have been allowed in  safe code anyway.

Any other existing uses of AddRef()/Release() will break.

==Arrays==

Built-in arrays have no place to put a reference count. Ref counted arrays
would 
hence
become a library type, based on a ref counted class with overloaded operators
for
the array operations.

==Results==

This is a very flexible approach, allowing for support of general RC objects,
as 
well
as specific support for COM objects and Objective-C ARC. AddRef()/Release()'s 
implementation
is entirely up to the user or library writer.

 safe code can be guaranteed to be memory safe, as long as AddRef()/Release() 
are correctly
implemented.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

## Some general comments

While its a start, this is hardly enough for Objective-C. Mostly for legacy 
reasons, most Objective-C methods return autoreleased objects (deferred release 
using an autorelease pool) based on a naming convention. Also, Objective-C 
objects can't be allocated from the D heap, so to avoid cycles we need weak 
pointers. More on Objective-C later.

While it's good that a direct call to AddRef/Release is forbidden in  safe
code, 
I think it should be forbidden in  system code too. The reason is that if the 
compiler is inserting calls to these automatically and you're also adding your 
own explicitly in the same function, it becomes practically impossible to
reason 
about the reference counts, short of looking at the assembly. Instead, I think 
you should create a  noarc attribute for functions: it'll prevent the compiler 
for inserting any of those calls so it becomes the responsibility of the author 
to make those calls (which are then allowed).  noarc would be incompatible with 
 safe, obviously.

Finally, that's a nitpick but I wish you'd use function names that fit D
better, 
such as opRetain and opRelease. Then you can add a "final void opRetain() { 
AddRef(); }" function to the IUnknown COM interface and we could do the same
for 
Objective-C.

## Objective-C autoreleased objects

Objective-C is a special case. In Objective-C we need to know whether the 
returned object of a function is already retained or if it is deferred released 
(autoreleased). This is easily deducted from the naming convention. 
Occasionally, we might need to create autorelease pools too, but that can 
probably stay  system.

(Note: all this idea of autoreleased objects might sound silly, but it was a 
great help before ARC, and Objective-C ARC has to be compatible with legacy
code 
so it conforms to those conventions.)

You can easily implement ARC for COM using an implementation of ARC for 
Objective-C, the reverse is not true because COM does not have this (old but 
still needed) concept of autorelease pools and deferred release where you need 
to know at each function boundary whether returned values (including those 
returned by pointer arguments) whether the object is expected to be retained or
not.

If I were you Walter, I would just not care about Objective-C idioms while 
implementing this feature at first. It'll have to be special cased anyway. 
Here's how I expect that'll be done:

What will need to be done later when adding Objective-C support is to add an 
internal "autoreleasedReturn" flag to a function that'll make codegen call 
"autorelease" in the callee when returning an object and "retain" in the caller 
where it receives an object from a function with that flag. Also, the same flag 
and behaviour is needed for out parameters (to mimick those cases where an 
object is returned by pointer). That flag will then be set automatically 
internally depending on the function name (only for Objective-C member 
functions), and it should be possible to override it explicitly with an 
attribute or a pragma of some sort. This is what Clang is doing, and we must 
match that to allow things to work.

Checking for null is redundant in the Objective-C case: that check is done by 
the runtime. That's of minor importance, but it might impact performance and 
should probably special-cased in this case.

## Optimizations

With Apple's implementation of reference counting (using global hash tables 
protected by spin locks), it is more efficient to update many counters in one 
operation. The codegen for Objective-C ARC upon assignement to a variable calls 
"objc_storeStrong(id *object, id value)", incrementing and decrementing the two 
counters presumably in one operation (as well as replacing the content of the 
variable pointed by the first argument with the new value).

Ideally, the codegen for Objective-C ARC in D would call the same functions so 
we have the same performance. This means that codegen should make a call 
"objc_retain" when first initializing a variable, "objc_storeStrong" when doing 
an assignment, and "objc_release" when destructing a variable.

As for returning autoreleased objects, there are two functions to choose from 
depending on whether the object needs to be retained at the same time nor not. 
(In general, the object needs to be retained prior autoreleasing if it comes 
from a variable not part of the function's stack frame.)

Here's Clang's documentation for how it implements ARC:
http://clang.llvm.org/docs/AutomaticReferenceCounting.html

## Objective-C weak pointers

Weak pointers are essential in order to break retain cycles in Objective-C
where 
there is no GC. They are implemented with the same kind of function calls as 
strong pointers. Unfortunately, Apple's Objective-C implementation won't sit 
well with D the way it works now.

Weak pointers are implemented in Objective-C by registering the address of the 
pointer with the runtime. This means that when a pointer is moved from one 
location to another, the need to be notified of that through a call to 
objc_moveWeak. This breaks one assumption of D that you can move memory at will 
without calling anything.

While we could still implement a working weak pointer with a template struct, 
that struct would have to allocate a pointer on the heap (where it is
guarantied 
to not move) so it can store the true weak pointer recognized by the runtime. 
I'm not sure that would be acceptable, but at least it would work.

## More on reference counting

I feel like I should share some of my thoughts here about a broader use of 
reference counting in D.

First, we don't have to assume the reference counter has to be part of the 
object. Apple implements reference counting using global hash tables where the 
key is the address. It works very well.

If we added a hash table like this for all memory allocated from the GC, we'd 
just have to find the base address of any memory block to get to its reference 
counter. I know you were designing with only classes in mind, but I want to 
point out that it is possible to reference-count everything the GC allocates if 
we want to.

The downside is that every assignment to a pointer anywhere has to call a 
function. While this is some overhead, it is more predictable than overhead
from 
a GC scan and would be preferred in some situation (games I guess). Another 
downside is you have an object retained by being present on the stack frame of
a 
C function, it'd have to be explicitly retained from elsewhere.

As for pointers not pointing to GC memory, the generic addRef/release functions 
can ignore those pointers just like the GC ignores them today when it does its
scan.

Finally, cycles can still be reclaimed by having the GC scan for them. Those 
scans should be less frequent however since most of the memory can be reclaimed 
through reference counting.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/25/2013 6:09 PM, Michel Fortin wrote:
 ## Some general comments

 While its a start, this is hardly enough for Objective-C. Mostly for legacy 

using an autorelease pool) based on a naming convention. Also, Objective-C objects can't be allocated from the D heap, so to avoid cycles we need weak pointers. More on Objective-C later.
 While it's good that a direct call to AddRef/Release is forbidden in  safe 

the compiler is inserting calls to these automatically and you're also adding your own explicitly in the same function, it becomes practically impossible to reason about the reference counts, short of looking at the assembly. Instead, I think you should create a noarc attribute for functions: it'll prevent the compiler for inserting any of those calls so it becomes the responsibility of the author to make those calls (which are then allowed). noarc would be incompatible with safe, obviously. It's a good point, but adding such an attribute to the function may be too coarse, for one, and may cause composition problems, for another. Maybe just disallowing it altogether is the best solution.
 Finally, that's a nitpick but I wish you'd use function names that fit D 

opRetain() { AddRef(); }" function to the IUnknown COM interface and we could do the same for Objective-C. Makes sense.
 ## Objective-C autoreleased objects

 Objective-C is a special case. In Objective-C we need to know whether the 

(autoreleased). This is easily deducted from the naming convention. Occasionally, we might need to create autorelease pools too, but that can probably stay system.
 (Note: all this idea of autoreleased objects might sound silly, but it was a 

so it conforms to those conventions.)
 You can easily implement ARC for COM using an implementation of ARC for 

still needed) concept of autorelease pools and deferred release where you need to know at each function boundary whether returned values (including those returned by pointer arguments) whether the object is expected to be retained or not.
 If I were you Walter, I would just not care about Objective-C idioms while 

Here's how I expect that'll be done: From reading over that clang document, O-C arc is far more complex than I'd anticipated. I think it is way beyond what we'd want in regular D. It also comes with all kinds of pointer and function annotations - something I strongly want to avoid.
 What will need to be done later when adding Objective-C support is to add an 

"autorelease" in the callee when returning an object and "retain" in the caller where it receives an object from a function with that flag. Also, the same flag and behaviour is needed for out parameters (to mimick those cases where an object is returned by pointer). That flag will then be set automatically internally depending on the function name (only for Objective-C member functions), and it should be possible to override it explicitly with an attribute or a pragma of some sort. This is what Clang is doing, and we must match that to allow things to work. I agree that this complexity should only be in O-C code.
 Checking for null is redundant in the Objective-C case: that check is done by 

should probably special-cased in this case.
 ## Optimizations

 With Apple's implementation of reference counting (using global hash tables 

operation. The codegen for Objective-C ARC upon assignement to a variable calls "objc_storeStrong(id *object, id value)", incrementing and decrementing the two counters presumably in one operation (as well as replacing the content of the variable pointed by the first argument with the new value).
 Ideally, the codegen for Objective-C ARC in D would call the same functions 

"objc_retain" when first initializing a variable, "objc_storeStrong" when doing an assignment, and "objc_release" when destructing a variable.
 As for returning autoreleased objects, there are two functions to choose from 

(In general, the object needs to be retained prior autoreleasing if it comes from a variable not part of the function's stack frame.)
 Here's Clang's documentation for how it implements ARC:
 http://clang.llvm.org/docs/AutomaticReferenceCounting.html

 ## Objective-C weak pointers

 Weak pointers are essential in order to break retain cycles in Objective-C 

as strong pointers. Unfortunately, Apple's Objective-C implementation won't sit well with D the way it works now.
 Weak pointers are implemented in Objective-C by registering the address of 

location to another, the need to be notified of that through a call to objc_moveWeak. This breaks one assumption of D that you can move memory at will without calling anything.
 While we could still implement a working weak pointer with a template struct, 

to not move) so it can store the true weak pointer recognized by the runtime. I'm not sure that would be acceptable, but at least it would work.
 ## More on reference counting

 I feel like I should share some of my thoughts here about a broader use of 

 First, we don't have to assume the reference counter has to be part of the 

key is the address. It works very well.
 If we added a hash table like this for all memory allocated from the GC, we'd 

counter. I know you were designing with only classes in mind, but I want to point out that it is possible to reference-count everything the GC allocates if we want to. D would need manual, RC and GC to coexist peacefully.
 The downside is that every assignment to a pointer anywhere has to call a 

a GC scan and would be preferred in some situation (games I guess). Another downside is you have an object retained by being present on the stack frame of a C function, it'd have to be explicitly retained from elsewhere. Doesn't this make it impractical to mix vanilla C with D code? An important feature of D is this capability, without worrying about a "JNI" style interface. As for D switching to a full refcounted GC for everything, I'm very hesitant for such a step. For one thing, reading the clang spec on all the various pointer and function annotations necessary is very off-putting.
 As for pointers not pointing to GC memory, the generic addRef/release 

does its scan.
 Finally, cycles can still be reclaimed by having the GC scan for them. Those 

through reference counting.

Oct 09 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 25.06.2013 23:00, Walter Bright wrote:
 Updated incorporating Steven's suggestion, and some comments about
 shared/const/mutable/purity.

 -------------------------------------------------------------

      Adding Reference Counting to D

Cool. I didn't expect this to be tackled so soon.

 3. A ref counted object is inherently a reference type, not a value type.

As Michel also said, the reference count does not have to be in inside the object itself, so we might want to allow reference counting on other types aswell.
 4. The compiler needs to know about ref counted types.

I imagine a few (constrained) templated functions for the different operations defined in the library could also do the job, though it might drown compilation speed. Also getting help from the optimizer to remove redundant calls will need some back doors.
 ==Proposal==

 If a class contains the following methods, in either itself or a base
 class, it is
 an RC class:


      T AddRef();
      T Release();

Is T typeof(this) here? I don't think we should force linking this functionality with COM, the programmer can do this with a simple wrapper.
 An RC class is like a regular D class with these additional semantics:

 1. In  safe code, casting (implicit or explicit) to a base class that
 does not
 have both AddRef() and Release() is an error.

 2. Initialization of a class reference causes a call to AddRef().

 3. Assignment to a class reference causes a call to AddRef() on the new
 value
 followed by a call to Release() on its original value.

It might be common knowledge, but I want to point out that the usual COM implementation (atomic increment/decrement and free when refcount goes down to 0) is not thread-safe for shared pointers. That means you either have to guard all reads and writes with a lock to make the full assignment atomic or have to implement reference counting very different (e.g. deferred reference counting).
 4. Null checks are done before calling any AddRef() or Release().

 5. Upon scope exit of all RC variables or temporaries, a call to
 Release() is performed,
 analogously to the destruction of struct variables and temporaries.

 6. If a class or struct contains RC fields, calls to Release() for those
 fields will
 be added to the destructor, and a destructor will be created if one
 doesn't exist already.

 7. If a closure is created that contains RC fields, either a compile
 time error will be
 generated or a destructor will be created for it.

 8. Explicit calls to AddRef/Release will not be allowed in  safe code.

 9. A call to AddRef() will be added to any argument passed as a parameter.

 10. Function returns have an AddRef() already done to the return value.

 11. The compiler can elide any AddRef()/Release() calls it can prove are
 redundant.

 12. AddRef() is not called when passed as the implicit 'this' reference.

Isn't this unsafe if a member function is called through the last existing reference and this reference is then cleared during execution of this member function or from another thread?
 13. Taking the address of, or passing by reference, any fields of an RC
 object
 is not allowed in  safe code. Passing by reference an RC field is allowed.

Please note that this includes slices to fixed size arrays.
 14. RC objects will still be allocated on the GC heap - this means that
 a normal
 GC run will reap RC objects that are in a cycle, and RC objects will get
 automatically
 scanned for heap references with no additional action required by the user.

 15. The class implementor will be responsible for deciding whether or
 not to support
 sharing. Casting to shared is already disallowed in  safe code, so this
 is only
 viable in system code.

 16. RC objects cannot be const or immutable.

This is a bit of a downer. If the reference count is not within the object, this can be implemented.
 17. Can RC objects be arguments to pure functions?

 ==Existing Code==

 D COM objects already have AddRef() and Release(). This proposal should
 not break
 that code, it'll just mean that there will be extra AddRef()/Release
 calls made.
 Calling AddRef()/Release() should never have been allowed in  safe code
 anyway.

 Any other existing uses of AddRef()/Release() will break.

 ==Arrays==

 Built-in arrays have no place to put a reference count. Ref counted
 arrays would hence
 become a library type, based on a ref counted class with overloaded
 operators for
 the array operations.

 ==Results==

 This is a very flexible approach, allowing for support of general RC
 objects, as well
 as specific support for COM objects and Objective-C ARC.
 AddRef()/Release()'s implementation
 is entirely up to the user or library writer.

  safe code can be guaranteed to be memory safe, as long as
 AddRef()/Release() are correctly
 implemented.

I feel I'm hijacking this proposal, but the step to library defined read/write barriers seems pretty small. Make AddRef, Release and assignment free template functions, e.g. void ptrConstruct(T,bool stackOrHeap)(T*adr, T p); void ptrAssign(T,bool stackOrHeap)(T*adr, T p); void ptrRelease(T,bool stackOrHeap)(T*adr); and we are able to experiment with all kinds of sophisticated GC algorithms including RC. Eliding redundant addref/release pairs would need some extra support though, I read that LLVM does something like this, but I don't know how.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 As Michel also said, the reference count does not have to be in inside the 

That opens the question of what is the point of other RC types? For example, C++ can throw any type - but it turns out that throwing anything but class types is largely pointless. My proposal does not specify where the count actually is - the two functions can be arbitrarily implemented.
 4. The compiler needs to know about ref counted types.

I imagine a few (constrained) templated functions for the different

compilation speed. Also getting help from the optimizer to remove redundant calls will need some back doors. I don't see how this can be done without specific compiler knowledge in a memory safe way.
      T AddRef();
      T Release();

Is T typeof(this) here?

T is not relevant to the proposal - it's up to the specific implementation of those functions.
 I don't think we should force linking this functionality with COM, the 

Yeah, that's Michel's suggestion, and it's a good one.
 An RC class is like a regular D class with these additional semantics:

 1. In  safe code, casting (implicit or explicit) to a base class that
 does not
 have both AddRef() and Release() is an error.

 2. Initialization of a class reference causes a call to AddRef().

 3. Assignment to a class reference causes a call to AddRef() on the new
 value
 followed by a call to Release() on its original value.

It might be common knowledge, but I want to point out that the usual COM

0) is not thread-safe for shared pointers. That means you either have to guard all reads and writes with a lock to make the full assignment atomic or have to implement reference counting very different (e.g. deferred reference counting). Since the implementation of AddRef()/Release() is up to the user, whether it uses locks or not and whether it supports shared or not is up to the user.
 12. AddRef() is not called when passed as the implicit 'this' reference.

Isn't this unsafe if a member function is called through the last existing

function or from another thread? No. The caller of the function still retains a reference in that thread.
 13. Taking the address of, or passing by reference, any fields of an RC
 object
 is not allowed in  safe code. Passing by reference an RC field is allowed.

Please note that this includes slices to fixed size arrays.

As I suggested, arrays would not be supported with this proposal - but the user can create ref counted array-like objects.
 16. RC objects cannot be const or immutable.

This is a bit of a downer. If the reference count is not within the object,

Also, an exception could be made for the AddRef()/Release() functions.
 I feel I'm hijacking this proposal, but the step to library defined 

template functions, e.g.
 void ptrConstruct(T,bool stackOrHeap)(T*adr, T p);
 void ptrAssign(T,bool stackOrHeap)(T*adr, T p);
 void ptrRelease(T,bool stackOrHeap)(T*adr);

 and we are able to experiment with all kinds of sophisticated GC algorithms 

support though, I read that LLVM does something like this, but I don't know how.

It's pretty invasive into the code generation and performance, and could completely disrupt the C compatibility of D.
Oct 09 2013
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Jacob Carlborg wrote:

On Jun 25, 2013, at 11:00 PM, Walter Bright wrote:

 Updated incorporating Steven's suggestion, and some comments about
 shared/const/mutable/purity.

It's great that you're bringing this up. I think it's a good idea to add reference counting to D. Although I don't think I can add much to the discussion and Michel have a lot better knowledge about Objective-C than I have. All I can say is that I really want it to be compatible with Objective-C.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 26-juin-2013 à 5:38, Walter Bright  a écrit :

 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 As Michel also said, the reference count does not have to be in inside the 


 That opens the question of what is the point of other RC types? For example, 

is largely pointless. RC is just another garbage collection scheme. You might favor it for its performance characteristics, its determinism, or the lower memory footprint. Or you might need it to interact with foreign code that relies on it (COM, Objective-C, etc.), in which case it needs to be customizable (use the foreign implementation) or be manually managed. That's two different use cases. And in the later case you can't use the GC to release cycles because foreign code is using memory invisible to the GC. It is important to note that when foreign code calls AddRef you don't want the GC to collect that object, at least not until Release is called.
 I don't think we should force linking this functionality with COM, the 


 Yeah, that's Michel's suggestion, and it's a good one.

It could also be done with user attributes: void x_init(ref X x); void x_destroy(ref X x); void x_assign(ref X a, X b); // retains a, releases b arc!(x_init, x_destroy, x_assign) class X {} This way you don't have to check for null in the generated code: the standalone function is in charge of that. Also, this "assign" function here provides good opportunity for optimization in the RC implementation because you can update the two reference counts in a single operation (in the case where they're stored at the same place and are protected by the same lock). It's an improvement over making two separate function calls.
 No. The caller of the function still retains a reference in that thread.

This should also apply to all function arguments. The caller is better placed than the callee to elide redundant AddRef/Release pairs, so it should be the one in charge of retaining the object for the callee.
 16. RC objects cannot be const or immutable.

This is a bit of a downer. If the reference count is not within the object,


 Also, an exception could be made for the AddRef()/Release() functions.

I'm not too fond of that idea.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:


Le 26-juin-2013 à 1:36, Walter Bright  a écrit :

 On 6/25/2013 6:09 PM, Michel Fortin wrote:
 Instead, I think you should create a  noarc attribute for functions: it'll 


responsibility of the author to make those calls (which are then allowed). noarc would be incompatible with safe, obviously.
 It's a good point, but adding such an attribute to the function may be too 

disallowing it altogether is the best solution. Well, it's mostly required to write runtime support functions. The attribute could be more obscure so people are less tempted to use it, but if you're going to implement the ref-counting code you'll need that.
 ## More on reference counting

 I feel like I should share some of my thoughts here about a broader use of 


 First, we don't have to assume the reference counter has to be part of the 


key is the address. It works very well.
 If we added a hash table like this for all memory allocated from the GC, 


reference counter. I know you were designing with only classes in mind, but I want to point out that it is possible to reference-count everything the GC allocates if we want to.
 D would need manual, RC and GC to coexist peacefully.

The problem is how to make the three of those use the same codegen? - Druntime could have a flag to disable/enable refcounting. It'd make the retain/release functions no-ops, but it'd not prevent the GC from reclaiming memory as it does today. - Druntime could have a flag to disable/enable garbage collection (it already has). That'd prevent cycles from being collected, but you could use weak pointers to work around that or request a collection manually at the appropriate time. - A noarc (or similar) attribute at the function level could be used to prevent the compiler from generating function calls on pointer assignments. You could make a whole module noarc if you want by adding " noarc:" at the top. Here's the annoying thing: noarc is totally safe if reference counting is disabled and we rely entirely on the GC. noarc is unsafe when reference counting is enabled.
 The downside is that every assignment to a pointer anywhere has to call a 


a GC scan and would be preferred in some situation (games I guess). Another downside is you have an object retained by being present on the stack frame of a C function, it'd have to be explicitly retained from elsewhere.
 Doesn't this make it impractical to mix vanilla C with D code? An important 

It's not very different than with the GC today. If you call a C function by giving it a ref-counted pointer argument, that memory block is guarantied to live at least for that call's lifetime (because it is retained by the caller). So simple calls to C functions are not a problem. If the C function puts that pointer elsewhere you'll need to retain it some other way, but you have to do this with the GC too. If you're implementing a callback called from C you need to care about what you return because the caller's C code won't retain it, while with the GC you could manage if C code did not store that pointer outside of the stack. I think that's all you have to worry about.
 As for D switching to a full refcounted GC for everything, I'm very hesitant 

pointer and function annotations necessary is very off-putting. Don't let Clang intimidate you. The Clang spec is about four to five time more complicated than needed because of autoreleased objects and because it supports weak pointers. Weak pointers can be implemented as a struct templates (as long as we have noarc). And all those annotations are for special cases, when you need to break the rules. You don't use them when doing normal programming, well except for __weak.
Oct 09 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 26.06.2013 11:38, Walter Bright wrote:
 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 I imagine a few (constrained) templated functions for the different
 operations defined in the library could also do the job, though it
 might drown compilation speed. Also getting help from the optimizer to
 remove redundant calls will need some back doors.

I don't see how this can be done without specific compiler knowledge in a memory safe way.

I currently don't see how it can be memory safe with this proposal.
 3. Assignment to a class reference causes a call to AddRef() on the new
 value
 followed by a call to Release() on its original value.

It might be common knowledge, but I want to point out that the usual COM implementation (atomic increment/decrement and free when refcount goes down to 0) is not thread-safe for shared pointers. That means you either have to guard all reads and writes with a lock to make the full assignment atomic or have to implement reference counting very different (e.g. deferred reference counting).

Since the implementation of AddRef()/Release() is up to the user, whether it uses locks or not and whether it supports shared or not is up to the user.

You have to put the lock around the pair of AddRef and Release, but if the compiler already splits this into two function calls, this cannot be done in the implementation.
 12. AddRef() is not called when passed as the implicit 'this' reference.

Isn't this unsafe if a member function is called through the last existing reference and this reference is then cleared during execution of this member function or from another thread?

No. The caller of the function still retains a reference in that thread.

Hmmm, I guess I misunderstand the proposal. Assume for example a refcounted class R and this code class R : RefCounted { int _x; int readx() { return _x; } } int main() { R r = new R; return r.readx(); } According to 12. there is no refcounting going on when calling or executing readx. Ok, now what happens here: class R : RefCounted { int _x; int readx(C c) { c.r = null; // "standard" rc deletes r here return _x; // reads garbage } } class C { R r; } int main() { C c = new C; c.r = new R; return c.r.readx(c); } This reads garbage or crashes if there is no reference counting going on when calling readx.
 13. Taking the address of, or passing by reference, any fields of an RC
 object
 is not allowed in  safe code. Passing by reference an RC field is
 allowed.

Please note that this includes slices to fixed size arrays.

As I suggested, arrays would not be supported with this proposal - but the user can create ref counted array-like objects.

Just to clarify, I meant taking a slice of a static array that is a field of a refcounted class. Is it forbidden to have a field like this in a refcounted class or is taking the address through slicing forbidden?
 I feel I'm hijacking this proposal, but the step to library defined
 read/write barriers seems pretty small. Make AddRef, Release and
 assignment free template functions, e.g.

 void ptrConstruct(T,bool stackOrHeap)(T*adr, T p);
 void ptrAssign(T,bool stackOrHeap)(T*adr, T p);
 void ptrRelease(T,bool stackOrHeap)(T*adr);

 and we are able to experiment with all kinds of sophisticated GC
 algorithms including RC. Eliding redundant addref/release pairs would
 need some extra support though, I read that LLVM does something like
 this, but I don't know how.

It's pretty invasive into the code generation and performance, and could completely disrupt the C compatibility of D.

I don't see a big difference between a free function and a member function call, though the template character of it might hurt compilation performance. Two more notes: - I'm not sure it is mentioned, but I think you have to describe what happens when copying a struct. pre- and post-blit actions have to be taken if the struct contain pointers to refcounted objects.
 10. Function returns have an AddRef() already done to the return value.

- A refcounted reference returned from a function (including new) would have to be Released if the return value is ignored or if only used as part of an expression.
Oct 09 2013
next sibling parent reply Robert Schadek <realburner gmx.de> writes:
On 10/10/2013 03:45 AM, Walter Bright wrote:
 Rainer Schuetze wrote:

 You have to put the lock around the pair of AddRef and Release, but if
 the compiler already splits this into two function calls, this cannot
 be done in the implementation.

operations, so no locks are required.
Oct 10 2013
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 12.10.2013 04:16, inout wrote:
 On Thursday, 10 October 2013 at 08:55:00 UTC, Robert Schadek
 wrote:
 On 10/10/2013 03:45 AM, Walter Bright wrote:
 Rainer Schuetze wrote:

 You have to put the lock around the pair of AddRef and Release, but if
 the compiler already splits this into two function calls, this cannot
 be done in the implementation.

operations, so no locks are required.

On shared objects, yes. Local objects need no atomics at all.

Atomic increments/decrements are not good enough for shared references. See this example from later in the discussion: Consider a global shared reference R that holds the last reference to an object O. One thread exchanges the reference with another reference P while another thread reads the reference into S. shared(C) R = O; ; refcnt of O is 1 in pseudo-assembly missing null-checks: Thread1 (R = P) Thread2 (S = R) mov ecx,[R] ; thread suspended mov eax,[P] inc [eax].refcnt mov ebx,[R] mov [R],eax dec [ebx].refcnt ; refcnt of O now 0 jnz done call delete_ebx ; thread resumed inc [ecx].refcnt done: The increment on [ecx].refcnt modifies garbage.
Oct 11 2013
next sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-12 06:16:17 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 On 12.10.2013 04:16, inout wrote:
 On Thursday, 10 October 2013 at 08:55:00 UTC, Robert Schadek
 wrote:
 I would imagine the counter to be manipulated with atomic_add_and_fetch
 operations, so no locks are required.

On shared objects, yes. Local objects need no atomics at all.

Atomic increments/decrements are not good enough for shared references. See this example from later in the discussion: Consider a global shared reference R that holds the last reference to an object O. One thread exchanges the reference with another reference P while another thread reads the reference into S. shared(C) R = O; ; refcnt of O is 1 in pseudo-assembly missing null-checks: Thread1 (R = P) Thread2 (S = R) mov ecx,[R] ; thread suspended mov eax,[P] inc [eax].refcnt mov ebx,[R] mov [R],eax dec [ebx].refcnt ; refcnt of O now 0 jnz done call delete_ebx ; thread resumed inc [ecx].refcnt done: The increment on [ecx].refcnt modifies garbage.

I think you are mixing shared references with shared objects. Atomic increment/decrement will work fine for shared objects with unshared pointers to it. But if the pointer to the object is itself shared and available from two threads (as in your example) then you need to properly serialize reads and writes to that pointer (with a mutex or through other means). Of course, then you fall into the problem that in D you are not able to set different attributes to an object and to its reference. (Hint: const(Object)ref) -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 12 2013
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 12.10.2013 14:16, Michel Fortin wrote:
 On 2013-10-12 06:16:17 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 On 12.10.2013 04:16, inout wrote:
 On Thursday, 10 October 2013 at 08:55:00 UTC, Robert Schadek
 wrote:
 I would imagine the counter to be manipulated with atomic_add_and_fetch
 operations, so no locks are required.

On shared objects, yes. Local objects need no atomics at all.

Atomic increments/decrements are not good enough for shared references. See this example from later in the discussion: Consider a global shared reference R that holds the last reference to an object O. One thread exchanges the reference with another reference P while another thread reads the reference into S. shared(C) R = O; ; refcnt of O is 1 in pseudo-assembly missing null-checks: Thread1 (R = P) Thread2 (S = R) mov ecx,[R] ; thread suspended mov eax,[P] inc [eax].refcnt mov ebx,[R] mov [R],eax dec [ebx].refcnt ; refcnt of O now 0 jnz done call delete_ebx ; thread resumed inc [ecx].refcnt done: The increment on [ecx].refcnt modifies garbage.

I think you are mixing shared references with shared objects. Atomic increment/decrement will work fine for shared objects with unshared pointers to it. But if the pointer to the object is itself shared and available from two threads (as in your example) then you need to properly serialize reads and writes to that pointer (with a mutex or through other means).

I agree, that's why I used the term "shared reference", too ;-) If you are using only shared objects, but not shared references, you'll have to use message passing coming with its own set of synchronization operations that are not easily made lock-free.
 Of course, then you fall into the problem that in D you are not able to
 set different attributes to an object and to its reference. (Hint:
 const(Object)ref)

I think being able to distinguish these types is missing from the type system. It's even worse for the class describing TypeInfo object as it is used for both the reference and the object.
Oct 12 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-13 06:54:04 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 I agree, that's why I used the term "shared reference", too ;-)
 
 If you are using only shared objects, but not shared references, you'll 
 have to use message passing coming with its own set of synchronization 
 operations that are not easily made lock-free.

For one of my projects I implemented a shared pointer like this. It uses the pointer value itself as a spin lock with the assumption that -1 is an invalid pointer value: 1. read pointer value 2. if read value is -1 go to line 1 (spin) 3. compare and swap (previously read value <-> -1) 4. if failure go to line 1 (spin) // now pointer is "locked", its value is -1 but we have a copy of the original 5. copy pointer locally or assign to it (and update counter) 6. write back pointer value atomically to replace the -1 No mutex, but there's a spin lock so it's not good if there's contention. That said, I find it extremely rare to want a shared pointer that isn't already protected by a mutex alongside other variables, or that isn't propagated using some form of message passing. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 13 2013
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 13.10.2013 13:48, Michel Fortin wrote:
 On 2013-10-13 06:54:04 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 I agree, that's why I used the term "shared reference", too ;-)

 If you are using only shared objects, but not shared references,
 you'll have to use message passing coming with its own set of
 synchronization operations that are not easily made lock-free.

For one of my projects I implemented a shared pointer like this. It uses the pointer value itself as a spin lock with the assumption that -1 is an invalid pointer value: 1. read pointer value 2. if read value is -1 go to line 1 (spin) 3. compare and swap (previously read value <-> -1) 4. if failure go to line 1 (spin) // now pointer is "locked", its value is -1 but we have a copy of the original 5. copy pointer locally or assign to it (and update counter) 6. write back pointer value atomically to replace the -1 No mutex, but there's a spin lock so it's not good if there's contention. That said, I find it extremely rare to want a shared pointer that isn't already protected by a mutex alongside other variables, or that isn't propagated using some form of message passing.

Locking is very bad if you have threads at different priorities as it might introduce priority inversion. Spinning is probably even worse in that scenario. At work, I use shared pointers all the time to pass information to a real time audio thread. The scheme uses triple-buffering of pointers for a lock free safe transport from/to the real time thread. Not having to worry about these low-level locking stuff is one of the good aspects about garbage collecting.
Oct 14 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-14 17:57:18 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 On 13.10.2013 13:48, Michel Fortin wrote:
 
 For one of my projects I implemented a shared pointer like this. It uses
 the pointer value itself as a spin lock with the assumption that -1 is
 an invalid pointer value:
 
 1. read pointer value
 2. if read value is -1 go to line 1 (spin)
 3. compare and swap (previously read value <-> -1)
 4. if failure go to line 1 (spin)
 // now pointer is "locked", its value is -1 but we have a copy of the
 original
 5. copy pointer locally or assign to it (and update counter)
 6. write back pointer value atomically to replace the -1
 
 No mutex, but there's a spin lock so it's not good if there's contention.
 
 That said, I find it extremely rare to want a shared pointer that isn't
 already protected by a mutex alongside other variables, or that isn't
 propagated using some form of message passing.

Locking is very bad if you have threads at different priorities as it might introduce priority inversion. Spinning is probably even worse in that scenario.

Spinning is good only when you very rarely expect contention, which is the case for me. The above code is used once per object the first time someone requests a weak pointer for it. Having contention for that just doesn't make sense in most usage patterns. But still, being curious I added a log message anytime it does actually has to spin, and I have yet to see that message once in my logs (which probably means aggressive enough unit tests are missing). If you have a lot of read accesses and rarely write to the pointer you could instead try a read-write mutex with concurrent read access. In any case, there's no solution that will be ideal in all cases. Different situations asks for different trade-offs.
 At work, I use shared pointers all the time to pass information to a 
 real time audio thread. The scheme uses triple-buffering of pointers 
 for a lock free safe transport from/to the real time thread.
 
 Not having to worry about these low-level locking stuff is one of the 
 good aspects about garbage collecting.

Indeed. The current garbage collector makes it easy to have shared pointers to shared objects. But the GC can also interrupt real-time threads for an unpredictable duration, how do you cope with that in a real-time thread? I know ARC isn't the ideal solution for all use cases. But neither is the GC, especially for real-time applications. So, which one would you recommend for a project having a real-time audio thread? -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 14 2013
next sibling parent reply Paulo Pinto <pjmlp progtools.org> writes:
Am 14.10.2013 21:42, schrieb Michel Fortin:
 On 2013-10-14 17:57:18 +0000, Rainer Schuetze <r.sagitario gmx.de> said:

 On 13.10.2013 13:48, Michel Fortin wrote:
 For one of my projects I implemented a shared pointer like this. It uses
 the pointer value itself as a spin lock with the assumption that -1 is
 an invalid pointer value:

 1. read pointer value
 2. if read value is -1 go to line 1 (spin)
 3. compare and swap (previously read value <-> -1)
 4. if failure go to line 1 (spin)
 // now pointer is "locked", its value is -1 but we have a copy of the
 original
 5. copy pointer locally or assign to it (and update counter)
 6. write back pointer value atomically to replace the -1

 No mutex, but there's a spin lock so it's not good if there's
 contention.

 That said, I find it extremely rare to want a shared pointer that isn't
 already protected by a mutex alongside other variables, or that isn't
 propagated using some form of message passing.

Locking is very bad if you have threads at different priorities as it might introduce priority inversion. Spinning is probably even worse in that scenario.

Spinning is good only when you very rarely expect contention, which is the case for me. The above code is used once per object the first time someone requests a weak pointer for it. Having contention for that just doesn't make sense in most usage patterns. But still, being curious I added a log message anytime it does actually has to spin, and I have yet to see that message once in my logs (which probably means aggressive enough unit tests are missing). If you have a lot of read accesses and rarely write to the pointer you could instead try a read-write mutex with concurrent read access. In any case, there's no solution that will be ideal in all cases. Different situations asks for different trade-offs.
 At work, I use shared pointers all the time to pass information to a
 real time audio thread. The scheme uses triple-buffering of pointers
 for a lock free safe transport from/to the real time thread.

 Not having to worry about these low-level locking stuff is one of the
 good aspects about garbage collecting.

Indeed. The current garbage collector makes it easy to have shared pointers to shared objects. But the GC can also interrupt real-time threads for an unpredictable duration, how do you cope with that in a real-time thread? I know ARC isn't the ideal solution for all use cases. But neither is the GC, especially for real-time applications. So, which one would you recommend for a project having a real-time audio thread?

Well, if real time concurrent GC for Java systems is good enough for systems that control militar missile systems, maybe it is good enough for real-time audio as well. -- Paulo
Oct 14 2013
parent reply Benjamin Thaut <code benjamin-thaut.de> writes:
Am 14.10.2013 22:59, schrieb Paulo Pinto:
 Well, if real time concurrent GC for Java systems is good enough for
 systems that control militar missile systems, maybe it is good enough
 for real-time audio as well.

 --
 Paulo

The problem is not that there are no GCs around in other languages which satisfy certain requirements. The problem is actually implementing them in D. I suggest that you read "The Garbage Collection Handbook" which explains this in deep detail. I'm currently reading it, and I might write an article about the entire D GC issue once I'm done with it.
Oct 16 2013
next sibling parent Paulo Pinto <pjmlp progtools.org> writes:
Am 16.10.2013 20:54, schrieb Benjamin Thaut:
 Am 14.10.2013 22:59, schrieb Paulo Pinto:
 Well, if real time concurrent GC for Java systems is good enough for
 systems that control militar missile systems, maybe it is good enough
 for real-time audio as well.

 --
 Paulo

The problem is not that there are no GCs around in other languages which satisfy certain requirements. The problem is actually implementing them in D. I suggest that you read "The Garbage Collection Handbook" which explains this in deep detail. I'm currently reading it, and I might write an article about the entire D GC issue once I'm done with it.

I have read it when it came out in the late 90's. My main focus areas in the university were compiler design, distributed systems and graphics programming. Although, like many, I tend to do plain boring enterprise applications nowadays. -- Paulo
Oct 16 2013
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-10-16 21:05, Sean Kelly wrote:

 I think the short version is that D being able to directly call C code is a
huge problem here.  Incremental GCs all rely on the GC being notified when
pointers are changed.  We might be able to manage it for SafeD, but then SafeD
would basically be its own language.

One need to be very careful with the memory when interfacing with C code today. What about having a function that notifies the GC that a pointer has been updated? -- /Jacob Carlborg
Oct 16 2013
prev sibling parent reply Benjamin Thaut <code benjamin-thaut.de> writes:
Am 16.10.2013 21:05, schrieb Sean Kelly:
 On Oct 16, 2013, at 11:54 AM, Benjamin Thaut <code benjamin-thaut.de> wrote:
 The problem is not that there are no GCs around in other languages which
satisfy certain requirements. The problem is actually implementing them in D. I
suggest that you read "The Garbage Collection Handbook" which explains this in
deep detail. I'm currently reading it, and I might write an article about the
entire D GC issue once I'm done with it.

I think the short version is that D being able to directly call C code is a huge problem here. Incremental GCs all rely on the GC being notified when pointers are changed. We might be able to manage it for SafeD, but then SafeD would basically be its own language.

I think a even bigger problem are structs. Because if you need write barriers for pointers on the heap you are going to have a problem with structs. Because you will never know if they are located on the heap or the stack. Additionally making the stack percisely scannable and adding GC-Points will require a lot of compiler support. And even if this is doable in respect to DMD its going to be a big problem for GDC or LDC to change the codegen.
Oct 16 2013
parent reply Benjamin Thaut <code benjamin-thaut.de> writes:
Am 17.10.2013 19:16, schrieb David Nadlinger:
 On Thursday, 17 October 2013 at 17:11:06 UTC, Sean Kelly wrote:
 And even if this is doable in respect to DMD its going to be a big
 problem for GDC or LDC to change the codegen.

Yes, any pointer anywhere. I recall someone posting a doc about a compromise solution a few years back, but I'd have to do some digging to figure out what the approach was.

LLVM actually comes with a quite expensive GC support infrastructure: http://llvm.org/docs/GarbageCollection.html. As far as I'm aware, it is not widely used in terms of the "top-tier" LLVM projects, so there might be quite a bit of work involved in getting that to run. David

Uhhh, this sounds really good. They in fact have everything to implement a generational garbage collector. This would improve the D GC situation a lot. But reading the part about the shadow stack really lowers my expectations. Thats really something you don't want. The performance impact is so going to be so big, that it doesn't make sense to use the better GC in the first place. Kind Regards Benjamin Thaut
Oct 17 2013
parent Benjamin Thaut <code benjamin-thaut.de> writes:
Am 17.10.2013 19:47, schrieb Sean Kelly:
 On Thursday, 17 October 2013 at 17:28:17 UTC, Benjamin Thaut wrote:
 Am 17.10.2013 19:16, schrieb David Nadlinger:

 But reading the part about the shadow stack really lowers my
 expectations. Thats really something you don't want. The performance
 impact is so going to be so big, that it doesn't make sense to use the
 better GC in the first place.

There's always a tradeoff. If an app is very delay-sensitive, then making the app run slower in general might be worthwhile if the delay could be eliminated.

Well I just read it again, and it appears to me that the shadow stack is something they already have implemented and it can be used for "gc prototyping" but if you want you can write your own code generator plugin and generate your own stack maps. It actually sounds more feasable to implement a generational GC with LLVM then with what we have in dmd. Kind Regards Benjamin Thaut
Oct 17 2013
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-14 20:45:35 +0000, "deadalnix" <deadalnix gmail.com> said:

 On Monday, 14 October 2013 at 19:42:36 UTC, Michel Fortin wrote:
 Indeed. The current garbage collector makes it easy to have shared 
 pointers to shared objects. But the GC can also interrupt real-time 
 threads for an unpredictable duration, how do you cope with that in a 
 real-time thread?
 
 I know ARC isn't the ideal solution for all use cases. But neither is 
 the GC, especially for real-time applications. So, which one would you 
 recommend for a project having a real-time audio thread?

If you don't want any pause, concurrent GC is the way to go. This type of GC come at a cost of increased memory usage (everything is a tradeoff) but exists.

I'm not an expert in GCs, but as far as I know a concurrent GC also requires some bookkeeping to be done when assigning to pointers, similar to ARC, and also when moving pointers, unlike ARC. So it requires hooks in the codegen that will perform atomic operations, just like ARC. Unless of course you use "fork" and scan inside the child process… but that has its own set of problems on some platforms. The only consensus we'll reach is that different projects have different needs. In theory being able to swap the GC for something else could bring everyone together. But to be able to replace the GC for another with a strategy different enough to matter (concurrent GC or ARC) you need the codegen to be different. So we can either: 1. make the codegen configurable -- which brings its own set of compatibility problems for compiled code but is good for experimentation, or 2. settle on something middle-ground performance-wise that can accommodate a couple of strategies, or 3. choose one GC strategy that ought to satisfy everybody and adapt the codegen to fit, or 4. keep everything as is. We're stuck with 4 until something else is decided. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 14 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-14 23:45:42 +0000, "deadalnix" <deadalnix gmail.com> said:

 On Monday, 14 October 2013 at 21:25:29 UTC, Michel Fortin wrote:
 I'm not an expert in GCs, but as far as I know a concurrent GC also 
 requires some bookkeeping to be done when assigning to pointers, 
 similar to ARC, and also when moving pointers, unlike ARC. So it 
 requires hooks in the codegen that will perform atomic operations, just 
 like ARC.

Usual strategy include : - When you JIT, change the function itself, to write pointers through a function that mark the old value as live. - When AOT, always go throw that function, which make a test and mark alive the old value if this is done during a collection. This basically add a read to a global and a test for each pointer write. - Use the page protection mechanism and do regular write. This can be done via fork, but also via remapping the GCed memory as COW. The tax is then more expensive, but you only pay it once per page you actually write and only when actually collecting. The good news, is that this tax is only required for object that contains shared mutable pointers. In D, most data are thread local or immutable. D's type system is really friendly to concurrent GC, and we definitively should go in that direction.
 The only consensus we'll reach is that different projects have 
 different needs. In theory being able to swap the GC for something else 
 could bring everyone together. But to be able to replace the GC for 
 another with a strategy different enough to matter (concurrent GC or 
 ARC) you need the codegen to be different. So we caneither:

ARC like system need a different codegen, but you can do this with regular codegen if you use page protection to detect writes.

Very insightful. Thank you.
 1. make the codegen configurable -- which brings its own set of 
 compatibility problems for compiled code but is good for 
 experimentation, or

Bad, we will end up having different incompatible binaries.

So as I understand it, your plan would then be: - use concurrent GC using the page protection mechanism and COW to catch writes during collection - add thread-local awareness to the GC so only shared and mutable memory needs COW Makes sense. But adding thread-local awareness requires a couple of language changes. It won't work as long as people keep casting things around so you need to fix a lot of cases where casts are needed. But otherwise, seems like a good plan. I'm a little wary of the cost of doing COW during collection. Obviously the GC isn't pausing the program per-see, but it'll be slowing it down. By how much is probably dependent on what you're doing. At the very least the GC should allocate types with no pointers on separate pages from those with pointers. Also, what are the calls required to implement page protection and COW on posix? I'd like to check whether those are allowed within the OS X and iOS sandbox. For instance fork() isn't allowed for sandboxed apps. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 14 2013
next sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-15 02:20:49 +0000, "deadalnix" <deadalnix gmail.com> said:

 Also, what are the calls required to implement page protection and COW 
 on posix? I'd like to check whether those are allowed within the OS X 
 and iOS sandbox. For instance fork() isn't allowed for sandboxed apps.

You need mmap, mprotect and all the signal handling machinery.

mprotect is the one I'm worried about, as it lets you set the executable bit (among other things) which could be exploited to run arbitrary code. So I tested it and it seems to work fine on OS X inside the sandbox (including for setting the executable bit). I guess an executable with a reference to mprotect would probably also pass Apple's Mac App Store validation, but I haven't tested. mprotect isn't available at all with the iOS SDK. So making this collector work on iOS (and the iOS Simulator) would require a different codegen. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 14 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-10-15 05:11, Michel Fortin wrote:

 mprotect isn't available at all with the iOS SDK. So making this
 collector work on iOS (and the iOS Simulator) would require a different
 codegen.

I haven't tried compiling anything and I don't know if I'm looking in the correct file but this file: /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS7.0.sdk/usr/include/sys/mman.h Does contain "mprotect". -- /Jacob Carlborg
Oct 15 2013
parent Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-15 07:28:16 +0000, Jacob Carlborg <doob me.com> said:

 On 2013-10-15 05:11, Michel Fortin wrote:
 
 mprotect isn't available at all with the iOS SDK. So making this
 collector work on iOS (and the iOS Simulator) would require a different
 codegen.

I haven't tried compiling anything and I don't know if I'm looking in the correct file but this file: /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS7.0.sdk/usr/include/sys/mman.h

Does
 
 contain "mprotect".

You're right. Yes it does exist. I was confused. Not only it does exist, but it lets you set the executable bit. I find that depressing, since I'm pretty sure App Store apps are prevented from setting the executable bit, and I'd tend to think now that they're blocking it by checking for references to mprotect it in the executable when submitting to the App Store. And by doing it this way they probably wouldn't be able to distinguish between setting the executable bit or making a page read-only. Also, someone would need to check that Windows Phone apps and Windows 8-style (Metro) apps can access mprotect (or equivalent) too. They're sandboxed just as heavily and statically checked upon submission the same way. Could some game consoles out there block it too? -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 15 2013
prev sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-15 02:20:49 +0000, "deadalnix" <deadalnix gmail.com> said:

 It will indeed cause trouble for code that mutate a large amount of 
 shared pointers. I'd say that such code is probably asking for trouble 
 in the first place, but as always, no silver bullet. I still think 
 solution is the one that fit D the best.

I think there's a small mistake in your phrasing, but it makes a difference. When the collector is running, it needs to know about any mutation for pointers to its shared memory pool, including pointers that are themselves thread-local but point to shared memory. So COW will be trouble for code that mutate a large amount of **pages containing pointers to shared memory**. And this which includes **pointers to immutable data** because immutable is implicitly shared. And this includes **pointers to const data** since those pointers might point to immutable (thus shared) memory. So any memory page susceptible of containing pointers to shared memory would need to use COW during collection. Which means all the thread's stacks, and also all objects with a pointer to shared, immutable, and const data. At this point I think it is fair to approximate this to almost all memory that could contain pointers. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 15 2013
parent Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-15 18:32:01 +0000, "deadalnix" <deadalnix gmail.com> said:

 No, that is the beauty of it :D
 
 Consider you have pointer from Tl -> shared -> immutable and TL -> immutable.
 
 I'm not covering TL collection here (It seem to be obvious that it 
 doesn't require to stop the world). So the starting point is that we 
 have the roots in all TL heaps/stacks, and we want to collect 
 shared/immutable without blocking the worlds.
 
 TL heap may get new pointers to the shared heap, but they can only come 
 from the shared heap itself or new allocations. At this point, you 
 consider every new allocations as live.
 
 Reading a pointer from the shared heap and copy it to the TL heap isn't 
 problematic in itself, but then we have a problem if this pointer is 
 now updated in the shared heap, as the GC may never scan this pointer.
 
 This is why you need to track pointer writes to the shared heap. The 
 write value itself isn't important : it come from either new alloc that 
 are live, or from somewhere else in the shared heap (so it will be 
 scanned as we track writes).

But you still have to scan the thread-local heaps and stacks to find pointers to shared memory. If you don't stop those threads, how do you know one of these threads isn't moving a pointer value during the scan from one place the GC still has to scan to another that the GC has just scanned, making it so the GC never sees the pointer? For instance: class A { // string is immutable and points to shared heap immutable(char)[] s; } A global; void func() { // GC scans the stack of this thread in the background // no reference to our string on the stack // moving string pointer to the stack // while the GC is running auto tmp = global.s; global.s = null; // GC scans the heap of this thread in the background // no reference to our string on the heap // (missed reference to our string now on the stack) } The thread can move the pointer around while the GC is looking away and you'll end up with a pointer to a freed string. So you have to use COW for the thread's stack, or get notified of a pointer assignment somehow (or of a pointer move), or stop the thread while you're scanning its heap. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 15 2013
prev sibling parent Rainer Schuetze <r.sagitario gmx.de> writes:
On 14.10.2013 21:42, Michel Fortin wrote:
 Indeed. The current garbage collector makes it easy to have shared
 pointers to shared objects. But the GC can also interrupt real-time
 threads for an unpredictable duration, how do you cope with that in a
 real-time thread?

The work I was talking about uses C++, not D, so there is no GC involved. The options I see for real-time threads in D is either a concurrent GC (which means read/write barriers for pointer accesses) or just excluding the real time thread from suspension by the GC. This forces the programmer to ensure that references in the real time thread are also found elsewhere. I'm not sure if this eliminates the benefits regarding locking, though.
 I know ARC isn't the ideal solution for all use cases. But neither is
 the GC, especially for real-time applications. So, which one would you
 recommend for a project having a real-time audio thread?

ARC doesn't work for real time threads anyway, because you are not allowed to deallocate if it can cause locks. It can only work if you defer reference counting into another thread through some buffering. Realistically I would currently recommend the approach above: exclude the thread from suspension, and keep a reference to used object elsewhere. This is probably about as difficult as avoiding allocations/deallocations in C++, but harder to debug.
Oct 15 2013
prev sibling parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 12.10.2013 20:31, deadalnix wrote:
 On Saturday, 12 October 2013 at 06:16:24 UTC, Rainer Schuetze wrote:
 in pseudo-assembly missing null-checks:

 Thread1 (R = P)        Thread2 (S = R)

                        mov ecx,[R]
                        ; thread suspended

You need an sequentially consistent write. You also need to increment the refcount BEFORE ! This codegen is incorrect.

How do you increment the counter without reading its address?
 mov eax,[P]
 inc [eax].refcnt

Same here.

Same here ;-)
 mov ebx,[R]
 mov [R],eax
 dec [ebx].refcnt      ; refcnt of O now 0
 jnz done
 call delete_ebx
                        ; thread resumed
                        inc [ecx].refcnt
 done:

 The increment on [ecx].refcnt modifies garbage.

This can be done atomically (even with eventually consistent increment, don't need full sequential consistency here, you still need fully sequential consistent decrement).

According to the "Handbook of Garbage Collection" by Richard Jones eager lock-free reference counting can only be done with a cas2 operation modifying two seperate locations atomically (algorithm 18.2 "Eager reference counting with CompareAndSwap is broken"). This might be the quoted paper: http://scholr.ly/paper/2199608/lock-free-reference-counting Unfortunately the CAS2 operation does not exist in most processors.
Oct 13 2013
parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 13.10.2013 17:15, schrieb Sean Kelly:
 On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 According to the "Handbook of Garbage Collection" by Richard Jones
 eager lock-free reference counting can only be done with a cas2
 operation modifying two seperate locations atomically (algorithm 18.2
 "Eager reference counting with CompareAndSwap is broken"). This might
 be the quoted paper:
 http://scholr.ly/paper/2199608/lock-free-reference-counting

 Unfortunately the CAS2 operation does not exist in most processors.

I suppose it's worth noting that Boost (and now standard C++) has a shared_ptr that works across threads and the implementation I've seen doesn't use a mutex. In fact, I think the Boost one doesn't even use CAS on x86, though it's been quite a few years so my memory could be wrong on that last detail.

I didn't read the paper, but I'd suspect that the paper refers to the case where both, the reference count _and_ the reference is thread-safe, since the boost/c++ shared_ptr only has a thread-safe reference count after all.
Oct 13 2013
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 13.10.2013 19:05, Sönke Ludwig wrote:
 Am 13.10.2013 17:15, schrieb Sean Kelly:
 On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 According to the "Handbook of Garbage Collection" by Richard Jones
 eager lock-free reference counting can only be done with a cas2
 operation modifying two seperate locations atomically (algorithm 18.2
 "Eager reference counting with CompareAndSwap is broken"). This might
 be the quoted paper:
 http://scholr.ly/paper/2199608/lock-free-reference-counting

 Unfortunately the CAS2 operation does not exist in most processors.

I suppose it's worth noting that Boost (and now standard C++) has a shared_ptr that works across threads and the implementation I've seen doesn't use a mutex. In fact, I think the Boost one doesn't even use CAS on x86, though it's been quite a few years so my memory could be wrong on that last detail.

I didn't read the paper, but I'd suspect that the paper refers to the case where both, the reference count _and_ the reference is thread-safe, since the boost/c++ shared_ptr only has a thread-safe reference count after all.

I haven't read it either, but AFAICT the cas2 operation is used two modify the pointer and the reference count at the same time atomically. I just checked boost::shared_ptr, it uses cas operations on the reference counts. It has the same problem as described in my example, see the read/write example 3 here: http://www.boost.org/doc/libs/1_54_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety boost::shared_ptr is also unsafe with respect to calling member functions through "->" as it doesn't increment the reference count.
Oct 14 2013
parent Rainer Schuetze <r.sagitario gmx.de> writes:
On 14.10.2013 19:50, John Colvin wrote:
 On Monday, 14 October 2013 at 17:43:33 UTC, Rainer Schuetze wrote:
 On 13.10.2013 19:05, Sönke Ludwig wrote:
 Am 13.10.2013 17:15, schrieb Sean Kelly:
 On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 According to the "Handbook of Garbage Collection" by Richard Jones
 eager lock-free reference counting can only be done with a cas2
 operation modifying two seperate locations atomically (algorithm 18.2
 "Eager reference counting with CompareAndSwap is broken"). This might
 be the quoted paper:
 http://scholr.ly/paper/2199608/lock-free-reference-counting

 Unfortunately the CAS2 operation does not exist in most processors.

I suppose it's worth noting that Boost (and now standard C++) has a shared_ptr that works across threads and the implementation I've seen doesn't use a mutex. In fact, I think the Boost one doesn't even use CAS on x86, though it's been quite a few years so my memory could be wrong on that last detail.

I didn't read the paper, but I'd suspect that the paper refers to the case where both, the reference count _and_ the reference is thread-safe, since the boost/c++ shared_ptr only has a thread-safe reference count after all.

I haven't read it either, but AFAICT the cas2 operation is used two modify the pointer and the reference count at the same time atomically. I just checked boost::shared_ptr, it uses cas operations on the reference counts. It has the same problem as described in my example, see the read/write example 3 here: http://www.boost.org/doc/libs/1_54_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety boost::shared_ptr is also unsafe with respect to calling member functions through "->" as it doesn't increment the reference count.

I'm totally out of my depth here but can't you store the reference count adjacent to the pointer and use CMPXCHG16B

This might work for a single pointer, but not if you have multiple pointers to the same object.
Oct 14 2013
prev sibling next sibling parent "inout" <inout gmail.com> writes:
On Thursday, 10 October 2013 at 08:55:00 UTC, Robert Schadek
wrote:
 On 10/10/2013 03:45 AM, Walter Bright wrote:
 Rainer Schuetze wrote:

 You have to put the lock around the pair of AddRef and 
 Release, but if
 the compiler already splits this into two function calls, this 
 cannot
 be done in the implementation.

atomic_add_and_fetch operations, so no locks are required.

On shared objects, yes. Local objects need no atomics at all.
Oct 11 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Saturday, 12 October 2013 at 06:16:24 UTC, Rainer Schuetze 
wrote:
 in pseudo-assembly missing null-checks:

 Thread1 (R = P)        Thread2 (S = R)

                        mov ecx,[R]
                        ; thread suspended

You need an sequentially consistent write. You also need to increment the refcount BEFORE ! This codegen is incorrect.
 mov eax,[P]
 inc [eax].refcnt

Same here.
 mov ebx,[R]
 mov [R],eax
 dec [ebx].refcnt      ; refcnt of O now 0
 jnz done
 call delete_ebx
                        ; thread resumed
                        inc [ecx].refcnt
 done:

 The increment on [ecx].refcnt modifies garbage.

This can be done atomically (even with eventually consistent increment, don't need full sequential consistency here, you still need fully sequential consistent decrement).
Oct 12 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 How do you increment the counter without reading its address?

I assumed that the reference count was in a struct with the data, and refcounted point to it. In this case, if you remove the pointer via a sequencially consistent write (while keeping a local copy internally) and THEN decrement the counter, the other thread will access another object (or skip on a null check). Granted the read is sequencially consistent.
Oct 13 2013
prev sibling next sibling parent "Sean Kelly" <sean invisibleduck.org> writes:
On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 According to the "Handbook of Garbage Collection" by Richard 
 Jones eager lock-free reference counting can only be done with 
 a cas2 operation modifying two seperate locations atomically 
 (algorithm 18.2 "Eager reference counting with CompareAndSwap 
 is broken"). This might be the quoted paper: 
 http://scholr.ly/paper/2199608/lock-free-reference-counting

 Unfortunately the CAS2 operation does not exist in most 
 processors.

I suppose it's worth noting that Boost (and now standard C++) has a shared_ptr that works across threads and the implementation I've seen doesn't use a mutex. In fact, I think the Boost one doesn't even use CAS on x86, though it's been quite a few years so my memory could be wrong on that last detail.
Oct 13 2013
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Monday, 14 October 2013 at 17:43:33 UTC, Rainer Schuetze wrote:
 On 13.10.2013 19:05, Sönke Ludwig wrote:
 Am 13.10.2013 17:15, schrieb Sean Kelly:
 On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze 
 wrote:
 According to the "Handbook of Garbage Collection" by Richard 
 Jones
 eager lock-free reference counting can only be done with a 
 cas2
 operation modifying two seperate locations atomically 
 (algorithm 18.2
 "Eager reference counting with CompareAndSwap is broken"). 
 This might
 be the quoted paper:
 http://scholr.ly/paper/2199608/lock-free-reference-counting

 Unfortunately the CAS2 operation does not exist in most 
 processors.

I suppose it's worth noting that Boost (and now standard C++) has a shared_ptr that works across threads and the implementation I've seen doesn't use a mutex. In fact, I think the Boost one doesn't even use CAS on x86, though it's been quite a few years so my memory could be wrong on that last detail.

I didn't read the paper, but I'd suspect that the paper refers to the case where both, the reference count _and_ the reference is thread-safe, since the boost/c++ shared_ptr only has a thread-safe reference count after all.

I haven't read it either, but AFAICT the cas2 operation is used two modify the pointer and the reference count at the same time atomically. I just checked boost::shared_ptr, it uses cas operations on the reference counts. It has the same problem as described in my example, see the read/write example 3 here: http://www.boost.org/doc/libs/1_54_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety boost::shared_ptr is also unsafe with respect to calling member functions through "->" as it doesn't increment the reference count.

I'm totally out of my depth here but can't you store the reference count adjacent to the pointer and use CMPXCHG16B
Oct 14 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 14 October 2013 at 17:50:01 UTC, John Colvin wrote:
 I'm totally out of my depth here but can't you store the 
 reference count adjacent to the pointer and use CMPXCHG16B

I think that can work if the refcount is stored with the pointer (ie. if a fat pointer is used) and not in the object. But that would defeat the whole point of the refcount :( It seems that Rainer Schuetze is right and that the implementation that boost::shared_ptr uses is not safe.
Oct 14 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 14 October 2013 at 19:42:36 UTC, Michel Fortin wrote:
 Indeed. The current garbage collector makes it easy to have 
 shared pointers to shared objects. But the GC can also 
 interrupt real-time threads for an unpredictable duration, how 
 do you cope with that in a real-time thread?

 I know ARC isn't the ideal solution for all use cases. But 
 neither is the GC, especially for real-time applications. So, 
 which one would you recommend for a project having a real-time 
 audio thread?

If you don't want any pause, concurrent GC is the way to go. This type of GC come at a cost of increased memory usage (everything is a tradeoff) but exists.
Oct 14 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 14 October 2013 at 21:25:29 UTC, Michel Fortin wrote:
 I'm not an expert in GCs, but as far as I know a concurrent GC 
 also requires some bookkeeping to be done when assigning to 
 pointers, similar to ARC, and also when moving pointers, unlike 
 ARC. So it requires hooks in the codegen that will perform 
 atomic operations, just like ARC.

Usual strategy include : - When you JIT, change the function itself, to write pointers through a function that mark the old value as live. - When AOT, always go throw that function, which make a test and mark alive the old value if this is done during a collection. This basically add a read to a global and a test for each pointer write. - Use the page protection mechanism and do regular write. This can be done via fork, but also via remapping the GCed memory as COW. The tax is then more expensive, but you only pay it once per page you actually write and only when actually collecting. The good news, is that this tax is only required for object that contains shared mutable pointers. In D, most data are thread local or immutable. D's type system is really friendly to concurrent GC, and we definitively should go in that direction.
 The only consensus we'll reach is that different projects have 
 different needs. In theory being able to swap the GC for 
 something else could bring everyone together. But to be able to 
 replace the GC for another with a strategy different enough to 
 matter (concurrent GC or ARC) you need the codegen to be 
 different. So we can either:

ARC like system need a different codegen, but you can do this with regular codegen if you use page protection to detect writes.
 1. make the codegen configurable -- which brings its own set of 
 compatibility problems for compiled code but is good for 
 experimentation, or

Bad, we will end up having different incompatible binaries.
Oct 14 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 15 October 2013 at 00:38:20 UTC, Michel Fortin wrote:
 So as I understand it, your plan would then be:

 - use concurrent GC using the page protection mechanism and COW 
 to catch writes during collection
 - add thread-local awareness to the GC so only shared and 
 mutable memory needs COW

Yes, I think this is what make the most sense for D. If the GC allow explicit free; the reference counting and other manual memory management techniques can be built on top of it.
 Makes sense. But adding thread-local awareness requires a 
 couple of language changes. It won't work as long as people 
 keep casting things around so you need to fix a lot of cases 
 where casts are needed.

Type qualifiers provide the necessary information. However, some practice (that are already mentioned as being undefined behavior) will become really unsafe. It also require to enrich the GC api, but users aren't supposed to use it directly :D
 I'm a little wary of the cost of doing COW during collection. 
 Obviously the GC isn't pausing the program per-see, but it'll 
 be slowing it down. By how much is probably dependent on what 
 you're doing. At the very least the GC should allocate types 
 with no pointers on separate pages from those with pointers.

Nothing is free, and indeed, trapping the write via memory protection is quite expensive. Hopefully, we can segregate object that contain mutable pointer from others and only memory protect theses. It will indeed cause trouble for code that mutate a large amount of shared pointers. I'd say that such code is probably asking for trouble in the first place, but as always, no silver bullet. I still think solution is the one that fit D the best.
 Also, what are the calls required to implement page protection 
 and COW on posix? I'd like to check whether those are allowed 
 within the OS X and iOS sandbox. For instance fork() isn't 
 allowed for sandboxed apps.

You need mmap, mprotect and all the signal handling machinery.
Oct 14 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 15 October 2013 at 11:03:01 UTC, Michel Fortin wrote:
 On 2013-10-15 02:20:49 +0000, "deadalnix" <deadalnix gmail.com> 
 said:

 It will indeed cause trouble for code that mutate a large 
 amount of shared pointers. I'd say that such code is probably 
 asking for trouble in the first place, but as always, no 
 silver bullet. I still think solution is the one that fit D 
 the best.

I think there's a small mistake in your phrasing, but it makes a difference. When the collector is running, it needs to know about any mutation for pointers to its shared memory pool, including pointers that are themselves thread-local but point to shared memory. So COW will be trouble for code that mutate a large amount of **pages containing pointers to shared memory**. And this which includes **pointers to immutable data** because immutable is implicitly shared. And this includes **pointers to const data** since those pointers might point to immutable (thus shared) memory.

No, that is the beauty of it :D Consider you have pointer from Tl -> shared -> immutable and TL -> immutable. I'm not covering TL collection here (It seem to be obvious that it doesn't require to stop the world). So the starting point is that we have the roots in all TL heaps/stacks, and we want to collect shared/immutable without blocking the worlds. TL heap may get new pointers to the shared heap, but they can only come from the shared heap itself or new allocations. At this point, you consider every new allocations as live. Reading a pointer from the shared heap and copy it to the TL heap isn't problematic in itself, but then we have a problem if this pointer is now updated in the shared heap, as the GC may never scan this pointer. This is why you need to track pointer writes to the shared heap. The write value itself isn't important : it come from either new alloc that are live, or from somewhere else in the shared heap (so it will be scanned as we track writes).
 So any memory page susceptible of containing pointers to shared 
 memory would need to use COW during collection. Which means all 
 the thread's stacks, and also all objects with a pointer to 
 shared, immutable, and const data. At this point I think it is 
 fair to approximate this to almost all memory that could 
 contain pointers.

No, only the shared one, that is the beauty of the technique. Not that I'm not making that up myself, it is how GC used to work in the Caml family for a while, and it has proven itself really efficient (in Caml family, most data are either immutable or thread local, and the shared heap typically small).
Oct 15 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
Yes and no.

You obviously need to scan TL heaps at some point. When doing so 
you'll have a set of root that allow you to scan shared/immutable 
heap. What is going on in the TL heap become irrelevant once you 
have the root. And getting the roots from the TL heap is another 
problem altogether (any kind of GC can be used for that, stop the 
world, where the world is thread local, or another concurrent GC, 
the important point being that it is an independent problem).
Oct 16 2013
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
On Oct 16, 2013, at 11:54 AM, Benjamin Thaut <code benjamin-thaut.de> =
wrote:
=20
 The problem is not that there are no GCs around in other languages =

them in D. I suggest that you read "The Garbage Collection Handbook" = which explains this in deep detail. I'm currently reading it, and I = might write an article about the entire D GC issue once I'm done with = it. I think the short version is that D being able to directly call C code = is a huge problem here. Incremental GCs all rely on the GC being = notified when pointers are changed. We might be able to manage it for = SafeD, but then SafeD would basically be its own language.=
Oct 16 2013
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
On Oct 16, 2013, at 1:05 PM, Benjamin Thaut <code benjamin-thaut.de> wrote:
=20
 Am 16.10.2013 21:05, schrieb Sean Kelly:
 On Oct 16, 2013, at 11:54 AM, Benjamin Thaut <code benjamin-thaut.de> wro=


=20
 The problem is not that there are no GCs around in other languages which=



. I suggest that you read "The Garbage Collection Handbook" which explains t= his in deep detail. I'm currently reading it, and I might write an article a= bout the entire D GC issue once I'm done with it.
=20
 I think the short version is that D being able to directly call C code is=


n pointers are changed. We might be able to manage it for SafeD, but then S= afeD would basically be its own language.
=20
 I think a even bigger problem are structs. Because if you need write barri=

ecause you will never know if they are located on the heap or the stack. Add= itionally making the stack percisely scannable and adding GC-Points will req= uire a lot of compiler support. And even if this is doable in respect to DMD= its going to be a big problem for GDC or LDC to change the codegen. Yes, any pointer anywhere. I recall someone posting a doc about a compromise= solution a few years back, but I'd have to do some digging to figure out wh= at the approach was.=20=
Oct 17 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 October 2013 at 17:11:06 UTC, Sean Kelly wrote:
 And even if this is doable in respect to DMD its going to be a 
 big problem for GDC or LDC to change the codegen.

Yes, any pointer anywhere. I recall someone posting a doc about a compromise solution a few years back, but I'd have to do some digging to figure out what the approach was.

LLVM actually comes with a quite expensive GC support infrastructure: http://llvm.org/docs/GarbageCollection.html. As far as I'm aware, it is not widely used in terms of the "top-tier" LLVM projects, so there might be quite a bit of work involved in getting that to run. David
Oct 17 2013
prev sibling parent "Sean Kelly" <sean invisibleduck.org> writes:
On Thursday, 17 October 2013 at 17:28:17 UTC, Benjamin Thaut 
wrote:
 Am 17.10.2013 19:16, schrieb David Nadlinger:

 But reading the part about the shadow stack really lowers my 
 expectations. Thats really something you don't want. The 
 performance impact is so going to be so big, that it doesn't 
 make sense to use the better GC in the first place.

There's always a tradeoff. If an app is very delay-sensitive, then making the app run slower in general might be worthwhile if the delay could be eliminated.
Oct 17 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 26.06.2013 13:12, Michel Fortin wrote:
 Le 26-juin-2013 à 5:38, Walter Bright  a
 écrit :

 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 As Michel also said, the reference count does not have to be in
 inside the object itself, so we might want to allow reference
 counting on other types aswell.

That opens the question of what is the point of other RC types? For example, C++ can throw any type - but it turns out that throwing anything but class types is largely pointless.

RC is just another garbage collection scheme. You might favor it for its performance characteristics, its determinism, or the lower memory footprint. Or you might need it to interact with foreign code that relies on it (COM, Objective-C, etc.), in which case it needs to be customizable (use the foreign implementation) or be manually managed. That's two different use cases. And in the later case you can't use the GC to release cycles because foreign code is using memory invisible to the GC. It is important to note that when foreign code calls AddRef you don't want the GC to collect that object, at least not until Release is called.

That means you have to maintain two reference counts if you have both ARC and COM used in the same class. ARC can only release the object if both counters are 0, while the COM implementation has to add/remove roots to the GC when counting from/to 0 to avoid that the object is collected while external references exist.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 2013-06-26 à 17:42, Rainer Schuetze <r.sagitario gmx.de> a écrit :

 On 26.06.2013 13:12, Michel Fortin wrote:
 Le 26-juin-2013 à 5:38, Walter Bright  a
 écrit :

 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 As Michel also said, the reference count does not have to be in
 inside the object itself, so we might want to allow reference
 counting on other types aswell.

That opens the question of what is the point of other RC types? For example, C++ can throw any type - but it turns out that throwing anything but class types is largely pointless.

RC is just another garbage collection scheme. You might favor it for its performance characteristics, its determinism, or the lower memory footprint. Or you might need it to interact with foreign code that relies on it (COM, Objective-C, etc.), in which case it needs to be customizable (use the foreign implementation) or be manually managed. That's two different use cases. And in the later case you can't use the GC to release cycles because foreign code is using memory invisible to the GC. It is important to note that when foreign code calls AddRef you don't want the GC to collect that object, at least not until Release is called.

That means you have to maintain two reference counts if you have both ARC and

0, while the COM implementation has to add/remove roots to the GC when counting from/to 0 to avoid that the object is collected while external references exist. Yes. The "external" reference count prevents the gc from releasing memory and the "internal" reference count keeps track of the number of references from gc-scanned memory. When both fall to zero, the memory is released immediately; when the external count falls to zero, the gc can collect memory if it isn't connected to any of its roots. Note that you could implement the external count as a separate hash table that'll include a gc-scanned pointer to the object. That pointer would keep the internal count above zero as long as it is present in the table. The external count doesn't need to be formally part of the gc data structure.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/26/2013 4:15 AM, Michel Fortin wrote:
 Well, it's mostly required to write runtime support functions. The attribute 

to implement the ref-counting code you'll need that. I know the temptation is strong to create more attributes as an easy solution, but I'd really like to try hard to find other ways.
 D would need manual, RC and GC to coexist peacefully.

 The problem is how to make the three of those use the same codegen?

 - Druntime could have a flag to disable/enable refcounting. It'd make the 

memory as it does today.
 - Druntime could have a flag to disable/enable garbage collection (it already 

pointers to work around that or request a collection manually at the appropriate time.
 - A  noarc (or similar) attribute at the function level could be used to 

could make a whole module noarc if you want by adding " noarc:" at the top.
 Here's the annoying thing:  noarc is totally safe if reference counting is 

counting is enabled. I don't really understand your point. My proposal enables manual, RC and GC to coexist peacefully. The GC wouldn't even know about RC.
 The downside is that every assignment to a pointer anywhere has to call a 



a GC scan and would be preferred in some situation (games I guess). Another downside is you have an object retained by being present on the stack frame of a C function, it'd have to be explicitly retained from elsewhere.
 Doesn't this make it impractical to mix vanilla C with D code? An important 


 It's not very different than with the GC today.

 If you call a C function by giving it a ref-counted pointer argument, that 

is retained by the caller). So simple calls to C functions are not a problem.
 If the C function puts that pointer elsewhere you'll need to retain it some 

callback called from C you need to care about what you return because the caller's C code won't retain it, while with the GC you could manage if C code did not store that pointer outside of the stack.
 I think that's all you have to worry about.

D (like C and C++) loves to manipulate pointers. Having to call a function every time this is done would be a disaster. It means that people would be motivated to drop down to C to do the fast code, and we might as well throw in the towel.
 As for D switching to a full refcounted GC for everything, I'm very hesitant 


pointer and function annotations necessary is very off-putting.
 Don't let Clang intimidate you. The Clang spec is about four to five time 

supports weak pointers. Weak pointers can be implemented as a struct templates (as long as we have noarc). And all those annotations are for special cases, when you need to break the rules. You don't use them when doing normal programming, well except for __weak.

Ok.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/26/2013 2:33 PM, Rainer Schuetze wrote:
 On 26.06.2013 11:38, Walter Bright wrote:
 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 I imagine a few (constrained) templated functions for the different
 operations defined in the library could also do the job, though it
 might drown compilation speed. Also getting help from the optimizer to
 remove redundant calls will need some back doors.

I don't see how this can be done without specific compiler knowledge in a memory safe way.

I currently don't see how it can be memory safe with this proposal.

I'm a little confused about what you are referring to here.
 3. Assignment to a class reference causes a call to AddRef() on the new
 value
 followed by a call to Release() on its original value.

It might be common knowledge, but I want to point out that the usual COM implementation (atomic increment/decrement and free when refcount goes down to 0) is not thread-safe for shared pointers. That means you either have to guard all reads and writes with a lock to make the full assignment atomic or have to implement reference counting very different (e.g. deferred reference counting).

Since the implementation of AddRef()/Release() is up to the user, whether it uses locks or not and whether it supports shared or not is up to the user.

You have to put the lock around the pair of AddRef and Release, but if the

implementation. Why is it necessary to put a lock around the pair?
 12. AddRef() is not called when passed as the implicit 'this' reference.

Isn't this unsafe if a member function is called through the last existing reference and this reference is then cleared during execution of this member function or from another thread?

No. The caller of the function still retains a reference in that thread.

Hmmm, I guess I misunderstand the proposal. Assume for example a refcounted

 class R : RefCounted
 {
     int _x;
     int readx() { return _x; }
 }
 int main()
 {
     R r = new R;
     return r.readx();
 }

 According to 12. there is no refcounting going on when calling or executing 

 class R : RefCounted
 {
     int _x;
     int readx(C c)
     {
         c.r = null; // "standard" rc deletes r here
         return _x;  // reads garbage
     }
 }
 class C
 {
     R r;
 }
 int main()
 {
     C c = new C;
     c.r = new R;
     return c.r.readx(c);
 }

 This reads garbage or crashes if there is no reference counting going on when 

I think you're right. Grrrr!
 13. Taking the address of, or passing by reference, any fields of an RC
 object
 is not allowed in  safe code. Passing by reference an RC field is
 allowed.

Please note that this includes slices to fixed size arrays.

As I suggested, arrays would not be supported with this proposal - but the user can create ref counted array-like objects.

Just to clarify, I meant taking a slice of a static array that is a field of

class or is taking the address through slicing forbidden? It would be forbidden to obtain a slice of a ref counted object in this way - or even to simply refer to a static array embedded in a ref counted object (in safe code).
 I feel I'm hijacking this proposal, but the step to library defined
 read/write barriers seems pretty small. Make AddRef, Release and
 assignment free template functions, e.g.

 void ptrConstruct(T,bool stackOrHeap)(T*adr, T p);
 void ptrAssign(T,bool stackOrHeap)(T*adr, T p);
 void ptrRelease(T,bool stackOrHeap)(T*adr);

 and we are able to experiment with all kinds of sophisticated GC
 algorithms including RC. Eliding redundant addref/release pairs would
 need some extra support though, I read that LLVM does something like
 this, but I don't know how.

It's pretty invasive into the code generation and performance, and could completely disrupt the C compatibility of D.

I don't see a big difference between a free function and a member function

 Two more notes:

 - I'm not sure it is mentioned, but I think you have to describe what happens 

contain pointers to refcounted objects. Yes. It's analogous to copying a struct that has fields which contain constructors and destructors.
 10. Function returns have an AddRef() already done to the return value.

- A refcounted reference returned from a function (including new) would have

expression.

That's right. Just as if a function returned a struct with a destructor. The model I am basing this on is C++'s shared_ptr<>, which makes use of all the various rules around construction, assignment, and destruction. The wrinkles we have are: 1. memory safety 2. working with the GC
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 26-juin-2013 à 19:48, Walter Bright  a écrit :

 D (like C and C++) loves to manipulate pointers. Having to call a function 

motivated to drop down to C to do the fast code, and we might as well throw in the towel. But at the same time, having a GC that stops the world at irregular interval is worse for certain kind of things, games notably. It's been stated often on the forum that game developers prefer increasing the overhead if it prevents those hiccups. Making everything in D reference-counted would undoubtedly increase the general overhead, but it'd allow game developers to leverage the whole language and its libraries instead of restricting themselves to a custom subset of the class hierarchy derived from a reference counted class. And about pointer manipulation: for cases where you know for certain that the pointer still points to the same memory block before and after the assignment (when you call popFront on an array for instance), you have no reference count to update and can elide the call. The downside of optional support for language-wide reference counting is that it requires two incompatible codegen (or rather one incompatible with RC). We could have only one if it's the one that calls the retain/release functions on pointer assignment, with those functions replaced with empty stubs in druntime when reference counting is disabled, but some overhead would remain for the function call. I'm not claiming this is the right solution. It's just an idea I wanted to mention as an aside because it has some common points. It is however a mostly separate matter from your initial goal of supporting custom reference counting schemes for some object hierarchies. I decided to write about it mostly because you talked about reimplementing arrays using classes and that got me thinking. But perhaps I shouldn't have mentioned it because it seems to be side-tracking the discussion.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/26/2013 6:33 PM, Michel Fortin wrote:
 Le 26-juin-2013 à 19:48, Walter Bright  a écrit :

 D (like C and C++) loves to manipulate pointers. Having to call a function 


motivated to drop down to C to do the fast code, and we might as well throw in the towel.
 But at the same time, having a GC that stops the world at irregular interval 

the forum that game developers prefer increasing the overhead if it prevents those hiccups. Making everything in D reference-counted would undoubtedly increase the general overhead, but it'd allow game developers to leverage the whole language and its libraries instead of restricting themselves to a custom subset of the class hierarchy derived from a reference counted class.
 And about pointer manipulation: for cases where you know for certain that the 

(when you call popFront on an array for instance), you have no reference count to update and can elide the call. I've never seen a scheme for "knows for certain" that did not involve extensive and intrusive pointer annotations, something we very much want to avoid. Pointer annotations work great in theory, but in practice no successful language I know of uses them (we'll see if Rust will become an exception).
 The downside of optional support for language-wide reference counting is that 

could have only one if it's the one that calls the retain/release functions on pointer assignment, with those functions replaced with empty stubs in druntime when reference counting is disabled, but some overhead would remain for the function call.
 I'm not claiming this is the right solution. It's just an idea I wanted to 

separate matter from your initial goal of supporting custom reference counting schemes for some object hierarchies. I decided to write about it mostly because you talked about reimplementing arrays using classes and that got me thinking. But perhaps I shouldn't have mentioned it because it seems to be side-tracking the discussion.

This proposal is modeled after C++'s shared_ptr<T> in that it should have equivalent performance and capabilities. Since it has been well accepted into the C++ "best practices", I think we're on solid ground with it.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 27.06.2013 02:11, Walter Bright wrote:
 On 6/26/2013 2:33 PM, Rainer Schuetze wrote:
 On 26.06.2013 11:38, Walter Bright wrote:
 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 I imagine a few (constrained) templated functions for the
 different operations defined in the library could also do the
 job, though it might drown compilation speed. Also getting help
 from the optimizer to remove redundant calls will need some
 back doors.

I don't see how this can be done without specific compiler knowledge in a memory safe way.

I currently don't see how it can be memory safe with this proposal.

I'm a little confused about what you are referring to here.

When preparing for dconf I read the "Garbage Collection Handbook" by Richard Jones, and it very much supported my suspicion that the usual reference counting cannot be both memory safe and high-performance.
 You have to put the lock around the pair of AddRef and Release, but
 if the compiler already splits this into two function calls, this
 cannot be done in the implementation.

Why is it necessary to put a lock around the pair?

To be more accurate, it is the assignment and the Release that have to be atomic, in addition to a concurrent read with AddRef. Imagine the reading thread is suspended while just having read the pointer, but not incremented the reference count yet. If an assignment with release and deletion is performed before the thread resumes, AddRef is called on garbage. IIRC you also have the GC handbook book on your shelf. Check the chapters on RC, especially algorithm 18.2 "Eager reference counting with CompareAndSwap is broken".
 Just to clarify, I meant taking a slice of a static array that is a
  field of a refcounted class. Is it forbidden to have a field like
 this in a refcounted class or is taking the address through slicing
 forbidden?

It would be forbidden to obtain a slice of a ref counted object in this way - or even to simply refer to a static array embedded in a ref counted object (in safe code).

Ok.
 Two more notes:

 - I'm not sure it is mentioned, but I think you have to describe
 what happens when copying a struct. pre- and post-blit actions have
 to be taken if the struct contain pointers to refcounted objects.

Yes. It's analogous to copying a struct that has fields which contain constructors and destructors.

Ok, I tend to forget about the swapping to a temporary when assigning structs.
 The model I am basing this on is C++'s shared_ptr<>, which makes use
 of all the various rules around construction, assignment, and
 destruction. The wrinkles we have are:

 1. memory safety

This is the hard part.
 2. working with the GC

I don't think that the GC is getting in the way as long as it is mark-and-sweep. A fully reference counting GC is a different story and can be made concurrent, but it is usually not eager and needs to defer actual reference counting to avoid locks. Instead it logs accesses to some thread local buffer which needs to be processed eventually.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:


 Why is it necessary to put a lock around the pair?


 To be more accurate, it is the assignment and the Release that have to
 be atomic, in addition to a concurrent read with AddRef. Imagine the
 reading thread is suspended while just having read the pointer, but not
 incremented the reference count yet. If an assignment with release and
 deletion is performed before the thread resumes, AddRef is called on
 garbage.

On my way to work today, I figured that a safe but slow implementation can work, if the interface is not AddRef/Release, but class C { C readThis(); void writeThis(ref C c); } where the function can include the necessary locks, e.g. class C { int refcnt; C readThis() { synchronized(this) { refcnt++; return this; } } void writeThis(ref C c) { synchronized(c) { C x = c; c = this; if (--c.refcnt == 0) delete c; } } } Reading/Writing null (e.g. when constructing or destructing a reference) would have to be special cased, that would not be necesessary with free functions.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:


Le 27-juin-2013 à 8:03, "Rainer Schuetze" <r.sagitario gmx.de> a écrit :

 On my way to work today, I figured that a safe but slow implementation can 

 class C
 {
  C readThis();
  void writeThis(ref C c);
 }

 where the function can include the necessary locks, e.g.

 class C
 {
  int refcnt;

  C readThis()
  {
    synchronized(this)
    {
      refcnt++;
      return this;
    }
  }
  void writeThis(ref C c)
  {
    synchronized(c)
    {
       C x = c;
       c = this;
       if (--c.refcnt == 0)
         delete c;
    }
  }
 }

There's an error in this code. You must synchronize on the lock protecting the pointer, not on the lock at the other end of the pointer's value. Also, you only need to do this if the pointer pointing to the object is shared. If the pointer is thread-local, assignment does not need to be atomic. And if the object itself is thread-local, not even the reference counter need to be atomic.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/26/2013 11:28 PM, Rainer Schuetze wrote:
 On 27.06.2013 02:11, Walter Bright wrote:
 On 6/26/2013 2:33 PM, Rainer Schuetze wrote:
 On 26.06.2013 11:38, Walter Bright wrote:
 On 6/26/2013 12:19 AM, Rainer Schuetze wrote:
 I imagine a few (constrained) templated functions for the
 different operations defined in the library could also do the
 job, though it might drown compilation speed. Also getting help
 from the optimizer to remove redundant calls will need some
 back doors.

I don't see how this can be done without specific compiler knowledge in a memory safe way.

I currently don't see how it can be memory safe with this proposal.

I'm a little confused about what you are referring to here.

When preparing for dconf I read the "Garbage Collection Handbook" by Richard Jones, and it very much supported my suspicion that the usual reference counting cannot be both memory safe and high-performance.

I think with the rules in the proposal we have we can support it.
 You have to put the lock around the pair of AddRef and Release, but
 if the compiler already splits this into two function calls, this
 cannot be done in the implementation.

Why is it necessary to put a lock around the pair?

To be more accurate, it is the assignment and the Release that have to be atomic, in addition to a concurrent read with AddRef. Imagine the reading thread is suspended while just having read the pointer, but not incremented the reference count yet. If an assignment with release and

I see. I'll have to think about that some more.
 IIRC you also have the GC handbook book on your shelf. Check the
 chapters on RC, especially algorithm 18.2 "Eager reference counting with
 CompareAndSwap is broken".

I have the book, but it is the first edition and there's no chapter 18 in it :-(
 Just to clarify, I meant taking a slice of a static array that is a
  field of a refcounted class. Is it forbidden to have a field like
 this in a refcounted class or is taking the address through slicing
 forbidden?

It would be forbidden to obtain a slice of a ref counted object in this way - or even to simply refer to a static array embedded in a ref counted object (in safe code).

Ok.
 Two more notes:

 - I'm not sure it is mentioned, but I think you have to describe
 what happens when copying a struct. pre- and post-blit actions have
 to be taken if the struct contain pointers to refcounted objects.

Yes. It's analogous to copying a struct that has fields which contain constructors and destructors.

Ok, I tend to forget about the swapping to a temporary when assigning structs.
 The model I am basing this on is C++'s shared_ptr<>, which makes use
 of all the various rules around construction, assignment, and
 destruction. The wrinkles we have are:

 1. memory safety

This is the hard part.
 2. working with the GC

I don't think that the GC is getting in the way as long as it is mark-and-sweep. A fully reference counting GC is a different story and can be

counting to avoid locks. Instead it logs accesses to some thread local buffer which needs to be processed eventually.

I don't think we should do a fully ref counted GC anyway.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 27.06.2013 15:50, Michel Fortin wrote:
 Le 27-juin-2013 à 8:03, "Rainer Schuetze" <r.sagitario gmx.de> a écrit :

 class C
 {
   C readThis();
   void writeThis(ref C c);
 }

 where the function can include the necessary locks, e.g.

 class C
 {
   int refcnt;

   C readThis()
   {
     synchronized(this)
     {
       refcnt++;
       return this;
     }
   }
   void writeThis(ref C c)
   {
     synchronized(c)
     {
        C x = c;
        c = this;
        if (--c.refcnt == 0)
          delete c;
     }
   }
 }

There's an error in this code. You must synchronize on the lock protecting the pointer, not on the lock at the other end of the pointer's value.

You're right (I have been about to run to a meeting when writing this). Then, readThis will also need a reference to the pointer. Another more obvious bug is that it should read if (--x.refcnt == 0) delete x;
 Also, you only need to do this if the pointer pointing to the object
 is shared. If the pointer is thread-local, assignment does not need
 to be atomic. And if the object itself is thread-local, not even the
 reference counter need to be atomic.

True, these issues only happen with shared pointers. But remember that fields in shared objects are also shared. I also have a hard time to imagine how the code above works with reading pointers that live in registers or writing to "references to registers". These are never shared, so they could have simpler implementations.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 27-juin-2013 à 13:04, Walter Bright  a écrit :

 I don't think we should do a fully ref counted GC anyway.

Speaking of the GC, you should probably rethink this point:
 14. RC objects will still be allocated on the GC heap - this means that a
normal
 GC run will reap RC objects that are in a cycle, and RC objects will get 

 scanned for heap references with no additional action required by the user.

If you allocate the object from the GC heap, the GC will collect it regardless of its reference count. That's fine as long as all the retaining pointers are visible to the GC. But if you're defining a COM object, likely that's because you'll pass a pointer to an external API, and this API might store the pointer somewhere not scanned by the GC. This API will call AddRef to make sure the object is retained, but if the GC doesn't see that pointer on its heap it'll deallocate and next time external code uses the object everything goes boom! So that doesn't work. If instead you allocate the object outside of the GC heap and your object contains pointers to the GC heap, you'll need to add roots to the GC for any pointer variable in the object. (This is what DMD/Objective-C currently does.) There's no way to detect cycles with that scheme, but it is simple. We could use a hybrid scheme with two reference counts: one for internal references that the GC can see and one for external references that the GC cannot see. The GC cannot collect an object if the external reference count is non-zero. If the external count is zero, it can collect the object if the internal reference count reaches zero or if it becomes unreachable from any root. This allows detection of cycles, as long as this cycle is only made of internal references. Care must be taken about incrementing/decrementing the right reference count depending on the context, which sounds tricky. Or we could use a somewhat less hybrid scheme where we have one reference count and the only thing it does is prevent objects from being deallocated. This can be implemented as one global hash table and you put all objects that have a non-zero reference count in that table. This hash table being scanned by the GC anything in it will never be collected. This will also detect internal cycles like the previous two-counter scheme, but it doesn't allow immediate deallocation as it waits for the GC to deallocate. (This is similar to how it worked in my defunct D/Objective-C bridge that did not rely on tweaking the compiler.)
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/27/2013 11:38 AM, Michel Fortin wrote:
 Le 27-juin-2013 à 13:04, Walter Bright  a écrit :

 I don't think we should do a fully ref counted GC anyway.

 14. RC objects will still be allocated on the GC heap - this means that a
normal
 GC run will reap RC objects that are in a cycle, and RC objects will get 


 scanned for heap references with no additional action required by the user.


pointers are visible to the GC. But if you're defining a COM object, likely that's because you'll pass a pointer to an external API, and this API might store the pointer somewhere not scanned by the GC. This API will call AddRef to make sure the object is retained, but if the GC doesn't see that pointer on its heap it'll deallocate and next time external code uses the object everything goes boom! So that doesn't work. We already require that if you're going to pass a pointer to any GC allocated data to external code, that you retain a pointer. I see no additional issue with requiring this for COM objects created on the GC heap.
 If instead you allocate the object outside of the GC heap and your object 

pointer variable in the object. (This is what DMD/Objective-C currently does.) There's no way to detect cycles with that scheme, but it is simple. Yes, but that's a lot harder (and more error-prone) than simply requiring the programmer to retain a pointer as I outlined above.
 We could use a hybrid scheme with two reference counts: one for internal 

cannot see. The GC cannot collect an object if the external reference count is non-zero. If the external count is zero, it can collect the object if the internal reference count reaches zero or if it becomes unreachable from any root. This allows detection of cycles, as long as this cycle is only made of internal references. Care must be taken about incrementing/decrementing the right reference count depending on the context, which sounds tricky. That also seems far more complex than what I proposed.
 Or we could use a somewhat less hybrid scheme where we have one reference 

can be implemented as one global hash table and you put all objects that have a non-zero reference count in that table. This hash table being scanned by the GC anything in it will never be collected. This will also detect internal cycles like the previous two-counter scheme, but it doesn't allow immediate deallocation as it waits for the GC to deallocate. (This is similar to how it worked in my defunct D/Objective-C bridge that did not rely on tweaking the compiler.)

I'd really like to stick to the shared_ptr<T> model. (A global hash table also is not so simple when factoring in loading and unloading DLLs.) Of course, for the O-C bridge, you can implement it as required to be compatible with O-C.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 27-juin-2013 à 15:32, Walter Bright  a écrit :

 On 6/27/2013 11:38 AM, Michel Fortin wrote:
 14. RC objects will still be allocated on the GC heap - this means that a 



 GC run will reap RC objects that are in a cycle, and RC objects will get 



 scanned for heap references with no additional action required by the user.



pointers are visible to the GC. But if you're defining a COM object, likely that's because you'll pass a pointer to an external API, and this API might store the pointer somewhere not scanned by the GC. This API will call AddRef to make sure the object is retained, but if the GC doesn't see that pointer on its heap it'll deallocate and next time external code uses the object everything goes boom! So that doesn't work.
 We already require that if you're going to pass a pointer to any GC allocated 

requiring this for COM objects created on the GC heap. Perhaps it's just me, but I'd say if you need to anticipate the duration for which you need to keep the object alive when you pass it to some external code it completely defeats the purpose of said external code calling AddRef and Release. With the scheme you propose, reference counting would be useful inside D code as a way to deallocate some classes of objects early without waiting a GC scan. The GC can collect cycles for those objects. People passing COM objects to external code however should allocate those objects outside of the GC if they intend to pass the object to external code. They should also add member pointers as GC roots. Also, no cycle detection for those objects. If done right it could be made memory safe, but cycles will leak. Maybe that could work.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/27/2013 1:15 PM, Michel Fortin wrote:
 Le 27-juin-2013 à 15:32, Walter Bright  a écrit :

 On 6/27/2013 11:38 AM, Michel Fortin wrote:
 14. RC objects will still be allocated on the GC heap - this means that a 




 GC run will reap RC objects that are in a cycle, and RC objects will get 




 scanned for heap references with no additional action required by the user.




pointers are visible to the GC. But if you're defining a COM object, likely that's because you'll pass a pointer to an external API, and this API might store the pointer somewhere not scanned by the GC. This API will call AddRef to make sure the object is retained, but if the GC doesn't see that pointer on its heap it'll deallocate and next time external code uses the object everything goes boom! So that doesn't work.
 We already require that if you're going to pass a pointer to any GC 


issue with requiring this for COM objects created on the GC heap.
 Perhaps it's just me, but I'd say if you need to anticipate the duration for 

it completely defeats the purpose of said external code calling AddRef and Release.
 With the scheme you propose, reference counting would be useful inside D code 

The GC can collect cycles for those objects.
 People passing COM objects to external code however should allocate those 

They should also add member pointers as GC roots. Also, no cycle detection for those objects. If done right it could be made memory safe, but cycles will leak.
 Maybe that could work.

Nothing about the proposal acts to prevent one from constructing COM objects any way they wish, including using malloc/free and managing it all themselves. All COM objects require is an implementation of the COM interface, which says nothing at all beyond having a pointer to an AddRef() and Release(). If you are building a COM object that is to be fired and forgotten into the void of unknown external code, I don't think there's any automated replacement for thinking carefully about it and constructing it accordingly. D's memory safety guarantees cannot, of course, cover unknown and unknowable external code. What I'm trying to accomplish with this proposal is: 1. A way to do ref-counted memory allocation for specific objects 2. Do it in a guaranteed memory safe manner (at least for the user of those objects) 3. Do it in a way that does not interfere with people who want to use the GC or do manual memory management 4. Not impose penalties on non-refcounted code 5. Do it in a way that offers a similar performance and overhead profile to C++'s shared_ptr<T> 6. Do it in a way that makes it usable to construct COM objects, and work with NSObject's 7. Not require pointer annotations 8. Address the most common "why I can't use D" complaint What I'm not trying to accomplish is: 1. Replacing all memory allocation in D with ref counting
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 27-juin-2013 à 16:56, Walter Bright  a écrit :

 What I'm trying to accomplish with this proposal is:

 1. A way to do ref-counted memory allocation for specific objects
 2. Do it in a guaranteed memory safe manner (at least for the user of those 

 3. Do it in a way that does not interfere with people who want to use the GC 

 4. Not impose penalties on non-refcounted code
 5. Do it in a way that offers a similar performance and overhead profile to 

 6. Do it in a way that makes it usable to construct COM objects, and work 

 7. Not require pointer annotations
 8. Address the most common "why I can't use D" complaint

 What I'm not trying to accomplish is:

 1. Replacing all memory allocation in D with ref counting

That list is great for limiting the scope of your DIP. Make sure you include it in the DIP. So if we return to the core of it, here's the problems that still need solving: 1. Depending on the reference counting scheme implemented, it might be more efficient to have a single operation for an assignment (retain a/release b) operation. I think that should be allowed. 2. If the pointer variable is shared assignment must be atomic (done under a lock, and it must always be the same lock for a given pointer, obviously). 3. If the pointer variable is shared, reading its value must be done atomically with a retain too. Here's a suggestion for problem number 1 above: class MyObject { // user-implemented static void opRetain(MyObject var); // must accept null static void opRelease(MyObject var); // must accept null // optional (showing default implementation below) // this can be made faster with for some implementations of ref-counting // only call it for an assignment, not for constructing/destructing the pointer // (notably for Objective-C) static void opPtrAssign(ref MyObject var, MyObject newVal) { opRetain(newVal); opRelease(var); var = newVal; } } This maps 1 on 1 to the underlying functions for Objective-C ARC. I don't have a solution for the shared case. We do in fact have a tail-shared problem here. If I have a shared(MyObject), the pointer is as much shared along with the object. When the pointer itself is shared, we need a lock to access it reliably and that can only be provided by the outer context. If we had a way to express tail-shared, then we could repeat the above three functions for tail-shared object pointers and it'd work reliably for that.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin Wrote:

Le 27-juin-2013 à 18:35, Michel Fortin a écrit :

 	class MyObject
 	{
 		// user-implemented
 		static void opRetain(MyObject var);  // must accept null
 		static void opRelease(MyObject var); // must accept null

 		// optional (showing default implementation below)
 		// this can be made faster with for some implementations of ref-counting
 		// only call it for an assignment, not for constructing/destructing the
pointer
 		// (notably for Objective-C)
 		static void opPtrAssign(ref MyObject var, MyObject newVal) {
 			opRetain(newVal);
 			opRelease(var);
 			var = newVal;
 		}
 	}

 This maps 1 on 1 to the underlying functions for Objective-C ARC.

Actually, I made a small error in opRetain. To match Objective-C ARC it should return the retained object: static MyObject opRetain(MyObject var); // must accept null and the default implementation for opPtrAssign would then become: static void opPtrAssign(ref MyObject var, MyObject newVal) { newVal = opRetain(newVal); opRelease(var); var = newVal; } One reason is that Objective-C blocks (equivalent of delegate literals) are stack allocated. If you call retain on a block, it'll make a copy on the heap and return that copy. Another reason for opRetain to return the object is to enable tail-call optimization for cases like this one: NSObject x; NSObject getX() { return x; // D ARC should insert an implicit opRetain here } Of course it doesn't necessarily need to work that way, but it'd certainly make it easier to integrate with Objective-C if it worked that way.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 25.06.2013 23:00, Walter Bright wrote:
 4. Null checks are done before calling any AddRef() or Release().

Here is another nitpick that needs to be addressed: As mentioned in the implementation of ComObject invariants (and out contracts) must not be called when returning from Release, if it is ok to actually delete the object.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 28.06.2013 00:35, Michel Fortin wrote:
 So if we return to the core of it, here's the problems that still
 need solving:

 1. Depending on the reference counting scheme implemented, it might
 be more efficient to have a single operation for an assignment
 (retain a/release b) operation. I think that should be allowed.

 2. If the pointer variable is shared assignment must be atomic (done
 under a lock, and it must always be the same lock for a given
 pointer, obviously).

 3. If the pointer variable is shared, reading its value must be done
 atomically with a retain too.

I just had an idea, maybe it is obvious and just distracts, but I thought it might be worth sharing: Instead of defining methods on the class type, we could also redefine the reference type. The compiler detects a type declaration "reference_type" in the class declaration and replaces all references to that class with that type. class C { alias shared_ptr!C reference_type; } C c = new C; is lowered to shared_ptr!C c = new C; "new C" returns a shared_ptr!C aswell. It is then up to the implementation of shared_ptr to define what member functions to call for reference counting and to deal with proper shared semantics in assignments. It can also define whether opCall should increment the reference count or not. For most of the needed functionality, struct semantics work out-of-the-box. 2 immediate gotchas - In a class hierarchy, you would want to define the reference_type in the base class only, so maybe it has to be a template. I'm not sure implicite casting to base class reference type and interfaces can be implemented. - the implementation of the shared_ptr template will have to be able to deal with the "raw" reference, so that might need some type modifier/annotation. I think this might also be true for the addRef/release version, if the implementation is not just working on the refcount, but is also calling other functions. - To elide redundant reference counting, the compiler will need annotations here, too. Move semantics of structs might reduce the number of reference count operations already, though.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 28.06.2013 09:07, Walter Bright wrote:
 Will add to proposal.

 On 6/27/2013 11:27 PM, Rainer Schuetze wrote:
 On 25.06.2013 23:00, Walter Bright wrote:
 4. Null checks are done before calling any AddRef() or Release().

Here is another nitpick that needs to be addressed: As mentioned in the implementation of ComObject invariants (and out contracts) must not be called when returning from Release, if it is ok to actually delete the object.


Sorry to produce these drop by drop, but while writing the last mail, I noticed another issue to think about: What happens if the class also implements interfaces? A reference of the interface type must do reference counting as well. So the interface must also define AddRef and Release. This is currently true for COM-interfaces derived from IUnknown, but not for other interfaces.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 28-juin-2013 à 4:55, Rainer Schuetze <r.sagitario gmx.de> a écrit :

 What happens if the class also implements interfaces? A reference of the 

define AddRef and Release. This is currently true for COM-interfaces derived from IUnknown, but not for other interfaces. I would assume if an object of a reference-counted class cannot be cast to its base non-reference-counted class that it'd be the same for casting to non-reference-counted interfaces.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 28.06.2013 13:37, Michel Fortin wrote:
 Le 28-juin-2013 à 4:55, Rainer Schuetze <r.sagitario gmx.de> a écrit
 :

 What happens if the class also implements interfaces? A reference
 of the interface type must do reference counting as well. So the
 interface must also define AddRef and Release. This is currently
 true for COM-interfaces derived from IUnknown, but not for other
 interfaces.

I would assume if an object of a reference-counted class cannot be cast to its base non-reference-counted class that it'd be the same for casting to non-reference-counted interfaces.

Yes, that is probably the way to go. But that makes using protocols like COM difficult in safe mode. We have already talked Walter into not linking reference counting to AddRef and Release, but if it is implemented with other methods, these cannot be added to the already existing COM interfaces. Passing or getting interface pointers to/from external code being unsafe sounds ok, but passing around these interface references in D code would be unsafe as well. Adding aliases or non-virtual wrappers to the interface declaration to forward reference counting to AddRef/Release might help but could also introduce ambiguities in a class that derives both from a reference counted base class and an interface like this.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 25-juin-2013 à 17:00, Walter Bright  a écrit :

 If a class contains the following methods, in either itself or a base class, 

 an RC class:


    T AddRef();
    T Release();

 An RC class is like a regular D class with these additional semantics:

 1. In  safe code, casting (implicit or explicit) to a base class that does not
 have both AddRef() and Release() is an error.

I'm just realizing that this means safe code cannot call any member function of the non-reference-counted base class. This would require an implicit conversion of "this" to the base class. system code could, but it'd be extremely uneasy doing such calls unless I am the one in charge of that code and can make sure the base function will never store the (unretained) pointer somewhere it shouldn't now and in the future. An misstep here and you get memory corruption. Seriously, I don't think system code should allow implicit conversions to the base class, it should be explicit. I am starting to doubt there is any value in inheriting the base ref-counted-class from another class.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 1:47 AM, Rainer Schuetze wrote:
 On 28.06.2013 00:35, Michel Fortin wrote:
 So if we return to the core of it, here's the problems that still
 need solving:

 1. Depending on the reference counting scheme implemented, it might
 be more efficient to have a single operation for an assignment
 (retain a/release b) operation. I think that should be allowed.

 2. If the pointer variable is shared assignment must be atomic (done
 under a lock, and it must always be the same lock for a given
 pointer, obviously).

 3. If the pointer variable is shared, reading its value must be done
 atomically with a retain too.

I just had an idea, maybe it is obvious and just distracts, but I thought it

 Instead of defining methods on the class type, we could also redefine the 

class declaration and replaces all references to that class with that type.
 class C
 {
     alias shared_ptr!C reference_type;
 }

 C c = new C;

 is lowered to

 shared_ptr!C c = new C;

 "new C" returns a shared_ptr!C aswell.

 It is then up to the implementation of shared_ptr to define what member 

semantics in assignments. It can also define whether opCall should increment the reference count or not. For most of the needed functionality, struct semantics work out-of-the-box.
 2 immediate gotchas

 - In a class hierarchy, you would want to define the reference_type in the 

casting to base class reference type and interfaces can be implemented.
 - the implementation of the shared_ptr template will have to be able to deal 

think this might also be true for the addRef/release version, if the implementation is not just working on the refcount, but is also calling other functions.
 - To elide redundant reference counting, the compiler will need annotations 

operations already, though.

The main problem with this is the decay of a shared_ptr!C to a C. Once that happens, all the memory safety goes out the window.
Oct 09 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 7:14 AM, Michel Fortin wrote:
 Le 25-juin-2013 à 17:00, Walter Bright  a écrit :

 If a class contains the following methods, in either itself or a base class, 


 an RC class:


     T AddRef();
     T Release();

 An RC class is like a regular D class with these additional semantics:

 1. In  safe code, casting (implicit or explicit) to a base class that does not
 have both AddRef() and Release() is an error.


conversion of "this" to the base class. That's right.
  system code could, but it'd be extremely uneasy doing such calls unless I am 

store the (unretained) pointer somewhere it shouldn't now and in the future. An misstep here and you get memory corruption. Seriously, I don't think system code should allow implicit conversions to the base class, it should be explicit. It's a worthy point.
 I am starting to doubt there is any value in inheriting the base 


Oct 09 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 10 October 2013 at 02:19:02 UTC, Walter Bright wrote:
  system code could, but it'd be extremely uneasy doing such

sure the base function will never store the (unretained) pointer somewhere it shouldn't now and in the future. An misstep here and you get memory corruption. Seriously, I don't think system code should allow implicit conversions to the base class, it should be explicit. It's a worthy point.

It means OOP is completely broken with that design.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 10/9/2013 7:21 PM, deadalnix wrote:
 It means OOP is completely broken with that design.

I know. The thread kind of petered out as we began to realize the obstacles with this approach. But it's important to have the conversation in the record so we don't have to go through it again.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 28.06.2013 21:50, Walter Bright wrote:
 The main problem with this is the decay of a shared_ptr!C to a C. Once
 that happens, all the memory safety goes out the window.

By "decay", do mean the lowering or something else? There is no stray C reference in user code, it always gets lowered to shared_ptr!C. Only trusted code in shared_ptr will have to deal with "raw" references. It is shared_ptr's responsibilty to maintain memory safety, just the same as for AddRef and Release.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 1:11 PM, Rainer Schuetze wrote:
 On 28.06.2013 21:50, Walter Bright wrote:
 The main problem with this is the decay of a shared_ptr!C to a C. Once
 that happens, all the memory safety goes out the window.

By "decay", do mean the lowering or something else? There is no stray C reference in user code, it always gets lowered to

references. It is shared_ptr's responsibilty to maintain memory safety, just the same as for AddRef and Release.

"Decay" means it is converted to type C in order to call functions that take C as the 'this' pointer or C as a parameter. The problem is both type C and type shared_ptr!C will exist.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 28.06.2013 22:29, Walter Bright wrote:
 On 6/28/2013 1:11 PM, Rainer Schuetze wrote:
 On 28.06.2013 21:50, Walter Bright wrote:
 The main problem with this is the decay of a shared_ptr!C to a C. Once
 that happens, all the memory safety goes out the window.

By "decay", do mean the lowering or something else? There is no stray C reference in user code, it always gets lowered to shared_ptr!C. Only trusted code in shared_ptr will have to deal with "raw" references. It is shared_ptr's responsibilty to maintain memory safety, just the same as for AddRef and Release.

"Decay" means it is converted to type C in order to call functions that take C as the 'this' pointer or C as a parameter. The problem is both type C and type shared_ptr!C will exist.

Any parameter of type C is also lowered to shared_ptr!C. Calling a member function would go through opDot, which could also do reference counting for safety. Treating every explicite or implicite usage of "this" as a temporary shared_ptr!C might be overkill, so it could be restricted to assigning "this" to another reference (this includes passing it as an argument to another function or returning it from a function). My current adhoc rule: if "this" is not followed by a '.', it has to be lowered to construct shared_ptr!C(this). Assuming the reference count is updated by shared_ptr!C.opDot, there will always be a thread local reference while inside a member function (it must have been called through an external reference at least once). Other member functions of the same object can always be called without ref-counting assuming that the object never gets destroyed through changing other references.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 2:03 PM, Rainer Schuetze wrote:
 On 28.06.2013 22:29, Walter Bright wrote:
 On 6/28/2013 1:11 PM, Rainer Schuetze wrote:
 On 28.06.2013 21:50, Walter Bright wrote:
 The main problem with this is the decay of a shared_ptr!C to a C. Once
 that happens, all the memory safety goes out the window.

By "decay", do mean the lowering or something else? There is no stray C reference in user code, it always gets lowered to shared_ptr!C. Only trusted code in shared_ptr will have to deal with "raw" references. It is shared_ptr's responsibilty to maintain memory safety, just the same as for AddRef and Release.

"Decay" means it is converted to type C in order to call functions that take C as the 'this' pointer or C as a parameter. The problem is both type C and type shared_ptr!C will exist.

Any parameter of type C is also lowered to shared_ptr!C.

I don't see how lowering C to shared_ptr!C and lowering share_ptr!C to C can work?
 Calling a member function would go through opDot, which could also do 

"this" as a temporary shared_ptr!C might be overkill, so it could be restricted to assigning "this" to another reference (this includes passing it as an argument to another function or returning it from a function). My current adhoc rule: if "this" is not followed by a '.', it has to be lowered to construct shared_ptr!C(this).
 Assuming the reference count is updated by shared_ptr!C.opDot, there will 

been called through an external reference at least once). Other member functions of the same object can always be called without ref-counting assuming that the object never gets destroyed through changing other references.

Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:

Le 28-juin-2013 à 17:03, Rainer Schuetze <r.sagitario gmx.de> a écrit :

 Any parameter of type C is also lowered to shared_ptr!C.

class C {} People still constantly forget that C used as a type represents a *reference* to an object of class C, not the object itself. If you replace type C with shared_ptr!C, you must then replace it with shared_ptr!(shared_ptr!C) and so on; there's no end to it. Also, I strongly doubt the compiler will be able to elide redundant calls to retain/release made within shared_ptr!C while still respecting normal struct semantics.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 6:42 PM, Michel Fortin wrote:
 Le 28-juin-2013 à 17:03, Rainer Schuetze <r.sagitario gmx.de> a écrit :

 Any parameter of type C is also lowered to shared_ptr!C.

People still constantly forget that C used as a type represents a *reference*

shared_ptr!C, you must then replace it with shared_ptr!(shared_ptr!C) and so on; there's no end to it.
 Also, I strongly doubt the compiler will be able to elide redundant calls to 

semantics.

Using some sort of shared_ptr!T was the original idea, but I could not figure a reasonable way to make it memory safe without the compiler knowing about it. The easiest way to have the compiler know about it is to make it some sort of class type, not a struct type.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/27/2013 11:33 AM, Rainer Schuetze wrote:
 On 27.06.2013 19:04, Walter Bright wrote:
 IIRC you also have the GC handbook book on your shelf. Check the
 chapters on RC, especially algorithm 18.2 "Eager reference counting with
 CompareAndSwap is broken".

I have the book, but it is the first edition and there's no chapter 18 in it :-(

I can remove the dust from my scanner to copy the 3 mostly relevant pages and


I understand the issue (I think), but I can't think of a case where the ref count would be 1 when this happens.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/28/2013 1:55 AM, Rainer Schuetze wrote:
 What happens if the class also implements interfaces? A reference of the 

define AddRef and Release. This is currently true for COM-interfaces derived from IUnknown, but not for other interfaces.

Even implementing IUnknown is a problem, if we do the suggestion that opAddref and opRelease be used as wrappers around AddRef and Release. I think the simplest thing is to not allow ref counted classes to implement interfaces other than ones derived from IUnknown.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 29.06.2013 00:22, Walter Bright wrote:
 Any parameter of type C is also lowered to shared_ptr!C.

I don't see how lowering C to shared_ptr!C and lowering share_ptr!C to C can work?

I don't see why you would want to lower from shared_ptr!C to C. It's only inside shared_ptr where access to the non-lowered C is needed, e.g. by disabling the lowering inside the shared_ptr. I was referring to "raw" references before, so the lowering would be better shared_ptr!(__raw(C)). But I agree, having the lowering include the original seems bad. I realized a worse flaw with my proposal: it doesn't solve the assignment problem it was meant to. shared_ptr implemented as a struct does not have full control of the assignment, but is only called for the postblit and the destruction of the previous value. It has no way to put a lock around the full assignment. Still thinking too much C++... Sorry for the noise.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/29/2013 12:16 AM, Rainer Schuetze wrote:
 Sorry for the noise.

No problem. It's a complicated subject, and none of us can think of all the ramifications. That's why this thread exists.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:

On 29.06.2013 06:38, Walter Bright wrote:
 On 6/27/2013 11:33 AM, Rainer Schuetze wrote:
 On 27.06.2013 19:04, Walter Bright wrote:
 IIRC you also have the GC handbook book on your shelf. Check the
 chapters on RC, especially algorithm 18.2 "Eager reference counting
 with
 CompareAndSwap is broken".

I have the book, but it is the first edition and there's no chapter 18 in it :-(

I can remove the dust from my scanner to copy the 3 mostly relevant pages and send them to you.


I tried to scan it yesterday, but got large black bar at the fold (don't know if this the correct term) that eraased the first inch of text. I would have to rip the book apart to get better results.
 I understand the issue (I think), but I can't think of a case where the
 ref count would be 1 when this happens.

Consider a global shared reference R that holds the last reference to an object O. One thread exchanges the reference with another reference P while another thread reads the reference into S. shared(C) R = O; ; refcnt of O is 1 in pseudo-assembly missing null-checks: Thread1 (R = P) Thread2 (S = R) mov ecx,[R] ; thread suspended mov eax,[P] inc [eax].refcnt mov ebx,[R] mov [R],eax dec [ebx].refcnt ; refcnt of O now 0 jnz done call delete_ebx ; thread resumed inc [ecx].refcnt done: The increment on [ecx].refcnt modifies garbage.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Rainer Schuetze wrote:
On 29.06.2013 09:36, Rainer Schuetze wrote:
                         inc [ecx].refcnt
 done:

Just wanted to add the book states that lock-free reference counting can be implemented with a cas2 operation modifying two seperate locations atomically. Unfortunately this operation does not exist in most processors. This might be the quoted paper: http://scholr.ly/paper/2199608/lock-free-reference-counting
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/29/2013 12:36 AM, Rainer Schuetze wrote:
 On 29.06.2013 06:38, Walter Bright wrote:
 On 6/27/2013 11:33 AM, Rainer Schuetze wrote:
 On 27.06.2013 19:04, Walter Bright wrote:
 IIRC you also have the GC handbook book on your shelf. Check the
 chapters on RC, especially algorithm 18.2 "Eager reference counting
 with
 CompareAndSwap is broken".

I have the book, but it is the first edition and there's no chapter 18 in it :-(

I can remove the dust from my scanner to copy the 3 mostly relevant pages and send them to you.


I tried to scan it yesterday, but got large black bar at the fold (don't know

rip the book apart to get better results. Ah, don't rip up your book! (I cut the back off of mine and scanned it, but I no longer care to store the thousands of pounds of books I have anymore, and I like that my whole library fits on my laptop now!).
 I understand the issue (I think), but I can't think of a case where the
 ref count would be 1 when this happens.

Consider a global shared reference R that holds the last reference to an

another thread reads the reference into S.
 shared(C) R = O;      ; refcnt of O is 1

 in pseudo-assembly missing null-checks:

 Thread1 (R = P)        Thread2 (S = R)

                        mov ecx,[R]
                        ; thread suspended
 mov eax,[P]
 inc [eax].refcnt
 mov ebx,[R]
 mov [R],eax
 dec [ebx].refcnt      ; refcnt of O now 0
 jnz done
 call delete_ebx
                        ; thread resumed
                        inc [ecx].refcnt
 done:

 The increment on [ecx].refcnt modifies garbage.

Ok, I see. Let me think about it some more.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Jacob Carlborg:

On 29 jun 2013, at 06:42, Walter Bright wrote:

 I think the simplest thing is to not allow ref counted classes to implement 

What about Objective-C interfaces?
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 29-juin-2013 à 6:08, Jacob Carlborg a écrit :

 On 29 jun 2013, at 06:42, Walter Bright wrote:

 I think the simplest thing is to not allow ref counted classes to implement 


 What about Objective-C interfaces?

Implementing ARC for Objective-C is going to require some more compiler support anyway (for autoreleased objects notably). Tweaking the compiler it so accepts Objective-C interfaces should just be a matter of tweaking the boolean expression that makes this check. "if (classdelc->objc && interfacedecl->objc) return true;" or something like that. As for which function the compiler should call, it'll probably need to be special-cased for Objective-C in the compiler too. Here's the list of changes that'd be needed for Objective-C ARC: == Retain == COM: if (obj) obj->AddRef(); ObjC: obj = objc_retain(obj); ObjC blocks: obj = objc_retainBlock(obj); // objc_retainBlock might do a copy == Release == COM: if (obj) obj->Release(); ObjC: objc_release(obj); == Assignment == COM: if (obj) obj->AddRef(); if (var) var->Release(); var = obj; ObjC: objc_storeStrong(&var, obj); ObjC blocks: obj = objc_retainBlock(obj); objc_release(var); var = obj; As long as Walter implements D ARC in a way we can make the above substitutions it shouldn't be too hard. Then, support for autorelease is a matter of calling objc_autorelease on returned objects from autoreleasing functions, followed by objc_retain after the function call in the caller. We'll also have to check what ObjC ARC does for pointer write-backs to autoreleased variables and mimick that. There's an optimized path for autoreleased return values that we should use, but I'd defer that to later. It involves a special no-op instruction to insert at the right place as a flag. Also, autoreleased returns should be eliminated when inlining.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Looks like this should go into the O-C DIP.


On 6/29/2013 5:38 AM, Michel Fortin wrote:
 Implementing ARC for Objective-C is going to require some more compiler 

accepts Objective-C interfaces should just be a matter of tweaking the boolean expression that makes this check. "if (classdelc->objc && interfacedecl->objc) return true;" or something like that.
 As for which function the compiler should call, it'll probably need to be 

that'd be needed for Objective-C ARC:
 == Retain ==
 COM:  if (obj) obj->AddRef();
 ObjC: obj = objc_retain(obj);
 ObjC blocks: obj = objc_retainBlock(obj); // objc_retainBlock might do a copy

 == Release ==
 COM:  if (obj) obj->Release();
 ObjC: objc_release(obj);

 == Assignment ==
 COM:  if (obj) obj->AddRef(); if (var) var->Release(); var = obj;
 ObjC: objc_storeStrong(&var, obj);
 ObjC blocks: obj = objc_retainBlock(obj); objc_release(var); var = obj;

 As long as Walter implements D ARC in a way we can make the above 

 Then, support for autorelease is a matter of calling objc_autorelease on 

function call in the caller. We'll also have to check what ObjC ARC does for pointer write-backs to autoreleased variables and mimick that.
 There's an optimized path for autoreleased return values that we should use, 

at the right place as a flag. Also, autoreleased returns should be eliminated when inlining.

Oct 09 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Jacob Carlborg:

On 29 jun 2013, at 22:24, Walter Bright wrote:

 Looks like this should go into the O-C DIP.

Shouldn't all this reference counting be in its own DIP?
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 1:50 AM, Jacob Carlborg wrote:
 On 29 jun 2013, at 22:24, Walter Bright wrote:

 Looks like this should go into the O-C DIP.


Yes. It's not ready yet, though.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 25-juin-2013 à 17:00, Walter Bright  a écrit :

 6. If a class or struct contains RC fields, calls to Release() for those 

 be added to the destructor, and a destructor will be created if one doesn't 

Another thing to note that the above is dangerous if the destructor is called from the GC and RC objects are allocated from GC memory. Referenced objects might already have been destroyed and you'll be calling Release() on them. This will happen when the GC releases a cycle.
Oct 09 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 12:35 PM, Michel Fortin wrote:
 Le 25-juin-2013 à 17:00, Walter Bright  a écrit :

 6. If a class or struct contains RC fields, calls to Release() for those 


 be added to the destructor, and a destructor will be created if one doesn't 


 Another thing to note that the above is dangerous if the destructor is called 

might already have been destroyed and you'll be calling Release() on them. This will happen when the GC releases a cycle.

Amended as: 6. If a class or struct contains RC fields, calls to Release() for those fields will be added to the destructor, and a destructor will be created if one doesn't exist already. Release() implementations should take care to not destroy objects that are already destroyed, which can happen if the objects are allocated on the GC heap and the GC removes a cycle of refcounted objects.
Oct 09 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 2013-06-30 à 16:32, Walter Bright  a écrit :

 Amended as:

 6. If a class or struct contains RC fields, calls to Release() for those 

 be added to the destructor, and a destructor will be created if one doesn't 

 Release() implementations should take care to not destroy objects that are 

 which can happen if the objects are allocated on the GC heap and the GC 

 refcounted objects.

Good advice. But... how do you implement that? For one thing, I doubt there's an API in the GC you can query for deleted objects, and if there was it'd be inefficient to call it for every call to Release. And also, will a virtual call to a function of a destroyed object work in the first place? It all seems quite fragile to me.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 3:05 PM, Michel Fortin wrote:
 Le 2013-06-30 à 16:32, Walter Bright  a écrit :

 Amended as:

 6. If a class or struct contains RC fields, calls to Release() for those 


 be added to the destructor, and a destructor will be created if one doesn't 


 Release() implementations should take care to not destroy objects that are 


 which can happen if the objects are allocated on the GC heap and the GC 


 refcounted objects.


inefficient to call it for every call to Release. And also, will a virtual call to a function of a destroyed object work in the first place? It all seems quite fragile to me.

The GC doesn't actually delete anything while it is doing a collection cycle. So the refcount could simply be checked.
Oct 09 2013
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 30, 2013, at 6:11 PM, Walter Bright wrote:

 On 6/30/2013 3:05 PM, Michel Fortin wrote:
 Le 2013-06-30 à 16:32, Walter Bright  a écrit :

 Amended as:

 6. If a class or struct contains RC fields, calls to Release() for those 



 be added to the destructor, and a destructor will be created if one doesn't 



 Release() implementations should take care to not destroy objects that are 



 which can happen if the objects are allocated on the GC heap and the GC 



 refcounted objects.



it'd be inefficient to call it for every call to Release. And also, will a virtual call to a function of a destroyed object work in the first place? It all seems quite fragile to me.

The GC doesn't actually delete anything while it is doing a collection cycle.

AFAIK, this isn't a requirement of the GC. May want to add it. I have bad experiences with trying to second guess the GC and when it actually kills the object. Note, if this is the case, then inc/dec refcount cannot depend on vtable, since that is zeroed. I'm wondering if the GC shouldn't set the RC to size_t.max when destructing, or even just +1 it, to ensure the ref count destructor doesn't accidentally free it before the reaper does. -Steve
Oct 09 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 30-juin-2013 à 18:11, Walter Bright  a écrit :

 On 6/30/2013 3:05 PM, Michel Fortin wrote:
 Le 2013-06-30 à 16:32, Walter Bright  a écrit :

 Amended as:

 6. If a class or struct contains RC fields, calls to Release() for those 



 be added to the destructor, and a destructor will be created if one doesn't 



 Release() implementations should take care to not destroy objects that are 



 which can happen if the objects are allocated on the GC heap and the GC 



 refcounted objects.



it'd be inefficient to call it for every call to Release. And also, will a virtual call to a function of a destroyed object work in the first place? It all seems quite fragile to me.
 The GC doesn't actually delete anything while it is doing a collection cycle. 

... checked and decremented, and if it reaches zero in the thread the GC is currently running then it doesn't have to delete the object as, in theory, it should be destructed as part of the same run. Ok, I get it now. You should add a requirement that the reference counter be atomic because the GC can run in any thread and you still need to decrement counters of referenced objects in destructor. Honestly, I think it'd be much easier if the runtime provided its own base object you could use for reference counting with the GC to collect cycles. The provided implementation could rely on internal details of the GC since both would be part of druntime. There isn't much room for alternate implementations when the GC is involved anyway.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 4:35 PM, Michel Fortin wrote:
 Le 30-juin-2013 à 18:11, Walter Bright  a écrit :

 On 6/30/2013 3:05 PM, Michel Fortin wrote:
 Le 2013-06-30 à 16:32, Walter Bright  a écrit :

 Amended as:

 6. If a class or struct contains RC fields, calls to Release() for those 




 be added to the destructor, and a destructor will be created if one 




 Release() implementations should take care to not destroy objects that are 




 which can happen if the objects are allocated on the GC heap and the GC 




 refcounted objects.




it'd be inefficient to call it for every call to Release. And also, will a virtual call to a function of a destroyed object work in the first place? It all seems quite fragile to me.
 The GC doesn't actually delete anything while it is doing a collection 


 ... checked and decremented, and if it reaches zero in the thread the GC is 

should be destructed as part of the same run. Ok, I get it now.
 You should add a requirement that the reference counter be atomic because the 

objects in destructor. I very much want to avoid requiring atomic counts - it's a major performance penalty. Note that if the GC is reaping a cycle, nobody else is referencing the object, so this should not be an issue.
 Honestly, I think it'd be much easier if the runtime provided its own base 

provided implementation could rely on internal details of the GC since both would be part of druntime. There isn't much room for alternate implementations when the GC is involved anyway.

Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 30, 2013, at 8:18 PM, Walter Bright wrote:

 I very much want to avoid requiring atomic counts - it's a major performance 

object, so this should not be an issue. I think you didn't understand what Michel was saying. Take for example: A->B->C->A this is a cycle. Imagine that nobody else is pointing at A, B or C. Fine. The GC starts to collect this cycle. But let's say that D is not being collected *AND* B has a reference to D. B could be getting destroyed in one thread, and decrementing D's reference count, while someone else in another thread is incrementing/decrementing D's reference count. I agree that RC optimally is thread-local. But if you involve the GC, then ref incs and decs have to be atomic. I don't think this is that bad. iOS on ARM which has terrible atomic primitives uses atomic reference counts. If you do NOT involve the GC and are careful about cycles, then you could potentially have a RC solution that does not require atomics. But that would have to be a special case, with the danger of having cycles. -Steve
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 30-juin-2013 à 20:25, Steven Schveighoffer a écrit :

 A->B->C->A

 this is a cycle.  Imagine that nobody else is pointing at A, B or C.  Fine. 

 But let's say that D is not being collected *AND* B has a reference to D.

 B could be getting destroyed in one thread, and decrementing D's reference 

reference count.
 I agree that RC optimally is thread-local.  But if you involve the GC, then 

Exactly what I was trying to explain. Thanks.
 I don't think this is that bad.  iOS on ARM which has terrible atomic 

Moreover iOS uses a single spinlock to protect a global hash table containing all reference counts.
 If you do NOT involve the GC and are careful about cycles, then you could 

have to be a special case, with the danger of having cycles. Not involving the GC is quite difficult: you need to be absolutely sure you have no pointer pointing to that thread-local ref-counted object anywhere in the GC-heap. Unfortunately, there's no way to guaranty statically what is part of the GC heap and what is not, so any non-atomic reference counter is not safe.
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:
On Jun 30, 2013, at 10:08 PM, Michel Fortin wrote:

 Le 30-juin-2013 à 20:25, Steven Schveighoffer a écrit :
 I don't think this is that bad.  iOS on ARM which has terrible atomic 


 Moreover iOS uses a single spinlock to protect a global hash table containing 

Hearing this, I actually find it amazing how well it works :)
 If you do NOT involve the GC and are careful about cycles, then you could 


have to be a special case, with the danger of having cycles.
 Not involving the GC is quite difficult: you need to be absolutely sure you 

GC-heap. Unfortunately, there's no way to guaranty statically what is part of the GC heap and what is not, so any non-atomic reference counter is not safe. This is true, I was thinking of garbage collected RC object referring to RC object, I wasn't thinking of fully GC object referring to RC object. In terms of pure functions and possibly a nogc attribute, this might be a possibility. Maybe at some point we have a nogcref attribute we attach to specific *types* so the compiler prevents you from storing any references to that type in the GC. I think it is be important to reserve the possibility for having cases where RC inc/dec is not atomic. Especially where we have D's type system identifying what is shared and what is not. Especially when there is the possibility for thread-local GCs. -Steve
Oct 09 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 5:25 PM, Steven Schveighoffer wrote:
 On Jun 30, 2013, at 8:18 PM, Walter Bright wrote:

 I very much want to avoid requiring atomic counts - it's a major performance 


object, so this should not be an issue.
 I think you didn't understand what Michel was saying.

 Take for example:

 A->B->C->A

 this is a cycle.  Imagine that nobody else is pointing at A, B or C.  Fine. 

 But let's say that D is not being collected *AND* B has a reference to D.

 B could be getting destroyed in one thread, and decrementing D's reference 

reference count.
 I agree that RC optimally is thread-local.  But if you involve the GC, then 

This is actually a problem right now with the GC, as destructors may be run in another thread than they belong in. The situation you describe is not worse or better than that, it's the same thing. The solution is to run the destructors in the same thread the objects belong in.
 I don't think this is that bad.  iOS on ARM which has terrible atomic 

It's bad. ARM is not the only processor out there.
Oct 09 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jun 30, 2013, at 10:26 PM, Walter Bright wrote:

 On 6/30/2013 5:25 PM, Steven Schveighoffer wrote:
 On Jun 30, 2013, at 8:18 PM, Walter Bright wrote:

 I very much want to avoid requiring atomic counts - it's a major 



referencing the object, so this should not be an issue.
 I think you didn't understand what Michel was saying.

 Take for example:

 A->B->C->A

 this is a cycle.  Imagine that nobody else is pointing at A, B or C.  Fine. 


 But let's say that D is not being collected *AND* B has a reference to D.

 B could be getting destroyed in one thread, and decrementing D's reference 


reference count.
 I agree that RC optimally is thread-local.  But if you involve the GC, then 


 This is actually a problem right now with the GC, as destructors may be run 

or better than that, it's the same thing. The solution is to run the destructors in the same thread the objects belong in. I think that's a tall order presently. For instance, on linux, the threads are all stopped using a signal. It's a very bad idea to run destructors in a signal handler. What it seems like you are saying is that a prerequisite for ref counting is to have thread-local GC working. If that is the case, we need to start a thread-local GC "thread" before this goes any further.
 I don't think this is that bad.  iOS on ARM which has terrible atomic 


 It's bad. ARM is not the only processor out there.

Pragmatically, I think if D targets x86 variants and ARM, it is well-situated in the mainstream of existing devices. Yes, it would be nice if it could target other obscure platforms, but if we are talking ref counting works poorly on those, I don't think we are any worse off than today. Note that we can keep the options open, and implement atomic RC now without many headaches. -Steve
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 7:36 PM, Steven Schveighoffer wrote:
 On Jun 30, 2013, at 10:26 PM, Walter Bright wrote:

 On 6/30/2013 5:25 PM, Steven Schveighoffer wrote:
 On Jun 30, 2013, at 8:18 PM, Walter Bright wrote:

 I very much want to avoid requiring atomic counts - it's a major 




referencing the object, so this should not be an issue.
 I think you didn't understand what Michel was saying.

 Take for example:

 A->B->C->A

 this is a cycle.  Imagine that nobody else is pointing at A, B or C.  Fine. 



 But let's say that D is not being collected *AND* B has a reference to D.

 B could be getting destroyed in one thread, and decrementing D's reference 



reference count.
 I agree that RC optimally is thread-local.  But if you involve the GC, then 



 This is actually a problem right now with the GC, as destructors may be run 


or better than that, it's the same thing. The solution is to run the destructors in the same thread the objects belong in.
 I think that's a tall order presently.  For instance, on linux, the threads 

signal handler.
 What it seems like you are saying is that a prerequisite for ref counting is 

thread-local GC "thread" before this goes any further. Not really. This doesn't make anything worse. Also, the proposed solution to this issue is to post the "destruct" list to the appropriate thread, and that thread runs it next time it calls the GC.
 I don't think this is that bad.  iOS on ARM which has terrible atomic 



 It's bad. ARM is not the only processor out there.

Pragmatically, I think if D targets x86 variants and ARM, it is well-situated

other obscure platforms, but if we are talking ref counting works poorly on those, I don't think we are any worse off than today. Note that we can keep the options open, and implement atomic RC now without many headaches.

We don't need to require atomic RC for these.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jul 1, 2013, at 3:11 AM, Walter Bright wrote:

 On 6/30/2013 7:36 PM, Steven Schveighoffer wrote:
 I think that's a tall order presently.  For instance, on linux, the threads 


signal handler.
 What it seems like you are saying is that a prerequisite for ref counting is 


thread-local GC "thread" before this goes any further.
 Not really. This doesn't make anything worse. Also, the proposed solution to 

thread runs it next time it calls the GC. I really urge you to make this a separate project. It's not trivial. Logically, it's sound, but the implementation will be very difficult. I also think Sean (and probably others) should be involved for that discussion.
 Pragmatically, I think if D targets x86 variants and ARM, it is 


it could target other obscure platforms, but if we are talking ref counting works poorly on those, I don't think we are any worse off than today. Note that we can keep the options open, and implement atomic RC now without many headaches.

We don't need to require atomic RC for these.

I didn't say that. I said we could implement atomic RC without any changes to the GC, and worry about optimizing with non-atomic RC later. As long as we make it *possible*. -Steve
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/1/2013 6:08 AM, Steven Schveighoffer wrote:
 On Jul 1, 2013, at 3:11 AM, Walter Bright wrote:

 On 6/30/2013 7:36 PM, Steven Schveighoffer wrote:
 I think that's a tall order presently.  For instance, on linux, the threads 



signal handler.
 What it seems like you are saying is that a prerequisite for ref counting 



thread-local GC "thread" before this goes any further.
 Not really. This doesn't make anything worse. Also, the proposed solution to 


thread runs it next time it calls the GC.
 I really urge you to make this a separate project.  It's not trivial. 

think Sean (and probably others) should be involved for that discussion. Make what a separate project? The destruction of objects by the GC in local threads? It already is not part of the ref counting proposal.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Steven Schveighoffer wrote:

On Jul 1, 2013, at 12:17 PM, Walter Bright wrote:

 I really urge you to make this a separate project.  It's not trivial. 


think Sean (and probably others) should be involved for that discussion.
 Make what a separate project? The destruction of objects by the GC in local 


As far as I can tell, the ref counting proposal is not viable without it, as long as you insist on non-atomic RC increments and decrements. How can it possibly not be a prerequisite to this, and therefore part of the proposal? Unless you are saying now that atomic ref counting is OK? I'm going by your previous statement:
 I very much want to avoid requiring atomic counts - it's a major performance 

-Steve
Oct 09 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-10-10 04:35, Walter Bright wrote:
 Steven Schveighoffer wrote:

 On Jul 1, 2013, at 12:17 PM, Walter Bright wrote:

  >> I really urge you to make this a separate project.  It's not
 trivial. Logically, it's sound, but the implementation will be very
 difficult.  I also think Sean (and probably others) should be involved
 for that discussion.
  >
  > Make what a separate project? The destruction of objects by the GC in
 local threads? It already is not part of the ref counting proposal.
  >


 As far as I can tell, the ref counting proposal is not viable without
 it, as long as you insist on non-atomic RC increments and decrements.
 How can it possibly not be a prerequisite to this, and therefore part of
 the proposal?

 Unless you are saying now that atomic ref counting is OK?

 I'm going by your previous statement:

  > I very much want to avoid requiring atomic counts - it's a major
 performance penalty.


 -Steve

Is this the last email in the conversation? In that case I think you clearly mark that with a post. -- /Jacob Carlborg
Oct 09 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 10/9/2013 11:52 PM, Jacob Carlborg wrote:
 Is this the last email in the conversation?

Yes, I posted them in chronological order.
Oct 10 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Michel Fortin wrote:
Le 30-juin-2013 à 22:26, Walter Bright  a écrit :

 This is actually a problem right now with the GC, as destructors may be run 

or better than that, it's the same thing. The solution is to run the destructors in the same thread the objects belong in. Indeed. Maybe that could work. How ironic that we can't implement RC efficiently because of the GC. That said, it strongly favors having a base RC object implementation in druntime, where it can be kept in sync with the GC.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/30/2013 7:47 PM, Michel Fortin wrote:
 Le 30-juin-2013 à 22:26, Walter Bright  a écrit :

 This is actually a problem right now with the GC, as destructors may be run 


or better than that, it's the same thing. The solution is to run the destructors in the same thread the objects belong in.
 Indeed. Maybe that could work. How ironic that we can't implement RC 

 That said, it strongly favors having a base RC object implementation in 


The GC doesn't need to know about it.
Oct 09 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
And that's the last email in the original thread!
Oct 10 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 10/10/2013 12:31 AM, Walter Bright wrote:
 And that's the last email in the original thread!

Durn, no it isn't.
Oct 10 2013
prev sibling parent "Sean Kelly" <sean invisibleduck.org> writes:
On Thursday, 10 October 2013 at 02:28:13 UTC, Walter Bright wrote:
 Steven Schveighoffer wrote:

 On Jun 30, 2013, at 8:18 PM, Walter Bright wrote:

 I very much want to avoid requiring atomic counts - it's a

cycle, nobody else is referencing the object, so this should not be an issue. I think you didn't understand what Michel was saying. Take for example: A->B->C->A this is a cycle. Imagine that nobody else is pointing at A, B or C. Fine. The GC starts to collect this cycle. But let's say that D is not being collected *AND* B has a reference to D. B could be getting destroyed in one thread, and decrementing D's reference count, while someone else in another thread is incrementing/decrementing D's reference count. I agree that RC optimally is thread-local. But if you involve the GC, then ref incs and decs have to be atomic.

I think this ties into the requirement that after the GC collects thread-local objects, they must be finalized by the thread that owns them (assuming it's still alive). What's missing is some way to track what thread owns an object. This isn't super difficult to add in the simple case, but if we allow thread-local objects to be transferred between threads, then the transferral of ownership has to be communicated to the GC. Assuming for the moment that's not a problem though, I think RC updates could be non-atomic for thread-local data.
Oct 11 2013
prev sibling next sibling parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
I've made short roundup of the different features/requirements that have 
been mentioned (may have forgotten some and added some) as this thread 
has a complexity that presumably makes it quite hard to follow for most 
readers. I have also attached an estimated priority for each requirement 
based on the discussion and my own experiences.

  - Memory safety [very important but also very difficult/limiting]
      Disallow escaping uncounted references to reference counted
      memory. Keywords: pure, scope, isolated/owned
  - COM compatible [important]
      Needs to support internal reference counting using
      AddRef/ReleaseRef, while obeying to the call convention
  - Objective-C compatible [important]
      Weak references, manual memory management and autorelease pools are
      some keywords here
  - Handle reference cycles [nice to have]
      Requires GC memory for storing the instances
  - Weak pointers [critical]
      Only briefly mentioned, but critical for many data structures
      (e.g. graphs or caches) requires external reference counting
  - Not require two separate counts for COM [mildly important]
      Using GC memory would require a second reference count for the
      D side of things, which is not desirable for multiple reasons
  - Support type qualifiers [critical]
      All usual type qualifiers and conversions should work as expected.
      This is not possible in a pure template based solution.
  - Support non-class types [nice to have]
      Although slightly limiting, classes provide a convenient
      abstraction and will arguably capture >90% use cases just fine
  - Support referencing fields/slices [nice to have]
      Letting references to members escape in a safe way would greatly
      increase the flexibility, but ties it tightly to the GC
  - Allow manual memory management [critical]
      For COM/Obj-C and any situation where external code is to take
      responsibility of the ref counting this needs to be an option
  - Not require new annotations [important]
      Getting this to work without introducing new keywords/syntax is
      strongly preferred by Walter
  - Safe shared(RefCountedType) variables [important]
      There needs to be a way to make shared references thread-safe
  - Support OOP reasonably well [important]
      The usual up and down casts should work and calling functions of
      base classes needs to be safe

Please mention any points that I have forgotten so that we have some 
kind of unit test against which proposed designs can be checked.
Oct 12 2013
next sibling parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
To support most of the requirements we need to offer some control over 
the reference type. Forcing the reference to be a pointer to the class 
instance precludes proper weak references and makes thread-safety difficult.

Rainer Schütze's proposal [1] looked promising, but didn't quite work 
out. However, by going a bit further, I think this approach can be fixed 
and will provide all the flexibility needed to implement solutions that 
can satisfy any of those requirements.

The basic idea is the same: Any reference to a class that is recognized 
as being reference counted is replaced by a struct that performs the 
reference counting using RAII (e.g. std.typecons.RefCounted). This 
allows any reference counting scheme to be implemented 
(internal/external, support weak refs or not, global counter table, GC 
memory or malloc, etc.).

TL;DR Let some code speak instead of a full blown spec first:

struct RefCounted(T) { /* ... */ }

//  referenceType!RefCounted
class C {
	// the presence of a C.ReferenceType template makes the class a
	// reference counted class
	// Note: A  referenceType UDA as above defined in object.d
         //       could be a cleaner/more explicit alternative
	alias ReferenceType = RefCounted;

	// C is now internally renamed to __ref_C to avoid ambiguities
	// and "C" itself is an alias for ReferenceType!__ref_C
	pragma(msg, C.stringof); // "RefCounted!__ref_C"

	void method()
	{
		// The "this" pointer, too, is of the reference counted
		// type. caveats: how to handle private fields? COM call
  		// convention?
		pragma(msg, typeof(this)); // "RefCounted!__ref_C"

		// Alternative: allow only pure functions to avoid
		// escaping references

		// Another alternative is to make 'scope' powerful
		// enough and use that:
		pragma(msg, typeof(this)); // "scope __ref_C"
	}
}

// The reference type itself is never const/immutable
// to enable reference counting for qualified types
C c; // -> RefCounted!__ref_C
const(C) d; // -> RefCounted!(const(__ref_C))

// To support the usual implicit conversions, some substitution is
// needed, since we have no implicit cast support for UDTs in the
// language
d = c; // d = typeof(D)(c)
        // or
        // d = typeof(D).implicitCastFrom(c)
        // or
        // d = typeof(C).implicitCastTo!D

// shared, however, is applied to the reference count itself (and
// transitively to the object) to force a thread-safety - or rather to
// avoid accidental use of unsafe implementations for shared references)
shared(const(C)) e; // -> shared(RefCounted!(const(__ref_C)))

---

Caveat: Changing the "this" pointer from '__ref_C' to 
'RefCounted!__ref_C' has implications on the calling convention, which 
needs to be taken into account when COM objects are involved. A simple 
COMPtr-like struct that only contains the target pointer may be enough 
here, though.

Also, to guarantee memory safety, some additional measures need to be 
taken to avoid escaping plain references to refcounted memory. One 
solution is the use of isolated/owned types, another is to make 'scope' 
not only check for shallow reference escaping, but also check for 
escaping of references to fields (similar thing but behaves 
differently). Both combined would of course be ideal. I think this is an 
issue that is mostly orthogonal to the refcount topic. See also the 
corresponding thread [2].

[1]: 
http://forum.dlang.org/thread/l34lei$255v$1 digitalmars.com?page=5#post-l352nk:242g3b:246:40digitalmars.com
[2]: http://forum.dlang.org/thread/kluaojijixhwigoujeip forum.dlang.org
Oct 12 2013
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Saturday, 12 October 2013 at 14:03:26 UTC, Sönke Ludwig wrote:
 I've made short roundup of the different features/requirements 
 that have been mentioned (may have forgotten some and added 
 some) as this thread has a complexity that presumably makes it 
 quite hard to follow for most readers. I have also attached an 
 estimated priority for each requirement based on the discussion 
 and my own experiences.

  - Memory safety [very important but also very 
 difficult/limiting]
      Disallow escaping uncounted references to reference counted
      memory. Keywords: pure, scope, isolated/owned

We have a first missing block here :D I do think this is mandatory.
  - Objective-C compatible [important]
      Weak references, manual memory management and autorelease 
 pools are
      some keywords here

Can someone explain me what an autorelease pool is ?
  - Handle reference cycles [nice to have]
      Requires GC memory for storing the instances

The good new is that we can (and IMO should) layer ref counting on top of GC. This is the only way to make both work nicely together and have safety net for leakage.
  - Weak pointers [critical]
      Only briefly mentioned, but critical for many data 
 structures
      (e.g. graphs or caches) requires external reference 
 counting

Easy for RefCounted but become tricky for GC stuff.
  - Not require two separate counts for COM [mildly important]
      Using GC memory would require a second reference count for 
 the
      D side of things, which is not desirable for multiple 
 reasons

Can you explain that one a bit more ? Especially how it require 2 count.
  - Support type qualifiers [critical]
      All usual type qualifiers and conversions should work as 
 expected.
      This is not possible in a pure template based solution.

Here we have the second piece missing. We need a way to tail qualify template.
  - Not require new annotations [important]
      Getting this to work without introducing new 
 keywords/syntax is
      strongly preferred by Walter

We have 2 missing bloc to make that work (from a language perpective, many runtime/compiler magic is also required).
  - Support OOP reasonably well [important]
      The usual up and down casts should work and calling 
 functions of
      base classes needs to be safe

I see no way to make that work without increasing the scope of scope (huhuhu :P)
 Please mention any points that I have forgotten so that we have 
 some kind of unit test against which proposed designs can be 
 checked.

You did an excellent job here. I guess we have 2 missing piece (and an incomplete one in the name of scope) to get sorted out and we can get something really nice here !
Oct 12 2013
parent Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-10-13 01:15:49 +0000, "deadalnix" <deadalnix gmail.com> said:

 Can someone explain me what an autorelease pool is ?

A basic concept in Objective-C to make manual reference counting bearable. As things are moving to *automatic* reference counting now autorelease pools are becoming less important, but they remain there for backward compatibility and autoreleased objects must be handled correctly by ARC following to the existing conventions. The concept is to have functions return autoreleased objects, objects pending release. Each time you autorelease an object, instead of the counter being decremented immediately, the object gets added to the autorelease pool and the pool decrement the counter later when it gets drained. So, when the caller gets an autoreleased object, it doesn't have to decrement the counter when it stopped using the object as a temporary, the object will be cleaned up automatically later, generally at the next iteration of the event loop. You only need to retain the object if you're storing it somewhere else than a local variable. So this is what made manual reference counting bearable in Objective-C. Autorelease pool support is only useful and needed for correctly implementing ARC for Objective-C object types. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Oct 12 2013
prev sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 10/13/13 11:19, deadalnix wrote:
 On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
 How do you increment the counter without reading its address?

I assumed that the reference count was in a struct with the data, and refcounted point to it. In this case, if you remove the pointer via a sequencially consistent write (while keeping a local copy internally) and THEN decrement the counter, the other thread will access another object (or skip on a null check). Granted the read is sequencially consistent.

No, if you have two (or more) threads concurrently accessing the object, it is possible that one threads reads the pointer, then sleeps before incrementing the count. Then another thread comes and /destroys/ the object, the memory is reused for something else, or even unmapped. Then the first thread wakes up and incs the counter, which is no longer there, causing a crash or data corruption. But this is only a problem for shared objects, which are accessed without any locking -- it's not a common case at all, and can be dealt with by simply taking a lock *before* reading the reference. (there are many much more complex solutions such as CAS2 or RCU based ones). artur
Oct 13 2013