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