Today I noticed the SIMD implementation of the Mandelbrot set algorithm I blogged about last year was successfully submitted to the language shootout webpage. However, I was a bit disappointed to see the C# version was still slower than the Java version, despite my use of the special SIMD instructions (though I was pleased that a quick port of my code to F# absolutely annihilates the OCAML version of this benchmark).

I had benchmarked my code as faster than the Java code on my Mac, the CentOS cluster at my work and two Ubuntu virtual machines (Mono >3.0, LLVM compiler). What gave?

Undeterred, I thought I would try to use SIMD to improve another C# benchmark, and took a shot at the N-body benchmark test. Once again, the version I wrote, in my hands, was much faster. But when submitted to the shoot-out and accepted, it was either much slower, or didn’t even run. My submission using the SSE instructions not only didn’t beat Java, it was actually slower than the original C# version!

Below are the timings on my top-of-the-line Mac for the two benchmarks, in both cases we see that the C# program runs in 80-90% of the time the Java Program takes. There are several key take aways here.

C# and Java have no meaningful performance differences.

C# and Java’s similar performance has different underpinnings

There are a lot of ways code can be fast, and I was surprised that Java and C# achieve similar speeds in very different ways.

The key advantage of the C# code was the SIMD instructions, which in theory give a ~2X speed up. However, they only win by ~20%. Why?

I think the assembly gives the answer. Just some quick snippets tell the whole story. Here is some C# code for the N-Body problem compiled to assembly:

The important insights into performance from the assembly here are:

1. Similar instructions are stacked on top of each other, allowing for pipelining (e.g. the same vhaddpd instruction follows the same vhaddpd, and both use different registers, so can execute simultaneously).
2. The “p” in the instructions (i.e. vhadd-“p”-d). This stands for “packed” meaning we are packing/doing two operations at once via SIMD.
3. Only registers XMM1-XMM4 appear in the instructions. There are more registers available, and more pipelining possible, but the Mono/LLVM compiler appears to only use the low-number/scratch registers. It is easier to write compilers that obey this restriction.

Now let’s compare that to some Java assembly emitted by the Oracle runtime for the same benchmark:

The important insights here are:

1. Java uses the version of the instructions with “s” (i.e. vmul-“s”-d) meaning single, and gets no SSE advantage. No doubt this makes writing compilers easier.
2. However, Java is using lots of registers, XMM15 shows up!
3. As a result of using all the registers used, the Java code has great pipelining. Note that up to 5 vmulsd instructions show up at once. The JVM is simply brilliant at packing operations together, and this means that even though I, the programmer, was smart and used SSE2, my C# code only won by 20%, and not 200%. It’s hard to beat Java pipelining.

All of which makes me wonder. What if we took the high-level language advantages of C# (low-overhead value types, easy interop via pointers, baked in generics, etc.). And combined them with the low-level advantages of the JVM (better array bounds check elimination, pipelining compiler optimizations, and maybe someday the occasional stack allocation of reference type variables…)

In the dark moments when one wonders if their research is doing enough to better the world, it’s always nice to remember you’re not a patent lawyer.  The radio program This American Life did a fantastic investigation of this issue recently, highly recommended and very entertaining, so I thought I would point it out here.  It explains how broken the system is, and although I don’t know how best to ensure people are compensated for their creative works, clearly we need better solutions.

The outcome of perceived or real patent fights basically moved me away from the Linux desktop.  In 2006 I thought the Linux desktop would become the world standard (the other options were far from awesome).  Instead the technology company that spends the least on research and development rose to prominence and essentially everyone I know who uses Linux comes from the tail end of the most affluent class of society (which probably makes them great targets for the now integrated Amazon search).  Here’s hoping this mess gets cleaned up in the next few years.

Determining which data structure to use for storing data involves trade-offs between how much memory they require and how long different operations, such as insertions, deletions, or searches take.  In C#, using a linear array is the fastest way to enumerate all of the objects in a collection.  However, the use of an array or list can have multiple drawbacks.  For example, Arrays and lists in C# can have frustrating size limits as objects in the CLR, regardless of system architecture, cannot be over 2 GB in size*.  Similarly, while a good data-structure for enumerations, lists and arrays are slower than other alternatives for searching.

I recently had a dataset for which the abilities to search, enumerate and hold over 2 GB of data from the collection were desirable.  These criteria naturally make a tree like data structure appealing.  However, in a high level language like C# where performance can often heavily depend on which run-time optimizations the virtual machine utilizes, determining the actual performance hit incurred by using a tree as compared to a list during an enumeration is more accurately answered with empirical data than Big O notation.

So, I tested how enumeration performance varies between a balanced binary tree and a list.  Since the tree was being enumerated by using the yield statement when a relevant node was found, I compared three methods.  One where a class containing a binary tree is enumerated with a yield, one where a class containing a list is enumerated with a yield statement (that is the class enumerates its internal list and yields each element), and one where that same class is enumerated by simply passing out the original List object.  In all cases enumerating 2²⁰ objects in total.  Here is the time comparison.

