November 06, 2015
Marc Schütz's post with a Droppable struct gave me an idea of how arrays could work when you want them to be reference counted. So here's the idea for arrays...

First, let's use @rc as a type qualifier for arrays and strings that are reference counted. For instance, this type is a reference-counted array of int:

	@rc int[]

When allocated, the array payload is allocated by requesting memory from the GC, but reserving space for a reference count before the actual content:

	refcount, value1, value2, ...

So this code:

	@rc int[] array = [100, 200];
	// memory: 1, 100, 200

generates a special reference-counted array. The array has a length field as well as two pointers instead of one. One pointer points to the values, the other points to refcount. Here's the equivalent struct:

	struct RCArray(T) {
		T* ptr;
		size_t length;
		size_t* refcount_ptr;
	}

With automatic reference counting, the reference count gets incremented when assigning to another variable:

	@rc int[] array2 = array;
	// memory: 2, 100, 200

So far so good. The interesting trick here happens when you assign a @rc array to a GC array: you increment refcount too:

	int[] array_gc = array;
	// memory: 3, 100, 200

But since it's a GC array with only one pointer, the pointer to refcount gets discarded on assignment. This means that the corresponding decrement will never happen, making sure refcount will never eventually reach zero. At this point, the only way the payload will be deallocated is when the GC scans the memory and sees the memory block as unreferenced. So that's how our array got transformed to a GC array!

From there, you can assign back the GC array to a @rc one:

	@rc int[] array3 = array_gc;

Because array_gc has no pointer to refcount, the one in array3 will be set to null. Thus, refcount is not going to be incremented or decremented here. Which is fine again, because the GC is already in charge of deallocating this array.

In the case the array never got assigned to a GC array, refcount would reach zero at some point, and the memory would be deallocated without waiting for the GC to collect.

Ok, so that's fine in theory. But in practice if you have @rc arrays like this they are almost always going to end up being owned by the GC as soon as you pass it to a function, making the refcount useless. There needs to be a way to make the GC taking ownership a rare event without forcing everyone to switch to @rc arrays. Ideas?


-- 
Michel Fortin
michel.fortin@michelf.ca
https://michelf.ca


_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

November 06, 2015
On 11/02/2015 05:07 PM, Andrei Alexandrescu wrote:
> Well so I'm unclear then. You asserted that code escaping a class reference is in poor style and we needn't support it. But now you're asserting code that escapes the address of an int is a "much more common case". These two can't be simultaneously true.

It's better to do `globalCallbackList.add(klass)` then
`klass.addYourselfToGlobalCallbackList()`. The code is more loosely
coupled and the owner of the class is the one escaping the reference.

And because of that it's more common to escape a field of a class than it is to escape the whole class in a method.

> * Structs and primitive data types are not supposed to escape freely in safe code so we can afford to restrict escaping for them.

Really? There is nothing preventing me from this atm.

struct Ref
{
    int* p;
    int[] ary;
}

class Foo
{
    auto foo() @safe
    {
        return new Ref(&field, ary[]);
    }

    int field;
    int[4] ary;
}



November 06, 2015
On 11/02/2015 10:54 PM, Timon Gehr wrote:
> Simple examples:
> 
> C id(@noescape C x){ return x; }

We don't need anything like that, our problem is that a called instance
method can escape `this` or a `field`.
If you want to borrow a class reference with limited lifetime to some
other function you can use a non-copyable wrapper (similar to Proxy).



November 06, 2015
On 11/03/2015 01:36 AM, Andrei Alexandrescu wrote:
> Probably that's the general case. But if a class has no public data members and member functions that don't leak member addresses, it stands to reason conversion could break no code.

If it's a non-final class (always a bad idea for an API but we have plenty in druntime/phobos), it could cause troubles in derived classes. But you're right if it doesn't escape anything conversion should be fairly smooth.

>> Same goes for specifying an allocator to use with a ref counted class.
> 
> I don't understand this part, could you please detail.

