Re: Lockless queue of waiters in LWLock

Hi, Pavel!

On Thu, Nov 3, 2022 at 1:51 PM Pavel Borisov <pashkin(dot)elfe(at)gmail(dot)com> wrote:
> > I'm planning to gather more detailed statistics on different
> > LWLockAcquire calls soon to understand prospects for further
> > optimizations.
>
> So, I've made more measurements.
>
> 1. Applied measuring patch 0001 to a patch with lockless queue
> optimization (v2) from [0] in this thread and run the same concurrent
> insert test described in [1] on 20 pgbench connections.
> The new results for ProcArray lwlock are as follows:
> exacq 45132 // Overall number of exclusive locks taken
> ex_attempt[0] 20755 // Exclusive locks taken immediately
> ex_attempt[1] 18800 // Exclusive locks taken after one waiting on semaphore
> ex_attempt[2] 5577 // Exclusive locks taken after two or more
> waiting on semaphore
> shacq 494871 // .. same stats for shared locks
> sh_attempt[0] 463211 // ..
> sh_attempt[1] 29767 // ..
> sh_attempt[2] 1893 // .. same stats for shared locks
> sh_wake_calls 31070 // Number of calls to wake up shared waiters
> sh_wakes 36190 // Number of shared waiters woken up.
> GroupClearXid 55300 // Number of calls of ProcArrayGroupClearXid
> EndTransactionInternal: 236193 // Number of calls
> ProcArrayEndTransactionInternal
>
> 2. Applied measuring patch 0002 to a Andres Freund's patch v3 from [2]
> and run the same concurrent insert test described in [1] on 20 pgbench
> connections.
> The results for ProcArray lwlock are as follows:
> exacq 49300 // Overall number of exclusive locks taken
> ex_attempt1[0] 18353 // Exclusive locks taken immediately by first
> call of LWLockAttemptLock in LWLockAcquire loop
> ex_attempt2[0] 18144. // Exclusive locks taken immediately by second
> call of LWLockAttemptLock in LWLockAcquire loop
> ex_attempt1[1] 9985 // Exclusive locks taken after one waiting on
> semaphore by first call of LWLockAttemptLock in LWLockAcquire loop
> ex_attempt2[1] 1838. // Exclusive locks taken after one waiting on
> semaphore by second call of LWLockAttemptLock in LWLockAcquire loop
> ex_attempt1[2] 823. // Exclusive locks taken after two or more
> waiting on semaphore by first call of LWLockAttemptLock in
> LWLockAcquire loop
> ex_attempt2[2] 157. // Exclusive locks taken after two or more
> waiting on semaphore by second call of LWLockAttemptLock in
> LWLockAcquire loop
> shacq 508131 // .. same stats for shared locks
> sh_attempt1[0] 469410 //..
> sh_attempt2[0] 27858. //..
> sh_attempt1[1] 10309. //..
> sh_attempt2[1] 460. //..
> sh_attempt1[2] 90. //..
> sh_attempt2[2] 4. // .. same stats for shared locks
> dequeue self 48461 // Number of dequeue_self calls
> sh_wake_calls 27560 // Number of calls to wake up
> shared waiters
> sh_wakes 19408 // Number of shared waiters woken up.
> GroupClearXid 65021. // Number of calls of
> ProcArrayGroupClearXid
> EndTransactionInternal: 249003 // Number of calls
> ProcArrayEndTransactionInternal
>
> It seems that two calls in each look in Andres's (and master) code
> help evade semaphore-waiting loops that may be relatively expensive.
> The probable reason for this is that the small delay between these two
> calls is sometimes enough for concurrent takers to free spinlock for
> the queue modification. Could we get even more performance if we do
> three or more tries to take the lock in the queue? Will this degrade
> performance in some other cases?

Thank you for gathering the statistics. Let me do some relative
analysis of that.

*Lockless queue patch*

1. Shared lockers
1.1. 93.60% of them acquire lock without sleeping on semaphore
1.2. 6.02% of them acquire lock after sleeping on semaphore 1 time
1.3. 0.38% of them acquire lock after sleeping on semaphore 2 or more times
2. Exclusive lockers
2.1. 45.99% of them acquire lock without sleeping on semaphore
2.2. 41.66% of them acquire lock after sleeping on semaphore 1 time
2.3. 12.36% of them acquire lock after sleeping on semaphore 2 or more times

In general, about 10% of lockers sleep on the semaphore.

*Andres's patch*

1. Shared lockers
1.1. 97.86% of them acquire lock without sleeping on the semaphore
(92.38% do this immediately and 5.48% after queuing)
1.2. 2.12% of them acquire lock after sleeping on semaphore 1 time
(2.03% do this immediately and 0.09% after queuing)
1.3. 0.02% of them acquire lock after sleeping on semaphore 2 or more
times (0.02% do this immediately and 0.00% after queuing)
2. Exclusive lockers
2.1. 74.03% of them acquire lock without sleeping on the semaphore
(37.23% do this immediately and 36.80% after queuing)
2.2. 23.98% of them acquire lock after sleeping on semaphore 1 time
(20.25% do this immediately and 3.73% after queuing)
2.3. 1.99% of them acquire lock after sleeping on semaphore 2 or more
times (1.67% do this immediately and 0.32% after queuing)

In general, about 4% of lockers sleep on the semaphore.

I agree with Pavel that the reason for the regression of the lockless
queue patch seems to be sleeping on semaphores. The lockless queue
patch seems to give only one chance to the lockers to acquire the lock
without such sleeping. But the current LWLock code gives two such
chances: before queuing and after queuing. LWLockWaitListLock()
includes perform_spin_delay(), which may call pg_usleep(). So, the
second attempt to acquire the lock may have significant changes (we
see almost the same percentage for exclusive lockers!).

Pavel, could you also measure the average time LWLockWaitListLock()
spends with pg_usleep()?

It's a bit discouraging that sleeping on semaphores is so slow that
even manual fixed-time sleeping is faster. I'm not sure if this is the
issue of semaphores or the multi-process model. If we don't change
this, then let's try with multiple lock tries as Pavel proposed.

------
Regards,
Alexander Korotkov