You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The implementation has a long-standing tail of issues:
The paper itself is known for having non-linearizability issues that trigger various failures when the data structure is stressed enough
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.
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)
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
The text was updated successfully, but these errors were encountered:
I just spotted a 1-core 100% CPU usage (I've 8 cores in total) after hours of idling at 0% in my application.
According to top -H, 100% of my application CPU usage is caused by the DefaultDispatcher thread. Looking at the thread dump, it only has this one stack:
After profiling, JMC shows the most sampled method to be, by far, LockFreeLinkedListNode.getNext().
Could this be related to these described issues and will it be fixed with the removal of the implementation?
I'm using Kotlin 2.0.10 + kotlinx.coroutines 1.8.1 - will upgrade in a sec and see if I can reproduce it with 1.9.0. Application source
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:
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 leverageThe text was updated successfully, but these errors were encountered: