www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RCArray is unsafe

reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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:

     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
     }

Any suggestions how to deal with this? As far as I can see, there 
are the following options:

1) Make borrowing (return ref)  system. This would defeat the 
purpose of DIP25.

2) Disallow (by convention) borrowing for refcounted objects. 
Again, this would make DIP25 pointless, and strictly speaking, 
anything that relies on convention cannot be  safe. And there's 
no guarantee that it doesn't affect other things besides RC.

3) Introduce a full linear type system. A _very_ large and 
invasive change, and probably cumbersome to work with.

4) Live with it. Accept that it's not possible to get the last 
bit of  safe-ty without extreme and unjustifiable costs. Make it 
 safe nevertheless, and formulate usage guides that people are 
expected to follow.

5) Make `RCArray` a special type whose purpose is known to the 
compiler, and implement complicated checks to verify  safe-ty. 
Again, kind of defeats the purpose, and adds complexity to the 
language and implementation.

6) Restrict borrowing to situations where it's  safe. Or better, 
allow it everywhere, but make it  system where necessary. I think 
problems can only happen at function boundaries (what happens 
inside a function can be checked statically), but I'd have to 
think about it more.

7) Anything else? Are there some small details (in whatever part 
of the language) that can be adjusted to get us additional 
guarantees?

Option 6) currently appears the most promising to me.

Comments?

[1] http://forum.dlang.org/thread/mcg8qq$1mbr$1 digitalmars.com
[2] http://wiki.dlang.org/DIP25
[4] 
http://forum.dlang.org/post/ilfwmeobprkcorpiqoui forum.dlang.org
[5] http://forum.dlang.org/post/mcqk4s$6qb$1 digitalmars.com
Mar 01 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/1/15 7:44 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net>" 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:

      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
      }
Thanks for pointing this out - it's a real problem. -- Andrei
Mar 01 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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:

     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
     }

 Any suggestions how to deal with this? As far as I can see, 
 there are the following options:
See: http://forum.dlang.org/post/bghjqvvrdcfqmoiyyuqz forum.dlang.org ...and: http://forum.dlang.org/post/cviwlkugnothraubcfgy forum.dlang.org
Mar 01 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 1 March 2015 at 16:54:15 UTC, Zach the Mystic 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:

    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
    }

 Any suggestions how to deal with this? As far as I can see, 
 there are the following options:
See: http://forum.dlang.org/post/bghjqvvrdcfqmoiyyuqz forum.dlang.org ...and: http://forum.dlang.org/post/cviwlkugnothraubcfgy forum.dlang.org
That's not applicable here though. The compiler doesn't know we're doing reference counting, so it cannot insert AddRef/Release calls.
Mar 01 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 17:48:15 UTC, Marc Schütz wrote:
 That's not applicable here though. The compiler doesn't know 
 we're doing reference counting, so it cannot insert 
 AddRef/Release calls.
Why can't structs also implement opAddRef/Release? Why is it restricted to classes?
Mar 01 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 17:48:15 UTC, Marc Schütz wrote:
 See:
 http://forum.dlang.org/post/bghjqvvrdcfqmoiyyuqz forum.dlang.org
 ...and:
 http://forum.dlang.org/post/cviwlkugnothraubcfgy forum.dlang.org
That's not applicable here though. The compiler doesn't know we're doing reference counting, so it cannot insert AddRef/Release calls.
Maybe the compiler can detect a split-pass and insert the appropriate calls to the correlate opAdd/opRelease functions for structs according to the same rules as for classes. Isn't split-passing a rare business in general?
Mar 01 2015
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/1/2015 7:44 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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.
Mar 01 2015
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2015-03-01 19:21:57 +0000, Walter Bright said:

 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.
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 } -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Mar 01 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 20:51:35 UTC, Michel Fortin wrote:
 On 2015-03-01 19:21:57 +0000, Walter Bright said:

 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.
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 }
Globals to impures, that is.
Mar 01 2015
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 01 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Monday, 2 March 2015 at 05:57:35 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:
Hmm. That's not so easy to solve.
But consider this. It's only an impure function which might alias a global. And since you already have access to the global in the impure function, there might be less incentive in general to pass it through a function. Other than that, you're stuck with a theoretical " impure!varName" function attribute, for example, which tells the caller which globals are accessed.
Mar 02 2015
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2015-03-02 05:57:12 +0000, 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.fortin michelf.com http://michelf.com/
Mar 03 2015
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2015-03-03 22:39:12 +0000, 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.fortin michelf.com http://michelf.com/
Mar 03 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 20:51:35 UTC, Michel Fortin wrote:
 On 2015-03-01 19:21:57 +0000, Walter Bright said:

 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.
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 }
What's the difference between that and this: void fun() { T[] ta = [T()].dup; T* t = ta[0]; delete ta; // or however you do it *t = ...; } Why is this a parameter passing issue and not a "you kept a sub-reference to a deleted chunk" issue?
Mar 02 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Monday, 2 March 2015 at 15:22:33 UTC, Zach the Mystic wrote:
 void fun() {
   T[] ta = [T()].dup;
   T* t = ta[0];
I meant: T* t = &ta[0];
Mar 02 2015
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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?
Mar 02 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 02 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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."
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/2/2015 1:09 PM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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.
Mar 02 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/2/15 2:57 PM, Walter Bright wrote:
 On 3/2/2015 1:09 PM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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
Mar 02 2015
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 02 2015
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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=?= <schuetzm 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
Mar 02 2015
prev sibling parent reply Ivan Timokhin <timokhin.iv gmail.com> writes:
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
Mar 04 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 04 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Mar 04 2015
next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 04 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 04 2015
prev sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 05 2015
parent reply "deadalnix" <deadalnix gmail.com> writes:
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 ?
Mar 05 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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?
Mar 05 2015
parent "deadalnix" <deadalnix gmail.com> writes:
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 :)
Mar 05 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 04 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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".
Mar 04 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 04 2015
prev sibling next sibling parent "sclytrack" <sclytrack fake.com> writes:
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
Mar 05 2015
prev sibling parent Nick Treleaven <ntrel-pub mybtinternet.com> writes:
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.
Mar 09 2015
prev sibling next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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! :-)
Mar 02 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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?
Mar 02 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 02 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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, 
 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.
