www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.typed_allocator: very very very primitive tracing example

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
For those keeping score at home, I've just updated

https://github.com/andralex/phobos/blob/allocator/std/allocator.d
https://github.com/andralex/phobos/blob/allocator/std/typed_allocator.d

with an extremely rudimentary example of how tracing would work with a 
typed allocator.

The basic idea (factoring out all system-y things such as pausing all 
threads and enumerating all registers, stacks, globals, and 
thread-locals) is:

1. The typed allocator marks all memory as "unused".

2. Scan all pointers either conservatively or not. This is the 
interesting part.

3. Done marking.

For 2, the current approach is to plant a pointer to function during 
allocation. That pointer knows what type had been allocated there and 
knows how to trace objects of that type. Once the indirect call has been 
made (starting from a root), no more indirect calls - scanDirect 
functions get instantiated for all fields appropriately. For each type, 
scanDirect scans all fields that in turn contain indirections.

This is a "pay-as-you-go" scheme in which scanning functions are 
generated (transitively) only for types that are, in fact, allocated on 
that heap.



Andrei
May 04 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/4/14, 9:26 PM, Andrei Alexandrescu wrote:

 For those keeping score at home, I've just updated

 https://github.com/andralex/phobos/blob/allocator/std/allocator.d
 https://github.com/andralex/phobos/blob/allocator/std/typed_allocator.d


Forgot to mention: this latest development seems to suggest that the 
UNTYPED part of the allocator is becoming somewhat feature stable, so 
it's approaching alpha state.

What std.allocator (i.e. the untyped part) needs right now is a few 
"best of" prepackaged allocators that are known to work well and allow 
coders to simply use them as short types or function calls, without 
needing to go through the intricate process of designing 
application-specific allocators.


Andrei
May 04 2014
parent Orvid King via Digitalmars-d <digitalmars-d puremagic.com> writes:
The only thing I could see being an issue is the size of resulting
scanning code, which could probably be mitigated by using a
`bitmap`-ish representation as a key, so that types that have the same
bitmap use the same scanning function. Also, I see a *very* large
number of indirect branching occurring with this design, so you might
as well account for a branch misprediction for each an every object of
a non-final class allocated, due to fields possibly storing classes
derived from the type of the field. This also begs the question, how
do you intend to account for references to objects allocated outside
of the scope of that particular typed allocator, which may, or may
not, have the function pointer for scanning them.

On 5/4/14, Andrei Alexandrescu via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 On 5/4/14, 9:26 PM, Andrei Alexandrescu wrote:

 For those keeping score at home, I've just updated

 https://github.com/andralex/phobos/blob/allocator/std/allocator.d
 https://github.com/andralex/phobos/blob/allocator/std/typed_allocator.d


 Forgot to mention: this latest development seems to suggest that the
 UNTYPED part of the allocator is becoming somewhat feature stable, so
 it's approaching alpha state.

 What std.allocator (i.e. the untyped part) needs right now is a few
 "best of" prepackaged allocators that are known to work well and allow
 coders to simply use them as short types or function calls, without
 needing to go through the intricate process of designing
 application-specific allocators.


 Andrei
May 05 2014