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

On Tuesday, 4 June 2019 at 18:37:38 UTC, Les De Ridder wrote:
> Hi everyone,
>
> I've started working on my GSoC project, titled Reference-Counted Data
> Structures for D.

Great project, good luck!

On Tuesday, 4 June 2019 at 18:37:38 UTC, Les De Ridder wrote:
> Hi everyone,
>
> I've started working on my GSoC project, titled Reference-Counted Data
> Structures for D.

Don't forget that this exists: https://github.com/dlang-community/containers/

You may want to at least copy some of the unit tests.

On Tuesday, 4 June 2019 at 21:10:29 UTC, Brian Schott wrote:
> Don't forget that this exists: https://github.com/dlang-community/containers/
>
> You may want to at least copy some of the unit tests.

Yes, I know about that library.

This project does have somewhat different goals however, mainly that it
targets inclusion in druntime and won't provide a range interface or
support for custom allocators (so it can be used in e.g. druntime
itself). For `rcarray` the goal is to be compatible with built-in
arrays.

Some of the unit tests can indeed be recycled though, and it might also
be interesting to benchmark against, so thanks for the reminder!

On Wednesday, 5 June 2019 at 23:44:42 UTC, Les De Ridder wrote:

> This project does have somewhat different goals however, mainly that it
> targets inclusion in druntime and won't provide a range interface

Why not provide a range interface?

—
/Jacob Carlborg

On Thursday, 6 June 2019 at 09:59:39 UTC, Jacob Carlborg wrote:
> On Wednesday, 5 June 2019 at 23:44:42 UTC, Les De Ridder wrote:
>
>> This project does have somewhat different goals however, mainly that it
>> targets inclusion in druntime and won't provide a range interface
>
> Why not provide a range interface?
>
> —
> /Jacob Carlborg

I'd like to keep the PRs as small as possible, so reviews aren't too
much work and don't slow down progress. Adding a range interface would
add a considerable amount of code that, while trivial, still has to be
properly documented, tested, and reviewed.

It's also not clear where a range interface should go. There is
(currently) no `core.range`, so the range interface would have to be put
in a companion module in Phobos, or it wouldn't be possible to properly
implement and unit test it without moving parts of `std.range` to
druntime.

On 2019-06-06 22:48, Les De Ridder wrote:

> I'd like to keep the PRs as small as possible, so reviews aren't too
> much work and don't slow down progress. Adding a range interface would
> add a considerable amount of code that, while trivial, still has to be
> properly documented, tested, and reviewed.

Fair enough.

> It's also not clear where a range interface should go. 

It would go in the same file as the data structures. Why would it go anywhere else?

> There is
> (currently) no `core.range`, so the range interface would have to be put
> in a companion module in Phobos, or it wouldn't be possible to properly
> implement and unit test it without moving parts of `std.range` to
> druntime.

There's "foreach", which is built-in, and the functions that make up the range API, that is: front, popFront and empty (for an input range).

-- 
/Jacob Carlborg