www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Fast GC allocation of many small objects

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
I'm working on a graph database with tens of millions of small 
nodes containing typically around 8-64 bytes of member data. Is 
there a faster way of allocating many small class objects such as

class Node
{
     // abstract members
}

class StrNode : Node
{
     string value;
}

// more Node-types...

other than

const nodeCount = 10_000_000;
foreach (0 .. n)
{
     auto node = new Node(someData);
     // connect node...
}
Mar 30 2018
next sibling parent reply rikki cattermole <rikki cattermole.co.nz> writes:
On 31/03/2018 9:31 AM, Per Nordlöw wrote:

 I'm working on a graph database with tens of millions of small nodes 
 containing typically around 8-64 bytes of member data. Is there a faster 
 way of allocating many small class objects such as
 
 class Node
 {
      // abstract members
 }
 
 class StrNode : Node
 {
      string value;
 }
 
 // more Node-types...
 
 other than
 
 const nodeCount = 10_000_000;
 foreach (0 .. n)
 {
      auto node = new Node(someData);
      // connect node...
 }


Use a custom allocator (that could be backed by the GC) using 
std.experimental.allocators :)
Mar 30 2018
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 30 March 2018 at 20:38:35 UTC, rikki cattermole wrote:

 Use a custom allocator (that could be backed by the GC) using 
 std.experimental.allocators :)


https://dlang.org/phobos/std_experimental_allocator.html

is massive.

I guess I should allocate my nodes using

     auto node = theAllocator.make!StrNode("alpha");

Could someone please give a working example of a GC-backed 
`theAllocator` suitable for my allocation pattern?
Mar 30 2018
next sibling parent rikki cattermole <rikki cattermole.co.nz> writes:
On 31/03/2018 9:46 AM, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 20:38:35 UTC, rikki cattermole wrote:

 Use a custom allocator (that could be backed by the GC) using 
 std.experimental.allocators :)


 
 https://dlang.org/phobos/std_experimental_allocator.html
 
 is massive.
 
 I guess I should allocate my nodes using
 
      auto node = theAllocator.make!StrNode("alpha");
 
 Could someone please give a working example of a GC-backed 
 `theAllocator` suitable for my allocation pattern?


The default theAllocator is the GC :)

Also see[0] and "Sample Assembly"[1] which will really interest you I think.

[0] https://dlang.org/phobos/std_experimental_allocator_gc_allocator.html
[1] https://dlang.org/phobos/std_experimental_allocator_building_blocks.html
Mar 30 2018
prev sibling next sibling parent reply Alexandru Jercaianu <alex.jercaianu gmail.com> writes:
On Friday, 30 March 2018 at 20:46:43 UTC, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 20:38:35 UTC, rikki cattermole 
 wrote:

 Use a custom allocator (that could be backed by the GC) using 
 std.experimental.allocators :)


 https://dlang.org/phobos/std_experimental_allocator.html

 is massive.

 I guess I should allocate my nodes using

     auto node = theAllocator.make!StrNode("alpha");

 Could someone please give a working example of a GC-backed 
 `theAllocator` suitable for my allocation pattern?


Hello,

You can try the following:
     struct Node
     {
         char[64] arr;
     }

      enum numNodes = 100_000_000;
      void[] buf = GCAllocator.instance.allocate(numNodes * 
Node.sizeof);
      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);

      foreach(i; 0 .. numNodes)
      {
          Node* n = cast(Node*)(reg.allocate(Node.sizeof).ptr);
          // do stuff with the new node
      }

I benchmarked this versus
      foreach(i; 0 .. numNodes)
      {
          auto n = new Node;
          // do stuff...
      }

