+Andres Freund <[email protected]>, I quote you below Hi Dhruv,
On 07/07/2026 21:41, Dhruv Aron wrote: > I would like to emphasize that I think the changes > here offer enough standalone benefits to merit their own patch. Agreed, I am looking forward to the patch. LOCKING Heikki Linnakangas [email protected] wrote at Jul 7, 2026, 8:14 PM > Hmm, we're now holding the buffer header lock much longer than before, > in InvalidateBuffer(). It's a spinlock, it really should not be held for > more than a few instructions. Is that paraphrasing storage/buffer/README? * Each buffer header contains a spinlock that must be taken when examining or changing fields of that buffer header. This allows operations such as ReleaseBuffer to make local state changes without taking any system-wide lock. We use a spinlock, not an LWLock, since there are no cases where the lock needs to be held for more than a few instructions. The problem with long locks is that it will keep other processes busy during contention, but since this is locking a single buffer, contention should be unlikely, and thus the effect should be small. DELETION OPTIMISATION OPPORTUNITY On 07/07/2026 21:41, Dhruv Aron wrote: > it enforces the invariant that *entries[x]* describes the page in buffer *x*. so this leads to two potential optimisations The first being using the buffer id to delete. void - BufTableDelete(BufferTag *tagPtr, uint32 hashcode) + BufferTableDeleteId(BufferTa , uint32 hashcode) while(id != BUF_TABLE_CHAIN_END) - if (BufferTagsEqual(&entries[id].tag, tagPtr)) + if (id == del_id)) The other would be to use a doubly linked list, increasing the entry memory footprint from 24 to 28 bytes, the deletion would require no iteration. + if(entries[id].prev != BUF_TABLE_CHAIN_END) + entries[entries[id].prev].next = entries[id].next + else buckets[bucket].head = entries[id].next MEMORY USAGE ANALYSIS On Jul 7, 2026 at 10:12 PM Heikki Linnakangas wrote > unpatched master, with shared_buffers='128 MB': > name | off | size | allocated_size > Shared Buffer Lookup Table | 141607040 | 926000 | 926108 > With this patch: > Shared Buffer Lookup Buckets | 141607040 | 65536 | 65644 > Shared Buffer Lookup Entries | 141672576 | 393216 | 393216 > > So the new hash table takes much less memory. That's nice because you > can then fit more in CPU caches. with 128MB the master uses 0x8000 buckets, patched uses 0x4000. Because 128MB = 0x4000 * 8192 master passes .nelems = 0x4000 + NUM_BUFFER_PARTITIONS increasing to the next power of two 0x8000. +static inline int +BufTableNumBuckets(void) +{ + return Max(NUM_BUFFER_PARTITIONS, pg_nextpower2_32(NBuffers)); +} + num_buckets = BufTableNumBuckets(); - size = NBuffers + NUM_BUFFER_PARTITIONS; - - ShmemRequestHash(.name = "Shared Buffer Lookup Table", - .nelems = size, - .ptr = &SharedBufHash, - .hash_info.keysize = sizeof(BufferTag), - .hash_info.entrysize = sizeof(BufferLookupEnt), - .hash_info.num_partitions = NUM_BUFFER_PARTITIONS, - .hash_flags = HASH_ELEM | HASH_BLOBS | HASH_PARTITION | HASH_FIXED_SIZE, + ShmemRequestStruct(.name = "Shared Buffer Lookup Buckets", + .size = (Size) num_buckets * sizeof(BufferLookupBucket), + .ptr = (void **) &buckets, + ); + + ShmemRequestStruct(.name = "Shared Buffer Lookup Entries", + .size = (Size) NBuffers * sizeof(BufferLookupEnt), + .ptr = (void **) &entries,Element size on 64-bit machines This slight misalignment might have played against the patched speed. Because for the master a power of two is at ~0.5 entry/bucket rate, and the patched version is at ~1 entry/bucket. BENCHMARK + int64 j = ord[i]; + BufTableInsert(&ptag[j], phash[j], bufids[j]); ... + sink += BufTableLookup(&ptag[j], phash[j]); ... + sink += BufTableLookup(&atag[j], ahash[j]); ... + BufTableDelete(&ptag[j], phash[j]); The benchmark covers a very particular case. The indices are shuffled but insert, lookup and delete, all use the same permutation. As a consequence of this. The lookup_hit test is always going to find each entry before its next entry in the bucket. The delete will always find the entry being deleted at bucket head. For lookup_miss it doesn't matter. It might seem hypocritical of me as I did exactly that when I worked on buffer pinning [1]. But in that case I was simulating prefetching, where pins follow roughly a fifo (or fpfu) order. MEMORY USAGE ANALYSIS + elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize); With .hash_info.keysize = sizeof(BufferTag) = 20 And MAXALIGN defined as the minimum multiple of 8 not smaller than the input. it was MAXALIGN(12) + MAXALIGN(20) = 16 + 24 = 40 assuming buckets = entries we would have another 8 bytes per bucket head and 8 bytes per segment, assuming buckets = 2 * entries we would have something like 56 + 2*8/256, not too far from allocated size. 128MB = 16384 entries, 926108 / 16384 = 56.52 Entries in the dynhash account for up to dir 0x8000 / 0x100 pointers = 1024 bucket heads 0x8000 pointers = 262144 and for the entries 0x4000 * 40 = 655360 918528 bytes close enough from the number quoted at the top In the patched version 0x4000 * 4 for indices = 65536 0x4000 * 24 for entries = 39216 THE REPLACED CODE Here I try to summarise what is being removed, it makes a lot of sense that it is faster. 1. external call hash_search_with_hash_value 2. freelist_idx: always computed, not used for lookup, pointer dereference+branch (((hctl)->num_partitions != 0) ? (hashvalue) % 32 : 0) 3. if (action ~ HASH_ENTER_*) branch and unlikely split 4. hash_initial_lookup: 4.1 calc_bucket: a branch and one or two pointer dereferences. 4.2 hashp->dir[bucket >> 8].?[bucket & 255]: two pointer dereferences and a branch (null check) 5. match function pointer, and keysize pointer references. 6 loop 5.1 currBucket->hashvalue == hashvalue possibly skipping 5.2 5.2 call match function by pointer (new version uses inline BufferTagsEqual). 6. update *foundPtr 7. switch (multiple branches?) 8. for insert/delete again pointer dereference + branch twice around SpinLock(Acquire/Release) The only bit of performance that was dropped is checking the hash code before the tag comparison. That could be a win if we think of comparing 32-bit then branching, successively. But if it is implemented with vector optimisation, the BufferTagEqual alone will probably be faster than trying to branch over it, not to mention the need to store the hash. [1] https://www.postgresql.org/message-id/flat/rfjyce5hmfkp2pbgjaxvmc76zy33kpokigbkwnounxfmz6uyd5%40vt7yxibmfy6n#e91277dae42b6774d8a65f7ac7480fc7 >
