Hi!
I didn't suggest log scale of usages, but rather "replacement-period based" increment: usage count could be incremented at most once in NBlocks/32 replaced items. Once it is incremented, its "replacement time" is remembered, and next NBlocks/32 replacements usage count of this buffer doesn't increment.
This way, increment is synchronized with replacement activity.
But you loose difference between "touched once" and "actively used". Log scale of usage solves this: usage count grows logarithmically, but drains linearly.
Digging further, I suggest as improvement of GClock algorithm:
- placing new buffer with usage count = 0 (and next NBlock/32 replacements its usage count doesn't increased)
- increment not by 1, but by 8 (it simulates "hot queue" of popular algorithms) with limit 32.
- scan at most 25 buffers for eviction. If no buffer with zero usage count found, the least used buffer (among scanned 25) is evicted.
(new buffers are not evicted during their first NBlock/32 replacements).
I do not understand where these numbers come from...
Best regards, Andrey Borodin.
