www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D's New GC and Object Allocation Pools

reply "Maxime Chevalier-Boisvert" <maximechevalierb gmail.com> writes:
Hello,

I was wondering if there have been updates regarding Andrei's 
announcement that he would rewrite the D garbage collector. Is 
there any kind of timeline for when a new version of the GC can 
be expected?

I also wanted to ask if there was an implementation of an object 
pool in the standard library. If not, I'm wondering what the best 
way to implement this is. Is there any way to overload new and 
destroy?

I was thinking of using the templated emplace operator from 
std.conv to allocate class objects into a large flat array, and 
to derive pool-allocated classes from a PoolObject base class. 
This base class would contain linked list pointers to implement a 
free list, as well as templated static methods to allocate and 
free the objects. Any advice welcome.
Oct 25 2014
next sibling parent reply "Mike" <none none.com> writes:
On Sunday, 26 October 2014 at 03:37:47 UTC, Maxime 
Chevalier-Boisvert wrote:

 I also wanted to ask if there was an implementation of an 
 object pool in the standard library. If not, I'm wondering what 
 the best way to implement this is. Is there any way to overload 
 new and destroy?


I'm not an authority on the subject, but I believe all you need 
to do is provide alternate implementations for _d_newclass[1] and 
destroy[2].  I experimented with this a little bit about a year 
ago, and it worked well for me.  I modified druntime for my 
experiments, but there may be a way to link in your 
implementations instead of the defaults at link time, thus giving 
you an "override" effect.


 I was thinking of using the templated emplace operator from 
 std.conv to allocate class objects into a large flat array, and 
 to derive pool-allocated classes from a PoolObject base class. 
 This base class would contain linked list pointers to implement 
 a free list, as well as templated static methods to allocate 
 and free the objects. Any advice welcome.


If you haven't already, check out the Memory Management article 
on the D Wiki [3].  It's a nice article that was written some 
time ago by an unknown author and migrated to the wiki last year 
to help keep it maintained.  I particularly like Explicit Class 
Allocation[4], Mark/Release[5], and Free Lists[6] as alternatives.

Mike

[1] - 
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/lifetime.d#L60
[2] - 
https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2379
[3] - http://wiki.dlang.org/Memory_Management
[4] - 
http://wiki.dlang.org/Memory_Management#Explicit_Class_Instance_Allocation
[5] - http://wiki.dlang.org/Memory_Management#Mark.2FRelease
[6] - http://wiki.dlang.org/Memory_Management#Free_Lists
Oct 25 2014
parent reply "Mike" <none none.com> writes:
On Sunday, 26 October 2014 at 04:22:29 UTC, Mike wrote:

 but there may be a way to link in your implementations instead 
 of the defaults at link time, thus giving you an "override" 
 effect.


The technique I was thinking of here is the --wrap option in the 
ld linker [1] (See the bottom of the page).  I use this in my 
microcontroller programming to override malloc and friends for 
devices that have discontinuous memory and no MMU.

I tried this on my Linux desktop, and while everything compiled 
and linked without errors, it resulted in a segmentation fault at 
runtime.  But where I have failed, others may succeed.  I tested 
with LDC and GDC, but not DMD.

Mike

[1] 
http://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_node/ld_3.html
Oct 26 2014
parent reply "Mike" <none none.com> writes:
On Sunday, 26 October 2014 at 07:08:21 UTC, Mike wrote:


 I tried this on my Linux desktop, and while everything compiled 
 and linked without errors, it resulted in a segmentation fault 
 at runtime.  But where I have failed, others may succeed.  I 
 tested with LDC and GDC, but not DMD.


It does work, but for some reason if I replace the printf 
statement below with D's writeln, I get a segmentation fault.  I 
don't know why.  Anywhere here's a trivial example to illustrate 
the idea.

module main;

import std.stdio;
import core.stdc.stdio;

extern (C) Object __wrap__d_newclass(const ClassInfo ci)
{
     printf("You haven't provided any custom allocation yet!\n");
     while(true) {}
     return null;
}

void main(string[] args)
{

}

Compile with:
gdc -Wl,-wrap,_d_newclass main.d

You'll see it output the string before it even reaches main 
because the runtime initialization seems to allocate a few 
things.  But, you get the idea. destroy is just a template, 
however, so it will need a different method.

