15

これに対する答えは、「それは不可能です。C++ に切り替えてください」になると思います。でも、とにかく捨てようと思いました。

私は大規模な二分木を扱っています。ツリーを反復処理するときにメモリの局所性を支援するために使用する分岐ノードを表す構造体の配列があります。

メモリを少し節約して、キャッシュの局所性を向上させるために、リーフ ノードのオブジェクト参照をオーバーラップさせることを考えています。そのオブジェクト参照は、すべてのリーフ データを指します。基本的には、次のようなものです。

[StructLayout(LayoutKind.Explicit)]
struct BranchData
{
    [FieldOffset(0)] // 1 byte
    internal byte SplitIndex;
    [FieldOffset(1)] // 4 bytes
    internal float SplitValue;
    [FieldOffset(5)] // 4 bytes
    internal int LowIndex;
    [FieldOffset(9)] // 4 bytes
    internal int HighIndex;
    [FieldOffset(0)] // 8 bytes (We're working with x64 here)
    internal LeafData Node;
}

上記は、次の実行時エラーを与えます

アセンブリ 'WindowsFormsApplication1、Version=1.0.0.0、Culture=neutral、PublicKeyToken=null' から型 'BranchData' を読み込めませんでした。オフセット 0 のオブジェクト フィールドが正しく配置されていないか、オブジェクト以外のフィールドと重複しているためです。

別の配列を使用してリーフ データを格納し、インデックスを使用してその配列を指すこともできますが、2 つのメモリ ルックアップがあります (メモリの離れた領域であることは確かです)。1 つは参照を取得するためのリーフ配列内の場所で、もう 1 つはリーフ データを取得するためのものです。このオーバーラップを達成できれば、それらのルックアップの 1 つを取り除きます。

オブジェクトを固定し、安全でないコードを使用してこの問題を解決できます。ここではスピードが重要な要素です。

4

2 に答える 2

18

この制限は、マネージ コードでは非常に基本的なものです。問題は、Nodeメンバーがオブジェクト参照であることです。実行時のポインター。他のフィールドと重複しています。

ガベージ コレクタは、そのポインタを見つけられる必要があります。ヒープ上の LeafData オブジェクトへのライブ参照があることを知るために両方が必要です。そして、ヒープが圧縮されたときに LeafData オブジェクトが移動されたときにそのポインターを更新します。

問題は、ユニオンがそのポインターを格納しているかどうかをコレクターが判断できる方法がないことです。そうでない場合、他のメンバーの値がGC への有効なオブジェクト参照のように見えるリスクがあります。そして、それは非常に悪いことです。

安全でない LeafData* を保存することは技術的に可能ですが、それには LeafData オブジェクトを固定する必要があります。ツリーが大きい場合、それは機能しません。何も移動できなくなると、GC が失敗します。LeafData データをアンマネージ メモリに格納することは、うさぎの穴の先にあり、それまでに C++ コードを書き始めていることになります。他にできることは、LeafData を構造体としてノード自体に格納することだけですが、適合性に満足する可能性はほとんどありません。

フィールドが L1 キャッシュ ラインの境界にまたがると、かなり激しく叩かれます。これが起こらないように、HighIndex の後にSplitIndex を配置します。

于 2013-07-23T17:39:30.057 に答える