diff options
| author | Alexander Korotkov <akorotkov@postgresql.org> | 2024-04-03 18:15:17 +0300 |
|---|---|---|
| committer | Alexander Korotkov <akorotkov@postgresql.org> | 2024-04-03 18:15:41 +0300 |
| commit | bf1e65080629e2b0ac47ffe245576da96eff8420 (patch) | |
| tree | d6eae6fbb978d03d72388d54a2ec86848a8979dd /src/backend/lib | |
| parent | 936e3fa3787a51397280c1081587586e83c20399 (diff) | |
| download | postgresql-bf1e65080629e2b0ac47ffe245576da96eff8420.tar.gz postgresql-bf1e65080629e2b0ac47ffe245576da96eff8420.zip | |
Use the pairing heap instead of a flat array for LSN replay waiters
06c418e163 introduced pg_wal_replay_wait() procedure allowing to wait for
the particular LSN to be replayed on standby. The waiters were stored in
the flat array. Even though scanning small arrays is fast, that might be a
problem at scale (a lot of waiting processes).
This commit replaces the flat shared memory array with the pairing heap,
which holds the waiter with the least LSN at the top. This gives us O(log N)
complexity for both inserting and removing waiters.
Reported-by: Alvaro Herrera
Discussion: https://postgr.es/m/202404030658.hhj3vfxeyhft%40alvherre.pgsql
Diffstat (limited to 'src/backend/lib')
| -rw-r--r-- | src/backend/lib/pairingheap.c | 18 |
1 files changed, 16 insertions, 2 deletions
diff --git a/src/backend/lib/pairingheap.c b/src/backend/lib/pairingheap.c index fe1deba13ec..7858e5e076b 100644 --- a/src/backend/lib/pairingheap.c +++ b/src/backend/lib/pairingheap.c @@ -44,12 +44,26 @@ pairingheap_allocate(pairingheap_comparator compare, void *arg) pairingheap *heap; heap = (pairingheap *) palloc(sizeof(pairingheap)); + pairingheap_initialize(heap, compare, arg); + + return heap; +} + +/* + * pairingheap_initialize + * + * Same as pairingheap_allocate(), but initializes the pairing heap in-place + * rather than allocating a new chunk of memory. Useful to store the pairing + * heap in a shared memory. + */ +void +pairingheap_initialize(pairingheap *heap, pairingheap_comparator compare, + void *arg) +{ heap->ph_compare = compare; heap->ph_arg = arg; heap->ph_root = NULL; - - return heap; } /* |