www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Yes, you can help std.allocator!

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Following up on Brian's nice offer:

 What's going on with std.allocator? I have a few projects (some on
 Github, some at EMSI) that use it because it seemed like it was on
 its way to being in Phobos. What can I do to help with this?
Things are going well with std.allocator. I broke the code into a package with modules, which makes it quite nice to deal with. Also I just implemented a simple heterogeneous freelist allocator akin to the Kernighan-Ritchie one: http://erdani.com/d/phobos-prerelease/std_experimental_allocator_kernighan_ritchie.html I did so more for demo/historical perspective purposes. I plan to add the part that adds new chunks on a need basis as a separate artifact. Now there _is_ something I could help with. Right now the allocator design works well as a flexible malloc/free implementation, but has no support for tracing-based garbage collection. I am evaluating whether I should add tracing capabilities to std.allocator, or stop here. Tracing would most definitely require new primitives such as embedding some sort of type information and resolving internal pointers. What would really help this evaluation and any other work on garbage collection would be a modularization of the tracing process. I'm envisioning a simple API that separates the system-dependent part of the tracer (stopping all threads, finding the roots in the globals, TLS, and stack) from what the collector is supposed to proceed with the tracing. So I'm thinking e.g. of a range that would iterate through all untyped words on all stacks as void* data. foreach (void* p; GC.traceAllStacks) { ... } Then we'd have typed data in TLS and globals. I guess those would come as ranges of Tuple!(void[], Typeinfo) or something similar. I'm sure I'm glossing over a number of details, so I'd need an expert in the GC workings to help me connect std.allocator with it. Once the GC has a low-level tracing API, I can figure what primitives I need to add to std.allocator to accommodate tracing. Thanks! Andrei
Apr 04 2015
next sibling parent Rikki Cattermole <alphaglosined gmail.com> writes:
On 5/04/2015 3:16 p.m., Andrei Alexandrescu wrote:
 Following up on Brian's nice offer:

 What's going on with std.allocator? I have a few projects (some on
 Github, some at EMSI) that use it because it seemed like it was on
 its way to being in Phobos. What can I do to help with this?
Things are going well with std.allocator. I broke the code into a package with modules, which makes it quite nice to deal with. Also I just implemented a simple heterogeneous freelist allocator akin to the Kernighan-Ritchie one: http://erdani.com/d/phobos-prerelease/std_experimental_allocator_kernighan_ritchie.html I did so more for demo/historical perspective purposes. I plan to add the part that adds new chunks on a need basis as a separate artifact. Now there _is_ something I could help with. Right now the allocator design works well as a flexible malloc/free implementation, but has no support for tracing-based garbage collection. I am evaluating whether I should add tracing capabilities to std.allocator, or stop here. Tracing would most definitely require new primitives such as embedding some sort of type information and resolving internal pointers. What would really help this evaluation and any other work on garbage collection would be a modularization of the tracing process. I'm envisioning a simple API that separates the system-dependent part of the tracer (stopping all threads, finding the roots in the globals, TLS, and stack) from what the collector is supposed to proceed with the tracing. So I'm thinking e.g. of a range that would iterate through all untyped words on all stacks as void* data. foreach (void* p; GC.traceAllStacks) { ... } Then we'd have typed data in TLS and globals. I guess those would come as ranges of Tuple!(void[], Typeinfo) or something similar. I'm sure I'm glossing over a number of details, so I'd need an expert in the GC workings to help me connect std.allocator with it. Once the GC has a low-level tracing API, I can figure what primitives I need to add to std.allocator to accommodate tracing. Thanks! Andrei
Moving the GC out of druntime, might be an interesting proposition. Pro: - D is no longer "garbage collected" - Easier to swap implementations Cons: - Technically none for the embedded guys - Quite a lot of work to get the current GC refactored into new design - Good bit of changes to phobos/druntime But this would most likely go a long way towards the goal of nogc I think.
Apr 04 2015
prev sibling next sibling parent reply "Kagamin" <spam here.lot> writes:
On Sunday, 5 April 2015 at 03:16:32 UTC, Andrei Alexandrescu 
wrote:
 Things are going well with std.allocator. I broke the code into 
 a package with modules, which makes it quite nice to deal with. 
 Also I just implemented a simple heterogeneous freelist 
 allocator akin to the Kernighan-Ritchie one:

 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_kernighan_ritchie.html
