kotlinx.coroutines icon indicating copy to clipboard operation
kotlinx.coroutines copied to clipboard

Remove concurrent doubly linked list from kotlinx.coroutines codebase

Open qwwdfsad opened this issue 2 years ago • 1 comments
trafficstars

We have LockFreeLinkedListNode and co. based on the "Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap" paper.

The implementation has a long-standing tail of issues:

  1. The paper itself is known for having non-linearizability issues that trigger various failures when the data structure is stressed enough
  2. DCLL is too generic: it allows all operations a trivial double-linked list (bi-directional iterations, mid-section removals etc.), which makes the reasoning and the maintenance of the concurrent invariants a tough task. Attempts to bisect a compact subset of only required invariants all failed.
  3. The implementation is slower than it could be: any mutating operation implies at least 4 CASes; any added element corresponds to a separate object with multiple atomic fields (prev, next, removal marker)
  4. Due to 2 & 3, the correct implementation is bloated, which contributes ~10% of optimized DEX size of kotlinx.coroutines.

The proposed solution is straightforward -- get rid of DCLL and replace it with recently added FADD-based ConcurrentLinkedList that semaphore, mutex and channels leverage

qwwdfsad avatar Sep 15 '23 12:09 qwwdfsad