GC performances

[Craig Black]

"Lutger" <lutger.blijdestijn at gmail.com> wrote in message 
news:fiekma$otu$1 at digitalmars.com...
> 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();
> }

Here's an array-based C++ implementation from the shootout.  It performs the 
best but was disqualified because it allocates everything in one big chunk 
and then uses placement new to allocate each node.
/* The Computer Language Shootout
 * http://shootout.alioth.debian.org/
 * Contributed by Paul Kitchin
 */


#include <iostream>
#include <sstream>

class Tree
{

      struct Node
      {

         Node(int value, std::size_t depth, std::size_t index, Node * nodes, 
std::size_t max)
            :
            value(value)
         {
            if (index * 2 + 2 < max)
            {
               new (nodes + index * 2 + 1) Node(2 * value - 1, depth - 1, 
index * 2 + 1, nodes, max);
               new (nodes + index * 2 + 2) Node(2 * value, depth - 1, index 
* 2 + 2, nodes, max);
            }
         }

         int check(std::size_t index, Node * nodes, std::size_t max) const
         {
            if (index * 2 + 2 < max)
            {
               return nodes[index * 2 + 1].check(index * 2 + 1, nodes, max) 
+ value - nodes[index * 2 + 2].check(index * 2 + 2, nodes, max);
            }
            return value;
         }

         int value;

      };

   public:

      Tree(int value, std::size_t depth)
         :
         size((2 << depth) - 1),
         nodes(static_cast< Node * >(operator new(size * sizeof(Node))))
      {
         new (nodes) Node(value, depth, 0, nodes, size);
      }

      ~Tree()
      {
         operator delete(nodes);
      }

      int check() const
      {
         return nodes->check(0, nodes, size);
      }

   private:

      std::size_t size;
      Node * nodes;

};

int main(int argc, char * * argv)
{
   std::size_t user_depth = 10;
   if (argc == 2)
   {
      std::istringstream convertor(argv[1]);
      if (!(convertor >> user_depth) || !convertor.eof())
      {
         std::cerr << "Usage: " << argv[0] << " [n]\n";
         std::cerr << "\tn must be an integer\n";
         return 1;
      }
   }
   std::size_t minimum_depth = 4;
   std::size_t maximum_depth = std::max(minimum_depth + 2, user_depth);
   {
      Tree tree(0, maximum_depth + 1);
      std::cout << "stretch tree of depth " << (maximum_depth + 1) << "\t 
check: " << tree.check() << '\n';
   }
   Tree long_lived_tree(0, maximum_depth);
   for (std::size_t depth = minimum_depth; depth <= maximum_depth; depth += 
2)
   {
      int iterations = 1 << (maximum_depth - depth + minimum_depth);
      int check = 0;
      for (int iteration = 1; iteration <= iterations; ++iteration)
      {
         Tree first(iteration, depth);
         Tree second(-iteration, depth);
         check += first.check() + second.check();
      }
      std::cout << (2 * iterations) << "\t trees of depth " << depth << "\t 
check: " << check << '\n';
   }
   std::cout << "long lived tree of depth " << maximum_depth << "\t check: " 
<< long_lived_tree.check() << '\n';
}