Guess this is very uncontroversial.

Timon asked on the other thread how to specify an allocator for a class. http://forum.dlang.org/post/laudxyyjjvkivqsupczq@forum.dlang.org

Something like operator new/delete that hardcodes the allocator used for
a class is a bad idea, b/c you don't know all usage patterns for a class
in advance. Also not all allocators have a single global instance.
So this should be decided at runtime by the user of a class.

>> It seems like a much better idea to decide that when using the class as opposed to when implementing the class.
> 
> Such an approach would need to first define which subset of classes work with both GC and RC. Do we agree on that? For example, classes that escape addresses of data members work safely only with GC. Same goes about classes that escape "this".
> 
> For my money, I have long looked for a way to implement reference counting outside of the class definition. I had my mind modeled after the C++ approach, and it does seem like a very sensible idea. Lately, however, I got disabused about the notion because I figured the set of manipulations allowed to GC classes largely surpasses the set of manipulations allowed to RC classes.
> 
> I am curious how you think you can define these two subsets.

First it seems that the RC set is a strict subset of the GC one, so any RC class could also be used as GC class.

The operations not allowed on an RC class are calling a method that escapes a reference to the class or one of it's fields, and escaping a reference to one of it's public fields.

Most of this could be achieved with a wrapper similar to Proxy, if there was an inferred @noescape attribute for methods.


And yes, this means you'd have to rewrite code that implicitly shares ownership

class Widget
{
  static Widget[] all;
  this()
  {
    all ~= this;
  }
}

to something that's explicit about how the ownership is shared (in this
case by using RC).

class Widget
{
 static RC!Widget[] all;
@noescape:
  this() {}
}

RC!Widget widget()
{
  auto rc = RC!Widget();
  Widget.all ~= rc;
  return rc;
}




January 14, 2016
Happy New Year in 2016 and beyond to everyone following this list! Well we hope to get ownership done this year :o).

I was reviewing older exchanges, in particular the one quoted below regarding exceptions providing messages as lazy/transferrable sequences of characters.

Droppable is definitely interesting, but let me make a simple point: a low-tech reference counted string would fit the bill perfectly well. Consider:

* Want lazy computation? Compute the string upon the first call to msg(), then memoize it.

* Want static allocation? Provide a means to encode that in the ref-counted string, e.g. by setting the reference count to uint.max etc.

I understand it's old tech that's not exciting, but (a) we need to figure out safe reference counted types anyway and (b) reference counted strings are well understood and very successful across the industry.

For fixing the issues with reference counting and safety, the silence in this group as of late suggests there are no new ideas and new work on this. So I suggest we proceed by refining http://wiki.dlang.org/DIP77.


Thanks,

Andrei

On 11/06/2015 07:45 AM, Marc Schütz wrote:
> On Friday, 6 November 2015 at 02:44:39 UTC, Michel Fortin wrote:
>> But how do you prevent the payload from being leaked in a way that it
>> outlives the droppable? For instance, someone might want to log the
>> exception message and put it into a queue for a separate logging
>> thread to process. You're giving raw access to the string, so it's
>> very easy mess things up if you are not careful.
>
> Well, that requires borrowing/sealed references:
>
> struct Droppable(T) {
>      private T payload;
>      void delegate(ref T object) dropper;
>      ref T borrow() return { return payload; }
>      alias borrow this;
>      @disabled this(this);
>      ~this() {
>          if(dropper) dropper(payload);
>      }
> }
>
> But that's a separate topic. My point was that this is a mechanism to
> abstract away from specific ownership schemes without making the
> ownership part of the type (i.e. `Exception` can be used as-is no matter
> whether the message if garbage collected or refcounted or static).
> _______________________________________________
> Dlang-study mailing list
> Dlang-study@puremagic.com
> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

January 15, 2016
The proposed solution is not safe at all. It guarantee that the payload is alive, but doesn't guarantee it is not moved.

