www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [GSoC] Reference-Counted Data Structures for D

reply Les De Ridder <les lesderid.net> writes:
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
Jun 04
next sibling parent Stefanos Baziotis <sdi1600105 di.uoa.gr> writes:
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!
Jun 04
prev sibling parent reply Brian Schott <briancschott gmail.com> writes:
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.
Jun 04
parent reply Les De Ridder <les lesderid.net> writes:
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!
Jun 05
parent reply Jacob Carlborg <doob me.com> writes:
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
Jun 06
parent reply Les De Ridder <les lesderid.net> writes:
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.
Jun 06
parent Jacob Carlborg <doob me.com> writes:
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
Jun 07