[SAoC] data structures

monkyyy crazymonkyyy at gmail.com
Sat Sep 12 18:16:01 UTC 2020


I intend to write 6 reasonably-general high-quality data 
structures that's complies with the standards of the std to 
submit it to the std.

Data structure summery(details on the github):
---

1. Ring array: an array with an access pattern that loops back on 
itself rather then overflowing
2. Opinionated list of lists: A array of nullable!T, where null 
is an end of a list.
3. Metadata: like nullable, but adds additional 7 bit int to 
round out the wasted space of nullable, and more flexible in 
usage pattern.
4. Member index arrays: A lighter version of SoA. Given a user 
defined T and a member of T, packs the designated members 
together for better cache usage for searches.
5. Fixed length string: When you want char[n] rather then the 
default char[].
6. Semi-static array: no gc, copy to larger array during overflow 
and custom allocator friendly array abstraction.

-----------

Month 1
----

* Get a dub package up and running.
* Get ring arrays to "feature complete".
* Make a *bodged* a-b fuzzy race testing/benchmarking framework 
that generates markdown test results.
   * Bodged: makeshift, slipshod, not intended to be stable.
* Make prototypes for the other 5 data structures.
* Learn d style and inline documentation system the community 
likes, adding it to ring array

Month 2
---

* Make/find a more robust testing system.
   * testing correctness of specific cases, as opposed to a fuzzer 
and benchmarker.
* Publish a-b test *results* on github inviting the community to 
criticize it in issues.
* Improve 3 more data structures to "feature complete".
   * The flexibility of which data structures is intended. To pace 
myself, or for interdependence, for example I will use metadata 
in opinionated list of list.

Month 3
---

* Improve remaining data structures to "feature complete".
* "Finalize" ring array.
* Respond to community feedback.

Month 4
---

* "Finalize" remaining data structures.
* Submit code to the std review process.

----

https://github.com/crazymonkyyy/datastuctureplayground
I primarily am in the discord.


More information about the Digitalmars-d mailing list