I guess you also mean opAssigns -- they would manipulate refcounts too right? In fact, they would be the primary means of decrementing the refcount *apart* from the destructor, right?
Mar 02 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Tuesday, 3 March 2015 at 00:05:50 UTC, Zach the Mystic wrote:
 I guess you also mean opAssigns -- they would manipulate 
 refcounts too right? In fact, they would be the primary means 
 of decrementing the refcount *apart* from the destructor, right?
Nevermind. I was a minute too soon with my post!
Mar 02 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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=?= 
 <schuetzm 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.
Mar 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/3/15 5:05 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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
Mar 03 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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=?= 
 <schuetzm 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...
Mar 03 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/3/15 9:30 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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=?= <schuetzm 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>
Mar 03 2015
prev sibling parent Nick Treleaven <ntrel-pub mybtinternet.com> writes:
On 03/03/2015 13:05, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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.
Mar 03 2015
prev sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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/ylpaqhnuiczfgfpqjuww forum.dlang.org
Mar 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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/ylpaqhnuiczfgfpqjuww 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
Mar 03 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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/ylpaqhnuiczfgfpqjuww 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.
Mar 03 2015
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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/ylpaqhnuiczfgfpqjuww 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.
Mar 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/3/15 9:40 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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/ylpaqhnuiczfgfpqjuww 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
Mar 03 2015
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/3/2015 9:44 AM, Andrei Alexandrescu wrote:
 On 3/3/15 9:40 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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.
Mar 03 2015
prev sibling parent "ixid" <adamsibson hotmail.com> writes:
 Somebody please write the code already. With no code we sit 
 forever on our testes speculating.
Isn't this testes-driven development?
Mar 03 2015
prev sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 03 2015
parent "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 03 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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/ylpaqhnuiczfgfpqjuww 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
Mar 03 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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/ylpaqhnuiczfgfpqjuww 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.
Mar 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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/ylpaqhnuiczfgfpqjuww 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
Mar 03 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 03 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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;".
Mar 03 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 04 2015
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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 cut&pasted by people implementing their own RC types.
Mar 04 2015
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 04 2015
next sibling parent "Paolo Invernizzi" <paolo.invernizzi no.address> writes:
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
Mar 04 2015
prev sibling next sibling parent "No" <no no.no> writes:
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
Mar 04 2015
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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?
Mar 04 2015
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Mar 04 2015
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 04 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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.
Mar 04 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/4/15 6:02 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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
Mar 04 2015
prev sibling next sibling parent reply "ponce" <contact gam3sfrommars.fr> writes:
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.
Mar 04 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 04 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Mar 04 2015
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 04 2015
prev sibling parent reply "ponce" <contact gam3sfrommars.fr> writes:
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.
Mar 04 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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 :^)
Mar 04 2015
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 04 2015
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 04 2015
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 04 2015
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 04 2015
parent "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 04 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 04 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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/offurllmuxjewizxedab forum.dlang.org See also my reply to deadalnix: http://forum.dlang.org/post/oyaoibmwybzfkhhufpow forum.dlang.org
Mar 04 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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/offurllmuxjewizxedab forum.dlang.org The only thing which bears reiterating is that with better attribute inference, the whole system becomes invisible for most uses.
Mar 04 2015
next sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 04 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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. ???
Mar 04 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 04 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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?
Mar 02 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
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?
Mar 02 2015
prev sibling parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
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.
Mar 03 2015
next sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Mar 03 2015
parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
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
Mar 03 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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. :-)
Mar 03 2015
prev sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 03 2015
parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
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.
Mar 03 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
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/offurllmuxjewizxedab 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.
Mar 04 2015
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/1/15 2:21 PM, Walter Bright wrote:
 On 3/1/2015 7:44 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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
      }
This is an odd example, how does one take a ref to an RCArray element without the machinery to retain the array? I would think that RCArray[x] would return something that isn't passable to a function. Or am I missing something?
 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.
