patterncppMinor
Lock-free list in C++
Viewed 0 times
listfreelock
Problem
I tried to write a lock-free list in C++. Unfortunately, the performance compared to an
What do you think? Are there major performance or code-style issues?
```
#include
template
// lock-free list-container
class lf_list {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// node-logic
struct base_node {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
base_node() : next_(nullptr), prev_(nullptr), refCount_(1) {
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// set new previous node
// return false if current node was removed from the list
bool insert(base_node* const prevItem) {
base_node* prev;
base_node* next;
base_node* current;
while (true) {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// create a local copy of the link-ptr
// -> other threads will wait here
do {
prev = prev_.load();
} while (!prev_.compare_exchange_strong(prev, nullptr) || prev == nullptr);
do {
next = next_.load();
} while (next == nullptr);
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// check if current node is still linked
if (!isLinked(next, prev)) {
// restore prev_
prev_.store(prev);
return false;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// set link-ptr of new node
prevItem->next_.store(this);
std::list secured with a simple mutex is bad.What do you think? Are there major performance or code-style issues?
```
#include
template
// lock-free list-container
class lf_list {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// node-logic
struct base_node {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
base_node() : next_(nullptr), prev_(nullptr), refCount_(1) {
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// set new previous node
// return false if current node was removed from the list
bool insert(base_node* const prevItem) {
base_node* prev;
base_node* next;
base_node* current;
while (true) {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// create a local copy of the link-ptr
// -> other threads will wait here
do {
prev = prev_.load();
} while (!prev_.compare_exchange_strong(prev, nullptr) || prev == nullptr);
do {
next = next_.load();
} while (next == nullptr);
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// check if current node is still linked
if (!isLinked(next, prev)) {
// restore prev_
prev_.store(prev);
return false;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// set link-ptr of new node
prevItem->next_.store(this);
Solution
There's really no need for all those "horizontal line" comments, which can make the code a bit harder to read. But if they're necessary, then at least use them sparingly. You also don't need any obvious comments, such as the ones indicating some of the individual overloaded operators. Readers of the code should easily be able to know about them.
Context
StackExchange Code Review Q#123201, answer score: 3
Revisions (0)
No revisions yet.