The first approach was about 30% faster.
Mar 30 2018
next sibling parent Alexandru Jercaianu <alex.jercaianu gmail.com> writes:
On Friday, 30 March 2018 at 23:09:33 UTC, Alexandru Jercaianu 
wrote:

 On Friday, 30 March 2018 at 20:46:43 UTC, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 20:38:35 UTC, rikki cattermole 
 wrote:

 Use a custom allocator (that could be backed by the GC) using 
 std.experimental.allocators :)


 https://dlang.org/phobos/std_experimental_allocator.html

 is massive.

 I guess I should allocate my nodes using

     auto node = theAllocator.make!StrNode("alpha");

 Could someone please give a working example of a GC-backed 
 `theAllocator` suitable for my allocation pattern?


 Hello,

 You can try the following:
     struct Node
     {
         char[64] arr;
     }

      enum numNodes = 100_000_000;
      void[] buf = GCAllocator.instance.allocate(numNodes * 
 Node.sizeof);
      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);

      foreach(i; 0 .. numNodes)
      {
          Node* n = cast(Node*)(reg.allocate(Node.sizeof).ptr);
          // do stuff with the new node
      }

 I benchmarked this versus
      foreach(i; 0 .. numNodes)
      {
          auto n = new Node;
          // do stuff...
      }

 The first approach was about 30% faster.


Sorry, I forgot to add which imports you need:

  import std.experimental.allocator.gc_allocator;
  import std.experimental.allocator.building_blocks.region;
  import std.experimental.allocator.building_blocks.null_allocator;
Mar 30 2018
prev sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 30 March 2018 at 23:09:33 UTC, Alexandru Jercaianu 
wrote:

 Hello,

 You can try the following:
     struct Node
     {
         char[64] arr;
     }

      enum numNodes = 100_000_000;
      void[] buf = GCAllocator.instance.allocate(numNodes * 
 Node.sizeof);
      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);


Thanks!

Is a `minAlign` of 16 recommended over 8 when allocating classes 
or arrays?
Mar 31 2018
next sibling parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 31 March 2018 at 20:17:26 UTC, Per Nordlöw wrote:

      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);


 Thanks!


Turns out that Region allocator wasn't fully qualified:

https://github.com/dlang/phobos/pull/6400

This will make it possible to allocate with it in pure code :)
Mar 31 2018
prev sibling parent reply Alexandru jercaianu <Alex.jercaianu gmail.com> writes:
On Saturday, 31 March 2018 at 20:17:26 UTC, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 23:09:33 UTC, Alexandru Jercaianu 
 wrote:

 Hello,

 You can try the following:
     struct Node
     {
         char[64] arr;
     }

      enum numNodes = 100_000_000;
      void[] buf = GCAllocator.instance.allocate(numNodes * 
 Node.sizeof);
      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);


 Thanks!

 Is a `minAlign` of 16 recommended over 8 when allocating 
 classes or arrays?


Hi,
I'm glad it was helpful.
To be honest, I don't know which alignment would be better and it 
probably depends on your machine.
This here says that 16 would work just fine [1] so I would go 
with that.

[1] - 
https://dlang.org/library/std/experimental/allocator/common/platform_alignment.html
Apr 01 2018
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Sunday, 1 April 2018 at 10:59:55 UTC, Alexandru jercaianu 
wrote:

 On Saturday, 31 March 2018 at 20:17:26 UTC, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 23:09:33 UTC, Alexandru Jercaianu 
 wrote:

 Hello,

 You can try the following:
     struct Node
     {
         char[64] arr;
     }

      enum numNodes = 100_000_000;
      void[] buf = GCAllocator.instance.allocate(numNodes * 
 Node.sizeof);
      auto reg = Region!(NullAllocator, 16)(cast(ubyte[])buf);


 Thanks!

 Is a `minAlign` of 16 recommended over 8 when allocating 
 classes or arrays?


 Hi,
 I'm glad it was helpful.
 To be honest, I don't know which alignment would be better and 
 it probably depends on your machine.
 This here says that 16 would work just fine [1] so I would go 
 with that.

 [1] - 
 https://dlang.org/library/std/experimental/allocator/common/platform_alignment.html


