GC performances

[Lutger]

bearophile wrote:
> Lutger Wrote:
...
>> Likely not the intent of the benchmark, but an array based 
>> implementation could be faster here.
> 
> It seems slower.
> 
> Bye,
> bearophile

I've hacked up an array based implementation without recursion and 
allocating whole trees at once. Although it produces the same results, 
it's probably flawed somewhere or the profiling is wrong I think. 
Anyway it runs much faster, perhaps you care to take a look. I'm not so 
good at these things:


import std.stdio, std.conv;
import std.math;

int left(int i) { return i * 2; }

int right(int i) { return ++i * 2; }

int parent(int i) { return i / 2; }

struct Tree
{
     static Tree bottumUpTree(int item, int depth)
     {
         Tree result;
         result.depth = depth;
         if (depth > 0)
         {
             auto len = pow(depth, cast(real)1);
             result.children.length = cast(uint)len;

         }
         else
             result.children.length = 1;
         result.children[0] = item;
         for (int i = 1; i < result.children.length; i+=2)
         {
             result.children[i] = (result.children[parent(i)] * 2) - 1;
             result.children[i + 1] = result.children[parent(i)] * 2;
         }
         return result;
     }

     int depth;

     int check()
     {
         int result = children[0];
         auto copy = children.dup;

         for (int i = children.length - ((depth * 2) -1); i < 
children.length; i+=2)
         {
             auto p = parent(i);
             copy[p] += children[i] - children[i+1];
         }

         for (int i = children.length - ((depth * 2) - 2); i > 0; i-=2)
         {
             auto p = parent(i);
             copy[p] += children[i-1] - children[i];
         }

         result+= copy[1] - copy[2];

         return result;
     }
     void deleteTree() { delete children; }
     int[] children;

     private int item;
}


void main(string[] args) {
     const minDepth = 4;
     int n = (args.length > 1) ? toInt(args[1]) : 2;
     int maxDepth = (minDepth + 2) > n ? minDepth + 2 : n;

     auto t = Tree.bottumUpTree(0, maxDepth + 1);
     writefln("stretch tree of depth ", maxDepth + 1, "\t check: ", 
t.check());
     t.deleteTree();

     auto longLivedTree = Tree.bottumUpTree(0, maxDepth);

     for (int depth = minDepth; depth <= maxDepth; depth += 2)
     {
         int check;
         int iterations = 1 << (maxDepth - depth + minDepth);


         for (int i = 1; i <= iterations; i++)
         {
             auto t1 = Tree.bottumUpTree(i, depth);
             check += t1.check();
             t1.deleteTree();
             auto t2 = Tree.bottumUpTree(-i, depth);
             check += t2.check();
             t2.deleteTree();
         }

         writefln(iterations * 2, "\t trees of depth ", depth, "\t 
check: ", check);
     }

     writefln("long lived tree of depth ", maxDepth, "\t check: ", 
longLivedTree.check);
     longLivedTree.deleteTree();
}