下面的文章討論了一種替代堆結構，它考慮到大多數服務器都是虛擬化的，因此大多數內存都被分頁到磁盤。Binary Heap vs（new）B-Heap：應該在CLR/.NET中實現嗎？
http://queue.acm.org/detail.cfm?id=1814327
可以（或應該）.NET開發人員實現B-堆數據結構，使父子關係在同一虛擬內存頁面內維持？如何或將在何處實施？
澄清
換句話說，是這種類型的數據結構內.NET需要作爲primimitive類型？實際上，它應該在CLR中本地實現，或者在p/invoke中實現。
當服務器管理員在虛擬機中部署我的.NET應用程序時，此二進制堆優化是否有意義？如果是這樣，它何時纔有意義？ （物品數量等）
至少在某種程度上，BCL集合似乎考慮了分頁問題。他們也考慮CPU緩存問題（這在某些方面是重疊的，因爲內存的局部性會以不同的方式影響兩者）。
請考慮Queue<T>將陣列用於內部存儲。在純粹的隨機訪問條件下（也就是說，從不存在尋呼或CPU緩存刷新的任何代價），這是一個糟糕的選擇;隊列幾乎總是被單獨添加到一個點，並從另一個點刪除，因此內部實現作爲單個鏈接列表幾乎可以在各種方式中獲勝（就此而言，就迭代隊列而言 - 它也支持 - 在純隨機訪問情況下，鏈表不應該比數組在這方面差得多）。在基於陣列的實現比單鏈表更好的情況下，恰恰是在考慮分頁和CPU緩存時。該MS尋求的解決方案在純隨機訪問情況下更糟，但在尋呼很重要的實際情況下效果更好，因此他們正在關注尋呼的影響。
當然，從外部看並不明顯 - 不應該這樣。從外面看，我們想要一個像隊列一樣工作的東西;使內部高效是一個不同的問題。
這些問題也以其他方式得到滿足。例如，GC工作的方式可以最大限度地減少所需的分頁數量，因爲其移動對象不僅可以減少碎片，還可以減少頁面錯誤。其他集合也以實現分頁的方式比最直接的解決方案建議的頻率更少。
這只是我從我看過的東西中脫穎而出的幾件事情。我敢打賭，這些問題在.NET團隊的許多其他地方也被考慮過。與其他框架一樣。考慮到一個重要的性能問題，就是他的Java無鎖哈希表（我真的完成了對C＃實現的檢查），除了無鎖併發性（整個練習的重點）之外，他們多次提到cache-lines ;而且這也是他不會拒絕的另一個表現問題！
請考慮一下，大多數藏品的大多數用途無論如何都會放在一個頁面中！
如果你正在實現自己的收藏，或者將標準收藏放到特別重要的地方，那麼這些都是你需要考慮的事情（有時候「不是問題」就足夠了，有時候不是）但這並不意味着他們從BCL中得到的東西並沒有被考慮過。
謝謝+1，內存佈局是否與可能最終分頁到磁盤的內容對齊？ +1的MSFT如果他們已經實施了這一點，並從未告訴我們。我不知道Mono的實施是什麼樣的。 – LamonteCristo 2010-10-15 02:48:47
關於對齊我不知道，但在我查看細節的情況下，細節正在以適合於該抽象級別的方式利用分頁和緩存行，就像堆B *樹一樣在鏈接到的文章中做了一個B堆。 '隊列
......基於'HashSet
如果您有特別特殊的場景和算法，那麼您可能會從受益於這種優化。
但一般來說，（在我想補充的CLR，即在託管代碼的頂部）重新實現CLR框架的核心部分，當你更有效地比CLR團隊做這樣做的機會是極其渺茫。所以我不會推薦它，除非你已經分析了你當前的實現，並且已經確定了與數據在存儲器中的地點相關的問題。即使如此，通過調整算法，使用CLR內存管理方案更好地工作，然後嘗試繞過或解決此問題，您將獲得更大的回報。
問題是關於Bin Heap數據結構，而不是關於（替換）託管堆。 – 2010-10-04 12:13:30
我認爲對這種情況有一個CLR支持是很好的......從.NET開發人員抽象出實現細節的地方。也許它可以在CLR中實現。也許它可以在圖書館中實施。無論哪種方式，這是一個有趣的優化。 – LamonteCristo 2010-10-04 22:13:07
如果您正在研究需要具有幾億條條目的優先隊列，則需要付費進行調查。請注意，該文章是關於服務器場的。 – 2010-10-03 18:45:37