Containers

[max haughton]

On Tuesday, 31 August 2021 at 17:21:02 UTC, 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.
>
> 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.

It's good that you are doing this Amaury, thanks.

We need better containers to compete with other languages. On top 
of that, there are patterns that other languages cannot do. One 
thing that comes to mind is how D is one of not many languages 
(languages with macros or similar probably can), that can easily 
allow one to write containers which lie about their layout. The 
most profitable example of that I can think of is automatically 
switching arrays of POD types to be a struct of arrays 
internally. This transformation makes random access to elements 
slower, however (say) loops where access to a subset of the 
elements dominates then this is much faster due to improved cache 
efficiency.