HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Concurrent queue

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
concurrentqueuestackoverflow

Problem

I recently wrote a concurrent, mutex-less (but not lockfree) queue and wanted to know if it is actually correct, and if there are any particular improvements I could make:

```
template
class concurrent_queue
{
protected:
T *storage;
std::size_t s;
std::atomic consumer_head, producer_head;

union alignas(16) dpointer
{
struct
{
T *ptr;
std::size_t cnt;
};
__int128 val;
};

dpointer consumer_pending, producer_pending;

public:
concurrent_queue(std::size_t s): storage(nullptr)
{
storage = static_cast(::operator new((s+1)*sizeof(T)));

consumer_head = storage;
__atomic_store_n(&(consumer_pending.val), (dpointer{storage, 0}).val, __ATOMIC_SEQ_CST);

producer_head = storage;

__atomic_store_n(&(producer_pending.val), (dpointer{storage, 0}).val, __ATOMIC_SEQ_CST);
this->s = s + 1;
}
~concurrent_queue()
{
while(consumer_head != producer_head)
{
((T*)consumer_head)->~T();
++consumer_head;
if(consumer_head == storage + s)
consumer_head = storage;
}
::operator delete(storage);
}

template
bool push(U&& e)
{
while(true)
{
dpointer a;
a.val = __atomic_load_n(&(producer_pending.val), __ATOMIC_ACQUIRE);
auto b = consumer_head.load(std::memory_order_relaxed);
auto next = a.ptr + 1;
if(next == storage + s) next = storage;

if(next == b) return false;
dpointer newval{next, a.cnt+1};
if(!__atomic_compare_exchange_n(&(producer_pending.val), &(a.val), (newval.val), true, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) continue;

new (a.ptr) T(std::forward(e));

while(!producer_head.compare_exchange_weak(a.ptr, next, std::memory_order_release, std::memory_order_relaxed));
return true;
}
}

Solution

Regarding the conditional return types in push() and pop(), it may be clearer to use a different type of infinite loop, such as a for(;;). This will better focus the attention to the loop contents.

You could also use curly braces for the single-line statements. Some of these lines are quite long, so the executed code is at the very end. This should also help distinguish them from the busy-waits.

Context

StackExchange Code Review Q#52481, answer score: 3

Revisions (0)

No revisions yet.