二叉堆与（新）B 堆：是否应该在 CLR/.NET 中实现，在哪里实现？
以下文章讨论了另一种堆结构，该结构考虑到大多数服务器都是虚拟化的，因此大多数内存都会分页到磁盘。
http://queue.acm.org/detail.cfm?id=1814327
.NET 开发人员可以（或应该）实现 B-Heap 数据结构，以便在同一虚拟内存页中维护父子关系吗？如何或在哪里实施？
澄清
换句话说，.NET 中是否需要这种类型的数据结构作为原始类型？确实，它应该在 CLR 中本地实现或在 ap/invoke 中实现。
当服务器管理员在虚拟机中部署我的 .NET 应用程序时，这种二进制堆优化有意义吗？如果是这样，什么时候有意义？ （物体数量等）
The following article discusses an alternative heap structure that takes into consideration that most servers are virtualized and therefore most memory is paged to disk.
http://queue.acm.org/detail.cfm?id=1814327
Can (or should) a .NET developer implement a B-Heap data structure so that parent-child relationships are maintained within the same Virtual Memory Page? How or where would this be implemented?
Clarification
In other words, is this type of data structure needed within .NET as a primimitive type? True it should be implemented in either natively in the CLR or in a p/invoke.
When a server administrator deploys my .NET app within a virtual machine, does this binary heap optimization make sense? If so, when does it make sense? (number of objects, etc)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
至少在某种程度上，BCL 集合似乎确实考虑了分页问题。他们还考虑了 CPU 缓存问题（这在某些方面是重叠的，因为内存的局部性可以影响两者，尽管以不同的方式）。
考虑
Queue使用数组进行内部存储。从纯粹的随机访问角度来看（也就是说，从来没有任何分页或 CPU 缓存刷新成本），这是一个糟糕的选择；队列几乎总是只在一个点添加到另一个点，因此作为单链表的内部实现几乎在所有方面都会获胜（就此而言，就遍历队列而言 - 它也支持- 在纯随机访问的情况下，链表在这方面不应该比数组差很多）。正是在考虑分页和 CPU 缓存时，基于数组的实现比单链表的表现更好。该 MS 寻求的解决方案在纯随机访问情况下更差，但在寻呼很重要的现实情况下更好，因此他们正在关注寻呼的影响。当然，从外部来看，这并不明显——也不应该如此。从外部来看，我们想要像队列一样工作的东西；使内部高效是一个不同的问题。
这些担忧也可以通过其他方式得到解决。例如，GC 的工作方式最大限度地减少了必要的分页量，因为它的移动对象不仅可以减少碎片，还可以减少页面错误。其他集合的实现方式也使分页频率低于最直接的解决方案所建议的频率。
这只是我所看到的一些事情中最突出的一些。我敢打赌，.NET 团队工作中的许多其他地方也考虑到了此类问题。其他框架也是如此。考虑一下 Cliff Click 在他的 Java 无锁哈希表（我真的已经检查完我的 C# 实现）中反复提到的一个重大性能问题，除了无锁并发性（练习的全部要点）之外，就是缓存行;这也是他没有忽视的另一个性能问题！
还要考虑到，大多数集合的大多数用途无论如何都适合一页！
如果您正在实现自己的集合，或者特别频繁地使用标准集合，那么您需要考虑这些事情（有时“不，不是问题”就足够思考，有时则不然），但事实并非如此。但这并不意味着我们还没有从 BCL 中得到什么来考虑它们。
To at least a certain extent, BCL collections do seem to take paging concerns into account. They also take CPU cache concerns into account (which overlaps in some regard, as locality of memory can affect both, though in different ways).
Consider that
Queue<T>uses arrays for internal storage. In purely random-access terms (that is to say, where there is never any cost for paging or CPU cache flushing) this is a poor choice; the queue will almost always be solely added to at one point and removed from at another and hence an internal implementation as a singly linked list would win in almost every way (for that matter, in terms of iterating through the queue - which it also supports - a linked list shouldn't do much worse than an array in this regard in a pure-random-access situation). Where array-based implementation fares better than singly-linked-list is precisely when paging and CPU cache are considered. That MS went for a solution that is worse in the pure-random-access situation but better in the real-world case where paging matters, so that they are paying attention to the effects of paging.Of course, from the outside that isn't obvious - and shouldn't be. From the outside we want something that works like a queue; making the inside efficient is a different concern.
These concerns are also met in other ways. The way the GC works, for example, minimises the amount of paging necessary as its moving objects not only makes for less fragmentation, but also makes for fewer page faults. Other collections are also implemented in ways to make paging less frequent than the most immediate solution would suggest.
That's just a few things that stand out to me from things I have looked at. I'd bet good money such concerns are also considered at many other places in the .NET teams work. Likewise with other frameworks. Consider that the one big performance concern Cliff Click mentions repeatedly in terms of his Java lock-free hashtable (I really much finish checking my C# implementation) apart from those of lock-free concurrency (the whole point of the exercise) is cache-lines; and it's also the one other performance concern he doesn't dismiss!
Consider also, that most uses of most collections are going to fit in one page anyway!
If you are implementing your own collections, or putting a standard collection into particularly heavy use, then these are things you need to think about (sometimes "nah, not an issue" is enough thinking, sometimes it isn't) but that doesn't mean they aren't already thought about in terms of what we get from the BCL.
如果您有一个特别特殊的场景和算法，那么您可能会从这种优化中受益。
但一般来说，当重新实现 CLR 框架的核心部分（我可能会在 CLR 之上添加，即在托管代码中）时，您比 CLR 团队更高效地完成任务的机会非常渺茫。因此，我不会推荐它，除非您已经对当前实现进行了概要分析，并且已经明确识别了与内存中数据位置相关的问题。即便如此，通过调整算法以更好地与 CLR 内存管理方案配合，然后尝试绕过或解决它，您也会获得更大的收益。
if you have an especially special-case scenario and algorithm then you might benefit from that kind of optimization.
But generally speaking, when reimplementing core parts of the CLR framework (on top of the CLR I might add, ie in managed code) your chances of doing it more efficiently than the CLR team did are incredibly slim. So I wouldn't recommend it unless you have already profiled the heck out of your current implementation and have positively identified issues related to locality of data in memory. And even then, you will get more bang for your buck by tweaking your algorithm to work better with the CLR memory management scheme then trying to bypass or work around it.