Doubly-linked list

[bartoszmodelski]

Lock-free doubly-linked list would be another good structure to add.

Use cases

Different scenarios where a group of threads awaits IO or result of some computation. Typically, in such a case, a promise of some kind maintains a linked list of waiting threads. Once operation finishes, they are woken up by issuer of promise.

The problem starts when cancellations come into play. The quickest deletion from a linked list is O(n), and in the case of some mass cancellations, those deletions may take a lot of time. This is particularly bad if cancellations were triggered by an overload as the system may melt down rather than regain stability. With a doubly linked-list, any node can be deleted in O(1).

I think there would be many concrete examples, e.g. promises in Domainslib. One mentioned by @kayceesrk is Lwt_sequence, which is used by Lwt to maintain a list of awaiting IO.

Design

It is notoriously hard to get right. There's a few papers, Lock-free deques and doubly linked lists seems the most solid. PPoPP 23 will have another implementation.

It might be helpful to know A Pragmatic Implementation of Non-Blocking Linked-Lists as well.

[lyrm]

Thanks for the issue. As I have already implemented a lock free sorted linked list (that will be pushed with an hash table), I will probably work on this data structure next if no one has already done it.