c# - 构造内存 hack 以重叠对象引用 - 这可能吗？

Question

我猜这个问题的答案将是“这不可能，切换到 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;
}

上面给出了以下运行时错误

Could not load type 'BranchData' from assembly 'WindowsFormsApplication1, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null' because it contains an object field at offset 0 that is incorrectly aligned or overlapped by a non-object field.

我可以使用一个单独的数组来存储叶数据，并使用索引指向该数组，但是我有 2 次内存查找(对于那些肯定是遥远的内存区域)。一个用于叶数组中的位置以获取引用，一个用于获取叶数据。如果我能实现这种重叠，我就可以摆脱其中一个查找。

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

Answer 1

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

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

问题是:收集器无法判断您的联合是否存储了该指针。如果不是，则存在其他成员的值看起来像是对 GC 的有效对象引用的风险。这非常非常糟糕。

存储不安全的 LeafData* 在技术上是可行的，但这需要固定 LeafData 对象。当树很大时，那是行不通的，当什么都不能移动时，GC 就会崩溃。将 LeafData 数据存储在非托管内存中是更难的事情，到那时你就可以开始编写 C++ 代码了。您唯一可以做的另一件事是将 LeafData 存储在节点本身中，作为一个结构，您不太可能对适合度感到满意。

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