Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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.
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.
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
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.
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
callables. That is, if for some reason AddRef and Release should be aliases,
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
any sense (one cannot add reference counting after the fact to an object).
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
"retain". It would be good to use the names Objective-C coders are used to.
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
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...
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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
function. Is the pure function allowed to call AddRef()/Release()? Not sure.
Re: draft proposal for ref counting in D
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
well with something like TempAlloc. I don't think we should use convention,
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.
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
Re: draft proposal for ref counting in D
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 well with something like TempAlloc. I don't think we should use convention, 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. > > 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. 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.
Re: draft proposal for ref counting in D
> On 6/25/2013 2:47 PM, Steven Schveighoffer wrote: >> 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. >> > > 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. 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
Re: draft proposal for ref counting in D
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 giving the compiler a way to elide careful tracking of temporaries' reference 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. 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
Re: draft proposal for ref counting in D
On 6/25/2013 2:47 PM, Steven Schveighoffer wrote: > 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. > 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.
Re: draft proposal for ref counting in D
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. Thi
Re: draft proposal for ref counting in D
On Jun 25, 2013, at 5:28 PM, Walter Bright wrote: > 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. 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
Re: draft proposal for ref counting in D
On 6/25/2013 6:31 PM, Michel Fortin wrote: > 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. Well, that's exactly the issue - an escaping reference.
Re: draft proposal for ref counting in D
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 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. > > 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 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 or forgets the reference, it's kept in memory until you don't need it. The concept was truly great, no doubt about that.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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 don't keep an unretained reference to an autoreleased object when the pool drains. > > 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
Re: draft proposal for ref counting in D
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 don't keep an unretained reference to an autoreleased object when the pool drains. >>> 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. > > 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. 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
Re: draft proposal for ref counting in D
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
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.
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
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.
Makes sense.
>
> ## 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:
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
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.
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
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
Re: draft proposal for ref counting in D
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 have memory safety. 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.
Re: draft proposal for ref counting in D
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 don't keep an unretained reference to an autoreleased object when the pool drains. >> 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. 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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. 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 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. > >> 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 programmer can do this with a simple wrapper. 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 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. >> 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. > >> 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, this can be implemented. Also, an exception could be made for the AddRef()/Release() functions. > > 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.
Re: draft proposal for ref counting in D
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 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. > 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. 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 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. > This proposal is modeled after C++'s shared_ptr 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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 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. 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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 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. 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 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. > > 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 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. > > 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. 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 for such a step. For one thing, reading the clang spec on all the various 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.
Re: draft proposal for ref counting in D
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
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?
>
>>
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.
I think you're right. G!
>
>>
>>>
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?
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
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.
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
to be Released if the return value is ignored or if only used as
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
On 6/26/2013 4:15 AM, Michel Fortin wrote: > 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. 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 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. 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 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. >> 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. > 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. 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 for such a step. For one thing, reading the clang spec on all the various 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. > Ok.
Re: draft proposal for ref counting in D
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.
>> I don't think we should force linking this functionality with COM, the
programmer can do this with a simple wrapper.
>
> 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,
this can be implemented.
>
> Also, an exception could be made for the AddRef()/Release() functions.
I'm not too fond of that idea.
Re: draft proposal for ref counting in D
Rainer Schuetze wrote:
On 27.06.2013 15:50, Michel Fortin wrote:
>
> Le 27-juin-2013 à 8:03, "Rainer Schuetze" 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.
Re: draft proposal for ref counting in D
Michel Fortin wrote:
Le 27-juin-2013 à 8:03, "Rainer Schuetze" a écrit :
> 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;
>}
> }
> }
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.
Re: draft proposal for ref counting in D
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 deletion is performed before the thread resumes, AddRef is called on garbage. 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 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. > > I don't think we should do a fully ref counted GC anyway.
Re: draft proposal for ref counting in D
Michel Fortin wrote: Le 2013-06-26 à 17:42, Rainer Schuetze 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 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. 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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. > 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 automatically >> 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. 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 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. 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 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. That also seems far more complex than what I proposed. > > 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.) > I'd really like to stick to the shared_ptr 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.
Re: draft proposal for ref counting in D
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 automatically > 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.)
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
Michel Fortin wrote: Le 28-juin-2013 à 4:55, Rainer Schuetze 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.
Re: draft proposal for ref counting in D
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
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
> 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
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.
Re: draft proposal for ref counting in D
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 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. >>> 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. >> 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. > > 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. > 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 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
Re: draft proposal for ref counting in D
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 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. >> 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. > > 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. 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
Rainer Schuetze wrote: On 28.06.2013 13:37, Michel Fortin wrote: > Le 28-juin-2013 à 4:55, Rainer Schuetze 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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
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.
>
>
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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, 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. > 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. That's right. > > @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. It's a worthy point. > > I am starting to doubt there is any value in inheriting the base ref-counted-class from another class. >
Re: draft proposal for ref counting in D
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, 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. 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.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
On 6/28/2013 6:42 PM, Michel Fortin wrote:
> Le 28-juin-2013 à 17:03, Rainer Schuetze 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.
>
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.
Re: draft proposal for ref counting in D
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 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. >
Re: draft proposal for ref counting in D
On Thursday, 10 October 2013 at 02:19:02 UTC, Walter Bright wrote: > > @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. It's a worthy point. It means OOP is completely broken with that design.
Re: draft proposal for ref counting in D
On 6/28/2013 1:55 AM, Rainer Schuetze wrote: > > 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. > > 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.
Re: draft proposal for ref counting in D
Rainer Schuetze wrote: On 29.06.2013 09:36, Rainer Schuetze wrote: > inc [ecx].refcnt > done: mov [S], ecx 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
Re: draft proposal for ref counting in D
Michel Fortin wrote:
Le 28-juin-2013 à 17:03, Rainer Schuetze 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.
Re: draft proposal for ref counting in D
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 understand the issue (I think), but I can't think of a case where the ref count would be 1 when this happens.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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 interfaces other than ones derived from IUnknown. What about Objective-C interfaces?
Re: draft proposal for ref counting in D
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 fields will > be added to the destructor, and a destructor will be created if one doesn't exist already. 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.
Re: draft proposal for ref counting in D
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 if this the correct term) that eraased the first inch of text. I would have to 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 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. > > Ok, I see. Let me think about it some more.
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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?
Re: draft proposal for ref counting in D
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 interfaces other than ones derived from IUnknown. > > 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.
Re: draft proposal for ref counting in D
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 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. >
Re: draft proposal for ref counting in D
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. > Shouldn't all this reference counting be in its own DIP? > Yes. It's not ready yet, though.
Re: draft proposal for ref counting in D
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 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. 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.
Re: draft proposal for ref counting in D
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. 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. Exactly what I was trying to explain. Thanks. > I don't think this is that bad. iOS on ARM which has terrible atomic primitives uses atomic reference counts. 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 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. 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.
Re: draft proposal for ref counting in D
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 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. >> 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. >> > > The GC doesn't actually delete anything while it is doing a collection cycle. So the refcount could simply be checked. 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
Re: draft proposal for ref counting in D
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 primitives uses atomic reference counts. > > Moreover iOS uses a single spinlock to protect a global hash table containing all reference counts. 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 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. > > 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. 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
Re: draft proposal for ref counting in D
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 fields will >> be added to the destructor, and a destructor will be created if one doesn't exist already. > 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. > 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.
Re: draft proposal for ref counting in D
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 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. >>> 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. >> The GC doesn't actually delete anything while it is doing a collection cycle. So the refcount could simply be checked. > > ... 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. 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 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. >
Re: draft proposal for ref counting in D
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 penalty. Note that if the GC is reaping 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. 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 primitives uses atomic reference counts. It's bad. ARM is not the only processor out there.
Re: draft proposal for ref counting in D
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 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. >> 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. > > The GC doesn't actually delete anything while it is doing a collection cycle. So the refcount could simply be checked. ... 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.
Re: draft proposal for ref counting in D
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 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. > 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. > The GC doesn't actually delete anything while it is doing a collection cycle. So the refcount could simply be checked.
Re: draft proposal for ref counting in D
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 penalty. Note that if the GC is reaping 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 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
Re: draft proposal for ref counting in D
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 performance penalty. Note that if the GC is reaping 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. > > 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 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 primitives uses atomic reference counts. > > 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
Re: draft proposal for ref counting in D
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 performance penalty. Note that if the GC is reaping 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. >> 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 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. 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 primitives uses atomic reference counts. >> 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. > We don't need to require atomic RC for these.
Re: draft proposal for ref counting in D
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 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. > > 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 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 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. >> > > 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
Re: draft proposal for ref counting in D
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 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. 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.
Re: draft proposal for ref counting in D
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 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. > 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. > The GC doesn't need to know about it.
Re: draft proposal for ref counting in D
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 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. >> 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 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.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
And that's the last email in the original thread!
Re: draft proposal for ref counting in D
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.
Re: draft proposal for ref counting in D
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. I would imagine the counter to be manipulated with atomic_add_and_fetch operations, so no locks are required.
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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
Re: draft proposal for ref counting in D
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 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. 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.