Not exactly. Note that we are taking by reference S, which is NOT reference counted. So you are passing indirectly a reference to an RC object. You aren't "borrowing" that reference. -Steve
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/2/2015 12:37 PM, Steven Schveighoffer wrote:
 Not exactly. Note that we are taking by reference S, which is NOT reference
 counted. So you are passing indirectly a reference to an RC object. You aren't
 "borrowing" that reference.
It's seems that to solve the problem, it has to be borrowed, in that a static check will be needed that what it points to cannot be modified/deleted through other references to the same data.
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/2/2015 12:42 PM, Walter Bright wrote:
 On 3/2/2015 12:37 PM, Steven Schveighoffer wrote:
 Not exactly. Note that we are taking by reference S, which is NOT reference
 counted. So you are passing indirectly a reference to an RC object. You aren't
 "borrowing" that reference.
It's seems that to solve the problem, it has to be borrowed, in that a static check will be needed that what it points to cannot be modified/deleted through other references to the same data.
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!
Mar 02 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 02 2015
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 02 2015
next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
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.
Mar 02 2015
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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 ;-)
Mar 03 2015
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 02 2015
next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
On Monday, 2 March 2015 at 22:51:03 UTC, Walter Bright wrote:
 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.
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
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 02 2015
next sibling parent "weaselcat" <weaselcat gmail.com> writes:
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.
Mar 02 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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?
Mar 02 2015
next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
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.
Mar 02 2015
next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
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)
Mar 02 2015
parent "weaselcat" <weaselcat gmail.com> writes:
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.
Mar 02 2015
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 02 2015
next sibling parent "Seo Sanghyeon" <sanxiyn gmail.com> writes:
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.
Mar 03 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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?
Mar 03 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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?
I'm not sure what you don't understand. The comment in the sample code seems clear to me. // "Move" `a` into `b` // Here's what happens under the hood: the pointer `a` gets copied (*not* // the data on the heap, just its address) into `b`. Now both are pointers // to the *same* heap allocated data. But now, `b` *owns* the heap // allocated data; `b` is now in charge of freeing the memory in the heap. let b = a; Now you have a variable b that owns the data. a is not usable anymore. // After the previous move, `a` can no longer be used // Error! `a` can no longer access the data, because it no longer owns the // heap memory //println!("a contains: {}", a); // TODO ^ Try uncommenting this line As explained here, if a is used, this is an error. In the example a is move to b. If you had let b = &a, then b would borrow from a. The same way, a would not be usable anymore. The difference with move is that, when b is destroyed, in the first case memory is freed. in the second case, memory is not freed and a is "reenabled". It is either possible to borrow once and disable who you borrow from, or borrow multiple time and everything become immutable for the time you borrow. This makes the problems mentioned in this thread effectively impossible happen.
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/2/2015 9:27 PM, deadalnix 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?
I'm not sure what you don't understand. The comment in the sample code seems clear to me. // "Move" `a` into `b` // Here's what happens under the hood: the pointer `a` gets copied (*not* // the data on the heap, just its address) into `b`. Now both are pointers // to the *same* heap allocated data. But now, `b` *owns* the heap // allocated data; `b` is now in charge of freeing the memory in the heap. let b = a; Now you have a variable b that owns the data. a is not usable anymore. // After the previous move, `a` can no longer be used // Error! `a` can no longer access the data, because it no longer owns the // heap memory //println!("a contains: {}", a); // TODO ^ Try uncommenting this line As explained here, if a is used, this is an error. In the example a is move to b. If you had let b = &a, then b would borrow from a. The same way, a would not be usable anymore. The difference with move is that, when b is destroyed, in the first case memory is freed. in the second case, memory is not freed and a is "reenabled". It is either possible to borrow once and disable who you borrow from, or borrow multiple time and everything become immutable for the time you borrow. This makes the problems mentioned in this thread effectively impossible happen.
What if 'a' is a field of a struct in some non-trivial data structure? How is the compiler going to statically keep track of which field instances in this structure are not usable?
Mar 02 2015
parent reply "weaselcat" <weaselcat gmail.com> writes:
On Tuesday, 3 March 2015 at 05:40:59 UTC, Walter Bright wrote:
 On 3/2/2015 9:27 PM, deadalnix 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?
I'm not sure what you don't understand. The comment in the sample code seems clear to me. // "Move" `a` into `b` // Here's what happens under the hood: the pointer `a` gets copied (*not* // the data on the heap, just its address) into `b`. Now both are pointers // to the *same* heap allocated data. But now, `b` *owns* the heap // allocated data; `b` is now in charge of freeing the memory in the heap. let b = a; Now you have a variable b that owns the data. a is not usable anymore. // After the previous move, `a` can no longer be used // Error! `a` can no longer access the data, because it no longer owns the // heap memory //println!("a contains: {}", a); // TODO ^ Try uncommenting this line As explained here, if a is used, this is an error. In the example a is move to b. If you had let b = &a, then b would borrow from a. The same way, a would not be usable anymore. The difference with move is that, when b is destroyed, in the first case memory is freed. in the second case, memory is not freed and a is "reenabled". It is either possible to borrow once and disable who you borrow from, or borrow multiple time and everything become immutable for the time you borrow. This makes the problems mentioned in this thread effectively impossible happen.
What if 'a' is a field of a struct in some non-trivial data structure? How is the compiler going to statically keep track of which field instances in this structure are not usable?
Borrowing 'a' from a struct would make the parent struct immutable during the borrow scope of 'a', I believe.
Mar 02 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 03 2015
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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.
Mar 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/3/15 5:45 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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
Mar 03 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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=?= 
 <schuetzm 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.