These values do not vary substantially based on the order of operations or repeated trials.  So, yowza,  an order of magnitude difference in enumerating the objects, which seemed far more severe than I would have imagined (I was expecting about 3X).  It appears much of this is due to the method call and overhead of the yield statement.  The two methods using the list are logically identical in code, but it seems the compiler can’t quite figure that out, leading to a 5X drop in performance.  Out of curiosity, I also compared to a dictionaries enumeration speed which took about twice as long as the fast list method, but which ran out of memory with a higher number of elements pretty readily.

My take home on this, is to only use arrays and lists in C# if the enumeration speed of a collection appears limiting.  It appears traversal of trees in the language is very slow, so trees are not generally recommended when the operations per node are fast.

*This may change on newer version of the MS CLR

Code Below

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Globalization;

namespace TestTreeVersusList
{
    class Program
    {
        public static int TreeDepth = 24;
        public static int ElementNumber=(int)(Math.Pow(2,TreeDepth));
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            ulong val = 0;
            ////now for the list
            val = 0;
            ListEnumerator le = new ListEnumerator();
            sw.Reset();
            sw.Start();
            foreach (node num in le.GetNodes())
            {
                val += num.value;
            }
            sw.Stop();
            Console.WriteLine("Time Taken For List with yield: " + sw.Elapsed.TotalSeconds.ToString() + " seconds");

            sw.Reset();
            sw.Start();
            foreach (node num in le.curList)
            {
                val += num.value;
            }
            sw.Stop();
            Console.WriteLine("Time Taken For List without yield: " + sw.Elapsed.TotalSeconds.ToString() + " seconds");
            le = null;

            //create a tree and a list
            BinaryTreeEnumerator tree = new BinaryTreeEnumerator();
            sw.Reset();
            sw.Start();
            val = 0;
            foreach (node num in tree.GetNodes())
            {
                val += num.value;
            }
            sw.Stop();
            Console.WriteLine("Time Taken For Tree: " + sw.Elapsed.TotalSeconds.ToString() + " seconds");
            tree = null;
            DictionaryEnumerator dict = new DictionaryEnumerator();
            sw.Reset();
            sw.Start();
            val = 0;
            foreach (var kv in dict.dict)//.dict)
            {
                val=kv;
                //val = kv.Key;
            }
            sw.Stop();
            Console.WriteLine("Time Taken For Dictionary: " + sw.Elapsed.TotalSeconds.ToString() + " seconds");
            dict = null;
        }
          }
    class node
    {
        public ulong value;
        public object o;
        public node Left;
       public node Right;
    }
    class BinaryTreeEnumerator
    {
        node root;
        int nodeCount;
        public IEnumerable<node> GetNodes()
        {
            Stack<node> traversalStack = new Stack<node>(2 * Program.TreeDepth);
            traversalStack.Push(this.root);
            while (traversalStack.Count > 0)
            {
                node current;
                current = traversalStack.Pop();
                if (current != null)
                {
                    if (current.value != 0)
                    {
                        traversalStack.Push(current.Right);
                        traversalStack.Push(current.Left);
                    }
                    yield return current;
                }
            }
            //traversalStack.TrimExcess();
        }
        //Just make a binary tree with a bunch of elements
        public BinaryTreeEnumerator()
        {
            this.root = new node() { value = 1, o = null };
            node current;
            Queue<node> traversalStack = new Queue<node>(2*Program.TreeDepth);
            traversalStack.Enqueue(this.root);
            while (traversalStack.Count > 0 && nodeCount < Program.ElementNumber)
            {                
                current = traversalStack.Dequeue();
                if (current.value != 0)
                {
                    current.Left = new node() { value = 1, o = null };
                    current.Right = new node() { value = 1, o = null };
                    nodeCount += 2;
                    traversalStack.Enqueue(current.Right);
                    traversalStack.Enqueue(current.Left);
                }
            }
        }
    }
    class ListEnumerator
    {
        public List<node> curList;
        public ListEnumerator()
        {
            curList = new List<node>(Program.ElementNumber);
            for(int i=0;i<Program.ElementNumber;i++)
            {
                 curList.Add(new node(){value=1,o=null});
            }
        }
        public IEnumerable<node> GetNodes()
        {
            foreach (node n in curList)
            {
                 yield return n;
            }
        }
    }
    class DictionaryEnumerator
    {
        public Dictionary<ulong,node> dict = new Dictionary<ulong,node>();
        public DictionaryEnumerator()
        {
            for (ulong i = 0; i < (ulong)Program.ElementNumber; i++)
            {
                dict[i] = new node() { value = i, o = null };
            }
        }
    }
}