The Rust road is to disable whatever is borrowed from in a mutable fashion, and const whatever is borrowed from in a const fashion. The alternative is to borrow from the copy rather than just root it. Alternatively, root the object but [borrow from/pass down] the rooted object rather than the original, so effectively to don't pass down twice the same thing.

This has a nice added bonus that ref parameters can be considered noalias and the optimizer can do more (alias analysis is probably the number 1 barrier for modern optimizers). Almost all benchmark where Rust beat C++ is due to extra alias informations.


2016-01-14 20:39 GMT+01:00 Andrei Alexandrescu <andrei@erdani.com>:

> Happy New Year in 2016 and beyond to everyone following this list! Well we hope to get ownership done this year :o).
>
> I was reviewing older exchanges, in particular the one quoted below regarding exceptions providing messages as lazy/transferrable sequences of characters.
>
> Droppable is definitely interesting, but let me make a simple point: a low-tech reference counted string would fit the bill perfectly well. Consider:
>
> * Want lazy computation? Compute the string upon the first call to msg(),
> then memoize it.
>
> * Want static allocation? Provide a means to encode that in the ref-counted string, e.g. by setting the reference count to uint.max etc.
>
> I understand it's old tech that's not exciting, but (a) we need to figure out safe reference counted types anyway and (b) reference counted strings are well understood and very successful across the industry.
>
> For fixing the issues with reference counting and safety, the silence in this group as of late suggests there are no new ideas and new work on this. So I suggest we proceed by refining http://wiki.dlang.org/DIP77.
>
>
> Thanks,
>
> Andrei
>
>
> On 11/06/2015 07:45 AM, Marc Schütz wrote:
>
>> On Friday, 6 November 2015 at 02:44:39 UTC, Michel Fortin wrote:
>>
>>> But how do you prevent the payload from being leaked in a way that it outlives the droppable? For instance, someone might want to log the exception message and put it into a queue for a separate logging thread to process. You're giving raw access to the string, so it's very easy mess things up if you are not careful.
>>>
>>
>> Well, that requires borrowing/sealed references:
>>
>> struct Droppable(T) {
>>      private T payload;
>>      void delegate(ref T object) dropper;
>>      ref T borrow() return { return payload; }
>>      alias borrow this;
>>      @disabled this(this);
>>      ~this() {
>>          if(dropper) dropper(payload);
>>      }
>> }
>>
>> But that's a separate topic. My point was that this is a mechanism to
>> abstract away from specific ownership schemes without making the
>> ownership part of the type (i.e. `Exception` can be used as-is no matter
>> whether the message if garbage collected or refcounted or static).
>> _______________________________________________
>> Dlang-study mailing list
>> Dlang-study@puremagic.com
>> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
>>
> _______________________________________________
> Dlang-study mailing list
> Dlang-study@puremagic.com
> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
>


January 14, 2016
On 01/14/2016 06:29 PM, Amaury SECHET wrote:
> The proposed solution is not safe at all. It guarantee that the payload
> is alive, but doesn't guarantee it is not moved.

How do you mean it would be moved?

> The Rust road is to disable whatever is borrowed from in a mutable
> fashion, and const whatever is borrowed from in a const fashion. The
> alternative is to borrow from the copy rather than just root it.
> Alternatively, root the object but [borrow from/pass down] the rooted
> object rather than the original, so effectively to don't pass down twice
> the same thing.

The sketch is attractive indeed, but the devil is in the very many details. I think adopting this model would be too large a change for us. Also it doesn't seems Rust is taking the world by storm, which makes it more risky to copy from it.

> This has a nice added bonus that ref parameters can be considered
> noalias and the optimizer can do more (alias analysis is probably the
> number 1 barrier for modern optimizers). Almost all benchmark where Rust
> beat C++ is due to extra alias informations.

Yah, that is a nice perk.


Andrei

_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

1 2 3 4 5
Next ›   Last »