c# - 二进制堆与(新)B 堆 : Should it be implemented in the CLR/. NET，以及在哪里？

Question

以下文章讨论了另一种堆结构，该结构考虑到大多数服务器都是虚拟化的，因此大多数内存都被分页到磁盘。

http://queue.acm.org/detail.cfm?id=1814327

.NET 开发人员能否(或应该)实现 B 堆数据结构，以便在同一虚拟内存页面中维护父子关系？如何或在哪里实现？

澄清
换句话说，.NET 中是否需要这种类型的数据结构作为原始类型？的确，它应该在 CLR 或 p/invoke 中本地实现。

当服务器管理员在虚拟机中部署我的 .NET 应用程序时，这种二进制堆优化是否有意义？如果是这样，什么时候有意义？ (对象数量等)

Answer 1

至少在某种程度上，BCL 集合似乎确实考虑了分页问题。他们还考虑了 CPU 缓存问题(这在某些方面是重叠的，因为内存的位置会影响两者，尽管方式不同)。

考虑 Queue<T>使用数组作为内部存储。在纯粹的随机访问术语中(也就是说，分页或 CPU 缓存刷新从来没有任何成本)这是一个糟糕的选择；队列几乎总是在一个点被单独添加并在另一个点被移除，因此作为单向链表的内部实现几乎在所有方面都会获胜(就此而言，就遍历队列而言 - 它也支持- 在纯随机访问的情况下，链表在这方面不应该比数组差很多)。基于数组的实现比单链表更好的地方恰恰是在考虑分页和 CPU 缓存时。该 MS 寻求的解决方案在纯随机访问情况下更糟糕，但在分页很重要的实际情况下更好，因此他们正在关注分页的影响。

当然，从外面看这并不明显——而且不应该如此。从外部看，我们想要像队列一样工作的东西；使内部高效是一个不同的问题。

这些担忧也以其他方式得到解决。例如，GC 的工作方式最大限度地减少了必要的分页数量，因为它的移动对象不仅可以减少碎片，还可以减少页面错误。其他集合的实现方式也比最直接的解决方案建议的分页频率低。

这只是我看过的几件让我印象深刻的事情。我敢打赌，在 .NET 团队工作的许多其他地方也考虑了这些问题。与其他框架一样。考虑到除了无锁并发(练习的重点)之外，Cliff Click 在他的 Java 无锁哈希表(我真的完成了检查我的 C# 实现)方面反复提到的一个重要性能问题是缓存行;这也是他没有忽视的另一个性能问题!

还请考虑，无论如何，大多数集合的大部分用途都将适合一个页面!

如果您正在实现自己的集合，或者将标准集合投入特别频繁的使用，那么这些就是您需要考虑的事情(有时“不，这不是问题”就足够了，有时则不然)但是这并不意味着他们还没有考虑到我们从 BCL 得到的东西。