[GSoC] Reference-Counted Data Structures for D

[Les De Ridder]

Hi everyone,

I've started working on my GSoC project, titled Reference-Counted 
Data
Structures for D.

Progress will be reported in this thread, so feel free to discuss 
the project
here.

Introduction
------------

Currently, D’s built-in data structures (arrays and associative 
arrays) and
Phobos collections (e.g. `std.container.rbtree`) rely on garbage 
collection.
This has a number of issues, including the inability to use them 
when compiling
with `-betterC`, GC pauses, and memory usage being 
nondeterministic.

The goal of this project is to implement `@nogc @safe` versions 
of common data
structures through the use of reference counting for memory 
management.
Reference counting is already being used with success by other 
systems
programming languages (such as C++) for the same purpose. With 
recent work by
Eduard Staniloiu on `__RefCount`[1],  an official implementation 
of these
collections can be added to D’s standard runtime.

Note: This project was initially going to be on *persistent* data 
structures.
The ‘persistent’ qualifier was dropped since the addition of 
traditional
reference counted collections will have a greater impact at this 
time.

Main goals
----------

1. Implement the most important collections (e.g. arrays/slices, 
singly/doubly
    linked lists, maps)
2. Better performance than `std.container`
3. Ensure the collections work with `-betterC`

This month
----------

The first month will be spent working on implementing 
arrays/slices
(`rcarray`). This can for a large part be based on earlier work 
done in
`stdx.collections`[2].


[1] https://github.com/dlang/druntime/pull/2608
[2] https://github.com/dlang-stdx/collections