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 个内存查找（对于那些肯定是遥远的内存区域）。一个用于叶子数组中的位置以获取引用，一个用于获取叶子数据。如果我能实现这种重叠，我就会摆脱其中一个查找。

我能够固定对象并使用不安全的代码来解决这个问题。速度是这里的关键因素。

4

2 回答 2

18

此限制在托管代码中非常重要。问题是您的Node成员是一个对象引用。运行时的指针。它与其他字段重叠。

垃圾收集器需要能够找到该指针。两者都必须知道堆上存在对 LeafData 对象的实时引用。并在堆压缩时移动 LeafData 对象时更新该指针。

问题是：收集器无法判断您的联合是否存储了该指针。如果不是这样，那么其他成员的值就有可能看起来像是对 GC 的有效对象引用。这非常非常糟糕。

存储不安全的 LeafData* 在技术上是可行的，但这需要固定 LeafData 对象。当树很大时，那是行不通的，当无法再移动任何东西时，GC 就会崩溃。将 LeafData 数据存储在非托管内存中更进一步，您将开始编写 C++ 代码。您唯一可以做的另一件事是将 LeafData 作为结构存储在节点本身中，您不太可能对拟合感到满意。

请注意，您应该避免这些未对齐的字段，当字段跨越 L1 高速缓存行边界时，您会被猛烈抨击。将 SplitIndex 放在 HighIndex之后，这样就不会发生这种情况。

于 2013-07-23T17:39:30.057 回答
2

我不知道这在实践中是否更快，但它在托管代码中的内存查找更少。

（我不知道的 CLR 本身中可能有更多查找。）

也就是说，您可以使用GCHandle非托管数据覆盖托管引用：

[StructLayout(LayoutKind.Explicit)]
public struct Data
{
    [FieldOffset(0)]
    public IntPtr NativeData;
    [FieldOffset(0)]
    public GCHandle Handle;
}


Data data = ...;
((YourClass)data.Handle.Target).Blah();
于 2013-08-29T01:24:13.443 回答