I want to start working on a container library. Interestingly enough, I don't think we have what we need on that front.

I'll describe here what are the design I intend to go for, and the rationales for it, but before, there is an unsolved problem that I don't know how to work around that is somewhat of a blocker. If one of you guys have an idea how to solve it, I'm taking. If I'm being honest, this is probably the most important problem that need to be solved for D right now. That problem is turtling down type qualifiers.

For instance, if we have a Vector!T, then we want it to convert to a Vector!(const T) and we want const(Vector!T) == const(Vector!(const T)), all of it implicitly. Same goes for other qualifiers.

To put it bluntly, I have no idea how to achieve this. And I don't think we'll have a good set of collection before this is sorted out.

Now onto the design:

• Value types. It is very easy to turn a value into a reference type, not so much the other way around. reference type also come with a bag of edges cases, like the collection being null vs empty, that cause confusion and problems in practice.
• COW. Value type collection can be very expensive to work with if the eagerly copy everything. On the other hand, COW ensures copies are cheap. There are also very common use case that are well served by COW collections, for instance, when one wants value types for collection that are infrequently changes - but you don't know or can't prove that they won't.
• Small collection features. As every engineer, but no mathematician will tell you, is that most numbers are small. It is also true of collection sizes. In order to speed things up for collection that are expected to be small, being able to specify Vector!(T, 8) to reserve 8 slots for elements, in the base collection, and only allocate on heap if the collection size grows past this. LLVM has a collection library doing so and it is the most useful thing in the world (see https://www.youtube.com/watch?v=vElZc6zSIXM for more details).
• Not expose much of its internals. This like iterators being raw pointers (or the result of using the in operator) for instance, impose constraint on the internal that almost always end up costing a ton of perf as new techniques are discovered (recent exemples include open addressing with SSE probing for instance). All of this needs to be wrapped.

I have a good idea how to solve all these problems. I have no idea how to solve the type qualifier one. I need help.

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

As far as I know, the best approach anyone's come up with for this is the headMutable pattern described in this blog post:

https://dlang.org/blog/2020/06/25/a-pattern-for-head-mutable-structures/

This gives us:

• Vector!T -> const(Vector!T) (built in)
• const(Vector!T) -> Vector!(const(T)) (via headMutable)
• Vector!(const(T)) -> const(Vector!(const(T))) (built in)
• const(Vector!(const(T))) -> Vector!(const(T)) (via headMutable)

The only conversion missing is

• const(Vector!(const(T))) -> const(Vector!T)

...which would have to be implemented as another method (tailUnqual?).

Of course many of these conversions are explicit, not implicit, but I don't think there's any way around that given D's current capabilities. The only user-defined implicit conversions in D are via inheritance and alias this, and neither can do what we need here.

This sounds similar to Clojure's immutable data structures. I agree these would be a good thing to have, although I think traditional mutable containers should also exist alongside them.

On Tuesday, 31 August 2021 at 18:11:04 UTC, Paul Backus wrote:

class RefContainer {
    Container c;
}

Here you go :)

There is obviously some boilerplate missing, but I'm sure you get the idea. One nice bonus is that you get a practically free clone method, that will only do so when you actually mutate things.

You'll note that in practice, you don't need to clone the container every time you write, you need to keep a ref count and only clone when the number of references to the container is greater than 1.

Lastly, my experience tells me that container being traditionally references was a mistakes. I have many scars to show for it.

Thank you for the Head mutable article. I'll dig into this and see if I can make it work.

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

Declare opAssign on Vector!(const T) that takes const Vector!T, then the assignment will compile.

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

Converting from Vector!T to Vector!(const T) should be possible through copy constructors and opAssign overloads, same for const(Vector!T) to const(Vector!(const T)).

having something like this should suffice for initialization for example:

static if (is(T == const)) {
  this(Vector!(Unqual!T) mutable) {
    this.array = mutable.array;  // Or you can do a complete copy.
  }

  static if (is(this == const)) {
    // ... well case for const T and const this
  }
}

Would be nice if even as value types different implementations say of a list would follow a well defined interface, same for other type of collections.

Imho, there is no problem here. null pointer to collection class means no collection present, while empty collection is just an empty collection. There should not be any conflation between these notions, in general, and could be made clear in the documentation.

It would be nice if the collection api would have rich and consistent api for working with it. I.e have common interfaces for lists, sets, queues and etc. that value and reference type collections implement. And that is not only about the list of methods they implement, but also the behavior they exhibit.

Java for example has a good api for collections, from which your collection library can take inspiration, and ofc with D twist of features.

I also tried poking around with a collection implementation, though not value types but ref types, and found it being problematic to implement, due to limitations of how safety annotations work.

You basically cannot force the interface being @safe/trusted/system based on element it contains without doing extensive compile time introspection...
So if you plan to add ref wrappers this one should be also resolved somehow to have a @safe lib, otherwise I'm afraid class wrappers will be only for @system code.

Best regards,
Alexandru.

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

Good initiative. I'd be happy to assist.

I have a bunch of value-type containers (struct + dup) lying around here being @safe pure nothrow @nogc whenever possible. It supports significantly more members than emsi-containers at least. It also tries to be dip-1000 compliant but there are like bugs lurking here and there.

Here's a likely incomplete list of the containers.

Feel free to give me a ping if you need any guidance.

You might find nxt.trie of special interest. Beware of its size, though.

There's also a benchmark at

benchmarks/containers

you can try out via either

benchmarks/containers/test-dmd-debug

or

benchmarks/containers/test-ldc-release

. It benchmarks a subset of the containers together with D arrays and AAs.

Somewhat related, I've also experimented with a run-time variant of Rust's ownership and borrowing rules at borrown.d.

Until later,
Per

On Tuesday, 31 August 2021 at 21:36:25 UTC, Per Nordlöw wrote:

benchmarks/containers/test-dmd-debug

benchmarks/containers/test-ldc-release

Should be

./test-dmd-debug

or

./test-ldc-release

under benchmarks/containers.

On Tuesday, 31 August 2021 at 18:24:54 UTC, deadalnix wrote:

So I read it and played with the concept a bit. If I'm honest, it fall very much short of where it needs to be.

It is inconvenient - but workable - when using things by value, however, the shortcoming become very apparent when it is used as a reference, or within a more complex type construction.

This similarly go for other proposed solution in the thread.

I don't think we'll ever have a set of container that are as good as they should without this being nailed down.

On Tuesday, 31 August 2021 at 21:36:25 UTC, Per Nordlöw wrote:

There is a ton of good work in there!

Do you agree with the direction explicated?

I expected to focus on Vector/Set/Map initially. This should serve most use case in practice.