[Performance] shootout.binarytrees when implemented with gc is 10x slower than C# on .NET 2.0

[Andrey Khropov]

Here is the D code for shootout.binarytrees with GC. Absolutely equal to the C#
code (I also embedded a timer):

------------------------------------------------------------------------
import std.c.stdlib, std.stdio, std.perf, std.gc;

int main(char[][] args)
{
    int N = args.length > 1 ? atoi(args[1]) : 1;
    
    auto t = new HighPerformanceCounter();
    t.start();

    int minDepth = 4;
    int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
    int stretchDepth = maxDepth + 1;

    TreeNode stretchTree = TreeNode.BottomUpTree(0, stretchDepth);
    writefln("stretch tree of depth ",stretchDepth,"\t check:
",stretchTree.ItemCheck);

    TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);

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

        for(int i = 1; i <= iterations; i++)
        {
            auto tempTree = TreeNode.BottomUpTree(i, depth);
            check += tempTree.ItemCheck;
            //delete tempTree;

            tempTree = TreeNode.BottomUpTree(-i, depth);
            check += tempTree.ItemCheck;
            //delete tempTree;
        }

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

    writefln("long lived tree of depth ",maxDepth,"\t check:
",longLivedTree.ItemCheck);
    
    t.stop();
    
    writefln(t.milliseconds()," ms elapsed.");

    return 0;
}

class TreeNode
{
public:
    this(int item, TreeNode left = null, TreeNode right = null)
    {
      this.item  = item;
      this.left  = left;
      this.right = right;
    }

    static TreeNode BottomUpTree(int item, int depth)
    {
        if(depth > 0)
            return new TreeNode(item
                                ,BottomUpTree(2 * item - 1, depth - 1)
                                ,BottomUpTree(2 * item, depth - 1));
        return new TreeNode(item);
    }

    int ItemCheck()
    {
        if(left)
            return item + left.ItemCheck() - right.ItemCheck();
        return item;
    }
private:
    TreeNode            left, right;
    int                 item;
}
------------------------------------------------------------------------
Here's the C# code (also with embedded timer):
------------------------------------------------------------------------
using System;
using System.Diagnostics;

class BinaryTrees
{
   const int minDepth = 4;

   public static void Main(String[] args) 
   {        
      int n = 0;
      if (args.Length > 0) n = Int32.Parse(args[0]);
      
      Stopwatch t = new Stopwatch();
      t.Start();  
    
      int maxDepth = Math.Max(minDepth + 2, n);
      int stretchDepth = maxDepth + 1;

      int check = (TreeNode.bottomUpTree(0,stretchDepth)).itemCheck();
      Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth,
check);

      TreeNode longLivedTree = TreeNode.bottomUpTree(0,maxDepth);

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

         check = 0;
         for (int i=1; i<=iterations; i++)
         {
            check += (TreeNode.bottomUpTree(i,depth)).itemCheck();  
            check += (TreeNode.bottomUpTree(-i,depth)).itemCheck(); 
         }

         Console.WriteLine("{0}\t trees of depth {1}\t check: {2}", 
            iterations*2, depth, check);
      }
 
      Console.WriteLine("long lived tree of depth {0}\t check: {1}", 
         maxDepth, longLivedTree.itemCheck());
         
      t.Stop();
      Console.WriteLine(t.ElapsedMilliseconds + "ms elapsed.");      
   }


   class TreeNode 
   {     
      private TreeNode left, right;
      private int item;

      TreeNode(int item){
         this.item = item;
      }
      
      TreeNode(int item,TreeNode left, TreeNode right){
         this.left = left; 
         this.right = right;
         this.item = item;
      }

      internal static TreeNode bottomUpTree(int item, int depth){
         if (depth>0){
            return new TreeNode(
                 item,
                 bottomUpTree(2*item-1, depth-1),
                 bottomUpTree(2*item, depth-1)
               );
         }
         else {
            return new TreeNode(item);
         }
      }

      internal int itemCheck(){
         // if necessary deallocate here 
         if (left==null) return item;
         else return item + left.itemCheck() - right.itemCheck(); 
      }
   }
}
------------------------------------------------------------------------

So the results are (with cmdline parameter = 16):

C# on .NET 2.0	    				 :  1.902 sec
DMD 0.173 - malloc(original version)  :  5.189 sec
C# on Mono 1.1.18				 :  6.630 sec
DMD 0.173 - full GC 				 : 19.720 sec

-- 
AKhropov