Well, if the exact same semantics were required (i.e. always evict the oldest buffer), then it's really O(M*n) where M is the number of bytes to evict, and n being the number of sublists; each sublist would have to be checked for each buffer that evicted. But, I agree, if that was the only concern then the extra comparisons _probably_ wouldn't be enough to be concerned about.

The bigger issue is how to lock the sublists. It seems heavy handed to lock all sublists, find the oldest buffer, evict it, and then unlock all sublists. But if each is locked, checked, then unlocked; each sublists' oldest buffer can change while the eviction thread is still iterating the sublists to find the oldest buffer.

So, while the current solution is not very elegant, it is simple, requires minimal locking, and appears to work well enough.