Mike
Oct 26 2014
next sibling parent Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 26 Oct 2014 08:05, "Mike via Digitalmars-d" <digitalmars-d puremagic.com>
wrote:

 On Sunday, 26 October 2014 at 07:08:21 UTC, Mike wrote:


 I tried this on my Linux desktop, and while everything compiled and




linked without errors, it resulted in a segmentation fault at runtime.  But
where I have failed, others may succeed.  I tested with LDC and GDC, but
not DMD.

 It does work, but for some reason if I replace the printf statement below


with D's writeln, I get a segmentation fault.  I don't know why.  Anywhere
here's a trivial example to illustrate the idea.


The std.stdio module has a shared static this which initialises the File
wrapper around C's stdin, stdout, and stderr.  I would first assume that it
segv's because the wrapper or internal pointer is null.

Iain.



 Oct 26 2014



prev sibling  parent reply "Maxime Chevalier-Boisvert" <maximechevalierb gmail.com>  writes:


What I'm trying to do is have some specific classes be 
pool-allocated though, not completely circumvent the GC.

On Sunday, 26 October 2014 at 08:02:25 UTC, Mike wrote:

 On Sunday, 26 October 2014 at 07:08:21 UTC, Mike wrote:


 I tried this on my Linux desktop, and while everything 
 compiled and linked without errors, it resulted in a 
 segmentation fault at runtime.  But where I have failed, 
 others may succeed.  I tested with LDC and GDC, but not DMD.


 It does work, but for some reason if I replace the printf 
 statement below with D's writeln, I get a segmentation fault.  
 I don't know why.  Anywhere here's a trivial example to 
 illustrate the idea.

 module main;

 import std.stdio;
 import core.stdc.stdio;

 extern (C) Object __wrap__d_newclass(const ClassInfo ci)
 {
     printf("You haven't provided any custom allocation yet!\n");
     while(true) {}
     return null;
 }

 void main(string[] args)
 {

 }

 Compile with:
 gdc -Wl,-wrap,_d_newclass main.d

 You'll see it output the string before it even reaches main 
 because the runtime initialization seems to allocate a few 
 things.  But, you get the idea. destroy is just a template, 
 however, so it will need a different method.

 Mike





 Oct 26 2014



  parent reply "Mike" <none none.com>  writes:


On Sunday, 26 October 2014 at 14:13:25 UTC, Maxime 
Chevalier-Boisvert wrote:

 What I'm trying to do is have some specific classes be 
 pool-allocated though, not completely circumvent the GC.


The method I proposed just overrides `new` (i.e. _d_newclass).  
What goes inside of `new` is up to you, including allocating from 
GC memory by calling the default via `__real__d_newclass` (The 
linker takes care of translating the symbol names). And since you 
have a `ClassInfo` object you can selectively choose which types 
are allocated from a pool, and which are allocated by the GC.

extern (C) Object __real__d_newclass(const ClassInfo ci)

extern (C) Object __wrap__d_newclass(const ClassInfo ci)
{
     if (ci.ClassName == "MyPoolAllocatedClass")
     {
         return allocateFromPool(ci);
     }
     else
     {
         retun __real__d_newclass(ci);
     }
}

This method is somewhat hackish, but I think it's the only way to 
override `new`.  Language support for this kind of thing would be 
nice. ` weak` attribute[1] perhaps, or `virtual`/`final` module 
methods anyone? `final` by default please. :)

Mike

[1] - 
https://gcc.gnu.org/onlinedocs/gcc-4.9.1/gcc/Function-Attributes.html#Function-Attributes



 Oct 26 2014



  parent  "Mike" <none none.com>  writes:


On Sunday, 26 October 2014 at 23:20:21 UTC, Mike wrote:

 Language support for this kind of thing would be nice. ` weak` 
 attribute[1] perhaps, or `virtual`/`final` module methods 
 anyone? `final` by default please. :)

 [1] - 
 https://gcc.gnu.org/onlinedocs/gcc-4.9.1/gcc/Function-Attributes.html#Function-Attributes


This is turning into a fun little exploration.  After reading 
this issue [1], I discovered that DMD already compiles all the 
runtime hooks as weak references, so you only need to declare a 
new `_d_newclass` implementation anywhere in your source code to 
override `new`.

