Hi
I came across this page
https://wiki.netbsd.org/projects/project/atomic_fifo_lifo_queues/
Recently, we have designed a high-performant (and what is also very
important -- truly lock-free -- not just "lockless") and memory
efficient FIFO queue based on ring buffers that use FAA (fetch-and-add)
and traditional M&S queue as an outer layer (for unbounded queues).
The queue, is in some sense, an improved version of LCRQ, the fastest
lock-free FIFO queue previously available, but it does *not* require
double-width CAS (cmpxchg16b) and we also made more memory efficient.
You can take a look at our recent paper:
http://drops.dagstuhl.de/opus/volltexte/2019/11335/pdf/LIPIcs-DISC-2019-28.pdf
C source code is also available: https://github.com/rusnikola/lfqueue
It seems like the new NetBSD network stack will require some new
scalable multiprocessor data structures. We would be glad to discuss if
our queue can potentially meet those needs.
From the page above, it seems you want to have FIFO+LIFO in the same
package. It is probably possible to do that but how critical is this
requirement? The reason I ask is because FIFO and LIFO need entirely
different approaches for good performance, so I was wondering if that is
a fundamental requirement.
Thanks,
Ruslan Nikolaev
