5. Lock-free data structures.

On Wed, Oct 21, 2015 at 09:11:38AM -0400, Andrei Alexandrescu via Digitalmars-d wrote: [...]
> My finance folks also rave about Pandas. I wish I could fork myself to look into it.
[...]

Unfortunately, forking a human process takes 9 months to spawn the new process (slow OS, y'know), and the new process's module constructor takes about 18 or so years to run before it's ready for use. :-D  Also, the specs are ambiguous in some key areas of the semantics, so implementations in practice don't quite manage to replicate the original process exactly.


T

-- 
Chance favours the prepared mind. -- Louis Pasteur

On Wednesday, 21 October 2015 at 15:34:14 UTC, Russel Winder wrote:
> On Wed, 2015-10-21 at 14:06 +0000, Jonathan M Davis via Digitalmars-d wrote:
>> 
> […]
>> > 1. Functional containers.
>> 
>> I fully expect that these have their place, but I honestly have no idea what they would be. When I've used functional languages, I've only ever found these attributes to be a royal pain to deal with, not a benefit. From what I've seen, containers are the sort of thing that almost always always need to be mutable to be of any real benefit. Upon occasion, constructing a container up front and then never tweaking it after that is useful, but that's pretty rare from what I've seen.
>> 
>> The only cases that I can think of where this could be really beneficial would be something like strings, and we're using arrays for those currently (though they are arguably functional containers given that they have immutable elements).
>
> I am confused as to why you would find these functional/persistent data structures to be a problem in functional languages. The whole point of them is they can be easily shared without any locks. In effect each amendment of the structure creates a fork (effectively a copy but without the copy bit) of it. This goes hand in hand with the functional, and especially tail recursive computational model.

My experience with immutable containers is that their performance is trash precisely because you can't mutate them. They end up being copied just to add elements or to change elements. And even if their internals are smart and share data as much as possible (though that starts moving into COW pretty quickly), the efficiency is still worse than having a properly mutable container would be. I'm sure that there are use cases where they would be useful, but I've sure never had one. I've found that functional languages can be great from an algorithmic perspective, but for data structures? Not so much.

And I'm by no means against having data structures like this in Phobos, but I think that having normal, reference containers is far more useful for the common case. Certainly, it's what most programs currently use and what most programmers expect. I'd much prefer that we get a solid set of reference containers working than spend a lot of time worrying about more exotic containers up front. IMHO, they can wait.

We'll see what the future may hold, and I could certainly end up being surprised, but I fully expect that I'll never use any functional containers if they're put into Phobos. They're just too unwieldy and inefficient.

- Jonathan M Davis

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.

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.

Perhaps I'm misreading what you meant though and this is what you intended all along.

> 4. Copy-on-write containers.
>
> These combine the advantages of value and reference containers: you get to think of them as values, yet they're not expensive to copy. Copying only occurs by necessity upon the first attempt to change them.
>
> The disadvantage is implementations get somewhat complicated. Also, they are shunned in C++ because there is no proper support for COW; for example, COW strings have been banned starting with C++11 which is quite the bummer.
>
> Together with Scott Meyers, Walter figured out a way to change D to support COW properly. The language change consists of two attributes.

Nice to have this option. I don't think I'd use it much though.

On 10/21/2015 10:51 AM, Robert burner Schadek wrote:
> On Wednesday, 21 October 2015 at 14:20:23 UTC, Andrei Alexandrescu wrote:
>> Containers will obey subsets of a nomenclature of primitives.
>
> Just to be crystal clear, something like this?
>
> void fun(Container)(ref Container c) if (hasAppend!Container) {
>      // append stuff to c
> }

Even simpler, hasMethod!(Container, "append") -- Andrei

On 10/21/2015 06:25 PM, Jonathan M Davis wrote:
>
> My experience with immutable containers is that their performance is
> trash precisely because you can't mutate them. They end up being copied
> just to add elements or to change elements.

I don't think this is what's being proposed here. Updates are fast.

> And even if their internals
> are smart and share data as much as possible (though that starts moving
> into COW pretty quickly),

COW copies the entire container.

> the efficiency is still worse than having a
> properly mutable container would be.

Not if you need access to older versions. If this is the case, then the "properly" mutable container carries a lot of runtime and memory overhead due to copying. Also, the difference is not very large for good implementations.

> I'm sure that there are use cases
> where they would be useful, but I've sure never had one. I've found that
> functional languages can be great from an algorithmic perspective, but
> for data structures? Not so much.

It's not tied to the language.

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

On 10/21/2015 11:13 AM, Timon Gehr wrote:
> On 10/21/2015 05:08 PM, Timon Gehr wrote:
>> There would be no mutable aliasing.
>
> Here, I mean within the data structure itself. There is nothing wrong with:
>
> class Cell{ int x=0; }
>
> FunSet!Cell a;
> a.insert(new Cell());
> auto b=a;
> foreach(c;a) c.x=1;
> assert(b.x==1);
>
> This is analogous to:
>
> struct SingletonFunSet(T){
>      T element;
> }
>
> auto a=SingletonFunSet!Cell(new Cell());
> auto b=a;
> a.element.x=1;
> assert(b.x==1);
>
> Here, SingletonFunSet!Cell is a value type, but it's constituents might
> not be.

It seems to me that's a departure from traditional persistent data structures. Those have immutable elements; far as I can tell you discuss containers that only have immutable topology. -- Andrei

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.

>
> 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.