0

I need low-latency c++ synchronized queue, requirements are:

  1. no memory allocation at runtime, i just want to memcpy new items
  2. lock-free
  3. one writer
  4. several readers (parallel)
  5. parallel reading and writing

Should I implement it myself or I can use something from boost or probaly you can share another implementation? Because I don't want to allocate memory most likely queue should use ring-buffer inside.

Below is ring-buffer I wrote on C#. It meets all requirements except 4. It's easy to rewrite it to c++, but I don't know how can I support several readers in this implementation keeping it lock-free:

public sealed class ArrayPool<T> where T : class, new()
{
    readonly T[] array;
    private readonly uint length;
    private readonly uint MASK;

    private volatile uint curWriteNum;
    private volatile uint curReadNum;

    public ArrayPool(uint length = 65536) // length must be power of 2
    {
        if (length <= 0) throw new ArgumentOutOfRangeException("length");
        array = new T[length];
        for (int i = 0; i < length; i++)
        {
            array[i] = new T();
        }
        this.length = length;
        MASK = length - 1;
    }

    public bool IsEmpty
    {
        get { return curReadNum == curWriteNum; }
    }

    /// <summary>
    /// TryGet() itself is not thread safe and should be called from one thread.
    /// However TryGet() and Obtain/Commit can be called from different threads
    /// </summary>
    /// <returns></returns>
    public T TryGet()
    {
        if (curReadNum == curWriteNum)
        {
            return null;
        }
        T result = array[curReadNum & MASK];
        curReadNum++;
        return result;
    }

    public T Obtain()
    {
        return array[curWriteNum & MASK];
    }

    public void Commit()
    {
        curWriteNum++;
        if (curWriteNum - curReadNum > length)
        {
            Log.Push(LogItemType.Error,
                "ArrayPool curWriteNum - curReadNum > length: "
                + curWriteNum + ' ' + curReadNum + ' ' + length);
        }
    }

}

Usage is simple, you first call Obtain then reconfigure the item and then call Commit.

I add my C# implementation just to show what I need. I think it's impossible to add support for "several readers" and keep implementation lock-free at the same time, so I need something new.

Oleg Vazhnev
  • 23,239
  • 54
  • 171
  • 305
  • 2
    I think you will have some *very* hard time with 4. – n. m. could be an AI Sep 26 '13 at 09:01
  • 1
    Duplicate of http://stackoverflow.com/questions/2702328/lock-free-queue-single-producer-multiple-consumers – Johannes S. Sep 26 '13 at 09:04
  • 1
    Boost has a lockfree queue with fixed-sized : http://www.boost.org/doc/libs/1_53_0/doc/html/boost/lockfree/queue.html . – lucasg Sep 26 '13 at 09:08
  • Is lock free more important than anything? Or are we assuming lock free is fast and we just want fast? – doctorlove Sep 26 '13 at 09:18
  • we just want fast, also we want to minimize the chance of "too big" delays. so low delays in average and not too much "outstanding" delays. so i think `lock-free` is almost required, but certainly not absolutely required. – Oleg Vazhnev Sep 26 '13 at 09:25
  • 3
    Don't even think about writing your own lock-free implementation unless you are an expert. Coming up with one that is correct is Hard. A correct lock-free queue is something you can publish. Even some of those that have been published have been [found to have mistakes](http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448) – the_mandrill Sep 26 '13 at 09:28
  • @the_mandrill well implementation I've posted i think fine. but it supports only one reader. it seems supporting several readers is very hard requirement, so probably I should take something not lock-free, but still pretty fast... – Oleg Vazhnev Sep 26 '13 at 09:30
  • I think you may well get race conditions here that will be very difficult to isolate. Also you have no error recovery in `Commit()`, so the caller has no idea the operation failed if the queue is full. Much better to use the `boost` one which has been checked by many people and has a well thought out interface. – the_mandrill Sep 26 '13 at 10:07
  • @the_mandrill queue is never full as I always have enough space. If queue is full by some reason I will find error message in logs and analyze. – Oleg Vazhnev Sep 26 '13 at 10:18
  • Can you guarantee that? Anyhow, there's still the problems with race conditions. Are the increments atomic? Also you don't have any methods that add data to the queue. If you want something reliable then don't roll your own, use boost. The boost one also satisfies the multi-reader/writer requirements. – the_mandrill Sep 26 '13 at 11:27
  • @the_mandrill i don't add items to queue. i reuse them. so i don't need to allocated memory at runtime. what `boost` class can you recomend as a replacement? – Oleg Vazhnev Sep 26 '13 at 12:31
  • What you are describing is a circular buffer, or a fixed-size queue. See the link to the boost queue that georgesl mentioned above. – the_mandrill Sep 26 '13 at 12:45
  • i think i can just use `boost::lockfree::queue` – Oleg Vazhnev Sep 26 '13 at 13:10

0 Answers0