Thanks. I presume if we know what type we should allocate, in my 
case a class `C`, we should use `C.alignof` otherwise we should 
default to `platformAlignment`.
Apr 01 2018
prev sibling parent reply Rubn <where is.this> writes:
On Friday, 30 March 2018 at 20:46:43 UTC, Per Nordlöw wrote:

 On Friday, 30 March 2018 at 20:38:35 UTC, rikki cattermole 
 wrote:

 Use a custom allocator (that could be backed by the GC) using 
 std.experimental.allocators :)


 https://dlang.org/phobos/std_experimental_allocator.html

 is massive.

 I guess I should allocate my nodes using

     auto node = theAllocator.make!StrNode("alpha");

 Could someone please give a working example of a GC-backed 
 `theAllocator` suitable for my allocation pattern?


Be willing to change your code, the allocator can change at any 
point. What you implement today may not work tomorrow, what you 
fix to work for tomorrow may not end up working the next day (in 
terms of releases). That really should be something that is 
mentioned when you suggest using an experimential feature, 
there's no guarantees at all. It might not even get put into 
phobos. If your project is going to be used over the course of a 
year or more than maybe you shouldn't use it.
Mar 31 2018
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 31 March 2018 at 19:31:37 UTC, Rubn wrote:

 Be willing to change your code, the allocator can change at any 
 point. What you implement today may not work tomorrow, what you 
 fix to work for tomorrow may not end up working the next day 
 (in terms of releases). That really should be something that is 
 mentioned when you suggest using an experimential feature, 
 there's no guarantees at all. It might not even get put into 
 phobos. If your project is going to be used over the course of 
 a year or more than maybe you shouldn't use it.


Ok, thanks for the point.

Is the dub package stdx-allocator [1] a better alternative in 
this regard?

[1] https://github.com/dlang-community/stdx-allocator
Mar 31 2018
parent Seb <seb wilzba.ch> writes:
On Saturday, 31 March 2018 at 19:38:31 UTC, Per Nordlöw wrote:

 On Saturday, 31 March 2018 at 19:31:37 UTC, Rubn wrote:

 Be willing to change your code, the allocator can change at 
 any point. What you implement today may not work tomorrow, 
 what you fix to work for tomorrow may not end up working the 
 next day (in terms of releases). That really should be 
 something that is mentioned when you suggest using an 
 experimential feature, there's no guarantees at all. It might 
 not even get put into phobos. If your project is going to be 
 used over the course of a year or more than maybe you 
 shouldn't use it.


 Ok, thanks for the point.

 Is the dub package stdx-allocator [1] a better alternative in 
 this regard?

 [1] https://github.com/dlang-community/stdx-allocator


Yep, that's why it was created. It's a snapshot of

https://docarchives.dlang.io/v2.077.0/phobos/std_experimental_allocator.html

It might be updated later, but with dub it's really easy to lock 
it to a specific version - which you can't when upgrading the 
compiler.
Mar 31 2018
prev sibling next sibling parent reply Boris-Barboris <ismailsiege gmail.com> writes:
On Friday, 30 March 2018 at 20:31:35 UTC, Per Nordlöw wrote:

 Is there a faster way of allocating many small class objects 
 such as...


maybe something like this:

import std.conv: to;
import std.stdio;

class Node {}

class StrNode : Node
{
     string value;
}

void main()
{
     writeln(StrNode.classinfo.name);	// onlineapp.StrNode
     size_t il = StrNode.classinfo.m_init.length;
     writeln(il); // 32
     void[] backBuf = new void[il * 1000];
     StrNode[] nodes = new StrNode[1000];
     for (int i = 0; i < 1000; i++)
     {
         backBuf[i * il .. (i+1) * il] = StrNode.classinfo.m_init;
         nodes[i] = cast(StrNode) &backBuf[i * il];
         nodes[i].value = i.to!string;
     }
     foreach (n; nodes[995..$])
         writeln(n.classinfo.name, " ", n.value);	
         // prints onlineapp.StrNode 995-999
}
Mar 31 2018
parent =?UTF-8?B?UsOpbXkgTW91w6t6YQ==?= <remy.moueza-dontspamme gmail.com> writes:
On Saturday, 31 March 2018 at 09:10:13 UTC, Boris-Barboris wrote:

 On Friday, 30 March 2018 at 20:31:35 UTC, Per Nordlöw wrote:

 Is there a faster way of allocating many small class objects 
 such as...


 maybe something like this:

 import std.conv: to;
 import std.stdio;

 class Node {}

 class StrNode : Node
 {
     string value;
 }

 void main()
 {
     writeln(StrNode.classinfo.name);	// onlineapp.StrNode
     size_t il = StrNode.classinfo.m_init.length;
     writeln(il); // 32
     void[] backBuf = new void[il * 1000];
     StrNode[] nodes = new StrNode[1000];
     for (int i = 0; i < 1000; i++)
     {
         backBuf[i * il .. (i+1) * il] = 
 StrNode.classinfo.m_init;
         nodes[i] = cast(StrNode) &backBuf[i * il];
         nodes[i].value = i.to!string;
     }
     foreach (n; nodes[995..$])
         writeln(n.classinfo.name, " ", n.value);	
         // prints onlineapp.StrNode 995-999
 }


