Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
June 04, 2019 [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
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 |
June 04, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Les De Ridder | 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!
|
June 04, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Les De Ridder | 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. |
June 05, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Brian Schott | 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!
|
June 06, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Les De Ridder | 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
|
June 06, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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.
|
June 07, 2019 Re: [GSoC] Reference-Counted Data Structures for D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Les De Ridder | 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 |
Copyright © 1999-2021 by the D Language Foundation