Re: Lockless queue of waiters in LWLock

Hi Andres,

Thank you for your feedback.

On Tue, Nov 1, 2022 at 2:15 AM Andres Freund <andres(at)anarazel(dot)de> wrote:
> On 2022-10-31 14:38:23 +0400, Pavel Borisov wrote:
> > If the lock state contains references to the queue head and tail, we can
> > implement a lockless queue of waiters for the LWLock. Adding new items to
> > the queue head or tail can be done with a single CAS operation (adding to
> > the tail will also require further setting the reference from the previous
> > tail). Given that there could be only one lock releaser, which wakes up
> > waiters in the queue, we can handle all the concurrency issues with
> > reasonable complexity.
>
> Right now lock releases happen *after* the lock is released.

That makes sense. The patch makes the locker hold the lock, which it's
processing the queue. So, the lock is held for a longer time.

> I suspect that is
> at least part of the reason for the regression you're seeing. It also looks
> like you're going to need a substantially higher number of atomic operations -
> right now the queue processing needs O(1) atomic ops, but your approach ends
> up with O(waiters) atomic ops.

Hmm... In the patch, queue processing calls CAS once after processing
the queue. There could be retries to process the queue parts, which
were added concurrently. But I doubt it ends up with O(waiters) atomic
ops. Pavel, I think we could gather some statistics to check how many
retries we have on average.

> I suspect it might be worth going halfway, i.e. put the list head/tail in the
> atomic variable, but process the list with a lock held, after the lock is
> released.

Good idea. We, anyway, only allow one locker at a time to process the queue.

------
Regards,
Alexander Korotkov