Re: Question about atomic FIFO/LIFO queues

[Ruslan Nikolaev <nruslan_devel%yahoo.com@localhost>]

Hi Taylor,

I was looking at this code again. Probably our queue is much faster and 
more scalable since pcq is CAS based, which is a more typical/classical 
approach. (For example, in our paper, we explain why FAA-based queues 
scale much much better, we also compare against CAS-based queues.)

(For example, see pp.13-14 in 
https://drops.dagstuhl.de/opus/volltexte/2019/11335/pdf/LIPIcs-DISC-2019-28.pdf

NCQ and MSQUEUE are CAS-based. Our queues (SCQ, SCQP) are FAA-based. You 
can see a big gap as we reach 18 per-CPU cores. Basically NCQ and 
MSQUEUE won't scale at all.)


The challenge there is to actually have a truly lock-free FAA queue; 
most queues are not, they incorrectly claim lock-freedom. We finally 
solve this problem in our paper.

Would you like us to explore if pcq can be replaced with our new DISC'19 
algorithm potentially? How critical for the overall networking 
performance is this code?

Ruslan


On 9/27/20 2:58 PM, Taylor R Campbell wrote:
> > Date: Fri, 25 Sep 2020 17:58:41 -0400
> > From: Ruslan Nikolaev <nruslan_devel%yahoo.com@localhost>
> >
> > 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).
> Cool!
>
> I don't actually know what the author of that project description had
> in mind, and he's no longer around, so we should probably just take
> that page down unless someone else remembers and it's still relevant.
> Parts of the network stack use pcq(9) for inter-CPU packet queueing,
> although in new code (and incrementally for old code) we generally try
> to minimize inter-CPU communication except to distribute load.
>
> https://man.NetBSD.org/pcq.9
> https://nxr.NetBSD.org/xref/src/sys/kern/subr_pcq.c