FairAsyncSemaphore link skipping

[rnarubin]

Porting issue 23 from the enterprise repo

rnarubin commented on Aug 23, 2017

FairAsyncSemaphore currently suffers from 2 (loosely related) shortcomings in its linked queue implementation: excessive head/tail updates, and GC nepotism

The first issue is that the head and tail pointers are updated with every push and poll (i.e. with acquires that queue and releases that dequeue). Stale pointers are tolerable, however, with the only drawback being link traversal to find the true head and tail nodes, so the pointers need not be updated at every opportunity. j.u.c.ConcurrentLinkedQueue uses such a strategy of skipping every other update (and incurring the smaller traversal cost) to reduce the amortized cost of insertion and removal. The same idea can be applied to FairAsyncSemaphore's queue.

The second issue is that forward links from dead nodes in the FAS queue are never cleared. Although a node becomes unreachable after being released (by advancing head), their links can still point to live nodes, which can have GC implications -- namely premature promotion to oldgen if the dead nodes were themselves long-lived. As part of the refactoring necessary to solve the first issue, this GC unlinking can also be addressed (using the same principles as j.u.c.CLQ).

These problems only appear in the FAS queue implementation; neither exist in FALock or FAReadWriteLock. (1) FALock always maintains a strict view of the true tail. FARWLock would require stronger consistency in updating its links to allow concurrent traversal, the cost of which likely isn't worth the benefit. (2) Both of their queues unlink completely during release.

[rnarubin]

rkhadiwa commented on Aug 23, 2017

AsyncChannels.UnboundedChannel doesn't unlink either, I think 2 applies