Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #584

Re: usage of vyukov's mpsc queue

Show all headers | View raw

Sorry I though you followed the link on the original post but it is a 
little broken. Here are the full details.

Intrusive MPSC node-based queue
-------------------------------
Advantages:
+ Intrusive. No need for additional internal nodes.
+ Wait-free and fast producers. One XCHG is maximum what one can get 
with multi-producer non-distributed queue.
+ Extremely fast consumer. On fast-path it's atomic-free, XCHG executed 
per node batch, in order to grab 'last item'.
+ No need for node order reversion. So pop operation is always O(1).
+ ABA-free.
+ No need for PDR. That is, one can use this algorithm out-of-the-box. 
No need for thread registration/deregistration, periodic activity, 
deferred garbage etc.

Disadvantages:
- Push function is blocking wrt consumer. I.e. if producer blocked in 
(*), then consumer is blocked too. Fortunately 'window of 
inconsistency' is extremely small - producer must be blocked exactly in 
(*). Actually it's disadvantage only as compared with totally lockfree 
algorithm. It's still much better lockbased algorithm.

struct mpscq_node_t
{
    mpscq_node_t* volatile  next;

};

struct mpscq_t
{
    mpscq_node_t* volatile  head;
    mpscq_node_t*           tail;
    mpscq_node_t            stub;

};

#define MPSCQ_STATIC_INIT(self) {&self.stub, &self.stub, {0}}

void mpscq_create(mpscq_t* self)
{
    self->head = &self->stub;
    self->tail = &self->stub;
    self->stub.next = 0;

}

void mpscq_push(mpscq_t* self, mpscq_node_t* n)
{
    n->next = 0;
    mpscq_node_t* prev = XCHG(&self->head, n);
    //(*)
    prev->next = n;

}

mpscq_node_t* mpscq_pop(mpscq_t* self)
{
    mpscq_node_t* tail = self->tail;
    mpscq_node_t* next = tail->next;
    if (tail == &self->stub)
    {
        if (0 == next)
            return 0;
        self->tail = next;
        tail = next;
        next = next->next;
    }
    if (next)
    {
        self->tail = next;
        return tail;
    }
    mpscq_node_t* head = self->head;
    if (tail != head)
        return 0;
    mpscq_push(self, &self->stub);
    next = tail->next;
    if (next)
    {
        self->tail = next;
        return tail;
    }
    return 0;
} 

Now if my consumer spins I can use this as is. But what if I am using 
signaling with an event as described in the original post. Can I just 
use the line     
  prev->next = n;
as is or do I need something else to ensure visiblity to the other thread?

Thanks,
-ephi
 

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-20 06:55 -0700
  Re: usage of vyukov's mpsc queue Joshua Maurice <joshuamaurice@gmail.com> - 2011-09-20 17:19 -0700
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-20 18:35 -0700
      Re: usage of vyukov's mpsc queue Ephraim Sinowitz <ephisinowitz@yahoo.com> - 2011-09-21 06:42 -0400
  Re: usage of vyukov's mpsc queue Joshua Maurice <joshuamaurice@gmail.com> - 2011-09-21 00:26 -0700
  Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 12:19 +0200
    Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 12:34 +0200
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <ephisinowitz@yahoo.com> - 2011-09-21 06:58 -0400
      Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 14:02 +0200
        Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 06:08 -0700
          Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 15:18 +0200
            Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 06:56 -0700
              Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 17:06 +0200
                Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 09:16 -0700
                Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 18:20 +0200
  Re: usage of vyukov's mpsc queue Dmitriy Vyukov <dvyukov@gmail.com> - 2011-09-21 09:58 -0700
    Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 19:33 +0200
      Re: usage of vyukov's mpsc queue dvyukov@google.com - 2011-10-02 04:13 -0700
        Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-10-04 12:15 +0200
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 11:04 -0700
      Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 11:17 -0700
      Re: usage of vyukov's mpsc queue "Chris M. Thomasson" <cristom@charter.net> - 2011-09-24 22:44 -0700

csiph-web