Hello.
I am trying to start with lock-free algorithms, and decided that spsc-queue
should be simple enough for starters.
Below is the queue that I've written in C++11.
Could you please comment whether it is correct, and whether it could be
made significantly faster. Thanks!
template<typename T, size_t Size>
class queue_t
{
typedef uint64_t uint_t;
static const size_t padding_size = 256;
char padding0_[padding_size];
T values_[Size];
char padding1_[padding_size];
std::atomic<uint_t> head_;
char padding2_[padding_size];
std::atomic<uint_t> tail_;
public:
queue_t ()
: head_ (0)
, tail_ (0)
{
// should have been static_assert but my compiler does not support it
yet
assert (Size >= 2 && ((Size - 1) & Size) == 0); // power of two
}
bool enqueue (const T & value)
{
const uint_t head = head_.load (std::memory_order_relaxed);
const uint_t tail = tail_.load (std::memory_order_acquire);
// full?
if ((head - tail) == Size)
return false;
values_[head & (Size - 1)] = value;
assert (head < std::numeric_limits<uint_t>::max ());
head_.fetch_add (1, std::memory_order_release);
return true;
}
bool dequeue (T & value)
{
const uint_t head = head_.load (std::memory_order_acquire);
const uint_t tail = tail_.load (std::memory_order_relaxed);
// empty?
if (head == tail)
return false;
value = values_[tail & (Size - 1)];
tail_.fetch_add (1, std::memory_order_release);
return true;
}
};
--
---
You received this message because you are subscribed to the Google Groups
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/c6d07944-86e3-42c0-ac01-f1f6ce8cb61a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
