Re: Intrusive SPSC node-base queue

[Dmitriy V'jukov]

On Fri, Sep 14, 2012 at 4:50 PM, Junchao Zhang <juncha...@gmail.com> wrote:

Dear Dmitry,

  I browsed your homepage  http://www.1024cores.net. It is very nice to read your code of concurrent queues.

  I find there are intrusive or non-intrusive MPSC node-base queue. Do you have any intrusive SPSC node-base queue? Is it possible for such thing?

  I find you have SPSC queue, and the queue manages node allocation itself.  In my mind if the client code can dynamically allocate nodes, perhaps an intrusive SPSC queue is more efficient.

+lock...@googlegroups.com

Hi,

As far as I remember it's impossible to do spsc intrusive queue w/o using atomic RMW operations. The simplest such queue would be the lock-free stack algorithm where the consumer grabs all the nodes with XCHG and then reverses the stack to get FIFO. But you need to measure whether it's faster than non-intrusive queue (with node cache) because such queue does not use atomic RMW operations and does not do node reversion.

 

[Samy Bahra]

You may find these interesting if you haven't read them before: http://lwn.net/Articles/423994/ and full paper at http://infoscience.epfl.ch/record/161286

[Dmitriy V'jukov]

Well, yes, according to the paper my atomic-free distributed rw-mutex can't possibly exist.

--
Dmitry Vyukov

All about lockfree/waitfree algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

[Massimo Torquati]

Hi,

You may also find the following work interesting:
http://www.springerlink.com/content/5q160889g79j5533/
and the companion presentation slides:
http://calvados.di.unipi.it/storage/talks/2012_SPSC_Europar.pdf

All the SPSC queues implementation presented in the work
do not use RMW operations and are intrusive.
One queue is bounded (named SPSC, aka fastforward queue)
and 2 queues are unbounded (the dSPSC and the uSPSC).

The dSPSC queue is a node based SPSC queue with node cache
(basically it is the Michael & Scott 2-lock MPMC queue algorithm
optimized for the SPSC case).

The uSPSC queue combines the SPSC and the dSPSC queues in order
to obtain a buffer-based (cache-oblivious) unbounded lock-free SPSC queue
(I already know that Dmitry do not like too much such 'software
engineering approach' ;) ).

You can find the real C++ implementation of the queues in the FastFlow
source code (SourceForge svn).

Hope this helps.

Regards,
Massimo

[Samy Bahra]

A memory barrier is still considered a heavy-weight operation. Note that SPSC M&S queue has been in literature for a *very long* time (M&S described it as a two-lock queue).

Thanks for sharing the papers, hope to do a more in-depth study later tonight.