On 22 June 2014 16:09, Andres Freund <andres@2ndquadrant.com> wrote:
>> So if we treat the fast array as a circular LRU, we get
>> * pinning a new buffer when array has an empty slot is O(1)
>> * pinning a new buffer when array is full causes us to move the LRU
>> into the hash table and then use that element
>> * unpinning a buffer will most often be O(1), which then leaves an
>> empty slot for next pin
>>
>> Doing it that way means all usage is O(1) apart from when we use >8
>> pins concurrently and that usage does not follow the regular pattern.
>
> Even that case is O(1) in the average case since insertion into a
> hashtable is O(1) on average...
>
> I've started working on a patch that pretty much works like that. It
> doesn't move things around in the array, because that seemed to perform
> badly. That seems to make sense, because it'd require moving entries in
> the relatively common case of two pages being pinned.
> It moves one array entry (chosen by [someint++ % NUM_ENTRIES] and moves
> it to the hashtable and puts the new item in the now free slot. Same
> happens if a lookup hits an entry from the hashtable. It moves one
> entry from the array into the hashtable and puts the entry from the
> hashtable in the free slot.
Yes, that's roughly how the SLRU code works also, so sounds good.
> That seems to work nicely, but needs some cleanup. And benchmarks.
ISTM that microbenchmarks won't reveal the beneficial L2 and RAM
effects of the patch, so I suggest we just need to do a pgbench, a
2-way nested join and a 10-way nested join with an objective of no
significant difference or better. The RAM and L2 effects are enough to
justify this, since it will help with both very small and very large
configs.
-- Simon Riggs http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services