[lttng-dev] [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

[Paul E. McKenney]

On Wed, Oct 03, 2012 at 05:04:36PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Tue, Oct 02, 2012 at 10:13:07AM -0400, Mathieu Desnoyers wrote:
> > > Implement wait-free concurrent queues, with a new API different from
> > > wfqueue.h, which is already provided by Userspace RCU. The advantage of
> > > splitting the head and tail objects of the queue into different
> > > arguments is to allow these to sit on different cache-lines, thus
> > > eliminating false-sharing, leading to a 2.3x speed increase.
> > > 
> > > This API also introduces a "splice" operation, which moves all nodes
> > > from one queue into another, and postpones the synchronization to either
> > > dequeue or iteration on the list. The splice operation does not need to
> > > touch every single node of the queue it moves them from. Moreover, the
> > > splice operation only needs to ensure mutual exclusion with other
> > > dequeuers, iterations, and splice operations from the list it splices
> > > from, but acts as a simple enqueuer on the list it splices into (no
> > > mutual exclusion needed for that list).
> > > 
> > > Feedback is welcome,
> > 
> > These look sane to me, though I must confess that the tail pointer
> > referencing the node rather than the node's next pointer did throw
> > me for a bit.  ;-)
> 
> Yes, this was originally introduced with Lai's original patch to
> wfqueue, which I think is a nice simplification: it's pretty much the
> same thing to use the last node address as tail rather than the address
> of its first member (its next pointer address (_not_ value)). It ends up
> being the same address in this case, but more interestingly, we don't
> have to use a struct cds_wfcq_node ** type: a simple struct
> cds_wfcq_node *  suffice.
> 
> Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Good point -- just confirming:

Acked-by: Paul E. McKenney <paulmck at linux.vnet.ibm.com>

> Lai, you are welcome to provide improvements to this code against the
> master branch. I will gladly consider any change you propose.
> 
> Thanks!
> 
> Mathieu
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
> 
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
>