While the single benchmark provided probably isn't statistically significant, I noticed that performance on system with 4 cores of less is worse with this patch.

If this is actually symptom of the patch, would it be possible to toggle lock behavior depending on available cores?

Currently, the number of sublists created is equal to the number of cores on the system.

While it'd be fairly trivial to extend the code to make it easy for an admin to define the number of sublists, I don't have any reason to believe that'd be a useful knob to export.

The batched log approach mentioned in the comments is also interesting. Possibly not directly applicable to cache page eviction policy where I expect the pressure to free up an old page to make space for data is more time-critical, but a useful model to keep in mind, alongside the probabilistic list sharding described in the article.

That's certainly an interesting approach.

It's got a maximum latency problem though.

If for some reason the unlucky thread that acquires the lock cannot process the batch faster than other threads are adding.... well that ends poorly

That would require a write rate very atypical for a cache and easily mitigated, though largely an almost impossible scenario.

Is the difference between O(1) and O(n) where n=number of cores really that big?

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.