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

This groups two nodes into one allocation, ideally halving the number of total allocations.

IMO this makes the comparision pretty meaningless.

Answer 2

Structures can be allocated on stack instead of the heap (not in every case though), which means that they are de-allocated as soon as they go out of scope - the Garbage Collector does not get involved in that scenario. That can result in smaller memory pressure and less garbage collections. Also, stack is (mostly) contigous area of memory, so access to it has better locality, which can (again, possibly) improve cache hits ratio on the CPU level.

Microsoft guidelines on choosing between classes and structures:

• structures should be small (16 bytes generally) and short lived
• they should be immutable

If those are met, then using a structure over a class will result in a performance gain.

Answer 3

I dont think that using struct here makes any difference at all. Especially after looking at source code of TreeNode, where instances of TreeNode are always copied in constructor and recursive bottomUpTree call.

Answer 4

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.