XobotOS：C＃バイナリツリーベンチマークで構造体が使用されるのはなぜですか？

Question

xobotosのreputed performance gainsについて興味があるので、私はバイナリツリーbenchmark codeをチェックアウトしました。

binary tree nodeのJavaバージョンは次のとおりです。

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

C# versionは次のとおりです。

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

    private Next next; 
    private int item; 
} 

私はここに構造体を使用する利点は次と前のポインタ以来、何であるか思ったんだけどそれでもクラスにカプセル化されています。

まあ、ものがある - 彼らは左と右のポインタを必要としないため、リーフ・ノードは、純粋な値型です。半分のノードが葉である典型的なバイナリツリーでは、オブジェクトの数が50％削減されます。それでも、掲載されているパフォーマンスの向上ははるかに大きいようです。

質問：これ以上はありますか？また

、私はC＃でツリーノードをこのように定義すると考えていないので（感謝Xamarin！）データ構造は非自明な方法で構造体を使用して恩恵を受けることができ、他のどのような？ （つまり、ビットオフトピックだと、オープンエンドにもかかわらず。）

Answer 1

これは、2つのノードを1つの割り当てにグループ化します。理想的には、合計割り当ての数を半分にします。

IMOこれは、比較がかなり無意味になります。

Answer 2

私はここで構造体を使用すると、まったく違いがあることと思ういけません。特にTreeNodeのソースコードを見ると、TreeNodeのインスタンスは常にコンストラクタと再帰的なbottomUpTree呼び出しでコピーされます。

Answer 3

構造体は、ヒープの代わりにスタックに割り当てることができます（ただし、いずれの場合もそうではありません）。つまり、スコープから外れるとすぐに割り当てが解除されます。つまり、ガベージコレクタはそのシナリオに関与しません。その結果、メモリの負荷が軽減され、ガベージコレクションが少なくなります。また、スタックは（ほとんど）連続したメモリ領域であるため、そのアクセスはより良い局所性を持ち、CPUレベルでキャッシュヒット率を向上させることができます。 choosing between classes and structures上

マイクロソフトのガイドライン：

• 構造は（16バイト、一般的に）小さく、短命が
• 彼らはその後、オーバー構造を使用して、それらが満たされている場合は不変

、する必要がありますする必要がありますクラスによってパフォーマンスが向上します。

Answer 4

私はちょうどこの奇妙なコードにまたがって同じ質問をしました。 Javaバージョンと一致するようにコードを変更すると、わずかに遅くなります。私は、 'struct TreeNode'の大部分はボトムの行を除いて、とにかくボックス化されて割り当てられると信じています。しかし、各ノードは、boxed TreeNodeとクラスNextの2つの割り当てをもたらす。割り当ての節約はすぐに消えます。 IMO、これはstructの適切な使用ではありません。