XobotOS: Why does the C# binary tree benchmark use a struct?

Question

Curious about the reputed performance gains in xobotos, I checked out the binary tree benchmark code.

The Java version of the binary tree node is:

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

The C# version is:

struct TreeNode
{
  class Next
  {
    public TreeNode left, right;
  }

  private Next next;
  private int item;
}

I'm wondering what the benefit of using a struct here is, since the Next and Previous pointers are still encapsulated in a class.

Well, there is one - leaf nodes are pure value types since they don't need left and right pointers. In a typical binary tree where half the nodes are leaves, that means a 50% reduction in the number of objects. Still, the performance gains listed seem far greater.

Question: Is there more to this?

Also, since I wouldn't have thought of defining tree nodes this way in C# (thanks Xamarin!) what other data structures can benefit from using structs in a non-obvious way? (Even though that's a bit off-topic and open ended.)

Answer 1

I just ran across this odd code and had the same question. If you change the code to match the Java version it will run just slightly slower. I believe most of the 'struct TreeNode' will get boxed and allocated anyway, except for the bottom row. However, each node results in 2 allocations: boxed TreeNode and class Next. The allocation savings quickly disappear. IMO, this is not an appropriate use of struct.