A Cache with Hybrid References
Sometimes you have to stop and think about the fact that allocating a new object every single time is too expensive. This is especially true for byte buffers and the like. In that case it makes sense to set up some kind of pool and pull objects from it, returning them once you’re done.
Maoni Stephens (http://blogs.msdn.com/maoni/) suggests using a 2-level cache:
use a 2-level caching mechanism:
· Maintain a strong reference for the cached items for x amount of time;
· After x amount of time is up, convert the strong references to weak references. Weak references will be considered to be kicked out of the cache before strong references are considered.
We have no reason to distrust this respected lady, who, by the way, is a performance PM in the CLR department.
There can be quite a few implementations of single-level caches. They all boil down to having some collection where objects get put back instead of being deleted, and from which they get pulled out for use. Most often it’s a queue, but sometimes it’s a stack or a plain list. The problem with such pools comes down to the actual load level. For example, say every minute 1000 objects get pulled from the pool and 1000 get returned. That means having around 1000 slots in the collection is enough for normal operation. If there’s a “spike” and 10000 objects get requested in a single second, 9000 new objects will get created and then returned to the pool afterward. Once the load drops back to 1000 operations per second, the pool will be sitting on 10000 objects — 10 times more than what’s actually needed. That’s wasted memory, and unnecessary fragmentation on top of it.
If our pool is queue-based (a First-In-First-Out model), all 10000 objects will keep getting cycled through and used, which isn’t great either. If the pool is stack-based (a First-In-Last-Out model), the 9000 excess objects simply won’t get used and will just sit there taking up memory.
A decent option can be using weak references in the pool’s collection. Such references will point to the pooled objects until the GC runs a collection, after which they become invalid. That’s acceptable, but not optimal, which is why it’s worth looking at hybrid approaches — the kind mentioned in the quote at the start of this post.
If you implement a 2-level cache the way Maoni suggests, you’ll need to walk through the collection at some interval and check each reference to see whether it’s time for it to move from Strong reference mode to Weak reference mode. There’s nothing inherently wrong with that kind of iteration, except that the operation isn’t thread-safe and has to be done under proper synchronization. The right thing to do is to put a lock around the whole collection-walking operation, as well as around every operation that takes objects out of or returns them to the cache.
As usual, that’s perfectly fine for normal people, but members of the Anonymous Paranoids society, which I happen to belong to, will find it a bit too expensive and unwarranted. 🙂
For a long time I looked into various complicated solutions — tried registering hybrid references in separate collections, made a copy of the pool’s collection before iterating it, and so on — but none of it satisfied me in terms of complexity or speed.
Today I finally found the way out, and it turned out to be pretty unexpected. I’d been stuck looking for some comprehensive solution, searching for approaches in “pure” programming, but the answer I found was sitting right on the surface.
It’s not exactly a “clean” trick: when an object is returned to the cache, I add a weak reference (WeakReference) to it into the pool, and a regular strong reference into a separate list. I don’t bother with subtleties like whether the object was already in that auxiliary list before, I never remove objects from it, and I never iterate over it. The only operation I perform on this auxiliary collection is clearing it out every few minutes.
That sounds a bit odd, but the idea is actually quite simple: I just don’t let objects in the pool die for a while. If an object gets pulled from the pool to be used, this collection has no effect on its lifetime at all. But if the object “sank to the bottom” — meaning it’s at the tail of the stack, or somewhere in the middle of the queue — we drop the one strong reference to it, and the weak reference dies the next time garbage gets collected.
So, some time after a “spike,” the pool will end up holding only as many objects as are actually needed for the current load, all the way down to being fully cleared out — every reference dying off — once the pool isn’t in use anymore.
This kind of memory usage strikes me as pretty close to optimal, even if the solution doesn’t 100% follow OOP conventions.
P.S. I’d recommend using a stack for the pool rather than a queue. This approach puts more load on the “near” objects of the stack, while the “far” ones almost never get used and can get cleaned up by the garbage collector. If you don’t want to allocate a lot of memory for this stack right away, it’s worth looking into the ideas of Justin Rogers.
P.P.S. To guarantee the desired object lifetime in the pool, it’s worth using something more elaborate than a single reference collection. For example, you could keep two collections and, in the cleanup method, swap the main one for the auxiliary one and drop the old auxiliary one. That way any object is guaranteed to hold a strong reference for at least the length of the cleanup interval.
Originally published 2008-05-03.