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 2019
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 2019
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 2019
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 2019
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 2019
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 2019
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 2019