C# - 固定/内联数组

Question

我正在用 C# 编写一个 B+ 树实现，我为我的应用程序选择的树实现有一个非常特定的结构，它是缓存敏感的。为了实现这些属性，它对树节点有严格的布局策略。

我想要的只是使用 C# 的 fixed 来表达固定大小缓冲区的关键字:

public abstract class Tree<K, T> { }
sealed class Node<K, T> : Tree<K, T>
{
    Node<K, T> right;
    fixed Tree<K, T> nodes[127]; // inline array of 128 nodes
}

不幸的是，固定大小的缓冲区只能用于原始值类型，如 int 和 float。仅使用普通数组会添加指针间接寻址，这会破坏此树类型的缓存友好属性。

我也无法生成 128 个字段并使用指针算法来提取我想要的字段，因为 there are no conversions between pointer types and managed objects .

剩下的唯一一件事就是用一个索引器生成 128 个字段，该索引器根据开关选择正确的字段(这不会很快)，或者将其编写为 C 库并使用 P/Invoke，这也会破坏性能。

有什么建议吗？

Answer 1

使用 C++/CLI。这使您可以完全控制布局，就像 C 一样，但是托管/非托管转换的成本比 p/invoke 低得多(可能根本没有额外成本)。

不幸的是，托管代码不太适合“缓存敏感”的工作:在托管堆内，您无力避免虚假共享。 C++/CLI 允许您使用非托管分配器，因此您不仅可以保持数据连续，还可以与缓存行对齐。

---

另请注意:使用 class 关键字会创建一个“引用类型”，它已经添加了您想要避免的间接级别。通过一些重组，您可能能够使用 struct 和数组，并且没有比您建议的代码更多的间接访问。