Let us consider the following one-reader/one-writer queue implemented with a linked list.
struct queue {
queue() {
tail = head = &reserved;
n = 0;
}
void push(item *it) {
tail->next = it;
tail = it;
n++;
}
item* pop() {
while (n == used);
++used;
head = head->next;
return head;
}
item reserved;
item *tail, *head;
int used = 0;
std::atomic <int> n;
}
Now I find that using volatile int n
could make my writer run faster, while I'm not sure whether it guarantees that head = head->next
can always read the correct value.
UPDATED: What if adding an atomic operation between tail->next
, n++
, i.e.,
void push(item *it) {
tail->next = it;
tail = it;
a.store(0, std::memory_order_release);
a.load(std::memory_order_acquire);
n++;
}
in which a
is never accessed by the reader? Will this guarantees the order of tail->next = it
and head = head->next
? (Still, it runs faster than using atomic n
)
As already pointed out in several other comments, volatile is unrelated to multithreading, so it should not be used here. However, the reason why volatile performs better then an atmoic simply is, because with a volatile ++n
translates to simple load, inc, store instructions, while with an atomic it translates to a more expensive lock xadd
(assuming you compile for x86).
But since this is only a single-reader single-writer queue, you don't need expensive read-modify-write operations:
struct queue {
queue() {
tail = head = &reserved;
n = 0;
}
void push(item *it) {
tail->next = it;
tail = it;
auto new_n = n.load(std::memory_order_relaxed) + 1;
n.store(new_n, std::memory_order_release);
}
item* pop() {
while (n.load(std::memory_order_acquire) == used);
++used;
head = head->next;
return head;
}
item reserved;
item *tail, *head;
int used = 0;
std::atomic <int> n;
}
This should perform equally good as a volatile version. If the acquire-load in pop
"sees" the value written by the store-release in push
, the two operations synchronize-with each other, thereby establishing the required happens-before relation.