Reference counted containers prototype

[Michel Fortin]

On 2011-12-27 14:57:18 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> On 12/27/11 8:21 AM, Michel Fortin wrote:
>> On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu
>>> 1. "Basic" containers - reference semantics, using classic garbage
>>> collection
>>> 
>>> 2. Reference counted containers - still reference semantics, using
>>> reference counting
>>> 
>>> 3. COW containers - value semantics, using reference counting to make
>>> copying O(1).
>> 
>> I like the idea, but...
>> 
>> I worry about fragmentation.
>> 
>> Say we have those three variant of each container and you write a
>> function accepting a container, which one do you use for the parameter?
>> The only type common to all three is "DListImpl", except it shouldn't
>> work because:
>> 
>> 1. you barred access to the underlying DListImpl in RefCounted (using
>> opDispatch instead of alias this)
>> 2. you want to spare users of writing "ref" every time they write a
>> function prototype
>> 
>> Those two design constrains makes it impossible to have a common type
>> independent of the "packaging" policy.
> 
> Things could be arranged to make that happen (e.g. by making "cow" a 
> runtime parameter), but I think that would be a wrong turn. These 
> options are important design choices, not happenstance details; one 
> should _not_ naively mix them. For example, say we arrange things such 
> that "cow" is opaque. Then code using a DList would have dramatically 
> different semantics depending on what DList you pass in, or would need 
> to guard everything with lst.isCow vs. not.

Indeed, COW must not be a runtime parameter.


>> I worry also about const and immutable.
>> 
>> It's nice to have reference counting, but it works poorly with const and
>> immutable. If a function declares it takes a const container, you'll
>> have to pass the reference counted container by ref to avoid mutating
>> the reference count, which goes contrary one of your goals.
> 
> I talked a lot about this with Walter and we concluded that the story 
> with const and immutable goes like this: in a RefCounted!T object, the 
> T is constant, not the RefCounted. So it would be RefCounted!(immutable 
> T).

That'll work, but I'm not sure where you're getting at with this.

Instead of writing "const DList!T" as the parameter type in your 
function you have to write "RefCounted!(const DListImpl!T)"? Isn't that 
worse than "ref const DList!T"?


>> - - -
>> 
>> Let me make a language suggestion that will address both of these problems.
>> 
>> Allow structs to be flagged so they are always passed by reference to a
>> function, like this:
>> 
>> ref struct DListImpl {…}
>> 
>> Now a function accepting a DListImpl will implicitly have it passed by
>> "ref" with no unnecessary copy, and no need to mutate a reference count:
>> 
>> void func(DListImpl list) {…}
>> 
>> Then you can use alias this in RefCounted giving access to a "ref
>> DListImpl" which can be passed to functions always by ref, regardless of
>> the packaging policy, and without the need to remember to write "ref"
>> every time you write a function accepting a container (because it is a
>> ref struct which is always implicitly passed by ref).
>> 
>> Functions that don't need to store a reference to the container won't
>> have to care about whether the container they get is maintained using a
>> reference counter, COW, or the GC. And those functions can accept a
>> const container, or even a value-type container (which gets implicitly
>> passed by ref).
>> 
>> So with implicit ref parameters for "ref struct" types you solve the
>> issue of fragmentation and of passing const containers to functions.
>> 
>> The underlying principle is that how to efficiently pass a type to
>> functions should be decided at the type level. You're trying to figure
>> out how it should work for containers, but I think it should apply more
>> broadly to the language as a whole.
>> 
>> But there is one more thing. ;-)
>> 
>> Implicit ref parameters could also solve elegantly the more general
>> problem of passing rvalues by reference if you make them accept rvalues.
>> Only parameters explicitly annotated with "ref" would refuse rvalues,
>> those implicitly passed by ref would accept them.
> 
> Not to seem dismissive, but this sounds quite complicated for what it 
> does. Could we implement it as a library feature? And assuming your 
> motivating argument wasn't as strong, is it needed?

It can't be a library feature because it requires the compiler to 
implicitly add a "ref" to functions parameters when they are of a "ref 
struct" type. That's pretty much all it does: add a flag to struct 
types, implicitly add "ref" to parameters based on that flag.

I'm not sure why you think it's complicated. Perhaps I should just not 
have talked about rvalues: that's a separate benefit you can built on 
top of it by adding one or two lines of code in DMD, but it's a 
separate thing.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/