On Wednesday, 21 October 2015 at 18:05:07 UTC, Jonathan M Davis wrote:
> On Wednesday, 21 October 2015 at 16:36:46 UTC, Brad Anderson wrote:
>> On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
>> [snip]
>>> 2. Reference containers.
>>>
>>> These have classic reference semantics (à la Java). Internally, they may be implemented either as class objects or as reference counted structs.
>>>
>>> They're by default mutable. Qualifiers should apply to them gracefully.
>>>
>>> 3. Eager value containers.
>>>
>>> These are STL-style. Somewhat surprisingly I think these are the worst of the pack; they expensively duplicate at the drop of a hat and need to be carefully passed around by reference lest performance silently drops. Nevertheless, when used as members inside other data structures value semantics might be the appropriate choice. Also, thinking of them as values often makes code simpler.
>>>
>>> By default eager value containers are mutable. They should support immutable and const meaningfully.
>>
>> Having both reference and value semantics for containers would be great. I don't understand why reference semantics would be implemented by the container themselves though. Why not a general purpose RC! (or RefCounted! if the current design is deemed sufficient) that can apply to anything, including containers? Then you'd only need to implement the value semantic containers (and maybe throw in some RC version aliases to promote the use of the RC versions so the option isn't overlooked). It seems kind of crazy that anything in D that wants to be reference counted would need to implement the logic themselves.
>>
>> If there are performance advantages (I haven't thought of any but perhaps there are) to bake the RC right into the container it might also be possible to use DbI take advantage of it in RC! when appropriate.
>>
>> It just seems so wrong to implement reference counting dozens of times independently, especially when that means implementing all the containers twice too.
>
> If we had value type containers and reference type containers, I would assume that they would at least share implementation, and maybe the reference types would just be wrappers around the value types. However, I completely fail to understand why you'd ever want a container that was a value type.

Well they are more efficient when used correctly (no inc/decs). Using them correctly does take some additional knowledge and consideration though. C++11 did take care of a whole class of implicit copying and RVO has long taken care of another class of them. I don't think it happens (in C++) quite as often as you are making it out to be (at least in my experience) but I'll admit I have had a bug or two caused by modifying a copy when I thought I was changing a reference. I could just as easily have bugs caused by modifying a reference when I thought I was modifying a copy though. Either approach comes with its own considerations.

> In my experience, it's very error-prone and adds no value.

Unless we end up with compiler assisted inc/dec elision they are always going to be faster. Perhaps marginally faster but still faster and the realtime guys are always going to demand the fastest option.

> It just makes it too easy to accidentally copy a container, and it can be pretty easy to have an iterator, range, etc. referring to a container that's already been destroyed (similar to having a dynamic array referring to a static array that's left scope).

Having the ranges of a container keep the reference count would make the speed advantage of the value types even more of a factor. That might actually change the performance advantage away from being just subtle to being strong. We'd need to benchmark to say for sure, of course.

Just a sidenote regarding iterator invalidation: C++, when following the new C++ Core Guidelines, is actually able to do static analysis of iterators for memory safety without ref count overhead. Herb Sutter showed a preview version of MSVC doing it during his keynote this month at CppCon[1]. It blew me away that they were about to do that with C++.

> As long as the containers have a dup method (or whatever we call it) so that they can be copied when you do want to copy them, I would think that that was more than enough. What do you get with a value type container that you consider better than a reference type? It's not like it lives on the stack as a value type. Most of the container's guts are on the heap regardless.
>
> - Jonathan M Davis

All that said, I agree with you that the implicit copying isn't really all that desirable. Perhaps there is a better way. What if instead of value semantics we had unique containers (akin to std.typecons.Unique or unique_ptr in C++) and required people to always state whether it was a copy or move? That takes care of the error prone implicit copying while retaining the performance characteristics.

1. https://www.youtube.com/watch?v=hEx5DNLWGgA

On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
> My experience with immutable containers is that their performance is
> trash precisely because you can't mutate them.

That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei

On 10/21/2015 12:34 PM, Ice Cream Man wrote:
> On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M Davis wrote:
>> They're just too unwieldy and inefficient.
>>
>> - Jonathan M Davis
>
> Only if you don't know how to use them. They are very wieldy, efficient
> AND safe, if you do know how to swing the ax. Its all about learning to
> work with them.

Yep, and part of learning is knowing when they shouldn't be used. -- Andrei

On 10/21/2015 12:36 PM, Brad Anderson wrote:
> I don't understand why reference semantics would be implemented by the
> container themselves though. Why not a general purpose RC! (or
> RefCounted! if the current design is deemed sufficient) that can apply
> to anything, including containers?

Two reasons:

1. A generic RC wrapper cannot be made @safe (or at least I don't know how).

2. A container designed for RC can make advantageous layout decisions.


Andrei

On 10/21/2015 01:42 PM, Ulrich Kuettler wrote:
> On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
>> I'm finally getting the cycles to get to thinking about Design by
>> Introspection containers. First off, there are several general
>> categories of containers. I think D should support all properly. One
>> question is which we go for in the standard library.
>>
>> 1. Functional containers.
>
> Very much in favor of functional (or persistent) containers. Immutable.
> Value semantics.
>
> This might take some getting used to, but if properly designed these
> containers would be killer for D. A dream come true.

I agree they're cool.

>> These are immutable; once created, neither their topology nor their
>> elements may be observably changed. Manipulating a container entails
>> creating an entire new container, often based on an existing container
>> (e.g. append takes a container and an element and creates a whole new
>> container).
>>
>> Internally, functional containers take advantage of common
>> substructure and immutability to share actual data. The classic
>> resource for defining and implementing functional containers is
>> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
>>
>>
>
> An insanely beautiful example is clojure's PersistantVector. AFAIK it
> made its way into Scala, too.

Far as I understand from http://hypirion.com/musings/understanding-persistent-vector-pt-1, it's that tree thing with carefully chosen slot sizes for cache friendliness?


Andrei

On Wednesday, 21 October 2015 at 18:48:18 UTC, Brad Anderson wrote:
> All that said, I agree with you that the implicit copying isn't really all that desirable. Perhaps there is a better way. What if instead of value semantics we had unique containers (akin to std.typecons.Unique or unique_ptr in C++) and required people to always state whether it was a copy or move? That takes care of the error prone implicit copying while retaining the performance characteristics.

Well, we could always have a wrapper for reference type containers that turns them into a value type, though I'm not sure that that really does much in terms of the efficiency you were talking about. But it could means that you'd end up passing around a pointer to that rather than the container itself, in which case, maybe that solves the problem for those who don't want a container to be managed by the GC and don't want it to be ref-counted when passing it around? I don't know.

Even if we're talking about a reference type container that's just straight up ref-counted or managed by the GC, there are still ways to pass around pointers or pseudo pointers to it which don't involve ref-counting if that's the real concern. Though honestly, I'd be concerned if a container was being passed around so much that ref-counting was a concern. A range would be better in most cases - but you really wouldn't want to be passing around the container as a value type in either case, because that would just copy it. So, if ref-counting is the concern, I wouldn't think that it would be all that hard for someone who cares to pass around something else which referred to the container and wasn't ref-counted.

- Jonathan M Davis

On Wednesday, 21 October 2015 at 18:50:05 UTC, Andrei Alexandrescu wrote:
> On 10/21/2015 12:34 PM, Ice Cream Man wrote:
>> On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M Davis wrote:
>>> They're just too unwieldy and inefficient.
>>>
>>> - Jonathan M Davis
>>
>> Only if you don't know how to use them. They are very wieldy, efficient
>> AND safe, if you do know how to swing the ax. Its all about learning to
>> work with them.
>
> Yep, and part of learning is knowing when they shouldn't be used. -- Andrei

I definitely won't disagree with that.

On 10/21/2015 07:24 PM, Andrei Alexandrescu wrote:
> On 10/21/2015 11:08 AM, Timon Gehr wrote:
>> Exactly. There would be no mutable aliasing. This way, the persistent
>> data type can behave like a mutable value type, such as a COW or eager
>> copy variant, but with nicer/different performance characteristics. It
>> would be great if exchanging different implementation strategies for
>> value semantics will be as seamless as possible. (If the initially
>> chosen strategy turns out to be wrong, this makes the fix easy.) Of
>> course, the implementation of the persistent data structure will be in
>> terms of non-mutating and possibly O(1)-COW operations only.
>
> Makes sense. Now that we got to talk - did you submit the bugs you found
> with DIP25? -- Andrei
>

Yup:

https://issues.dlang.org/buglist.cgi?email1=timon&emailreporter1=1&emailtype1=substring&list_id=204001&query_format=advanced&resolution=---&short_desc=DIP25&short_desc_type=allwordssubstr

On Wednesday, 21 October 2015 at 19:07:50 UTC, Jonathan M Davis wrote:
> On Wednesday, 21 October 2015 at 18:48:18 UTC, Brad Anderson wrote:
>> All that said, I agree with you that the implicit copying isn't really all that desirable. Perhaps there is a better way. What if instead of value semantics we had unique containers (akin to std.typecons.Unique or unique_ptr in C++) and required people to always state whether it was a copy or move? That takes care of the error prone implicit copying while retaining the performance characteristics.
>
> Well, we could always have a wrapper for reference type containers that turns them into a value type,

ugh...that sounds horrible.

On 10/21/2015 02:05 PM, Jonathan M Davis wrote:
> If we had value type containers and reference type containers, I would
> assume that they would at least share implementation, and maybe the
> reference types would just be wrappers around the value types.

Well, I thought the same. I was surprised.

> However,
> I completely fail to understand why you'd ever want a container that was
> a value type.

Sometimes you want a value container as a member of a struct which in turn is a value type.


Andrei