version(DigitalMars)
{
     extern (C) Object _d_newclass(const ClassInfo ci)
     {
         // add your own `new` implementation here
     }
}

void main(string[] args)
{ }

Compile with:
dmd test.d

No special compiler/linker flags or symbol names. Cool!

LDC has support for decorating functions with LLVM attributes [2] 
that could potentially include creating `weak` symbols, but LDC 
will have to decorate `_d_newclass` this way in druntime before 
overriding with this technique will be possible.

GDC also has infrastructure for supporting such attributes [3], 
but the `weak` attribute will have to be added to the list, and 
decorations added to `_d_newclass` in the same way.

Maybe I'll submit some pull requests and see how they're received.

I still don't know how to call the default implementation, using 
this technique, without copying the source code from druntime.  
That's not a deal-breaker, but it stinks.

The only way I was able to override `destroy` was to copy the 
entire object.di from druntime to my project folder and modify 
the code there.  That also stinks.

This little skirmish has opened up a few possibilities for my 
work.  Very interesting.

Mike

[1] - https://github.com/ldc-developers/ldc/issues/405
[2] - 
https://github.com/redstar/ldc/commit/69f231f48f355b6399d67950f057bea72f0a64c3
[3] - http://wiki.dlang.org/GDC/Using_GDC#Attributes



 Oct 26 2014



prev sibling next sibling parent  "Kyoji Klyden" <trampzy yahoo.com>  writes:


On Sunday, 26 October 2014 at 03:37:47 UTC, Maxime
Chevalier-Boisvert wrote:

 Hello,

 I was wondering if there have been updates regarding Andrei's 
 announcement that he would rewrite the D garbage collector. Is 
 there any kind of timeline for when a new version of the GC can 
 be expected?

 I also wanted to ask if there was an implementation of an 
 object pool in the standard library. If not, I'm wondering what 
 the best way to implement this is. Is there any way to overload 
 new and destroy?

 I was thinking of using the templated emplace operator from 
 std.conv to allocate class objects into a large flat array, and 
 to derive pool-allocated classes from a PoolObject base class. 
 This base class would contain linked list pointers to implement 
 a free list, as well as templated static methods to allocate 
 and free the objects. Any advice welcome.


Regarding the GC, the last I heard Andrei didn't have it at the
top of his to do list. He seems to be putting most of his effort
right now into completing the C++ integration. However, work on
the GC is still in high demand it would seem.

(I don't have any helpful answers for your other questions,
though.. sry!)



 Oct 25 2014



prev sibling next sibling parent reply "Damian" <damianday hotmail.co.uk>  writes:


On Sunday, 26 October 2014 at 03:37:47 UTC, Maxime 
Chevalier-Boisvert wrote:

 Hello,

 I was wondering if there have been updates regarding Andrei's 
 announcement that he would rewrite the D garbage collector. Is 
 there any kind of timeline for when a new version of the GC can 
 be expected?

 I also wanted to ask if there was an implementation of an 
 object pool in the standard library. If not, I'm wondering what 
 the best way to implement this is. Is there any way to overload 
 new and destroy?

 I was thinking of using the templated emplace operator from 
 std.conv to allocate class objects into a large flat array, and 
 to derive pool-allocated classes from a PoolObject base class. 
 This base class would contain linked list pointers to implement 
 a free list, as well as templated static methods to allocate 
 and free the objects. Any advice welcome.


For your object pool, why not just create functions, alloc and 
free, instead of trying to override them - something like below

version (USE_GC)
{
   import core.memory;
}
else
{
   import core.stdc.stdlib: malloc, free;
}

struct MemPool
{
   void* alloc(size_t size, bool usePool = true) nothrow
   {
     version (USE_GC) return GC.malloc(size);
     else malloc(size);
   }

   void Free(void* p) nothrow
   {
     version (USE_GC) GC.free(p);
     else free(p);
   }
}



 Oct 26 2014



  parent reply "Maxime Chevalier-Boisvert" <maximechevalierb gmail.com>  writes:


I'll do that if I have to, but it's cleaner with an override of 
new as it makes it impossible to mistakenly allocate the object 
outside of the pool. It's also nicer if you can pass arguments to 
your constructor.

