Allocators with in-memory compression

I am wondering, are there projects/at least some research on combination of in-memory compression and memory allocators (at the expense of some speed, of course)?

For example, imagine the scenario: we have a huge tree we must process. This tree doesn't fit into memory. With compressing allocator, we're able to fit pretty any tree.

Of course, one can use iterational approach without constructing the tree at once, but my question is purely theoretical (for today).

Probably dereferencing would need special macros/templates so that the allocator would be able to unpack the selected regions. But what if one region references another region, etc.? There must be some very complicated algorithm, probably resolved only in managed languages (but Boehm was able to make a GC for C++!)

Or maybe it's so complicated/slow (even compared to saved memory) that isn't worth at all? Virtual memory & swapping may be very slow, especially in garbage-collected environments. Recently a 1 gb app was making the whole OS unresponsive... So kernel-level mechanisms aren't necessarily efficient.

You can think of it (i'm still trying to assure you that's not a very stupid idea) as of opposition fast 开发者_如何学编程usermode futexes vs. slow native mutexes, fast usermode green threads (as in Erlang with up to 20 million simultanous processes on a machine) vs. slower native threads etc.

See The Case for Compressed Caching in Virtual Memory Systems for some related ideas that talk about compressing virtual memory. There's a Linux implementation of this idea (compcache).

I'm not it even makes sense to do compression in an allocator. An allocators jobs is to give back how many bytes I ask it to allocate (and avoid heap fragmentation and all that other jazz). It has no knowledge of what data I'm going to put in that memory. If memory is really tight then in-memory compression should be performed by the application.

A good example of in-memory compression can be seen by the clever tricks Redis uses documented here.