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

Lock-free list in C++

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

Problem

I tried to write a lock-free list in C++. Unfortunately, the performance compared to an 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.