Containers

[Steven Schveighoffer]

On 8/31/21 1:21 PM, deadalnix wrote:
> 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.

This is the crux of the tail-const problem. The language allows 
tail-const for only 2 types, T[] and T*. Everything else is fully const 
or fully mutable.

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

I had an idea a long time ago, but ashamedly never brought it to 
fruition. But long story short, I think we need a way to specify "tail" 
for modifiers, and allow implicitly casting the head. Then you'd have 
`tailconst(Vector!int)`, and you are good. I actually had a decent 
syntax for it, but I'm not sure it would fly anyway.

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

Null vs. empty isn't a problem for non-class reference types. Of course, 
without tail-const, you are kinda screwed.

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

I don't agree that COW is a good idea for generic collections. IIRC, C++ 
tried this with std::string and it was a disaster.

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

I think this is a great idea.

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

Feel free to copy any of my ideas from dcollections for this. See 
https://github.com/schveiguy/dcollections/blob/master/concepts.txt

Also note that Dcollections were strictly reference types, but had 
struct-based implementations (which could actually be swapped out with a 
different implementation if anyone had ever developed any). It came in 
handy in some cases, like the hash bucket collision linked list was just 
the implementation for the standard linked list.

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

Feel free to ping, maybe on slack. We can discuss the tail-const problem.

-Steve