Guess, it's a matter of time until we get something like yashwantraoShambshioSubramaniamSort in phobos.
Apr 05 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/5/15 4:50 AM, Kagamin wrote:
 On Sunday, 5 April 2015 at 03:16:32 UTC, Andrei Alexandrescu wrote:
 Things are going well with std.allocator. I broke the code into a
 package with modules, which makes it quite nice to deal with. Also I
 just implemented a simple heterogeneous freelist allocator akin to the
 Kernighan-Ritchie one:

 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_kernighan_ritchie.html
Guess, it's a matter of time until we get something like yashwantraoShambshioSubramaniamSort in phobos.
I was thinking of a variety of descriptive names along the lines of HeterogeneousFreeList of VarLengthSortedFreeList etc. but after a little investigation it seems the K-R implementation is enough of a classic to be a good moniker. -- Andrei
Apr 05 2015
prev sibling next sibling parent "Laeeth Isharc" <laeeth nospamlaeeth.com> writes:
On Sunday, 5 April 2015 at 03:16:32 UTC, Andrei Alexandrescu 
wrote:
 Things are going well with std.allocator. I broke the code into 
 a package with modules, which makes it quite nice to deal with. 
 Also I just implemented a simple heterogeneous freelist 
 allocator akin to the Kernighan-Ritchie one:
...
 I'm envisioning a simple API that separates the 
 system-dependent part of the tracer (stopping all threads, 
 finding the roots in the globals, TLS, and stack) from what the 
 collector is supposed to proceed with the tracing.

 So I'm thinking e.g. of a range that would iterate through all 
 untyped words on all stacks as void* data.

 foreach (void* p; GC.traceAllStacks)
 {
     ...
 }

 Then we'd have typed data in TLS and globals. I guess those 
 would come as ranges of Tuple!(void[], Typeinfo) or something 
 similar
I cannot think of much I can do to help - I just started reading the GC code on the ferry over - but this is very cool. Intrinsically, and because it addresses a perception that is an impediment to adoption (even though I reckon people make a lazy mental association of GC with problems associated with Java in its early days when it actually might not be a real barrier for many of them with D today in their actual use case - just like the spurious 'D has two standard libraries' meme). Only one suggestion - I know there are some GC benchmarks in Phobos/Druntime. Might it be an idea to relate these to some of the standard benchmarks people use to evaluate GC in other languages, so people have clarity on the tradeoffs. We don't need to make these salient until the time is right.
Apr 05 2015
prev sibling parent Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 04/05/2015 05:16 AM, Andrei Alexandrescu wrote:
 Right now the allocator design works well as a flexible malloc/free
 implementation, but has no support for tracing-based garbage collection.
 
 I am evaluating whether I should add tracing capabilities to
 std.allocator, or stop here. Tracing would most definitely require new
 primitives such as embedding some sort of type information and resolving
 internal pointers.
Just to make sure we're on the same page here. You're talking about implementing the GC in terms of std.allocator, not about making std.allocator GCable, right? This would be fairly interesting for us too experiment with, as we could easily try out different allocator architectures. But then again the GC needs to use highly optimized data structures to lookup metadata, we'll likely only choose a single allocator architecture, and we already know a few good ones https://code.dawg.eu/talks/2015-03-20-garbage_collection_dmeetup/#9. So while the heap layer idea is interesting and would facilitate to try different allocators, it's a substantial amount of work, to add the marking and metadata to std.allocator. We already started to modularize the GC a little and can try out different architectures by hand, so I don't think it's worth the effort.
 What would really help this evaluation and any other work on garbage
 collection would be a modularization of the tracing process.
It's already pretty much like that. Scanning is not a range but callback based and misses GC.addRoots and GC.addRanges, wouldn't be too much work to add that. https://github.com/D-Programming-Language/druntime/blob/7877f65a6baf53b0c53c1babf9a0f0a5d1893940/src/gc/gc.d#L2205 There is also no TypeInfo yet. -Martin
Apr 11 2015