內存壓縮分配器

Question

我想知道，有沒有項目/至少一些關於內存壓縮和內存分配器組合的研究（當然是犧牲一些速度）？

例如，假設場景：我們必須處理一棵巨大的樹。這棵樹不適合記憶。通過壓縮分配器，我們可以適應任何樹。

當然，可以使用迭代方法而無需一次構建樹，但我的問題純粹是理論上的（今天）。

可能的解引用將需要特殊的宏/模板，以便分配器能夠解壓縮選定的區域。但是如果一個地區參考另一個地區等呢？必須有一些非常複雜的算法，可能只在託管語言中解析（但Boehm能夠爲C++製作GC）。

或者它可能太複雜/慢（即使與保存的內存相比）在所有？ 虛擬內存&交換可能非常緩慢，特別是在垃圾收集環境中。最近一個1 GB的應用程序使整個操作系統無響應...因此，內核級別的機制不一定高效。

你可以想到它（我仍然試圖向你保證這不是一個非常愚蠢的想法），因爲反對式快速用戶模式futexes與慢速本地互斥，快速用戶模式綠色線程（如Erlang中高達2000萬機器上的同步過程）與較慢的原生線程等。

Answer 1

請參閱The Case for Compressed Caching in Virtual Memory Systems瞭解有關壓縮虛擬內存的一些相關概念。這個想法有一個Linux實現（compcache）。

我不是很有意義在分配器中進行壓縮。分配器的工作是回饋我分配多少個字節（並避免堆碎片和所有其他爵士）。它不知道我將要存入哪些數據。如果內存非常緊張，那麼內存壓縮應該由應用程序執行。

內存壓縮的一個很好的例子可以通過使用文檔here的巧妙技巧Redis來看出。