Binary Heap vs（new）B-Heap：应该在CLR/.NET中实现吗？

Question

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

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

可以（或应该）.NET开发人员实现B-堆数据结构，使父子关系在同一虚拟内存页面内维持？如何或将在何处实施？

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

当服务器管理员在虚拟机中部署我的.NET应用程序时，此二进制堆优化是否有意义？如果是这样，它何时才有意义？ （物品数量等）

Answer 1

至少在某种程度上，BCL集合似乎考虑了分页问题。他们也考虑CPU缓存问题（这在某些方面是重叠的，因为内存的局部性会以不同的方式影响两者）。

请考虑Queue<T>将阵列用于内部存储。在纯粹的随机访问条件下（也就是说，从不存在寻呼或CPU缓存刷新的任何代价），这是一个糟糕的选择;队列几乎总是被单独添加到一个点，并从另一个点删除，因此内部实现作为单个链接列表几乎可以在各种方式中获胜（就此而言，就迭代队列而言 - 它也支持 - 在纯随机访问情况下，链表不应该比数组在这方面差得多）。在基于阵列的实现比单链表更好的情况下，恰恰是在考虑分页和CPU缓存时。该MS寻求的解决方案在纯随机访问情况下更糟，但在寻呼很重要的实际情况下效果更好，因此他们正在关注寻呼的影响。

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

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

这只是我从我看过的东西中脱颖而出的几件事情。我敢打赌，这些问题在.NET团队的许多其他地方也被考虑过。与其他框架一样。考虑到一个重要的性能问题，就是他的Java无锁哈希表（我真的完成了对C＃实现的检查），除了无锁并发性（整个练习的重点）之外，他们多次提到cache-lines ;而且这也是他不会拒绝的另一个表现问题！

请考虑一下，大多数藏品的大多数用途无论如何都会放在一个页面中！

如果你正在实现自己的收藏，或者将标准收藏放到特别重要的地方，那么这些都是你需要考虑的事情（有时候“不是问题”就足够了，有时候不是）但这并不意味着他们从BCL中得到的东西并没有被考虑过。

Answer 2

如果您有特别特殊的场景和算法，那么您可能会从受益于这种优化。

但一般来说，（在我想补充的CLR，即在托管代码的顶部）重新实现CLR框架的核心部分，当你更有效地比CLR团队做这样做的机会是极其渺茫。所以我不会推荐它，除非你已经分析了你当前的实现，并且已经确定了与数据在存储器中的地点相关的问题。即使如此，通过调整算法，使用CLR内存管理方案更好地工作，然后尝试绕过或解决此问题，您将获得更大的回报。