Re: [boost] [lockfree::fifo] Review

Subject: Re: [boost] [lockfree::fifo] Review
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-12-18 05:48:28

"Tim Blechmann" <tim_at_[hidden]> wrote in message
news:4B23A083.7080008_at_klingt.org...

> >> i just went through the replies ... (maybe i should upcase some parts
> >> in
> >> the documentation, that the implementation focus on WORST CASE, not
> >> AVERAGE CASE performance ... people keep complaining that the
> >> stack/fifo
> >> may be outperformed be blocking algorithms, which is both true and
> >> irrelevant for me, as these implementations are soft real-time safe
> >> (and
> >> could be made hard real-time safe).
> >
> > Agreed.
> > Are you planning to augment your library with algorithms for different
> > needs? Like MPSC, SPMC and so forth? I think that could be useful,
> > because it looks like implementing the most generic MPMC case won't give
> > you the best results.

> i just added a lock-free single-producer/single-consumer ringbuffer to
> my git repository, branch topic/spsc_ringbuffer ... it implements an
> algorithm, that is commonly found in open source audio applications ...
> performs about 8 times faster than the m-s fifo queue (which is based on
> linked lists).

FWIW Tim, here is a very simple pseudo-code implementation of a nice
single-producer/consumer bounded queue:
_______________________________________________________________
template<template T,
                size_t T_depth>
class spsc_queue
{
    atomic<T*> m_buffer[T_depth]; // = { NULL }
    size_t m_head; // = 0
    size_t m_tail; // = 0

public:
    bool push(T* object)
    {
        if (m_buffer[m_head].load(memory_order_relaxed))
        {
            return false;
        }

        m_buffer[m_head].store(memory_order_release);

        ++m_head;

        if (m_head == T_depth)
        {
            m_head = 0;
        }

        return true;
    }

    T* pop()
    {
        T* object = m_buffer[m_tail].load(memory_order_acquire);

        if (object)
        {
            m_buffer[m_tail].store(NULL, memory_order_relaxed);

            ++m_tail;

            if (m_tail == T_depth)
            {
                m_tail = 0;
            }
        }

        return object;
    }
};
_______________________________________________________________

This is good because the producer and consumer do not interfere with each
other wrt the `spsc_queue::m_head/tail' variables. I think I noticed that
you are allowing producers and consumers to load both the reader and writer
variables and use them to determine boundary conditions (e.g., empty/full)
right?