XobotOS:为什么C#二叉树基准测试使用结构

Question

对xobotos中著名的性能提升感到好奇，我查看了二叉树基准代码。

二叉树节点的 Java 版本是：

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

C# 版本为：

struct TreeNode
{
  class Next
  {
    public TreeNode left, right;
  }
  private Next next;
  private int item;
}

我想知道在这里使用结构有什么好处，因为下一个和上一个指针仍然封装在一个类中。

嗯，有一个 - 叶节点是纯值类型，因为它们不需要左右指针。在典型的二叉树中，一半的节点是叶子，这意味着对象数量减少了 50%。尽管如此，列出的性能提升似乎要大得多。

问：还有更多吗？

另外，由于我不会想到在 C# 中以这种方式定义树节点(感谢 Xamarin！(，还有哪些其他数据结构可以从以不明显的方式使用结构中受益？(尽管这有点偏离主题和开放式。

Answer 1

我刚刚遇到了这个奇怪的代码并遇到了同样的问题。如果您更改代码以匹配 Java 版本，它的运行速度会稍微慢一些。我相信大多数"结构 TreeNode"无论如何都会被装箱和分配，除了底行。但是，每个节点都会产生 2 个分配：盒装 TreeNode 和类 Next。节省的分配费用很快消失。IMO，这不是结构的适当使用。

Answer 2

这会将两个节点分组到一个分配中，理想情况下将总分配数减半。

IMO 这使得比较变得毫无意义。

Answer 3

结构可以在堆栈而不是堆上分配(尽管并非在所有情况下(，这意味着一旦它们超出范围就会被取消分配 - 垃圾收集器不会参与这种情况。这可能会导致较小的内存压力和更少的垃圾回收。此外，堆栈(大部分(是连续的内存区域，因此访问它具有更好的局部性，这可以(再次，可能(提高 CPU 级别的缓存命中率。

Microsoft在类和结构之间进行选择的准则：

• 结构应该很小(通常为 16 个字节(且寿命短
• 它们应该是不可变的

如果满足这些条件，则在类上使用结构将导致性能提升。

Answer 4

我认为在这里使用结构没有任何区别。特别是在查看了 TreeNode 的源代码之后，其中 TreeNode 的实例总是在构造函数和递归的 bottomUpTree 调用中复制。