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

[Kyle Furlong]

Andrey Khropov wrote:
> 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
> 

Andrey, its no secret that the D GC is not implemented to be the fastest 
around. C# I believe uses at the least a generational collector, which I 
think is also copying.

D currently uses a conservative mark and sweep collector. Rock solid, 
but slow.