11

对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;
}

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

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

问题：还有更多吗？

此外，由于我不会想到在 C# 中以这种方式定义树节点（感谢 Xamarin！）还有哪些其他数据结构可以从以非显而易见的方式使用结构中受益？（尽管这有点离题且开放式。）

4

4 回答 4

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.

于 2012-12-10T19:23:27.577 回答
0

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

IMO this makes the comparision pretty meaningless.

于 2012-05-17T12:16:47.307 回答
0

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

Microsoft 关于在类和结构之间进行选择的指南：

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

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

于 2012-05-17T11:27:35.223 回答
-1

我不认为在这里使用 struct 有什么不同。特别是在查看 TreeNode 的源代码后，TreeNode 的实例总是在构造函数和递归的 bottomUpTree 调用中复制。

于 2012-05-17T07:27:21.833 回答