lwlock optimization opportunities

Hi,

This started as a reply to
https://postgr.es/m/CAH2-WzkbCvgKrmw%2Bf%2B1hwgXhmiv%2BUNRihotALXftUiNr%3D3VUKA%40mail.gmail.com
but after typing for a while I decided that it's large and unrelated
enough to be better handled as a new thread.


On 2020-11-27 11:08:49 -0800, Peter Geoghegan wrote:
> We've made LWLocks much more scalable in the last 10 years. Why
> shouldn't we expect to do the same again in the next 10 years? I
> wouldn't bet against it. I might even do the opposite (predict further
> improvements to LWLocks).

I've done a bunch of benchmarking that shows clear areas of
improvements:

- For LWLockWaitForVar() / LWLockUpdateVar() we take the wait list lock
  - largely unnecessarily in a lot of cases. On platforms that have
  atomic 8 byte reads we don't need the lock to read/write *valptr. Nor
  do we need to look at the list of waiters in LWLockUpdateVar() if
  LW_FLAG_HAS_WAITERS is not set.  WAL insertion is a fairly hot path,
  so it'd be nice to improve this.


- For locks that are frequently share-locked (e.g. procarray lock,
  buffer locks) making the share-lock acquisition an atomic xadd,
  instead of a a compare-exchange loop is a boon. It does make the code
  a bit more complicated (to handle races where the optimistically added
  shared locker happens after an exclusive acquisition), which lead me
  to remove that optimization before committing the current lwlock lock
  protocol. But I think it's time to add it, because we end up with a
  lot of entirely unnecessary retries in read-only/mostly workloads.


- Currently waking up waiters is O(#waiters) syscalls, because we wake
  up each waiting backend via a separate semaphore. In linux that boils
  down to a futex(semaphore, WAKE) syscall. The work the kernel needs to
  do for each of the futexes is substantial - in workloads with a lot of
  blocking I have seen 30% of the CPU time spent in related code.

  I played around with using futex() directly inside lwlock.c - yields
  quite a bit of benefits, because a) we can wake up many wakers at
  once, removing syscalls / futex lookups, b) there's far fewer
  different futexes & cachelines touched.

  Even things like only waking up shared-lockers etc can be done in one
  syscall, via FUTEX_WAIT_BITSET, FUTEX_WAKE_BITSET (with bits
  indicating the different wait modes).


- LWLockAcquireOrWait(), which we use for WALWriteLock, can waste a lot
  of CPU time if (some) of the waiters actually need to wait for WAL to
  be written out. We wake up *all* the waiters, none of them takes the
  lock, then all of them try to acquire the lock again - that's a lot of
  contention on a single poor cacheline, and a lot of pressure on the OS
  scheduler.

  I think what we instead need is a combo of LWLockAcquire/Release that
  allows a callback to inspect what needs to be done with which waiters.

  In the WAL case such a callback could utilize a 'flush request
  position' publicized for each PGPROC to decide whether to wake the
  process because the lock request is already fulfilled, and wake
  exactly one of the remaining processes to actually acquire the lock
  (rather than exiting LWLockAcquireOrFalse as currently the case).


- There are a large number of lwlocks - some of them bottlenecks - that
  are only ever taken in exclusive mode. For those locks we can use more
  efficient locking protocols:
  - Lock release does not need to be an atomic operation (there's no
    concurrent count of readers that concurrently can
    change). That can be a significant performance benefit.
  - Lock acquisition can be an atomic-exchange, instead of a
    compare-exchange.

  Unfortunately that probably requires designing the lock representation
  a bit differently. I don't know if it's feasible to share the data
  structure and just use different lock/unlock functions.


There's more, but that's already a long list ;)

Regards,

Andres