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...
}

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 :)

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?

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

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.

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;

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
}

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;
}

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.

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