Re: RCArray is unsafe
On 04/03/2015 08:55, Ivan Timokhin wrote:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference counts are both 2
arr = RCArray!int([]); // There is another owner, so arr
// forgets about the old payload
} // Last owner of the array ('copy') gets destroyed and happily
// frees the payload.
val = 3; // Oops.
}
We could prevent reassignment of arr while val is alive, but perhaps
still allow mutation of existing elements through arr.
I've changed Marc Schütz's example to explore this:
void main() {
auto a = RCArray!int([5]); // a's refcount is now 1
foo(a, a[0]); // pass by ref
}
void foo(ref RCArray!int a, ref int t) {
a[0] = 4; // ok
a = RCArray!int([]); // drop the old a
t = 3; // oops, t is gone
}
I think Rust would enforce that either a *or* t can be mutably borrowed
at once (and for a, t can't even be immutably-borrowed). Without
designing a system, in theory foo is OK if a is const, but that prevents
a[0] = 4. This could be allowed as long as a is not reassigned (i.e. a
is head-const).
To support RCDynamicArray that supports appending and resizing, these
operations also need to be excluded, whilst potentially allowing
existing elements to be mutated.
(I've seen Andrei's solution for the above example, but it doesn't work
for Ivan Timokhin's code, and for the former it can be non-ideal).
Perhaps a parameter attribute similar to head-const (but somehow
configurable by the container author) could enforce this. The author of
foo would need to use this attribute for a. The container could mark the
safe mutation operations with this attribute.
Just an idea. I haven't considered other types of container, maybe it
would help those also.
Re: RCArray is unsafe
On Thursday, 5 March 2015 at 18:41:31 UTC, deadalnix wrote: Kind of OT, but your train of thought is very difficult to follow the way you are communicating (ie by updating on previous post by answering to yourself). Could you post some more global overview at some point, so one does not need to gather various information for various posts please ? Okay. I seem to be mixing my more well-thought out ideas with ideas I get on the spur of the moment. Then they come out in a jumble. I have to confess that a lot of my ideas just pop into my head. Did you want me to talk about how I would do ownership with my reference safety system?
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 08:56:20 UTC, Ivan Timokhin wrote:
Excuse me if I miss something obvious, but:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference
counts are both 2
arr = RCArray!int([]); // There is another owner,
so arr
// forgets about the old
payload
} // Last owner of the array ('copy') gets destroyed
and happily
// frees the payload.
val = 3; // Oops.
}
struct PileInfo Red TOP of PILE
{
int refCount;
RCDataBlock * top;
RCDataBlock * bottom;
}
struct RCDataBlock Blue
{
PileInfo * pileInfo;
RCDataBlock * next;
Array * payload;//Actual Data.
}
struct RCArray
{
RCDataBlock * block;
}
RCArray a,b,c,d;//all different piles
a = b;
b = c;
d = a; //makes them one single pile.
What if you pile them up. Blue cubes which contain the data.
And a Red cube containing the reference count equal to
the sum of all references to the blue cube of the same pile.
Basically a pile of blue cubes with a red cube on top.
1) RCArray a,b,c,d; //
[1]
x -a
[1]
x -b
[1]
x -c
[1]
x -d
2) a = b; //
[2]
x -[old b1]
x -a,b
[1]
x -c
[1]
x -d
3) b = c; //
[3]
x -b,c
x -[old b1]
x -a,[old b2]
[1]
x -d
4) d=a; //
[4]
x -b,c
x -[old b1]
x -[old a1],[old b2]
x -d,a
Re: RCArray is unsafe
On Thursday, 5 March 2015 at 20:47:55 UTC, Zach the Mystic wrote: Did you want me to talk about how I would do ownership with my reference safety system? I'd like you to expose what is pretty settled down in your mind so we can have a base to understand the in flux part of the ideas :)
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 18:05:52 UTC, Zach the Mystic wrote:
On Wednesday, 4 March 2015 at 17:22:15 UTC, Steven
Schveighoffer wrote:
Again, I think this is an issue with the expectation of
RCArray. You cannot *save* a ref to an array element, only a
ref to the array itself, because you lose control over the
reference count.
What you need is a special RCSlave type, which is reference
counted not to the type of its *own* data, but to its parent's.
In this case, a RCArraySlave!(T) holds data of type T, but a
pointer to an RCArray, which it decrements when it gets
destroyed. This could get expensive, with an extra pointer per
instance than a regular T, but it would probably be safe.
A way to do this is to have a core RCData type which has the
count itself and the chunk of memory the count refers to in type
ambiguous form:
struct RCData {
int count;
// the point is that RCData can be type ambiguous
void[] chunk;
this(size_t size)
{
chunk = new void[size];
count = 0;
}
void addRef() {
++count;
}
void decRef() {
if (count --count == 0)
delete chunk;
}
}
Over top of that you create a basic element type which refcounts
an RCData rather than itself:
struct RCType(E) {
E element;
RCType* data;
this(this)
{
data.addRef();
}
~this()
{
data.decRef();
}
[...etc...]
}
Then you have an RCArray which returns RCType elements when
indexed rather than naked types:
struct RCArray(E) {
E[] array;
private RCData* data;
RCElement!E opIndex(size_t i) return
{
return RCElement!E(array[start + i], data);
}
this(E[] a)
{
data = new RCData(a * sizeof(a));
array = cast(E[]) data.chunk;
}
this(this)
{
data.addRef();
}
~this()
{
data.decRef();
}
//...
}
This might work. The idea is to only leak references to types
which also have pointers to the original data.
Re: RCArray is unsafe
Kind of OT, but your train of thought is very difficult to follow the way you are communicating (ie by updating on previous post by answering to yourself). Could you post some more global overview at some point, so one does not need to gather various information for various posts please ?
Re: RCArray is unsafe
On 3/4/15 12:55 AM, Ivan Timokhin wrote:
Excuse me if I miss something obvious, but:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference counts are both 2
arr = RCArray!int([]); // There is another owner, so arr
// forgets about the old payload
} // Last owner of the array ('copy') gets destroyed and happily
// frees the payload.
val = 3; // Oops.
}
That's a problem, thanks very much for pointing it out. -- Andrei
Re: RCArray is unsafe
On 3/4/15 2:03 AM, deadalnix wrote:
A free list does not work as the data can be live. You cannot reuse it
to maintain the free list.
Actually you can, which is a bit surprising. Consider:
RCArray!int arr;
arr.length = 10;
arr[5] = 42;
fun(arr, arr[5]);
...
void fun(ref RCArray!int a, ref int b) {
assert(b == 42);
a = a.init; // array goes to freelist
a.length = 10; // array may reuse the previous one!
assert(b == 42);
}
Now the interesting here thing is, the last assert should be allowed to
fail. The code is still safe because there is no change of type, and the
use of b after the array is gone is a bug in the application anyway
because the parent structure is out of existence.
This makes code potentially tighter on memory usage but potentially more
difficult to debug.
Andrei
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 17:13:13 UTC, Zach the Mystic wrote: (Also, `pure` functions will need no `static` parameter attributes, and functions both `pure` and `@nogc` will not need ) ...will not need `@noscope` either.
Re: RCArray is unsafe
On 3/4/15 10:42 AM, Andrei Alexandrescu wrote:
On 3/4/15 12:55 AM, Ivan Timokhin wrote:
Excuse me if I miss something obvious, but:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference counts
are both 2
arr = RCArray!int([]); // There is another owner, so arr
// forgets about the old payload
} // Last owner of the array ('copy') gets destroyed and happily
// frees the payload.
val = 3; // Oops.
}
That's a problem, thanks very much for pointing it out. -- Andrei
Again, I think this is an issue with the expectation of RCArray. You
cannot *save* a ref to an array element, only a ref to the array itself,
because you lose control over the reference count.
I don't think arr[0] should correctly bind to foo's second argument.
-Steve
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 09:06:01 UTC, Walter Bright wrote: On 3/4/2015 12:13 AM, deadalnix wrote: The #1 argument for DIP25 compared to alternative proposal was its simplicity. I assume at this point that we have empirical evidence that this is NOT the case. The complexity of a free list doesn't remotely compare to that of adding an ownership system. My reference safety system has ownership built in, more-or-less for free: http://forum.dlang.org/post/offurllmuxjewizxe...@forum.dlang.org See also my reply to deadalnix: http://forum.dlang.org/post/oyaoibmwybzfkhhuf...@forum.dlang.org
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 07:50:50 UTC, Manu wrote: Well you can't get to a subcomponent if not through it's owner. If the question is about passing RC objects members to functions, then the solution is the same as above, the stack needs a reference to the parent before it can pass a pointer to it's member down the line for the same reasons. Yeah, or you could mimic such a reference by wrapping the call in an addRef/release cycle, as a performance optimization. The trouble then is what if that member pointer escapes? Well I'd imagine that it needs to be a scope pointer (I think we all agree RC relies on scope). So a raw pointer to some member of an RC object must be scope(*). I have a whole Reference Safety System which doesn't need explicit scope because it incorporates it implicitly: http://forum.dlang.org/post/offurllmuxjewizxe...@forum.dlang.org That it can't escape, combined with knowledge that the stack has a reference to it's owner, guarantees that it won't disappear. I think you and I are on the same page.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 08:13:33 UTC, deadalnix wrote: On Wednesday, 4 March 2015 at 03:46:36 UTC, Zach the Mystic wrote: That's fine. I like DIP25. It's a start towards stronger safety guarantees. While I'm pretty sure the runtime costs of my proposal are lower than yours, they do require compiler hacking, which means they can wait. I don't think that it is fine. At this point we need to : - Not free anything as long as something is alive. - Can't recycle memory. - Keep track of allocated chunk to be able to free them (ie implementing malloc on top of malloc). Well, I don't want to make any enemies. I thought that once the compiler was hacked people could just change their deferred-freeing code.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 17:06:53 UTC, Walter Bright wrote: On 3/4/2015 6:27 AM, ponce wrote: You define a clear owner for everything so that this never happens. That's what we do in C++ and shared_ptr is can be avoided as much as we like. C++ doesn't have ownership annotations and no checkable notion of a clear owner. The standard library + type system provides mechanisms for clear ownership, but it does not check borrowing. Borrowing is potentially unsafe, and the programmer knows it, but it is not a big deal.
Re: RCArray is unsafe
On 3/4/2015 6:27 AM, ponce wrote: You define a clear owner for everything so that this never happens. That's what we do in C++ and shared_ptr is can be avoided as much as we like. C++ doesn't have ownership annotations and no checkable notion of a clear owner.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 08:13:33 UTC, deadalnix wrote:
On Wednesday, 4 March 2015 at 03:46:36 UTC, Zach the Mystic
wrote:
That's fine. I like DIP25. It's a start towards stronger
safety guarantees. While I'm pretty sure the runtime costs of
my proposal are lower than yours, they do require compiler
hacking, which means they can wait.
I don't think that it is fine.
At this point we need to :
- Not free anything as long as something is alive.
- Can't recycle memory.
- Keep track of allocated chunk to be able to free them (ie
implementing malloc on top of malloc).
It means that RC is attached to an ever growing arena. Code
that would manipulate RCArray and append to it on a regular
manner must expect some impressive memory consumption.
Even if we manage to do this in phobos (I'm sure we can) it is
pretty much guaranteed at this point that noone else will, at
least safely. The benefit is reduced because of the bookeeping
that need to be done for memory to be freed in addition to
reference count themselves.
The #1 argument for DIP25 compared to alternative proposal was
its simplicity. I assume at this point that we have empirical
evidence that this is NOT the case.
To me, DIP25 is just the first step towards an ownership system.
The only language additions you need to it are out! parameters,
to track escapes to other parameters, static parameters
(previously called noscope), to say that the parameter won't be
copied to a global, and one more function attribute (for which I
can reuse noscope as @noscope) which says the return value will
nto be allocated on the heap. All of these will be rare, as they
aim to target the exceptional cases rather than the norms
(scope would be the norm. Hence @noscope to target the rare
cases):
Examples:
T* fun(return T* a, T* b, T**c);
This signature would indicate complete ownership transferred from
`a` to the return value, since only `a` can be returned (see why
below)
T* gun(return out!b T* a, T** b);
`a` is declared to be copied both to the return value and to `b`.
Therefore it is not owned. (If you're following my previous
definition of `out!` in DIP71, you'll notice I moved `out!` to
the source parameter rather than the target, but the point is the
same.)
T* hun(return T* a) @noscope {
if(something)
return a;
else return new T;
}
Again, no ownership. If you *might* return a heap or global, the
function must be marked @noscope (Again I've readapted the word
to a new meaning from dIP71. I'm using `static` now for
`noscope's original meaning.)
Another example:
T* jun(return static T* a) {
static T* t;
t = a;
return a;
}
Again, no ownership, because of the `static` parameter attribute.
In a previous post, you suggested that such an attribute was
unnecessary, but an ownership system would require that a given
parameter `a` which was returned, not also be copied to a global
at the same time. So `static` tells the compiler this, and thus
cancels ownership.
My point is that DIP25's `return` parameters are the beginning of
an ownership system. An option to specify that the function
*will* return a given `return` parameter as opposed to *might*
return it is the only thing needed. Hence the additions named
above. (Also, `pure` functions will need no `static` parameter
attributes, and functions both `pure` and `@nogc` will not need )
With the exception of some minor cosmetic changes, all this is
in, or at least hinted at, in my previously posted Reference
Safety System:
http://forum.dlang.org/post/offurllmuxjewizxe...@forum.dlang.org
The only thing which bears reiterating is that with better
attribute inference, the whole system becomes invisible for most
uses.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 17:22:15 UTC, Steven Schveighoffer wrote: Again, I think this is an issue with the expectation of RCArray. You cannot *save* a ref to an array element, only a ref to the array itself, because you lose control over the reference count. What you need is a special RCSlave type, which is reference counted not to the type of its *own* data, but to its parent's. In this case, a RCArraySlave!(T) holds data of type T, but a pointer to an RCArray, which it decrements when it gets destroyed. This could get expensive, with an extra pointer per instance than a regular T, but it would probably be safe.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 18:05:52 UTC, Zach the Mystic wrote: On Wednesday, 4 March 2015 at 17:22:15 UTC, Steven Schveighoffer wrote: Again, I think this is an issue with the expectation of RCArray. You cannot *save* a ref to an array element, only a ref to the array itself, because you lose control over the reference count. What you need is a special RCSlave type, which is reference counted not to the type of its *own* data, but to its parent's. In this case, a RCArraySlave!(T) holds data of type T, but a pointer to an RCArray, which it decrements when it gets destroyed. This could get expensive, with an extra pointer per instance than a regular T, but it would probably be safe. Another solution is to get compiler help. If you know the lifetime of a sub-reference `p.t` to be shorter than of its Rc'd parent `p`, the compiler can wrap its `p.t's lifetime in an addRef/release cycle for P. This works in calling a function: fun(p, p.t); Let's say that you know that `p.t` won't escape (a different question). The compiler doesn't need to know about `p.t` to wrap the whole function like this: p.opAddRef(); // or equivalent fun(p, p.t); p.opRelease(); It just needs to know that `p.t's lifetime is shorter than `p's.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 18:17:41 UTC, Andrei Alexandrescu wrote: Yah, this is a fork in the road: either we solve this with DIP25 + implementation, or we add stricter static checking disallowing two lent references to data in the same scope. The third solution is to keep track of lifetimes, recognize refcounted types for structs the same as suggested for classes in DIP74, and wrap the lifetime of the subreference `t.s` in an opAdd/Release cycle for `t`, as illustrated in my other reply. You could have the compiler recognize a refcounted struct by simply declaring void opAddRef(); and void opRelease();, with the compiler automatically aliasing them to this(this) and ~this.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 17:13:13 UTC, Zach the Mystic wrote:
Another example:
T* jun(return static T* a) {
static T* t;
t = a;
return a;
}
Again, no ownership, because of the `static` parameter
attribute. In a previous post, you suggested that such an
attribute was unnecessary, but an ownership system would
require that a given parameter `a` which was returned, not also
be copied to a global at the same time. So `static` tells the
compiler this, and thus cancels ownership.
Actually, I think you convinced me before that `static` (or
`noscope`) parameters wouldn't carry their weight. Instead,
copying a parameter reference to a global variable is unsafe by
default. Wrap it in a `@trusted` lambda if you know what you're
doing. (Trusted lambdas are assumed to copy no reference
parameters.) In this way, you can assume ownership. Any unsafe
global escapes are just ignored. ???
Re: RCArray is unsafe
On 3/4/15 6:02 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: I hope to finish writing up a proposal in the next days. Really, it is _much_ simpler than the previous one, and it will require almost no manual annotations. Looking forward to it! -- Andrei
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:49:06 UTC, Walter Bright wrote: On 3/4/2015 2:03 AM, deadalnix wrote: A free list does not work as the data can be live. It is a to free list. What I wanted to illustrate is that it is not a free list (which use the freed storage to maintain its state) as you cannot recycle storage. You need to maintain metadata about allocation in another structure. I don't see why. Isn't it what the to free list is ? Also you cannot free anything until all the refcount are to 0. Right. This RC system will only cut it for short lived entities. Not a problem if they aren't constantly reassigning the value. Having pool of object you recycle is a common strategy to reduce allocations when performance is critical. It is for instance incompatible with RC as proposed.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:50:54 UTC, Walter Bright wrote: On 3/4/2015 1:16 AM, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. How do you type an an array of pointers with different owners? Either the array is owning its elements or is is borrowing them. There is no array of element with different owners. How do you deal with the combinatoric explosion of template instantiations with all those different ownership types? It is better than the combinatoric explosion of the code I have to write to support the various scheme proposed here (here RC and GC are 100% separet worlds). As long as RC require bookkeeping, the codegen must be different anyway.
Re: RCArray is unsafe
On 3/4/15 9:22 AM, Steven Schveighoffer wrote:
On 3/4/15 10:42 AM, Andrei Alexandrescu wrote:
On 3/4/15 12:55 AM, Ivan Timokhin wrote:
Excuse me if I miss something obvious, but:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference counts
are both 2
arr = RCArray!int([]); // There is another owner, so arr
// forgets about the old payload
} // Last owner of the array ('copy') gets destroyed and
happily
// frees the payload.
val = 3; // Oops.
}
That's a problem, thanks very much for pointing it out. -- Andrei
Again, I think this is an issue with the expectation of RCArray. You
cannot *save* a ref to an array element, only a ref to the array itself,
because you lose control over the reference count.
I don't think arr[0] should correctly bind to foo's second argument.
Yah, this is a fork in the road: either we solve this with DIP25 +
implementation, or we add stricter static checking disallowing two lent
references to data in the same scope.
Andrei
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 19:22:25 UTC, Zach the Mystic wrote: On Wednesday, 4 March 2015 at 18:17:41 UTC, Andrei Alexandrescu wrote: Yah, this is a fork in the road: either we solve this with DIP25 + implementation, or we add stricter static checking disallowing two lent references to data in the same scope. The third solution is to keep track of lifetimes, recognize refcounted types for structs the same as suggested for classes in DIP74, and wrap the lifetime of the subreference `t.s` in an opAdd/Release cycle for `t`, as illustrated in my other reply. You could have the compiler recognize a refcounted struct by simply declaring void opAddRef(); and void opRelease();, with the compiler automatically aliasing them to this(this) and ~this. I'm sorry, I just realized this proposal is too complicated, and it wouldn't even work. I think stricter static checking in @safe code is the way to go. When passing a global RC type to an impure, or duplicating the same RC reference variable in a function call, it's unsafe. The workaround is to make copies and use them: static RcType s; // global RcType c; // Instead of: func(s); func(c, c); // ...do this: auto tmp = s; // get stack reference func(tmp); auto d = c; // copy Rc'd type func(c, d); Expensive, perhaps, but safe.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 03:46:36 UTC, Zach the Mystic wrote: That's fine. I like DIP25. It's a start towards stronger safety guarantees. While I'm pretty sure the runtime costs of my proposal are lower than yours, they do require compiler hacking, which means they can wait. I don't think that it is fine. At this point we need to : - Not free anything as long as something is alive. - Can't recycle memory. - Keep track of allocated chunk to be able to free them (ie implementing malloc on top of malloc). It means that RC is attached to an ever growing arena. Code that would manipulate RCArray and append to it on a regular manner must expect some impressive memory consumption. Even if we manage to do this in phobos (I'm sure we can) it is pretty much guaranteed at this point that noone else will, at least safely. The benefit is reduced because of the bookeeping that need to be done for memory to be freed in addition to reference count themselves. The #1 argument for DIP25 compared to alternative proposal was its simplicity. I assume at this point that we have empirical evidence that this is NOT the case.
Re: RCArray is unsafe
Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. Bye, bearophile
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 09:16:22 UTC, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. Bye, bearophile +1 --- Paolo
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 09:06:01 UTC, Walter Bright wrote: On 3/4/2015 12:13 AM, deadalnix wrote: The #1 argument for DIP25 compared to alternative proposal was its simplicity. I assume at this point that we have empirical evidence that this is NOT the case. The complexity of a free list doesn't remotely compare to that of adding an ownership system. A free list does not work as the data can be live. You cannot reuse it to maintain the free list. You need to maintain metadata about allocation in another structure. Also you cannot free anything until all the refcount are to 0. This RC system will only cut it for short lived entities.
Re: RCArray is unsafe
Excuse me if I miss something obvious, but:
void main()
{
auto arr = RCArray!int([0]);
foo(arr, arr[0]);
}
void foo(ref RCArray!int arr, ref int val)
{
{
auto copy = arr; //arr's (and copy's) reference counts are both 2
arr = RCArray!int([]); // There is another owner, so arr
// forgets about the old payload
} // Last owner of the array ('copy') gets destroyed and happily
// frees the payload.
val = 3; // Oops.
}
On Mon, Mar 02, 2015 at 03:22:52PM -0800, Andrei Alexandrescu wrote:
On 3/2/15 2:57 PM, Walter Bright wrote:
His insight was that the deletion of the payload occurred before the end
of the lifetime of the RC object, and that this was the source of the
problem. If the deletion of the payload occurs during the destructor
call, rather than the postblit, then although the ref count of the
payload goes to zero, it doesn't actually get deleted.
I.e. the postblit manipulates the ref count, but does NOT do payload
deletions. The destructor checks the ref count, if it is zero, THEN it
does the payload deletion.
Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-)
Unless, of course, we missed something obvious.
And since an RCArray may undergo several assignments during its lifetime
(thus potentially needing to free several chunks of memory), the arrays
to be destroyed will be kept in a freelist-style structure. Destructor
walks the freelist and frees the chunks.
Andrei
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 09:16:22 UTC, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. Bye, bearophile +1
Re: RCArray is unsafe
On 3/4/2015 12:13 AM, deadalnix wrote: The #1 argument for DIP25 compared to alternative proposal was its simplicity. I assume at this point that we have empirical evidence that this is NOT the case. The complexity of a free list doesn't remotely compare to that of adding an ownership system. Besides, we expect to provide sample code for how to do this that can be pretty much cutpasted by people implementing their own RC types.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:03:13 UTC, deadalnix wrote: On Wednesday, 4 March 2015 at 09:06:01 UTC, Walter Bright wrote: On 3/4/2015 12:13 AM, deadalnix wrote: The #1 argument for DIP25 compared to alternative proposal was its simplicity. I assume at this point that we have empirical evidence that this is NOT the case. The complexity of a free list doesn't remotely compare to that of adding an ownership system. A free list does not work as the data can be live. You cannot reuse it to maintain the free list. You need to maintain metadata about allocation in another structure. Also you cannot free anything until all the refcount are to 0. This RC system will only cut it for short lived entities. And come on, DIP25, DIP69 and DIP74 to get there. Come on, that is not even simpler than the alternative.
Re: RCArray is unsafe
On 3/4/2015 2:03 AM, deadalnix wrote: A free list does not work as the data can be live. It is a to free list. You need to maintain metadata about allocation in another structure. I don't see why. Also you cannot free anything until all the refcount are to 0. Right. This RC system will only cut it for short lived entities. Not a problem if they aren't constantly reassigning the value.
Re: RCArray is unsafe
Walter Bright: How do you type an an array of pointers with different owners? Sound doesn't mean it should be able to do everything. It will be just an approximated model. It means it's going to forbid some valid code, just like every type system. You use some @system code to work around some of those limitations. And if the design is good, such islands of unsafety are located inside Phobos constructs that leak (http://en.wikipedia.org/wiki/Leaky_abstraction ) very little. Bye, bearophile
Re: RCArray is unsafe
On 3/4/2015 2:06 AM, deadalnix wrote: And come on, DIP25, DIP69 and DIP74 to get there. Come on, that is not even simpler than the alternative. DIP69 has pretty much been abandoned.
Re: RCArray is unsafe
On 3/4/2015 1:16 AM, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. How do you type an an array of pointers with different owners? How do you deal with the combinatoric explosion of template instantiations with all those different ownership types?
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:50:54 UTC, Walter Bright wrote: How do you type an an array of pointers with different owners? You mean an array of pointers to objects with different owners? The array is the owner of the objects it points to. Or else it should be @trusted? How do you deal with the combinatoric explosion of template instantiations with all those different ownership types? Type erasure.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:50:54 UTC, Walter Bright wrote: On 3/4/2015 1:16 AM, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. How do you type an an array of pointers with different owners? scope T*[] array; How do you deal with the combinatoric explosion of template instantiations with all those different ownership types? There will be no combinatorial explosion. In our latest proposal (well, currently only in our minds), `scope` is a storage class, not a type modifier. For templates, which parameters are scope and which aren't depends only on the code inside the templates. There will be literally no additional instantiations because of different ownership. I'm already halfway through the inference algorithm. I'm still looking for a way to formalize the detection of borrowing with aliasing (the problem started in the OP of this thread), in order to make those situations @system. I try to do it in a way that will also make deadalnix's isolated islands idea easy to implement later on. I hope to finish writing up a proposal in the next days. Really, it is _much_ simpler than the previous one, and it will require almost no manual annotations.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 10:50:54 UTC, Walter Bright wrote: On 3/4/2015 1:16 AM, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. How do you type an an array of pointers with different owners? You define a clear owner for everything so that this never happens. That's what we do in C++ and shared_ptr is can be avoided as much as we like. How do you deal with the combinatoric explosion of template instantiations with all those different ownership types? What we do in C++: with unsafety. Taking raw pointer in function parameters and function returns. Mark in comments assumptions about which lifetime exceed what. Modern C++ has no such combinatoric explosion. Instead of a std::vector of pointers, you know have a std::vector of std::uinque_ptr. It still is quite easy, in the very least easier that doing deterministic destructon in D.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 09:16:22 UTC, bearophile wrote: Walter Bright: The complexity of a free list doesn't remotely compare to that of adding an ownership system. A sound complete ownership system is the only good enough solution for D. That's my opinion. Bye, bearophile For that matters, I'd be happy with an unsound incomplete unsafe ownership system :) scoped ownership feels right, while RC and GC feel heavyweight.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 14:21:24 UTC, ponce wrote: For that matters, I'd be happy with an unsound incomplete unsafe ownership system :) You already have that :^)
Re: RCArray is unsafe
On 3 March 2015 at 06:37, Walter Bright via Digitalmars-d
digitalmars-d@puremagic.com wrote:
On 3/1/2015 12:51 PM, Michel Fortin wrote:
That's actually not enough. You'll have to block access to global
variables too:
S s;
void main() {
s.array = RCArray!T([T()]); // s.array's refcount is now 1
foo(s.array[0]); // pass by ref
}
void foo(ref T t) {
s.array = RCArray!T([]); // drop the old s.array
t.doSomething(); // oops, t is gone
}
Thinking about it, there are many other ways this can happen. At the moment,
I'm stuck thinking of a solution other than requiring foo() to be pure.
Anyone have ideas?
My immediate impression on this problem:
s.array[0] is being passed to foo from main. s does not belong to main
(is global), and main does not hold have a reference to s.array.
Shouldn't main just need to inc/dec array around the call to foo when
passing un-owned references down the call tree.
It seems to me that there always needs to be a reference _somewhere_
on the stack for anything being passed down the call tree (unless the
function is pure). Seems simplest to capture a stack ref at the top
level, then as it's received as arguments to each callee, it's
effectively owned by those functions and they don't need to worry
anymore.
So, passing global x to some function; inc/dec x around the function
call that it's passed to...? Then the stack has its own reference, and
the global reference can go away safely.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 05:12:15 UTC, Walter Bright wrote: On 3/2/2015 6:04 PM, weaselcat wrote: On Tuesday, 3 March 2015 at 01:56:09 UTC, Walter Bright wrote: On 3/2/2015 4:40 PM, deadalnix wrote: After moving resources, the previous owner can no longer be used. How does that work with the example presented by Marc? He couldn't pass s and a member of s because s is borrowed as mutable. He would have to pass both as immutable. A pointer to s could be obtained otherwise and passed. No. Rust compiler forbids you from obtaining the pointer otherwise. Namely, it is a compile time error to make an alias of a mutably borrowed pointer.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 22:42:44 UTC, weaselcat wrote: I don't think you were advocating for this but, +1 for a borrow system similar to Rust. We're working on it ;-)
Re: RCArray is unsafe
On 3/3/15 5:45 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: On Tuesday, 3 March 2015 at 09:05:46 UTC, Walter Bright wrote: On 3/2/2015 9:58 PM, weaselcat wrote: Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe. Right, now consider that struct is a leaf in a complex graph of data structures. Then you still cannot have more than one mutable reference to the entire graph. Because that is impractical, Rust uses unsafe (i.e. @trusted in D speak) accessors that cast away the ownership, but do so in a way that doesn't violate the guarantees. For example, the type system doesn't allow you to get mutable references to the left and right children of a binary tree node. But there can be an accessor method that internally does some unsafe magic to return a tuple with mutable references to them, annotated with the information that they are mutably borrowed from the node. Both child refs are mutable, and the parent node is inaccessible as long as they exist. Well... the bigger problem is that it's relying on a convention. The accessor method needs to be constructed in a particular way that's easy to get wrong and that the compiler has no way to check for us. :o) Andrei
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 05:12:15 UTC, Walter Bright wrote: On 3/2/2015 6:04 PM, weaselcat wrote: On Tuesday, 3 March 2015 at 01:56:09 UTC, Walter Bright wrote: On 3/2/2015 4:40 PM, deadalnix wrote: After moving resources, the previous owner can no longer be used. How does that work with the example presented by Marc? He couldn't pass s and a member of s because s is borrowed as mutable. He would have to pass both as immutable. A pointer to s could be obtained otherwise and passed. Under normal circumstances, if the pointer to s is an lvalue, the refcount will be bumped when it is taken. Isn't the only problem now aliasing something (i.e. a global) invisibly through a parameter? This is easily solved -- when passing a global reference, or duplicating a variable in the same call, wrap the call in an add/release cycle. This preserves the alias for the duration of the call. Or are we also talking about taking the address of a non-rc'd subcomponent of an rc'd struct?
Re: RCArray is unsafe
On 3/3/15 5:05 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: The object is still accessible after its refcount went to zero, and can therefore potentially be resurrected. Probably not a problem, but needs to be taken into account, in particular in with respect to the freelist. That's tricky, because an object can be released and resurrected several times, and care must be taken that it will not end up in the freelist and get destroyed multiple times. And that hasn't even touched on thread-safety yet. Could you please give an example? The bigger problem is that it's relying on a convention. The RC wrapper needs to be constructed in a particular way that's easy to get wrong and that the compiler has no way to check for us. Agreed. Andrei
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 08:04:25 UTC, Manu wrote: My immediate impression on this problem: s.array[0] is being passed to foo from main. s does not belong to main (is global), and main does not hold have a reference to s.array. Shouldn't main just need to inc/dec array around the call to foo when passing un-owned references down the call tree. It seems to me that there always needs to be a reference _somewhere_ on the stack for anything being passed down the call tree (unless the function is pure). Seems simplest to capture a stack ref at the top level, then as it's received as arguments to each callee, it's effectively owned by those functions and they don't need to worry anymore. So, passing global x to some function; inc/dec x around the function call that it's passed to...? Then the stack has its own reference, and the global reference can go away safely. This is my position too. There is another problem being discussed now, however, having to do with references to non-rc'd subcomponents of an Rc'd type.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 08:04:25 UTC, Manu wrote: So, passing global x to some function; inc/dec x around the function call that it's passed to...? Then the stack has its own reference, and the global reference can go away safely. Yes, the sane thing to do is to improve the general type system and general optimizer. The special casing D is going for will lead to no good. New non-trivial special case features just punches more holes in the type system. Which is the opposite of what is needed to bring D to a stable state. By trivial I mean syntax sugar, which always is ok, but a type system should be general with no special casing in it. What you need to do is to a way to implement smart pointers as non-ref-capable types, and the ability to do moves to transfer ownership up the call stack, and good general opimizations in the backends for it. AFAIK the current type system is too weak to enforce it. The type system also lacks head-const-ref, which often is needed for safe manual optimization? The special casing effort is largely wasted because one cannot have efficient ARC without whole program/module optimization anyway. Swift ARC does better when optimizing larger units. With whole program optimization, stronger typing and smart inlining the RC performance issues can be reduced more efficiently. It would be better to focus on ways to tighten the type system and how to utilize stronger typing for optimization of larger units (whole module/program). Special casing in the language makes optimization algorithms harder to write. Long term evil.
Re: RCArray is unsafe
On 3/3/15 7:38 AM, Zach the Mystic wrote: On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org There's a misunderstanding here. The object being assigned keeps a trailing list of past values and defers their deallocation to destruction. -- Andrei
Re: RCArray is unsafe
On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: On 3/2/2015 1:09 PM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: I have discovered a marvellous solution, but this post is too short to describe it. Fortunately, Fermat (er, Andrei) was able to pass along his dazz idea to me this afternoon, before he expired to something he had to attend to. We were both in the dumps about this problem last night, but I think he solved it. His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, then although the ref count of the payload goes to zero, it doesn't actually get deleted. I.e. the postblit manipulates the ref count, but does NOT do payload deletions. The destructor checks the ref count, if it is zero, THEN it does the payload deletion. Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. Clever :-) But there are two things: The object is still accessible after its refcount went to zero, and can therefore potentially be resurrected. Probably not a problem, but needs to be taken into account, in particular in with respect to the freelist. That's tricky, because an object can be released and resurrected several times, and care must be taken that it will not end up in the freelist and get destroyed multiple times. And that hasn't even touched on thread-safety yet. The bigger problem is that it's relying on a convention. The RC wrapper needs to be constructed in a particular way that's easy to get wrong and that the compiler has no way to check for us.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu wrote: I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org There's a misunderstanding here. The object being assigned keeps a trailing list of past values and defers their deallocation to destruction. -- Andrei So you need an extra pointer per instance? Isn't that a big price to pay? Is the only problem we're still trying to solve aliasing which is not recognized as such and therefore doesn't bump the refcounter like it should? An extra pointer would be overkill for that. Isn't it better to just recognize the aliasing when it happens? As far as taking the address of an RcArray element, the type of which element is not itself Rc'ed, it's a different problem. The only thing I've been able to come up with is maybe to create a wrapper type within RcArray for the individual elements, and have that type do refcounting on the parent instead of itself, if that's possible.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 09:05:46 UTC, Walter Bright wrote: On 3/2/2015 9:58 PM, weaselcat wrote: Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe. Right, now consider that struct is a leaf in a complex graph of data structures. Rust has several pointer types, so what is gonna happen depend on the pointer type. However, either the entry in the graph you have owns 'a', in which case it can be disabled as only one owner of a exists, so there is no problem tracking it, or the thing is borrowed, in which case you can have multiple path to 'a' but you cannot borrow yourself (unless it is immutable).
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 15:03:41 UTC, Andrei Alexandrescu wrote: On 3/3/15 5:45 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: On Tuesday, 3 March 2015 at 09:05:46 UTC, Walter Bright wrote: On 3/2/2015 9:58 PM, weaselcat wrote: Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe. Right, now consider that struct is a leaf in a complex graph of data structures. Then you still cannot have more than one mutable reference to the entire graph. Because that is impractical, Rust uses unsafe (i.e. @trusted in D speak) accessors that cast away the ownership, but do so in a way that doesn't violate the guarantees. For example, the type system doesn't allow you to get mutable references to the left and right children of a binary tree node. But there can be an accessor method that internally does some unsafe magic to return a tuple with mutable references to them, annotated with the information that they are mutably borrowed from the node. Both child refs are mutable, and the parent node is inaccessible as long as they exist. Well... the bigger problem is that it's relying on a convention. The accessor method needs to be constructed in a particular way that's easy to get wrong and that the compiler has no way to check for us. :o) To avoid misunderstandings: It is in reply to a sub-thread where Walter asked about how Rust's type system works. This is an example for Rust, not for D. Therefore, your reply isn't really valid. In Rust, it is an escape hatch from a fundamentally safe type system, whereas in D it would be a necessary convention to make usage of RC safe.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 08:59:08 UTC, Ola Fosheim Grøstad wrote: On Tuesday, 3 March 2015 at 08:04:25 UTC, Manu wrote: So, passing global x to some function; inc/dec x around the function call that it's passed to...? Then the stack has its own reference, and the global reference can go away safely. Yes, the sane thing to do is to improve the general type system and general optimizer. The special casing D is going for will lead to no good. New non-trivial special case features just punches more holes in the type system. Which is the opposite of what is needed to bring D to a stable state. By trivial I mean syntax sugar, which always is ok, but a type system should be general with no special casing in it. What you need to do is to a way to implement smart pointers as non-ref-capable types, and the ability to do moves to transfer ownership up the call stack, and good general opimizations in the backends for it. AFAIK the current type system is too weak to enforce it. The type system also lacks head-const-ref, which often is needed for safe manual optimization? The special casing effort is largely wasted because one cannot have efficient ARC without whole program/module optimization anyway. Swift ARC does better when optimizing larger units. With whole program optimization, stronger typing and smart inlining the RC performance issues can be reduced more efficiently. It would be better to focus on ways to tighten the type system and how to utilize stronger typing for optimization of larger units (whole module/program). Special casing in the language makes optimization algorithms harder to write. Long term evil. You just reminded me of ParaSail. Here is the latest version of their pointer free programming paper. https://drive.google.com/file/d/0B6Vq5QaY4U7ubm5qVkFpMEtmN2s/view?pli=1 -- Paulo
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 17:40:59 UTC, Marc Schütz wrote: All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. If the last RcType is a global, will the list ever get freed at all? No, Andrei's proposed solution would take care of that. On assignment to RCArray, if the refcount goes to zero, the old array is put onto the cleanup list. But there can still be borrowed references to it's elements. However, these can never outlive the RCArray, therefore it's safe to destroy all of the arrays in the cleanup list in the destructor. Wouldn't you need a lifetime system for this? A global, for example, couldn't borrow safely. I'm all in favor of an ownership/borrowing system, but that would be for a different DIP, right? It seems like taking the address of a sub-element of an RcType is inherently unsafe, since it separates the memory from the refcount.
Re: RCArray is unsafe
On 03/03/2015 13:05, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: The bigger problem is that it's relying on a convention. The RC wrapper needs to be constructed in a particular way that's easy to get wrong and that the compiler has no way to check for us. Maybe the compiler could enforce that opRelease is truly @safe - i.e. doesn't call any @trusted code. Although there would still need to be an escape hatch for doing unsafe ref-counting without the overhead of a free list.
Re: RCArray is unsafe
On 3/3/2015 9:44 AM, Andrei Alexandrescu wrote: On 3/3/15 9:40 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. No, the cool thing about freelists is they use free memory to chain things together. I don't think the payload memory can be repurposed to be a free list until the destructor runs, because the whole problem is the payload may still be live to some references to it.
Re: RCArray is unsafe
On 3/3/2015 9:19 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: Therefore, your reply isn't really valid. In Rust, it is an escape hatch from a fundamentally safe type system, whereas in D it would be a necessary convention to make usage of RC safe. My understanding of Rust is that many library types rely on unsafe code under the hood to make them work. Rust does have an 'unsafe' mechanism to support this. But that's ok. The idea is it must be possible to create a type with a safe interface. The internals don't have to be safe.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 07:17:11 UTC, Sativa wrote:
On Sunday, 1 March 2015 at 15:44:49 UTC, Marc Schütz wrote:
Walter posted an example implementation of a reference counted
array [1], that utilizes the features introduced in DIP25 [2].
Then, in the threads about reference counted objects, several
people posted examples [3, 4] that broke the suggested
optimization of eliding `opAddRef()`/`opRelease()` calls in
certain situations.
A weakness of the same kind affects DIP25, too. The core of
the problem is borrowing (ref return as in DIP25), combined
with manual (albeit hidden) memory management. An example to
illustrate:
1 struct T {
2 void doSomething();
3 }
4 struct S {
5 RCArray!T array;
7 }
8 void main() {
9 auto s = S(RCArray!T([T()])); // s.array's refcount
is
10 now 1
11 foo(s, s.array[0]); // pass by ref
++ s.array[0] = myt; // Would also be
invalid
12 }
13 void foo(ref S s, ref T T) {
14 s.array = RCArray!T([]); // drop the old
s.array
15 t.doSomething(); // oops, t is gone
16 }
1. Assignment to RC types is not the same as assignments to
non-RC types.
2. Allocation of RC types is more than just allocating of
non-RC types.
Using the above example:
#9: The assignment and allocation does two things:
a. Decrements the current RC of s.array(here it is null so
no RC is used)
b. Increments the ref count of the allocated RCArray by one.
#11: we pass both s and a referent to inside S. This is odd
behavior and not technically required in this case(just pass
S). Of course, we can't expect such behavior to creep up in
complex code.
#14. In this case the behavior is correct. The assignment does
the following:
a. Decrements the current RC of s.array(here was 1, so now
it is 0)
b. Increments the current RC of the newly allocated RC array
and assigns it to s.array.
#15. Since T refers to the old s.array, which now has a ref
count of 0(which we can assume to then be unallocated), line 15
becomes a run-time error.
---
How to fix?
It seems that the only way to make it work well is to use sort
of lazy ref counting.
Here references are created at the start of functions and
decremented at the end of functions... rather that in
place(which then causes problems with things that happen after
it).
But this can't work as in the ++ I added. Here it would solve
your problem but not fix the a generalization of it.
---
Is there a solution? Essentially no. Only at the end of the
program could we possibly have the last function release all RC
counted arrays. Since it is the end of the program it is the
only time we can know that no more RC types will be used.
The problem is analogous to the multiple-inheritance problem.
---
Flow analysis can only help so far(it won't help with
dynamically allocated types that are allocated depending on
some random factor.
---
Note that since t is pointing to a part of S, technically we
can't release s until t is released.
So, effectively, S has to be ref counted too! And it's ref
count must check check T's ref count. If it is non-zero then
the it can't release itself(or the reference to it's array).
Also, something eventually has to release S(or which is then
s.array). When? Well, since t depends on S, it is when t is
released. So we would naturally have to inform t that it should
too release s when it is released.
So, if that sort of makes sense I'll explain the solution: It
might be a bit fuzzy but I'll try to make things very clear. [I
will also sometimes conflate the usage of concrete objects and
their corresponding abstract types. e.g., T with t. It should
be clear context which is meant. e.g., If I say T is
released, I mean that the object with type T was released.
When they need to be distinguished between I will do so(mainly
in the code examples]
A *reference counted* type, from here on designated as RCT, is
a type that only allows itself to be released to the heap when
nothing depends on it. [Obviously if anything depends on it
when after it is released will fail to be fulfilled]
If a RCT does not contains any references to any RCT's we will
call it a free RCT or FRCT. Such types behave in a simple way.
They can be free'ed completely immediately. Since FRCT's do not
contain any references to other RCT's all their references are
simple references that can be free'ed immediately.
We require that if a type contains a reference to a RCT then it
too is a RCT. [the relation ContainsRCT(T1,T2) ==
ContainsRCT(T2,T1) == Both T1 and T2 are either RCT's or not
RCT's] This isn't a big deal but without it we end up requiring
all types to be RCT's. Here we allow some types to be not be
RCT's.
In code,
class T { } // a standard non-reference counted type.
// It can't use any RCT's as references. It is
your basic D
Re: RCArray is unsafe
On 3/3/15 9:00 AM, Zach the Mystic wrote: On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu wrote: I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org There's a misunderstanding here. The object being assigned keeps a trailing list of past values and defers their deallocation to destruction. -- Andrei So you need an extra pointer per instance? Yah, or define your type to be single-assignment (probably an emerging idiom). You can massage the extra pointer with other data thus reducing its cost. Isn't that a big price to pay? Is the only problem we're still trying to solve aliasing which is not recognized as such and therefore doesn't bump the refcounter like it should? An extra pointer would be overkill for that. Isn't it better to just recognize the aliasing when it happens? It's all tradeoffs. This has runtime overhead. A static analysis would have the challenges of being permissive enough, cheap enough, not add notational overhead, etc. etc. Andrei
Re: RCArray is unsafe
On 3/3/15 10:22 AM, Zach the Mystic wrote: On Tuesday, 3 March 2015 at 17:40:59 UTC, Marc Schütz wrote: All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. If the last RcType is a global, will the list ever get freed at all? No. Making a global variable of a reference counted type would be poor design. Andrei
Re: RCArray is unsafe
Somebody please write the code already. With no code we sit forever on our testes speculating. Isn't this testes-driven development?
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 18:49:43 UTC, Andrei Alexandrescu wrote: On 3/3/15 10:22 AM, Zach the Mystic wrote: On Tuesday, 3 March 2015 at 17:40:59 UTC, Marc Schütz wrote: All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. If the last RcType is a global, will the list ever get freed at all? No. Making a global variable of a reference counted type would be poor design. Andrei Considering glopbal here means thread local, I think it does make sense to use global for various forms of cache.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 19:50:46 UTC, Paulo Pinto wrote: You just reminded me of ParaSail. Here is the latest version of their pointer free programming paper. https://drive.google.com/file/d/0B6Vq5QaY4U7ubm5qVkFpMEtmN2s/view?pli=1 Thanks! Section «5. Related Work» was a fun read. :-)
Re: RCArray is unsafe
On 3/3/15 12:35 PM, Zach the Mystic wrote:
On Tuesday, 3 March 2015 at 18:48:36 UTC, Andrei Alexandrescu wrote:
On 3/3/15 9:00 AM, Zach the Mystic wrote:
On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu wrote:
I was dazzed, but I'm not anymore. I wrote my concern here:
http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org
There's a misunderstanding here. The object being assigned keeps a
trailing list of past values and defers their deallocation to
destruction. -- Andrei
So you need an extra pointer per instance?
Yah, or define your type to be single-assignment (probably an emerging
idiom). You can massage the extra pointer with other data thus
reducing its cost.
Isn't that a big price to
pay? Is the only problem we're still trying to solve aliasing which is
not recognized as such and therefore doesn't bump the refcounter like it
should? An extra pointer would be overkill for that. Isn't it better to
just recognize the aliasing when it happens?
It's all tradeoffs. This has runtime overhead.
Isn't allocating and collecting a freelist also overhead?
No. I don't have time now for a proof of concept and it seems everybody
wants to hypothesize about code that doesn't exist instead of writing
code and then discussing it.
A static analysis would have the challenges of being permissive
enough, cheap enough, not add notational overhead, etc. etc.
It's certainly permissive: you can do anything, and compiler wraps
uncertain operations with add/release cycles automatically. These are:
passing a global as a mutable reference to an impure function; aliasing
the same variable in two parameters with itself. The unoptimized
lowerings would be:
{
auto tmp = myGlobal; // bump count
impureFun(myGlobal);
} // tmp destroyed, --count
{
auto tmp2 = c; // bump count
fun(c, c);
} // --count
The only addition is an optimization where the compiler elides the
assignments and calls the add/release cycles directly.
Do you have something reviewable, or just your own past posts?
For the time being I want to move forward with DIP25 and deferred freeing.
Andrei
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 18:48:36 UTC, Andrei Alexandrescu
wrote:
On 3/3/15 9:00 AM, Zach the Mystic wrote:
On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu
wrote:
I was dazzed, but I'm not anymore. I wrote my concern here:
http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org
There's a misunderstanding here. The object being assigned
keeps a
trailing list of past values and defers their deallocation to
destruction. -- Andrei
So you need an extra pointer per instance?
Yah, or define your type to be single-assignment (probably an
emerging idiom). You can massage the extra pointer with other
data thus reducing its cost.
Isn't that a big price to
pay? Is the only problem we're still trying to solve aliasing
which is
not recognized as such and therefore doesn't bump the
refcounter like it
should? An extra pointer would be overkill for that. Isn't it
better to
just recognize the aliasing when it happens?
It's all tradeoffs. This has runtime overhead.
Isn't allocating and collecting a freelist also overhead?
A static analysis would have the challenges of being permissive
enough, cheap enough, not add notational overhead, etc. etc.
It's certainly permissive: you can do anything, and compiler
wraps uncertain operations with add/release cycles automatically.
These are: passing a global as a mutable reference to an impure
function; aliasing the same variable in two parameters with
itself. The unoptimized lowerings would be:
{
auto tmp = myGlobal; // bump count
impureFun(myGlobal);
} // tmp destroyed, --count
{
auto tmp2 = c; // bump count
fun(c, c);
} // --count
The only addition is an optimization where the compiler elides
the assignments and calls the add/release cycles directly.
Re: RCArray is unsafe
On 2015-03-02 05:57:12 +, Walter Bright said:
On 3/1/2015 12:51 PM, Michel Fortin wrote:
That's actually not enough. You'll have to block access to global
variables too:
Hmm. That's not so easy to solve.
Let's see. The problem is that 'ref' variables get invalidated by some
operations. Perhaps we could just tell the compiler that doing this or
that will makes 'ref' variables unsafe after that point. Let's try
adding a @refbreaking function attribute, and apply it to
RCArray.opAssign:
S s;
void main() {
s.array = RCArray!T([T()]);
foo(s.array[0]);
}
void foo(ref T t) {
t.doSomething(); // all is fine
s.array = RCArray!T([]); // here, RCArray.opAssign would be labeled
@refbreaking
t.doSomething(); // cannot use 'ref' variable after doing a
refbreaking operation
}
Also, the above shouldn't compile anyway because @refbreaking would
need to be transitive, and it follows that `foo` would need to be
@refbreaking too:
void foo(ref T t) @refbreaking {
...
}
which in turn means that `main` too needs to be @refbreaking.
So what needs to be @refbreaking? Anything that might deallocate. This
includes `opRelease` if it deallocates when the counter reaches zero.
Although you could implement `opRelease` in a way that sends the memory
block to an autorelease pool of some kind, in which case draining the
autorelease pool at a later point would be @refbreaking.
--
Michel Fortin
michel.for...@michelf.com
http://michelf.com/
Re: RCArray is unsafe
On 4 March 2015 at 01:07, Zach the Mystic via Digitalmars-d digitalmars-d@puremagic.com wrote: On Tuesday, 3 March 2015 at 08:04:25 UTC, Manu wrote: My immediate impression on this problem: s.array[0] is being passed to foo from main. s does not belong to main (is global), and main does not hold have a reference to s.array. Shouldn't main just need to inc/dec array around the call to foo when passing un-owned references down the call tree. It seems to me that there always needs to be a reference _somewhere_ on the stack for anything being passed down the call tree (unless the function is pure). Seems simplest to capture a stack ref at the top level, then as it's received as arguments to each callee, it's effectively owned by those functions and they don't need to worry anymore. So, passing global x to some function; inc/dec x around the function call that it's passed to...? Then the stack has its own reference, and the global reference can go away safely. This is my position too. There is another problem being discussed now, however, having to do with references to non-rc'd subcomponents of an Rc'd type. Well you can't get to a subcomponent if not through it's owner. If the question is about passing RC objects members to functions, then the solution is the same as above, the stack needs a reference to the parent before it can pass a pointer to it's member down the line for the same reasons. The trouble then is what if that member pointer escapes? Well I'd imagine that it needs to be a scope pointer (I think we all agree RC relies on scope). So a raw pointer to some member of an RC object must be scope(*). That it can't escape, combined with knowledge that the stack has a reference to it's owner, guarantees that it won't disappear.
Re: RCArray is unsafe
On Wednesday, 4 March 2015 at 03:46:36 UTC, Zach the Mystic wrote: Just my own past posts. My suggestion is based on the compiler doing all the work. I don't know how it could be tested without hacking the compiler. I think that part of the fear of my idea is that I want structs to get some of the behavior suggested in DIP74 for classes, i.e. the compiler inserts calls to opAddRef/opRelease on its own at certain times. Since structs only have postblits and destructors, there's no canonical way to call them as separate functions. The behavior I'm suggesting would only be good if you had a refcounted type, which means it's superfluous if not harmful to insert it just because in other types of structs. If it turns out that some of the behavior desirable for refcounted classes is useful for structs too, it may be necessary to hint to the complier that a struct is indeed of the refcounted type. For example, void opAddRef(); and void opRelease(); could be specially recognized, with no definitions even permitted (error on attempt), implying alias opAddRef this(this);, alias opRelease ~this;.
Re: RCArray is unsafe
On 2015-03-03 22:39:12 +, Michel Fortin said:
Let's see. The problem is that 'ref' variables get invalidated by some
operations. Perhaps we could just tell the compiler that doing this or
that will makes 'ref' variables unsafe after that point. Let's try
adding a @refbreaking function attribute, and apply it to
RCArray.opAssign:
S s;
void main() {
s.array = RCArray!T([T()]);
foo(s.array[0]);
}
void foo(ref T t) {
t.doSomething(); // all is fine
s.array = RCArray!T([]); // here, RCArray.opAssign would be labeled
@refbreaking
t.doSomething(); // cannot use 'ref' variable after doing a
refbreaking operation
}
Also, the above shouldn't compile anyway because @refbreaking would
need to be transitive, and it follows that `foo` would need to be
@refbreaking too:
void foo(ref T t) @refbreaking {
...
}
which in turn means that `main` too needs to be @refbreaking.
So what needs to be @refbreaking? Anything that might deallocate. This
includes `opRelease` if it deallocates when the counter reaches zero.
Although you could implement `opRelease` in a way that sends the memory
block to an autorelease pool of some kind, in which case draining the
autorelease pool at a later point would be @refbreaking.
And giving it some more thought, @refbreaking also has the interesting
property that any pair of opAddRef/opRelease with no @refbreaking call
between them can be elided safely.
--
Michel Fortin
michel.for...@michelf.com
http://michelf.com/
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 21:37:20 UTC, Andrei Alexandrescu
wrote:
On 3/3/15 12:35 PM, Zach the Mystic wrote:
Isn't allocating and collecting a freelist also overhead?
No. I don't have time now for a proof of concept and it seems
everybody wants to hypothesize about code that doesn't exist
instead of writing code and then discussing it.
Okay.
The unoptimized lowerings would be:
{
auto tmp = myGlobal; // bump count
impureFun(myGlobal);
} // tmp destroyed, --count
{
auto tmp2 = c; // bump count
fun(c, c);
} // --count
The only addition is an optimization where the compiler elides
the
assignments and calls the add/release cycles directly.
Do you have something reviewable, or just your own past posts?
Just my own past posts. My suggestion is based on the compiler
doing all the work. I don't know how it could be tested without
hacking the compiler.
For the time being I want to move forward with DIP25 and
deferred freeing.
That's fine. I like DIP25. It's a start towards stronger safety
guarantees. While I'm pretty sure the runtime costs of my
proposal are lower than yours, they do require compiler hacking,
which means they can wait.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 15:01:02 UTC, Andrei Alexandrescu wrote: On 3/3/15 5:05 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: The object is still accessible after its refcount went to zero, and can therefore potentially be resurrected. Probably not a problem, but needs to be taken into account, in particular in with respect to the freelist. That's tricky, because an object can be released and resurrected several times, and care must be taken that it will not end up in the freelist and get destroyed multiple times. And that hasn't even touched on thread-safety yet. Could you please give an example? No, I can't, because it isn't true. I was confused...
Re: RCArray is unsafe
On 3/3/15 9:30 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: On Tuesday, 3 March 2015 at 15:01:02 UTC, Andrei Alexandrescu wrote: On 3/3/15 5:05 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: The object is still accessible after its refcount went to zero, and can therefore potentially be resurrected. Probably not a problem, but needs to be taken into account, in particular in with respect to the freelist. That's tricky, because an object can be released and resurrected several times, and care must be taken that it will not end up in the freelist and get destroyed multiple times. And that hasn't even touched on thread-safety yet. Could you please give an example? No, I can't, because it isn't true. I was confused... silently wipes sweat off forehead
Re: RCArray is unsafe
On 3/3/15 9:40 AM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: On Tuesday, 3 March 2015 at 17:00:17 UTC, Zach the Mystic wrote: On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu wrote: I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org There's a misunderstanding here. The object being assigned keeps a trailing list of past values and defers their deallocation to destruction. -- Andrei So you need an extra pointer per instance? Isn't that a big price to pay? All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. No, the cool thing about freelists is they use free memory to chain things together. Somebody please write the code already. With no code we sit forever on our testes speculating. Is the only problem we're still trying to solve aliasing which is not recognized as such and therefore doesn't bump the refcounter like it should? An extra pointer would be overkill for that. Isn't it better to just recognize the aliasing when it happens? As far as taking the address of an RcArray element, the type of which element is not itself Rc'ed, it's a different problem. The only thing I've been able to come up with is maybe to create a wrapper type within RcArray for the individual elements, and have that type do refcounting on the parent instead of itself, if that's possible. No, Andrei's proposed solution would take care of that. On assignment to RCArray, if the refcount goes to zero, the old array is put onto the cleanup list. But there can still be borrowed references to it's elements. However, these can never outlive the RCArray, therefore it's safe to destroy all of the arrays in the cleanup list in the destructor. Yes, that's exactly right, thanks for putting it so clearly. Andrei
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 17:00:17 UTC, Zach the Mystic wrote: On Tuesday, 3 March 2015 at 16:31:07 UTC, Andrei Alexandrescu wrote: I was dazzed, but I'm not anymore. I wrote my concern here: http://forum.dlang.org/post/ylpaqhnuiczfgfpqj...@forum.dlang.org There's a misunderstanding here. The object being assigned keeps a trailing list of past values and defers their deallocation to destruction. -- Andrei So you need an extra pointer per instance? Isn't that a big price to pay? All instances need to carry a pointer to refcount anyway, so the freelist could just be stored next to the refcount. The idea of creating that list, however, is more worrying, because it again involves allocations. It can get arbitrarily long. Is the only problem we're still trying to solve aliasing which is not recognized as such and therefore doesn't bump the refcounter like it should? An extra pointer would be overkill for that. Isn't it better to just recognize the aliasing when it happens? As far as taking the address of an RcArray element, the type of which element is not itself Rc'ed, it's a different problem. The only thing I've been able to come up with is maybe to create a wrapper type within RcArray for the individual elements, and have that type do refcounting on the parent instead of itself, if that's possible. No, Andrei's proposed solution would take care of that. On assignment to RCArray, if the refcount goes to zero, the old array is put onto the cleanup list. But there can still be borrowed references to it's elements. However, these can never outlive the RCArray, therefore it's safe to destroy all of the arrays in the cleanup list in the destructor.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 09:05:46 UTC, Walter Bright wrote: On 3/2/2015 9:58 PM, weaselcat wrote: Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe. Right, now consider that struct is a leaf in a complex graph of data structures. Then you still cannot have more than one mutable reference to the entire graph. Because that is impractical, Rust uses unsafe (i.e. @trusted in D speak) accessors that cast away the ownership, but do so in a way that doesn't violate the guarantees. For example, the type system doesn't allow you to get mutable references to the left and right children of a binary tree node. But there can be an accessor method that internally does some unsafe magic to return a tuple with mutable references to them, annotated with the information that they are mutably borrowed from the node. Both child refs are mutable, and the parent node is inaccessible as long as they exist.
Re: RCArray is unsafe
On 3/2/2015 9:58 PM, weaselcat wrote: Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe. Right, now consider that struct is a leaf in a complex graph of data structures.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 21:12:20 UTC, deadalnix wrote: On Monday, 2 March 2015 at 20:54:20 UTC, Walter Bright wrote: I looked at how Rust does it. I was hoping it was something clever, but it isn't. A copy is made of the object to which a borrowed reference is taken - in other words, the reference count is incremented. For D structs, that means, if there's a postblit, a copy must be made. For D ref counted classes, a ref count increment must be done. I was hoping to avoid that, but apparently there's no way. There are cases where this can be avoided, like calling pure functions. Another win for pure functions! I do think you are confusing how Rust does it. In Rust, borrowing makes the source and borrowed reference immutable by default. So by default the problem do not occurs. You can also borrow a mutable reference, in which case the source is disabled for the duration of the borrowing. That makes it impossible to borrow a mutable reference twice. The above mentioned scenario cannot happen at all in Rust, by design. As a result, there is solution for the problem, as the problem cannot occur in the first place. I don't think you were advocating for this but, +1 for a borrow system similar to Rust.
Re: RCArray is unsafe
On 3/2/2015 3:22 PM, Andrei Alexandrescu wrote: And since an RCArray may undergo several assignments during its lifetime (thus potentially needing to free several chunks of memory), the arrays to be destroyed will be kept in a freelist-style structure. Destructor walks the freelist and frees the chunks. Right, I had neglected to add that.
Re: RCArray is unsafe
On 3/2/15 12:37 PM, Walter Bright wrote:
On 3/1/2015 12:51 PM, Michel Fortin wrote:
That's actually not enough. You'll have to block access to global
variables too:
S s;
void main() {
s.array = RCArray!T([T()]); // s.array's refcount is now 1
foo(s.array[0]); // pass by ref
}
void foo(ref T t) {
s.array = RCArray!T([]); // drop the old s.array
t.doSomething(); // oops, t is gone
}
Thinking about it, there are many other ways this can happen. At the
moment, I'm stuck thinking of a solution other than requiring foo() to
be pure. Anyone have ideas?
I have a solution (as in working implementation), but also a deadline
that's staring me in the face so this will have to wait a couple more days.
I also have a bit of an attack to const/immutable support but that's
less good (allows too much freedom).
Andrei
Re: RCArray is unsafe
On 3/2/15 12:53 PM, Walter Bright wrote: I was hoping to avoid that, but apparently there's no way. There is! There is! -- Andrei
Re: RCArray is unsafe
On Monday, 2 March 2015 at 21:00:54 UTC, Andrei Alexandrescu
wrote:
On 3/2/15 12:37 PM, Walter Bright wrote:
On 3/1/2015 12:51 PM, Michel Fortin wrote:
That's actually not enough. You'll have to block access to
global
variables too:
S s;
void main() {
s.array = RCArray!T([T()]); // s.array's refcount
is now 1
foo(s.array[0]); // pass by ref
}
void foo(ref T t) {
s.array = RCArray!T([]); // drop the old s.array
t.doSomething(); // oops, t is gone
}
Thinking about it, there are many other ways this can happen.
At the
moment, I'm stuck thinking of a solution other than requiring
foo() to
be pure. Anyone have ideas?
I have a solution (as in working implementation), but also a
deadline that's staring me in the face so this will have to
wait a couple more days.
I also have a bit of an attack to const/immutable support but
that's less good (allows too much freedom).
I have discovered a marvellous solution, but this post is too
short to describe it.
Re: RCArray is unsafe
On 3/2/15 2:57 PM, Walter Bright wrote: On 3/2/2015 1:09 PM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: I have discovered a marvellous solution, but this post is too short to describe it. Fortunately, Fermat (er, Andrei) was able to pass along his dazz idea to me this afternoon, before he expired to something he had to attend to. We were both in the dumps about this problem last night, but I think he solved it. His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, then although the ref count of the payload goes to zero, it doesn't actually get deleted. I.e. the postblit manipulates the ref count, but does NOT do payload deletions. The destructor checks the ref count, if it is zero, THEN it does the payload deletion. Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. And since an RCArray may undergo several assignments during its lifetime (thus potentially needing to free several chunks of memory), the arrays to be destroyed will be kept in a freelist-style structure. Destructor walks the freelist and frees the chunks. Andrei
Re: RCArray is unsafe
On 3/2/15 3:22 PM, Andrei Alexandrescu wrote: On 3/2/15 2:57 PM, Walter Bright wrote: On 3/2/2015 1:09 PM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: I have discovered a marvellous solution, but this post is too short to describe it. Fortunately, Fermat (er, Andrei) was able to pass along his dazz idea to me this afternoon, before he expired to something he had to attend to. We were both in the dumps about this problem last night, but I think he solved it. His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, then although the ref count of the payload goes to zero, it doesn't actually get deleted. I.e. the postblit manipulates the ref count, but does NOT do payload deletions. The destructor checks the ref count, if it is zero, THEN it does the payload deletion. Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. And since an RCArray may undergo several assignments during its lifetime (thus potentially needing to free several chunks of memory), the arrays to be destroyed will be kept in a freelist-style structure. Destructor walks the freelist and frees the chunks. We may apply the same principle (memory may only be freed during destruction) to DIP74. If we figure a cheap way to keep a freelist of objects to be deallocated, we can borrow multiple times without a reference count add. But I didn't think this through yet. -- Andrei
Re: RCArray is unsafe
On Sunday, 1 March 2015 at 19:22:06 UTC, Walter Bright wrote:
On 3/1/2015 7:44 AM, Marc =?UTF-8?B?U2Now7x0eiI=?=
schue...@gmx.net wrote:
A weakness of the same kind affects DIP25, too. The core of
the problem is
borrowing (ref return as in DIP25), combined with manual
(albeit hidden) memory
management. An example to illustrate:
struct T {
void doSomething();
}
struct S {
RCArray!T array;
}
void main() {
auto s = S(RCArray!T([T()])); // s.array's refcount is
now 1
foo(s, s.array[0]); // pass by ref
}
void foo(ref S s, ref T T) {
s.array = RCArray!T([]); // drop the old s.array
t.doSomething(); // oops, t is gone
}
The trouble seems to happen when there are two references to
the same object passed to a function. I.e. there can be only
one borrowed ref at a time.
I'm thinking this could be statically disallowed in @safe code.
Yes, it's a classical aliasing problem. Of course, if the
references can't possible alias because of their types, it's ok.
However, for non-pure functions, it's always (?) unsafe, because
they have access to all kinds of global variables. Too bad we
don't have pure by default :-(
Re: RCArray is unsafe
On Monday, 2 March 2015 at 20:54:20 UTC, Walter Bright wrote: On 3/2/2015 12:42 PM, Walter Bright wrote: For D structs, that means, if there's a postblit, a copy must be made. For D ref counted classes, a ref count increment must be done. I was hoping to avoid that, but apparently there's no way. There are cases where this can be avoided, like calling pure functions. Another win for pure functions! It seems like the most common use case for passing a global to a parameter is to process that global in a pure way. You already have access to it in an impure function, so you could just access it directly. The good news is that from within the passed-to function, no further calls will treat it as global.
Re: RCArray is unsafe
On 3/2/2015 1:12 PM, deadalnix wrote: I do think you are confusing how Rust does it. In Rust, borrowing makes the source and borrowed reference immutable by default. So by default the problem do not occurs. May I refer you to: http://static.rust-lang.org/doc/0.6/tutorial-borrowed-ptr.html#borrowing-managed-boxes-and-rooting Again the lifetime of y is L, the remainder of the function body. But there is a crucial difference: suppose x were to be reassigned during the lifetime L? If the compiler isn't careful, the managed box could become unrooted, and would therefore be subject to garbage collection. A heap box that is unrooted is one such that no pointer values in the heap point to it. It would violate memory safety for the box that was originally assigned to x to be garbage-collected, since a non-heap pointer---y---still points into it. [...] For this reason, whenever an expression borrows the interior of a managed box stored in a mutable location, the compiler inserts a temporary that ensures that the managed box remains live for the entire lifetime. [...] This process is called rooting. It's possible that this is an old and obsolete document, but it's what I found.
Re: RCArray is unsafe
On 3/2/2015 1:09 PM, Marc =?UTF-8?B?U2Now7x0eiI=?= schue...@gmx.net wrote: I have discovered a marvellous solution, but this post is too short to describe it. Fortunately, Fermat (er, Andrei) was able to pass along his dazz idea to me this afternoon, before he expired to something he had to attend to. We were both in the dumps about this problem last night, but I think he solved it. His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, then although the ref count of the payload goes to zero, it doesn't actually get deleted. I.e. the postblit manipulates the ref count, but does NOT do payload deletions. The destructor checks the ref count, if it is zero, THEN it does the payload deletion. Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 20:54:20 UTC, Walter Bright wrote: I looked at how Rust does it. I was hoping it was something clever, but it isn't. A copy is made of the object to which a borrowed reference is taken - in other words, the reference count is incremented. For D structs, that means, if there's a postblit, a copy must be made. For D ref counted classes, a ref count increment must be done. I was hoping to avoid that, but apparently there's no way. There are cases where this can be avoided, like calling pure functions. Another win for pure functions! I do think you are confusing how Rust does it. In Rust, borrowing makes the source and borrowed reference immutable by default. So by default the problem do not occurs. You can also borrow a mutable reference, in which case the source is disabled for the duration of the borrowing. That makes it impossible to borrow a mutable reference twice. The above mentioned scenario cannot happen at all in Rust, by design. As a result, there is solution for the problem, as the problem cannot occur in the first place.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 00:08:10 UTC, Walter Bright wrote: On 3/2/2015 3:47 PM, weaselcat wrote: That's actually very old(0.6 - nearly 2 years ago.) I believe rooting was dropped from the language completely. http://doc.rust-lang.org/book/ownership.html also, rust by example chapter 17-19 cover this http://rustbyexample.com/move.html Thanks for the info. But I don't see how Marc's example is prevented by this. It wouldn't be compilable(it borrows the same object mutably twice) I think so, anyways. I'm not that big on rust. During a borrow, the owner may NOT (a) mutate the resource, or (b) mutably lend the resource. During a mutable borrow, the owner may NOT (a) access the resource, or (b) lend the resource.
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 00:08:10 UTC, Walter Bright wrote: On 3/2/2015 3:47 PM, weaselcat wrote: That's actually very old(0.6 - nearly 2 years ago.) I believe rooting was dropped from the language completely. http://doc.rust-lang.org/book/ownership.html also, rust by example chapter 17-19 cover this http://rustbyexample.com/move.html Thanks for the info. But I don't see how Marc's example is prevented by this. After moving resources, the previous owner can no longer be used. That means you cannot borrow twice, which mean you can't get yourself into the mentioned situation.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 20:37:46 UTC, Walter Bright wrote:
On 3/1/2015 12:51 PM, Michel Fortin wrote:
That's actually not enough. You'll have to block access to
global variables too:
S s;
void main() {
s.array = RCArray!T([T()]); // s.array's refcount is
now 1
foo(s.array[0]); // pass by ref
}
void foo(ref T t) {
s.array = RCArray!T([]); // drop the old s.array
t.doSomething(); // oops, t is gone
}
So with Andrei's solution, will s.array ever get freed, since s
is a global? I guess it *should* never get freed, since s is a
global and it will always exist as a reference.
Which makes me think about a bigger problem... when you opAssign,
don't you redirect the variable to a different instance? Won't
the destructor then destroy *that* instance (or not destroy it,
since it just got a +1 count) instead of the one most recently
decremented? How does it hold onto the instance to be destroyed?
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 01:23:24 UTC, Zach the Mystic wrote: Which makes me think about a bigger problem... when you opAssign, don't you redirect the variable to a different instance? Won't the destructor then destroy *that* instance (or not destroy it, since it just got a +1 count) instead of the one most recently decremented? How does it hold onto the instance to be destroyed? auto y = new RcStruct; y = null; y's old RcStruct gets decremented to zero, but who owns it now? Whose destructor ever gets run on it?
Re: RCArray is unsafe
On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, RcArray, a struct, already does this. You wouldn't delete in a postblit anyway would you? Do you need opRelease and ~this to be separate for structs too?
Re: RCArray is unsafe
On 3/2/15 4:01 PM, Zach the Mystic wrote: On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: His insight was that the deletion of the payload occurred before the end of the lifetime of the RC object, and that this was the source of the problem. If the deletion of the payload occurs during the destructor call, rather than the postblit, RcArray, a struct, already does this. You wouldn't delete in a postblit anyway would you? Deletion occurs in opAssign. Do you need opRelease and ~this to be separate for structs too? Probably not. Andrei
Re: RCArray is unsafe
On Tuesday, 3 March 2015 at 02:10:23 UTC, weaselcat wrote: On Tuesday, 3 March 2015 at 02:04:15 UTC, weaselcat wrote: On Tuesday, 3 March 2015 at 01:56:09 UTC, Walter Bright wrote: On 3/2/2015 4:40 PM, deadalnix wrote: After moving resources, the previous owner can no longer be used. How does that work with the example presented by Marc? He couldn't pass s and a member of s because s is borrowed as mutable. He would have to pass both as immutable. Er, I was speaking in terms of Rust of course(it has no distinction between const and immutable like D afaik) http://dpaste.com/30WAMVQ I hope this helps explain it and I didn't butcher it too bad : ) Sorry for the triple reply.
Re: RCArray is unsafe
On Monday, 2 March 2015 at 22:58:19 UTC, Walter Bright wrote: I.e. the postblit manipulates the ref count, but does NOT do payload deletions. The destructor checks the ref count, if it is zero, THEN it does the payload deletion. Pretty dazz idea, dontcha think? And DIP25 still stands unscathed :-) Unless, of course, we missed something obvious. Add me to we. I'm dazzed! :-)
