D data structures

(open letter for the d foundation meeting)

The issue of improving the std data structures has been stagnant for a decade. When I raised the issue every time I’m told that it was for the sake of allocators, but despite this no one I know seems to care if allocators are implemented, and that I’d understand the issue if I wanted to use -betterC. I’m now writing a betterC project and am even more annoyed and still completely indifferent to allocators.

I view data structures as one of maybe 5 important tasks for an std and d has a gaping wound, any suggestion to improve the situation is shut down instantly. Which is just dumb, it's been a decade; and implementing allocators and then agreeing on data structures to include could easily take another. So I’m offering a few proposals of me sitting irritated with this situation for 2 years.

I offer the following proposals to improve the situation:

Admit Fault, Stop the Bleeding

`std.experimental.allocator` went unmerged, whatever the core devs’ reasons for leaving it unmerged, I don’t know and don’t care why, but once progress stopped this should have been seen as a signal to re-open the issue.

In my ideal world, you make the call that allocators aren’t happening, aren’t important, and data structures are long overdue. And would therefore put out a call for any and all code people would give for `std.expertmental.datastuctures` and merge most of it as temp code as you prep for a long-term solution for d3.

I doubt this will be accepted but is here for completeness and clarification of the following compromises.

Static Sized Data Structures

There seems to be confusion around the issue of data structures as part of the GC debates. Allocation only happens for some data structures.

A circular buffer does not need to know if it’s being called on the stack, global scope, malloc’ed by an allocator or new’ed by the standard gc. It is an array with op overloads and is part of many allocator designs. Having a good default circular buffer is unlikely to interface with any allocator API (maybe as part of some growing operation, but that would be an internal detail) and may speed up the implementation of allocators.

So Prospal 2: accept movement on data structures that are statically sized.

Make Data Structures a Planned Major Part of D3

Snar is working on a new allocator API; sure, still don’t care. But maybe Ivy worked and there will be progress; prove it, make a list of data structures that will be part of d3, and get someone the bureaucracy seal of approval to start work with snar’s draft API.

Prove me wrong that it will take 5 to 10 years to implement.

Weaken the Position to Some Ratio of Data Structures Work with Allocators and -BetterC

I’m not convinced that all data structures are used by all platforms. -BetterC implies wasm or embedded or some other constrained environment, it’s highly unlikely that they will use a Python-inspired data structure like DataFrames which makes one-liner database queries. Likewise, d project for a web server on a full PC is unlikely to turn off GC and care about compact bools and picking the exactly right size of int and would rather scale by parallelism.

I expect people will use different data structures based on the environment, so maybe have a rule that half the data structures should be allocator-friendly.