I would have used std.conv.emplace:

import std.stdio;
import std.conv : emplace, to;

class Node {
     string value;

     this (long n) {
         this.value = n.to!string;
     }

     override string toString () {
         return "Node (value: " ~ value ~ ")";
     }
}

void main (string [] args) {

     /* size_t size = Node.sizeof; */
     size_t size = Node.classinfo.m_init.length;
     void [] memory = new void [size * 1000];
     Node [] nodes  = new Node [1000];

     foreach (i, node; nodes) {
         void [] buf = memory [i * size.. i * size + size];
         nodes [i] = emplace!Node (buf, i);
     }
     nodes [0]  .writeln;
     nodes [$-1].writeln;
}
Mar 31 2018
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/30/18 4:31 PM, Per Nordlöw wrote:

 I'm working on a graph database with tens of millions of small nodes 
 containing typically around 8-64 bytes of member data. Is there a faster 
 way of allocating many small class objects such as
 
 class Node
 {
      // abstract members
 }
 
 class StrNode : Node
 {
      string value;
 }
 
 // more Node-types...
 
 other than
 
 const nodeCount = 10_000_000;
 foreach (0 .. n)
 {
      auto node = new Node(someData);
      // connect node...
 }
 


You may be interested in this proposal, which was inspired by trying to 
implement a reserve feature for AAs (requires a similar mechanism).

https://issues.dlang.org/show_bug.cgi?id=17881

Note that the recommendations in the replies here have the unfortunate 
drawback of tying all allocations to one block, scanned by the GC all at 
once, and will only get collected when none of them are referenced. On 
32-bit systems this also leads to a high likelihood of false pointers 
keeping the block alive.

More use cases for the feature request may help push for acceptance.

-Steve
Apr 02 2018
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 2 April 2018 at 18:22:43 UTC, Steven Schveighoffer 
wrote:

 You may be interested in this proposal, which was inspired by 
 trying to implement a reserve feature for AAs (requires a 
 similar mechanism).

 https://issues.dlang.org/show_bug.cgi?id=17881
 


Ok, thanks. I'll push for it.

One thing, though, that boggles me; how does the GC know where 
each class instance start and what type it has when I the 
allocator constructs it using `emplace` in my Region? So that the 
GC knows which destructor to call where.

Furher, is it ok to use my allocator to allocate both pod, 
structs and classes? Or aren't allocators supposed to be used in 
that way?
Apr 02 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/2/18 2:51 PM, Per Nordlöw wrote:

 On Monday, 2 April 2018 at 18:22:43 UTC, Steven Schveighoffer wrote:

 You may be interested in this proposal, which was inspired by trying 
 to implement a reserve feature for AAs (requires a similar mechanism).

 https://issues.dlang.org/show_bug.cgi?id=17881


 
 Ok, thanks. I'll push for it.
 
 One thing, though, that boggles me; how does the GC know where each 
 class instance start and what type it has when I the allocator 
 constructs it using `emplace` in my Region? So that the GC knows which 
 destructor to call where.


It probably doesn't. Yet another reason to have a feature for this 
supported by the GC instead of a wrapper allocator.


 Furher, is it ok to use my allocator to allocate both pod, structs and 
 classes? Or aren't allocators supposed to be used in that way?


An allocator can be used to create anything AFAIK.

-Steve
Apr 02 2018