On Sunday, 26 October 2014 at 11:16:39 UTC, Damian wrote:

 On Sunday, 26 October 2014 at 03:37:47 UTC, Maxime 
 Chevalier-Boisvert wrote:

 Hello,

 I was wondering if there have been updates regarding Andrei's 
 announcement that he would rewrite the D garbage collector. Is 
 there any kind of timeline for when a new version of the GC 
 can be expected?

 I also wanted to ask if there was an implementation of an 
 object pool in the standard library. If not, I'm wondering 
 what the best way to implement this is. Is there any way to 
 overload new and destroy?

 I was thinking of using the templated emplace operator from 
 std.conv to allocate class objects into a large flat array, 
 and to derive pool-allocated classes from a PoolObject base 
 class. This base class would contain linked list pointers to 
 implement a free list, as well as templated static methods to 
 allocate and free the objects. Any advice welcome.


 For your object pool, why not just create functions, alloc and 
 free, instead of trying to override them - something like below

 version (USE_GC)
 {
   import core.memory;
 }
 else
 {
   import core.stdc.stdlib: malloc, free;
 }

 struct MemPool
 {
   void* alloc(size_t size, bool usePool = true) nothrow
   {
     version (USE_GC) return GC.malloc(size);
     else malloc(size);
   }

   void Free(void* p) nothrow
   {
     version (USE_GC) GC.free(p);
     else free(p);
   }
 }





 Oct 26 2014



  parent  "Kagamin" <spam here.lot>  writes:


On Sunday, 26 October 2014 at 14:14:43 UTC, Maxime 
Chevalier-Boisvert wrote:

 I'll do that if I have to, but it's cleaner with an override of 
 new as it makes it impossible to mistakenly allocate the object 
 outside of the pool. It's also nicer if you can pass arguments 
 to your constructor.


Such thing are not very appreciated. But if you really want it, 
you can declare one disabled constructor, it will deny 
construction of an object, and declare a normal member function, 
which can serve as an initializer. Also emplace passes arguments 
to constructor, it can be done for any function, you can just 
copy emplace's source and tweak to your liking (if you're going 
to disable the constructor). If you think, simple type inference 
is not enough and want a real signature copy, you can look at the 
BlackHole template.



 Oct 26 2014



prev sibling next sibling parent  "Sean Kelly" <sean invisibleduck.org>  writes:


On Sunday, 26 October 2014 at 03:37:47 UTC, Maxime 
Chevalier-Boisvert wrote:

 I also wanted to ask if there was an implementation of an 
 object pool in the standard library. If not, I'm wondering what 
 the best way to implement this is. Is there any way to overload 
 new and destroy?


Andrei has an allocator proposal that seemed largely done but for 
whatever reason it hasn't been submitted yet.

http://erdani.com/d/phobos-prerelease/std_allocator.html

Object pools seems like the kind of thing it should be good at.



 Oct 26 2014



prev sibling next sibling parent  "Kagamin" <spam here.lot>  writes:


Came up a while ago: 
http://forum.dlang.org/post/komuednbngkbeirrrptq forum.dlang.org



 Oct 26 2014



prev sibling  parent  Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>  writes:


On 10/25/14 8:37 PM, Maxime Chevalier-Boisvert wrote:

 Hello,

 I was wondering if there have been updates regarding Andrei's
 announcement that he would rewrite the D garbage collector. Is there any
 kind of timeline for when a new version of the GC can be expected?


There is no timeline as of now. I'd need a good contiguous hunk of time 
to dedicate to this, and the opportunity hasn't shown itself so far. But 
I am optimistic I'll have the opportunity in the near future.

You should also know about the experimental Sociomantic GC for D2 which 
has been recently announced: http://goo.gl/lOvttC


 I also wanted to ask if there was an implementation of an object pool in
 the standard library. If not, I'm wondering what the best way to
 implement this is. Is there any way to overload new and destroy?

 I was thinking of using the templated emplace operator from std.conv to
 allocate class objects into a large flat array, and to derive
 pool-allocated classes from a PoolObject base class. This base class
 would contain linked list pointers to implement a free list, as well as
 templated static methods to allocate and free the objects. Any advice
 welcome.


My allocator (which has been mentioned) is a low-level backend for such 
stuff. It's of good quality (i.e. fast) but very primitive in the sense 
it has no porcelain on it - you need to instantiate the desired 
combination yourself, call directly methods such as allocate() and 
deallocate(), and traffic in void[].


Andrei



 Oct 28 2014