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

Subject: Re: [boost] [lockfree::fifo] Review
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-12-21 09:34:25

"Tim Blechmann" <tim_at_[hidden]> wrote in message 
news:4B2E059C.3020808_at_klingt.org...
> > FWIW Tim, here is a very simple pseudo-code implementation of a nice
> > single-producer/consumer bounded queue:

> interesting ... it passes objects via pointers, though, which limits its
> usefulness ... still, if it performs better than my spsc ringbuffer, it
> would be interesting to use it as template specialization for pointer
> types ...

Here is another "interesting" pointer-based algorithm. It's not a strict 
FIFO and it allows producers to act as consumers; here is some pseudo-code:
_____________________________________________________________
template<typename T, size_t T_depth>
struct wierd_mpsc_queue
{
    atomic<T*> m_buffer[T_depth]; // = { NULL };
    atomic<size_t> m_head; // = 0
    size_t m_tail; // = 0

    T* push(T* object)
    {
        assert(object);

        size_t i = m_head.fetch_add(1, memory_order_relaxed) % T_depth;

        object = m_buffer[i].exchange(object, memory_order_release);

        if (object)
        {
            atomic_thread_fence(memory_order_acquire);
        }

        return object;
    }

    T* pop()
    {
        T* object = m_buffer[m_tail].exchange(NULL, memory_order_acquire);

        if (object)
        {
            m_tail = (m_tail == T_depth - 1) ? 0 : (m_tail + 1);
        }

        return object;
    }
};
_____________________________________________________________

This is pretty weird because it's a multi-producer/single-consumer, however, 
it can behave as if it was a multi-producer/multi-consumer when the 
producers start to consume a full buffer. Also, sometimes you just don't 
care about a "strict" ordering...

;^)