Mar 03 2015
parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/3/2015 9:19 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm 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.
Mar 03 2015
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
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).
Mar 03 2015
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 2 March 2015 at 22:51:03 UTC, Walter Bright wrote:
 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.
Yes, this page is obsolete, but it is still very interesting as it is a viable solution for us.
Mar 02 2015
prev sibling parent "Zach the Mystic" <reachzach gggmail.com> writes:
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.
Mar 02 2015
prev sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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=?= 
 <schuetzm 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 :-(
Mar 02 2015
prev sibling parent reply "Sativa" <Sativa Indica.org> writes:
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 type of class. rcclass FRCT // rcclass means reference counted class. It is identical to your basic // D type of class but has different keyword designator(which is why we call them free). { int x; float[] y // etc, FRCT does not point to any RCT's } rcclass X { } // Just another RCT rcclass RCT { FRCT myFRCT; int y; RCT foo(ref barRCT); X x; // etc Basically this is a class that can include other RCT's } ---- Ultimately we could simply use the basic D class but we would have to designate every type as an RCT type... even the basic types. I'm trying to avoid some basic issues of that method that would derail the discussion. [But for those that want to know: one could simply treat all objects in d as rcclass types describe above, even basic types and such, but optimize out the reference counting part in in the compiler for those basic and FRCT types... this then would simply lead back to the method I'm using to describe it but simply some of the details were hidden in the "simple method" by the compiler] So, once you have such a type system. The way to deal with the complex relationships that exist are to know them: 1. A RCT have the following relationships between it's containing types. We will denote T to be a non-RCT type, FRCT to be an FRCT, and RCT to be an RCT. RCT can contain T's, FRCT's, and/or, RCT's. In Code: rcclass RCT { T t; FRCT myFRCT; RCT myRCT; } In this case, which is the only case we will talk about w.l.o.g), when an RCT is released it must attempt to release each of it's references... in example above: t, myFRCT, and myRCT. Since t is a simple type, it can be released immediately. No RCT's point to it because if they did, then T would be an RCT and it isn't. Similarly myFRCT can easily be released because it is just a complex of things like T's. In this case though there is something slightly different about it which is the referencing counting part. Essentially it's contained types are simple types but it still has a reference counting aspect for itself. Basically T's and FRCT's can free themselves when they need to. This is because they know how to free each reference they contain and it can't cause referential problems simply because they do not contain such references. This by no means they won't cause other parts of code to access invalid references. A pointer to such a member of a class can easily try and access the member after the object has been freed. But this is not our concern because we are only dealing with RCT's. Our goal isn't to have everything be RCT's. If that was the case then the T and FRCT cases would not be needed since we won't use them. e.g., We might want the GC to handle non-RCT and some other method for FRCT's. This allows one to build on current D system. But one must remember that RCT's only guarantee valid referencing when they access other RCT's. The last sentence above directs where we are going with this: Since we have RCT we can make sure they know how to communicate with each other. (we are creating a metatype here) By having the proper communication system here it is possible for the types to know when they need to be released. In fact, it is not hard and several methods can be used, even simultaneously. Axiom: Every RCT has the ability to have any other RCT that contains a reference to it, to be able to release it. Also, vice versa! [This requirement essentially allows the very final reference to know that it needs to release other dependencies it had and allows it to not only clean up itself but everything else it needs to clean up] Once you have the above requirement of RCT's(The implement dealt with at a different time), you can lazily release objects in the background without issue(fragmentation of the heap is a harder matter but still has a solution because of the above requirement). How do they communicate: Your example will do: rcstruct T { void doSomething(); } rcstruct S { T[] array; } void main() { auto s = S(new T()); // Here when the compiler creates the array of T's S knows T is a RFC. // In this case it can get at the hidden communications layer of T and // inform T that it is using it. Hence at this point // Both S and T can communicate with each other! (not just blind inc/dec of an int auto t = s.array[0]; foo(s, s.array[0]); // nothing special except foo much create an added reference to the two argments // This can be optimized out as long as foo returns once for every time it // is called. In this case, At the start of foo, the counters will be inc'ed // and at the end they will be dec'ed. Always a zero sum outside the function call. t.doSomething(); // Skip to foo, come back when done with foo! Great, t is still around! // (RC is still zero at this point!) } void foo(ref S s, ref T t) { s.array = new T[]; // Here we are reassigning the array. No problem! We simply inc the ref count on the new array and decment it on the old. Just like normal ARC'ing! The only different is that t is not immediately release! Even though it has a RC count of 0. Think of it as lazy ARC'ing... or LARC'ing! ;) t.doSomething(); // Great, even though t has an RC count of zero, it hasn't been released yet! } So, what is this LARCING? Essentially instead of s simply dumping t in foo, it informs t that it is no longer using it. This sets the RC = 0 !!BUT!! t does not free itself immediately! If it does, it leads to the problem you have given and also to the extended problem I have shown above(calling t.doSomething in main). If t sticks around though, we are not releasing memory and hence what is the point? Well, as usual this is an engineering problem. We have a few cases. 1. The compiler can prove that a RCT goes out of scope and is not used any more. In this case t can release itself at the end of the function where it is provable that it is no longer used. (In your example it is at the end of foo ad in my example it is at the end of main) Flow analysis, simple brute force checking, etc are used here. Most cases in program will fall under this category. Local variables that are not referenced to by global variables are proven to be releasable at the end of the function call. Hence, many cases will work as simple ARC'ing and not require LARC'ing. 2. The compiler cannot prove when a variable is release. This is when the type itself has to decide when it is not being used. (this the last part of the problem and your example falls under it) In this case, the communication between S and T is crucial. When s decides it no longer need t, it informs t. t has a list of every reference that is using it(this can just be a pointer to the ref count of the RCT). Having this list, while potentially weighty, lets t know when all the references to it are not needed any more(sort of chains or links between any other RCT and t have been broken). Once this is done it is a simple matter of t trying to release itself every time it goes out of scope. a. At some point t will release itself b. t will never be able to release itself(this is generally due to program error in which a reference was made to t without removing the reference when it was done). Note this is why if every type is an RCT, prevents dangling(e.g., we would have full LARC'ing... or FLARC'ing.). FLARC'ing may not be optimal though(all pointers would have to be RCT which would probably be quiet inefficient. Also interdependencies are handled easily: s.t = t; t.s = s; while (!isFree(t) && !isFree(s)) { s.t = null; t.s = null; if (t.refCount == 0) s.release(); if (s.refCount == 0) t.release(); } The reason that t and s are released in LARC'ing is because at the 2nd time through the loop s.release() knows that t no longer depend and can release itself immediately(because t.s = null set s's *t entry* to 0 on it so now s knows that t doesn't depend on it). This is just a prototype that can be used to show that any level of nesting between types will eventually resolve all releases properly. c. Alternatively, a GC like memory manager can scan through the types and release all types who's reference count = 0 and who's dependencies are all invalid(nothing depends on it). It can do this in the background without issue and can compact consecutively release objects without issue. i.e., the GC knows what part of the heap belonged to objects there were ref counted and if it is proven they have any references then it can mark them as free'ed memory. Consecutive free'ed objects in memory can be combined since they never will be used again. This can be done behind in parallel and is sort of minor defragmentation. In fact, analogous to defragmenting a drive. If you know a file is not being used then you can defragment it in the background and move the various parts around without issue because you know it is not being used. Once it is being uses, you run into issues with having to stop the threads that are using that part of the heap. (I think this limitation could ultimately be removed for most practical cases.) In this case the GC would have to have a list of all objects of RCT's. Essentially the GC is given to the task of LARC'ing in the background. Finally, which such an structural approach(Essentially implementing the reference list, which is a random access list containing all the references(pointers to all classes that use the type)) to ref counting becomes pretty stable and in probably 99%+ of program usage, statically proven to release memory(step a above, The compiler inserts many static releases that are released immediately and many types will be simple types that don't need LARC'ing). The two issues with this, as always, are speed and memory usage. I think it should rather fast(most releases are direct and just release themselves since they don't have references. On top of that the remaining are mostly FRCT's which can be released nearly immediately(they can, but don't until they are informed it is ok). For the full blown RCT types, the way they release things is in a hierarchical manner which can create avalanches of changes. If many objects are waiting for one object to be released, then when it does, they all could be released immediately. But this chain reaction is simply lazily recursive and eventually terminates. The only real problem is how to deal with un-managed references to RCT types. These are references(say pointers) to RCT's that may not be "smart"(inform the RFC that it is no longer being refered to. A simple pointer to a class that doesn't do any communication is the prototypical problem. The only solution seems to be to just accept it. It is a necessary evil. Allow it but require the program to know the intricate details. Such pointers are needed for speed and don't inherently cause any problems. It's only when they are abused can issues creep in. If one, say, had RCT pointers that are used for some types of problems and simple pointers when they are needed, it becomes pretty marginal of an issue. (if you are doing driver programming and have to have speed and direct access then use the simple pointers but it is your just to know if your references are working as expected. In many cases, RCT pointers can be used in many of the cases which make further minimize the singular problem case(that of non-informative referencing). (We could call such types "Peeping Toms"... but as long as they only peek it is ok(not by law, in programming ;)). At this, imagine that such a system was implemented. It would provide almost complete automatic memory management coverage with releasing resources as they are generally released in the program flow. In fact, with a GC(don't you just hate it when your garbage man doesn't pick up your trash sometimes? specially if he never picks it up) that essentially works parallel, most of the actual releasing can be done in the background without ever stopping the program. The benefits are: Better real-time behavior, Some programs might never need to compact the heap(in fact, if intelligent heap allocation is used, probably most programs could benefit from it), and debugging is much easier(Essentially more like manual management for most objects... just the compiler handles for us, but we know when, most likely, an object goes out of scope it will be released). Seg faults due to invalid memory access will almost be reduced to 0(since the corner case... the problem case of simple references is not used as much as all the other ways to use objects). The downside? There really isn't one except memory usage! One can come up with special cases that simply don't work well under LARC'ing but because it allows one to use non-LARC'ing types, the programmer will just have to manage it on is own or a mixed combination. Another great benefit is performance. One may think with all the all the extra allocation and deallocation code that the end's of functions would be slowed down(do to objects being lazily released). This is not necessarily the case because it is LARC'ing, the releases can be done later... say outside a performant piece of the code. It can even be faster than directly releasing it because that could be slow in and of itself, which, again, with LARC'ing, we can chose a better time to release the object or do it in the background. Unfortunately, if I'm not mistaken, with FLARC'ing, all classes would essentially double in size. This is because if every reference the type has is a RCT then it would essentially need to store a pointer to the object as to provide a link to it. With limited LARC'ing I think one could probably achieve a good balance. (for large classes and/or a large number of objects, one could just avoid LARC'ing to prevent the overhead and doing it manually or with GC) Some codetalk(tm) of how the interaction goes: Object s is being initialized. It is a RFC type. It has, as a member, a object x that is also a RFC type. In the course of s being initialized, it initializes x. We'll assume it is not null. To do this s creates the object for x then informs x that it has a reference to it(we could have multiple types of references for further optimization if we want). e.g., x = new X; x.CreateReference(s); s.CreateReferenec(x); // We use directionless binding references Now, suppose at some point s is being released. At the end of scope the compiler inserts s.Release(); S now tries to release itself. It checks it's ref count and the list of all references it has. e.g., refCount = 0; refList = {} then in s.Release() if (s.refCount == 0 && s.refList.IsEmpty) { GC.RemoveRCT(s); // GC.RemoveRCT is not necessary needed but using it hear for expressive purposes. s.Free(); } else GC.AddRCT(s); // Here, since the compiler potentially isn't going insert another s.Release() outside the function we have to let the GC handle it in this case s free's itself immediately. If either refCount != 0 or refList != empty, the GC is given control(it is made aware that S needs to be periodically checked to see if it can be released.(the GC simply does the if (s.refCount == 0 && s.refList.IsEmpty) s.Free(); in a parallel thread. If s.refCount == 0 and s.refList is empty at some point then the GC ends up free'ing s. Also, the compiler may be able to insert another s.Release() in the outer scope of the function all if it releases that it s was probably not released before. This doesn't hurt anything except an extra check that might be wasted(profiling could remove this check or even insert it). The only way s can't be released is if it's refCount and refList are not empty. This is "danling" references and can only happen when mixing non-RCT's with RCT's. So we know how s should release it self but how does t know that s no longer needs it? (so t can release itself at some point) well, this has to do when x is assigned to. e.g., s.x = new X; // Hidden, we have s update it's ref list and inform both the hold x and the new x what is going on. here the assignment will need to remove the old x from refList and add the new x. This keeps the the list up to date. (there is a big corner case here that I believe would never occur but will have to think about it more) Any ways, I'll leave it at that for now!
Mar 02 2015
parent "Biker" <biker outlaw.net> writes:
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 type of class. rcclass FRCT // rcclass means reference counted class. It is identical to your basic // D type of class but has different keyword designator(which is why we call them free). { int x; float[] y // etc, FRCT does not point to any RCT's } rcclass X { } // Just another RCT rcclass RCT { FRCT myFRCT; int y; RCT foo(ref barRCT); X x; // etc Basically this is a class that can include other RCT's } ---- Ultimately we could simply use the basic D class but we would have to designate every type as an RCT type... even the basic types. I'm trying to avoid some basic issues of that method that would derail the discussion. [But for those that want to know: one could simply treat all objects in d as rcclass types describe above, even basic types and such, but optimize out the reference counting part in in the compiler for those basic and FRCT types... this then would simply lead back to the method I'm using to describe it but simply some of the details were hidden in the "simple method" by the compiler] So, once you have such a type system. The way to deal with the complex relationships that exist are to know them: 1. A RCT have the following relationships between it's containing types. We will denote T to be a non-RCT type, FRCT to be an FRCT, and RCT to be an RCT. RCT can contain T's, FRCT's, and/or, RCT's. In Code: rcclass RCT { T t; FRCT myFRCT; RCT myRCT; } In this case, which is the only case we will talk about w.l.o.g), when an RCT is released it must attempt to release each of it's references... in example above: t, myFRCT, and myRCT. Since t is a simple type, it can be released immediately. No RCT's point to it because if they did, then T would be an RCT and it isn't. Similarly myFRCT can easily be released because it is just a complex of things like T's. In this case though there is something slightly different about it which is the referencing counting part. Essentially it's contained types are simple types but it still has a reference counting aspect for itself. Basically T's and FRCT's can free themselves when they need to. This is because they know how to free each reference they contain and it can't cause referential problems simply because they do not contain such references. This by no means they won't cause other parts of code to access invalid references. A pointer to such a member of a class can easily try and access the member after the object has been freed. But this is not our concern because we are only dealing with RCT's. Our goal isn't to have everything be RCT's. If that was the case then the T and FRCT cases would not be needed since we won't use them. e.g., We might want the GC to handle non-RCT and some other method for FRCT's. This allows one to build on current D system. But one must remember that RCT's only guarantee valid referencing when they access other RCT's. The last sentence above directs where we are going with this: Since we have RCT we can make sure they know how to communicate with each other. (we are creating a metatype here) By having the proper communication system here it is possible for the types to know when they need to be released. In fact, it is not hard and several methods can be used, even simultaneously. Axiom: Every RCT has the ability to have any other RCT that contains a reference to it, to be able to release it. Also, vice versa! [This requirement essentially allows the very final reference to know that it needs to release other dependencies it had and allows it to not only clean up itself but everything else it needs to clean up] Once you have the above requirement of RCT's(The implement dealt with at a different time), you can lazily release objects in the background without issue(fragmentation of the heap is a harder matter but still has a solution because of the above requirement). How do they communicate: Your example will do: rcstruct T { void doSomething(); } rcstruct S { T[] array; } void main() { auto s = S(new T()); // Here when the compiler creates the array of T's S knows T is a RFC. // In this case it can get at the hidden communications layer of T and // inform T that it is using it. Hence at this point // Both S and T can communicate with each other! (not just blind inc/dec of an int auto t = s.array[0]; foo(s, s.array[0]); // nothing special except foo much create an added reference to the two argments // This can be optimized out as long as foo returns once for every time it // is called. In this case, At the start of foo, the counters will be inc'ed // and at the end they will be dec'ed. Always a zero sum outside the function call. t.doSomething(); // Skip to foo, come back when done with foo! Great, t is still around! // (RC is still zero at this point!) } void foo(ref S s, ref T t) { s.array = new T[]; // Here we are reassigning the array. No problem! We simply inc the ref count on the new array and decment it on the old. Just like normal ARC'ing! The only different is that t is not immediately release! Even though it has a RC count of 0. Think of it as lazy ARC'ing... or LARC'ing! ;) t.doSomething(); // Great, even though t has an RC count of zero, it hasn't been released yet! } So, what is this LARCING? Essentially instead of s simply dumping t in foo, it informs t that it is no longer using it. This sets the RC = 0 !!BUT!! t does not free itself immediately! If it does, it leads to the problem you have given and also to the extended problem I have shown above(calling t.doSomething in main). If t sticks around though, we are not releasing memory and hence what is the point? Well, as usual this is an engineering problem. We have a few cases. 1. The compiler can prove that a RCT goes out of scope and is not used any more. In this case t can release itself at the end of the function where it is provable that it is no longer used. (In your example it is at the end of foo ad in my example it is at the end of main) Flow analysis, simple brute force checking, etc are used here. Most cases in program will fall under this category. Local variables that are not referenced to by global variables are proven to be releasable at the end of the function call. Hence, many cases will work as simple ARC'ing and not require LARC'ing. 2. The compiler cannot prove when a variable is release. This is when the type itself has to decide when it is not being used. (this the last part of the problem and your example falls under it) In this case, the communication between S and T is crucial. When s decides it no longer need t, it informs t. t has a list of every reference that is using it(this can just be a pointer to the ref count of the RCT). Having this list, while potentially weighty, lets t know when all the references to it are not needed any more(sort of chains or links between any other RCT and t have been broken). Once this is done it is a simple matter of t trying to release itself every time it goes out of scope. a. At some point t will release itself b. t will never be able to release itself(this is generally due to program error in which a reference was made to t without removing the reference when it was done). Note this is why if every type is an RCT, prevents dangling(e.g., we would have full LARC'ing... or FLARC'ing.). FLARC'ing may not be optimal though(all pointers would have to be RCT which would probably be quiet inefficient. Also interdependencies are handled easily: s.t = t; t.s = s; while (!isFree(t) && !isFree(s)) { s.t = null; t.s = null; if (t.refCount == 0) s.release(); if (s.refCount == 0) t.release(); } The reason that t and s are released in LARC'ing is because at the 2nd time through the loop s.release() knows that t no longer depend and can release itself immediately(because t.s = null set s's *t entry* to 0 on it so now s knows that t doesn't depend on it). This is just a prototype that can be used to show that any level of nesting between types will eventually resolve all releases properly. c. Alternatively, a GC like memory manager can scan through the types and release all types who's reference count = 0 and who's dependencies are all invalid(nothing depends on it). It can do this in the background without issue and can compact consecutively release objects without issue. i.e., the GC knows what part of the heap belonged to objects there were ref counted and if it is proven they have any references then it can mark them as free'ed memory. Consecutive free'ed objects in memory can be combined since they never will be used again. This can be done behind in parallel and is sort of minor defragmentation. In fact, analogous to defragmenting a drive. If you know a file is not being used then you can defragment it in the background and move the various parts around without issue because you know it is not being used. Once it is being uses, you run into issues with having to stop the threads that are using that part of the heap. (I think this limitation could ultimately be removed for most practical cases.) In this case the GC would have to have a list of all objects of RCT's. Essentially the GC is given to the task of LARC'ing in the background. Finally, which such an structural approach(Essentially implementing the reference list, which is a random access list containing all the references(pointers to all classes that use the type)) to ref counting becomes pretty stable and in probably 99%+ of program usage, statically proven to release memory(step a above, The compiler inserts many static releases that are released immediately and many types will be simple types that don't need LARC'ing). The two issues with this, as always, are speed and memory usage. I think it should rather fast(most releases are direct and just release themselves since they don't have references. On top of that the remaining are mostly FRCT's which can be released nearly immediately(they can, but don't until they are informed it is ok). For the full blown RCT types, the way they release things is in a hierarchical manner which can create avalanches of changes. If many objects are waiting for one object to be released, then when it does, they all could be released immediately. But this chain reaction is simply lazily recursive and eventually terminates. The only real problem is how to deal with un-managed references to RCT types. These are references(say pointers) to RCT's that may not be "smart"(inform the RFC that it is no longer being refered to. A simple pointer to a class that doesn't do any communication is the prototypical problem. The only solution seems to be to just accept it. It is a necessary evil. Allow it but require the program to know the intricate details. Such pointers are needed for speed and don't inherently cause any problems. It's only when they are abused can issues creep in. If one, say, had RCT pointers that are used for some types of problems and simple pointers when they are needed, it becomes pretty marginal of an issue. (if you are doing driver programming and have to have speed and direct access then use the simple pointers but it is your just to know if your references are working as expected. In many cases, RCT pointers can be used in many of the cases which make further minimize the singular problem case(that of non-informative referencing). (We could call such types "Peeping Toms"... but as long as they only peek it is ok(not by law, in programming ;)). At this, imagine that such a system was implemented. It would provide almost complete automatic memory management coverage with releasing resources as they are generally released in the program flow. In fact, with a GC(don't you just hate it when your garbage man doesn't pick up your trash sometimes? specially if he never picks it up) that essentially works parallel, most of the actual releasing can be done in the background without ever stopping the program. The benefits are: Better real-time behavior, Some programs might never need to compact the heap(in fact, if intelligent heap allocation is used, probably most programs could benefit from it), and debugging is much easier(Essentially more like manual management for most objects... just the compiler handles for us, but we know when, most likely, an object goes out of scope it will be released). Seg faults due to invalid memory access will almost be reduced to 0(since the corner case... the problem case of simple references is not used as much as all the other ways to use objects). The downside? There really isn't one except memory usage! One can come up with special cases that simply don't work well under LARC'ing but because it allows one to use non-LARC'ing types, the programmer will just have to manage it on is own or a mixed combination. Another great benefit is performance. One may think with all the all the extra allocation and deallocation code that the end's of functions would be slowed down(do to objects being lazily released). This is not necessarily the case because it is LARC'ing, the releases can be done later... say outside a performant piece of the code. It can even be faster than directly releasing it because that could be slow in and of itself, which, again, with LARC'ing, we can chose a better time to release the object or do it in the background. Unfortunately, if I'm not mistaken, with FLARC'ing, all classes would essentially double in size. This is because if every reference the type has is a RCT then it would essentially need to store a pointer to the object as to provide a link to it. With limited LARC'ing I think one could probably achieve a good balance. (for large classes and/or a large number of objects, one could just avoid LARC'ing to prevent the overhead and doing it manually or with GC) Some codetalk(tm) of how the interaction goes: Object s is being initialized. It is a RFC type. It has, as a member, a object x that is also a RFC type. In the course of s being initialized, it initializes x. We'll assume it is not null. To do this s creates the object for x then informs x that it has a reference to it(we could have multiple types of references for further optimization if we want). e.g., x = new X; x.CreateReference(s); s.CreateReferenec(x); // We use directionless binding references Now, suppose at some point s is being released. At the end of scope the compiler inserts s.Release(); S now tries to release itself. It checks it's ref count and the list of all references it has. e.g., refCount = 0; refList = {} then in s.Release() if (s.refCount == 0 && s.refList.IsEmpty) { GC.RemoveRCT(s); // GC.RemoveRCT is not necessary needed but using it hear for expressive purposes. s.Free(); } else GC.AddRCT(s); // Here, since the compiler potentially isn't going insert another s.Release() outside the function we have to let the GC handle it in this case s free's itself immediately. If either refCount != 0 or refList != empty, the GC is given control(it is made aware that S needs to be periodically checked to see if it can be released.(the GC simply does the if (s.refCount == 0 && s.refList.IsEmpty) s.Free(); in a parallel thread. If s.refCount == 0 and s.refList is empty at some point then the GC ends up free'ing s. Also, the compiler may be able to insert another s.Release() in the outer scope of the function all if it releases that it s was probably not released before. This doesn't hurt anything except an extra check that might be wasted(profiling could remove this check or even insert it). The only way s can't be released is if it's refCount and refList are not empty. This is "danling" references and can only happen when mixing non-RCT's with RCT's. So we know how s should release it self but how does t know that s no longer needs it? (so t can release itself at some point) well, this has to do when x is assigned to. e.g., s.x = new X; // Hidden, we have s update it's ref list and inform both the hold x and the new x what is going on. here the assignment will need to remove the old x from refList and add the new x. This keeps the the list up to date. (there is a big corner case here that I believe would never occur but will have to think about it more) Any ways, I'll leave it at that for now!
tldr; ``I don't know what I'm talking about.``
Mar 03 2015