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 <atomic>
template <typename T>
// 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);
prevItem->prev_.store(prev);
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// try to link new node
current = this;
if (prev != nullptr) {
if (!prev->next_.compare_exchange_strong(current, prevItem)) {
// fail!
// restore prev_
prev_.store(prev);
// retry
continue;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// success!
// final link new node
prev_.store(prevItem);
return true;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// remove the node from the list
// return false if current node was removed from the list
bool remove() {
base_node* next;
base_node* prev;
base_node* current;
while (true) {
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// create a local copy of the link-ptr
// -> other threads will wait here
do {
next = next_.load();
} while (!next_.compare_exchange_strong(next, nullptr) || next == nullptr);
do {
prev = prev_.load();
} while (!prev_.compare_exchange_strong(prev, nullptr) || prev == nullptr);
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// check if current node is still linked
if (!isLinked(next, prev)) {
// restore next_ and prev_
next_.store(next);
prev_.store(prev);
return false;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// try to remove current node from the next node
current = this;
if (next != nullptr) {
if (!next->prev_.compare_exchange_strong(current, prev)) {
// fail!
// restore next_ and prev_
next_.store(next);
prev_.store(prev);
// retry
continue;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// try to remove current node from the previous node
if (prev != nullptr) {
do {
current = this;
} while (!prev->next_.compare_exchange_strong(current, next));
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// success!
// final link node
next_.store(next);
prev_.store(prev);
// remove list-reference
refCount_--;
return true;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// check if next and prev are still valid links
bool isLinked(const base_node* const next, const base_node* const prev) const {
base_node* next_this = next->prev_.load();
base_node* prev_this = prev->next_.load();
return (next_this == nullptr || next_this == this) && (prev_this == nullptr || prev_this == this);
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// link to the next node
std::atomic<base_node*> next_;
// link to the previous node
std::atomic<base_node*> prev_;
// reference count for iterator memory management
std::atomic<int> refCount_;
};
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// data-node
struct node : public base_node {
node() {
}
node(const T& d) : data(d) {
}
T data;
};
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
public:
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// lock-free iterator
class iterator {
public:
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// constructors
iterator() : ptr_(nullptr) { }
iterator(node* ptr) : ptr_(ptr) {
addReference();
}
iterator(const iterator& that) : ptr_(that.ptr_) {
addReference();
}
iterator(iterator && that) : ptr_(that.ptr_) {
that.ptr_ = nullptr;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// assignment operators
void operator = (const iterator& that) {
delReference(ptr_);
ptr_ = that.ptr_;
addReference();
}
void operator = (iterator && that) {
delReference(ptr_);
ptr_ = that.ptr_;
that.ptr_ = nullptr;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// destructor
virtual ~iterator() {
delReference(ptr_);
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// increment reference count of the current node
void addReference() {
if (ptr_ != nullptr) {
ptr_->refCount_++;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// decrement reference count of the current node
// if the count is 0, delete the node
void delReference(base_node* ptr) {
if (ptr != nullptr && --(ptr->refCount_) == 0) {
delete ptr;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// prefix-increment operator
iterator operator++() {
base_node* ptr = ptr_;
while ((ptr_ = ptr_->next_) == nullptr) {};
delReference(ptr);
addReference();
return *this;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// postfix-increment operator
iterator operator++(int) {
base_node* ptr = ptr_;
iterator it((node*)ptr);
while ((ptr_ = ptr_->next_) == nullptr) {}
delReference(ptr);
addReference();
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// prefix-decrement operator
iterator operator--() {
base_node* ptr = ptr_;
while ((ptr_ = ptr_->prev_) == nullptr) {}
delReference(ptr);
addReference();
return *this;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// postfix-decrement operator
iterator operator--(int) {
base_node* ptr = ptr_;
iterator it((node*)ptr);
while ((ptr_ = ptr_->prev_) == nullptr) {}
delReference(ptr);
addReference();
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// data operators
T& operator*() const {
return ((node*)ptr_)->data;
}
T& operator->() const {
return ((node*)ptr_)->data;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// compare operators
bool operator==(const iterator& it) const {
return ptr_ == it.ptr_;
}
bool operator!=(const iterator& it) const {
return ptr_ != it.ptr_;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// return node handle
node* handle() const {
return (node*)ptr_;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
private:
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// ptr to current node
base_node* ptr_;
};
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// constructors
lf_list() {
last_.prev_ = &last_;
last_.next_ = &last_;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// destructor
virtual ~lf_list() {
clear();
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// position iterators
iterator begin() {
return iterator((node*)(last_.next_.load()));
}
iterator end() {
return iterator((node*)&last_);
}
iterator rbegin() {
return iterator((node*)(last_.prev_.load()));
}
iterator rend() {
return iterator((node*)&last_);
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert next as new previous node of it
iterator insert(const iterator& it, const T next) {
node* tmp = new node(next);
bool check;
if (it.handle() != nullptr) {
check = it.handle()->insert(tmp);
}
if (check) {
return iterator(tmp);
}
return end();
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert next as previous node of it
// next will be removed of a previous list!
iterator insert(const iterator& it, iterator& next) {
bool check;
next.handle()->remove();
next.addReference();
if (it.handle() != nullptr) {
check = it.handle()->insert(tmp);
}
if (check) {
return next;
}
return end();
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// remove and return first element of the list
iterator pop_front() {
node* next;
node* prev;
iterator it;
do {
it = begin();
} while (it != end() && !erase(it));
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// remove and return last element of the list
iterator pop_back() {
node* next;
node* prev;
iterator it;
do {
it = rbegin();
} while (it != rend() && !erase(it));
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert and return new element at the beginning of the list
iterator push_front(const T data) {
node* next;
node* prev;
iterator it;
do {
it = begin();
} while (insert(it, data) == end());
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert and return new element at the end of the list
iterator push_back(const T data) {
node* next;
node* prev;
iterator it;
do {
it = rbegin();
} while (insert(it, data) == end());
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert and return new element at the beginning of the list
iterator push_front(iterator& data) {
node* next;
node* prev;
iterator it;
do {
it = begin();
} while (insert(it, data) == end());
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// insert and return new element at the end of the list
iterator push_back(iterator& data) {
node* next;
node* prev;
iterator it;
do {
it = rbegin();
} while (insert(it, data) == end());
return it;
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// remove iterator from the list
bool erase(iterator it) {
return it.handle()->remove();
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// remove all nodes from the list
void clear() {
for (iterator it = begin(); it != end(); it++) {
erase(it);
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
private:
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// the first and the last empty node (contains no data)
base_node last_;
};
Test code:
void iterateThread(std::list<int>& list, std::mutex& m, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
int i = 0;
volatile int tmp;
while (i < 10000000) {
m.lock();
for (auto it = list.begin(); it != list.end(); it++) {
tmp += *it;
i++;
}
m.unlock();
}
pthread_barrier_wait(bar);
}
void iterateThread_lf(lf_list<int>& list, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
int i = 0;
volatile int tmp;
while (i < 10000000) {
for (auto it = list.begin(); it != list.end(); it++) {
tmp += *it;
i++;
}
}
pthread_barrier_wait(bar);
}
void iterateRThread(std::list<int>& list, std::mutex& m, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
int i = 0;
volatile int tmp;
while (i < 10000000) {
m.lock();
for (auto it = list.rbegin(); it != list.rend(); it++) {
tmp += *it;
i++;
}
m.unlock();
}
pthread_barrier_wait(bar);
}
void iterateRThread_lf(lf_list<int>& list, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
int i = 0;
volatile int tmp;
while (i < 10000000) {
for (auto it = list.rbegin(); it != list.rend(); it++) {
tmp += *it;
i++;
}
}
pthread_barrier_wait(bar);
}
void push_backThread(std::list<int>& list, std::mutex& m, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
for (int i = 0; i < 5000000; i++) {
m.lock();
list.push_back(i);
m.unlock();
}
pthread_barrier_wait(bar);
}
void push_backThread_lf(lf_list<int>& list, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
for (int i = 0; i < 5000000; i++) {
list.push_back(i);
}
pthread_barrier_wait(bar);
}
void push_frontThread(std::list<int>& list, std::mutex& m, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
for (int i = 0; i < 5000000; i++) {
m.lock();
list.push_front(i);
m.unlock();
}
pthread_barrier_wait(bar);
}
void push_frontThread_lf(lf_list<int>& list, pthread_barrier_t* bar) {
pthread_barrier_wait(bar);
for (int i = 0; i < 5000000; i++) {
list.push_front(i);
}
pthread_barrier_wait(bar);
}
void test() {
std::list<int> list;
lf_list<int> list_lf;
for (int i = 0; i < 1000000; i++) {
list_lf.push_back(i);
list.push_back(i);
}
int numThreads = 4;
pthread_barrier_t bar;
pthread_barrier_init(&bar, 0, numThreads + 1);
std::thread thread[numThreads];
std::chrono::high_resolution_clock::time_point t1;
std::chrono::high_resolution_clock::time_point t2;
for (int i = 0; i < numThreads; i++) {
if (i % 4 == 0) {
thread[i] = std::thread(iterateThread_lf, std::ref(list_lf), &bar);
} else if (i % 4 == 1) {
thread[i] = std::thread(iterateRThread_lf, std::ref(list_lf), &bar);
} else if (i % 4 == 2) {
thread[i] = std::thread(push_backThread_lf, std::ref(list_lf), &bar);
} else if (i % 4 == 3) {
thread[i] = std::thread(push_frontThread_lf, std::ref(list_lf), &bar);
}
}
t1 = std::chrono::high_resolution_clock::now();
pthread_barrier_wait(&bar);
pthread_barrier_wait(&bar);
t2 = std::chrono::high_resolution_clock::now();
for (int i = 0; i < numThreads; i++) {
thread[i].join();
}
auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count();
std::cout << duration << std::endl;
std::mutex m;
for (int i = 0; i < numThreads; i++) {
if (i % 4 == 0) {
thread[i] = std::thread(iterateThread, std::ref(list), std::ref(m), &bar);
} else if (i % 4 == 1) {
thread[i] = std::thread(iterateRThread, std::ref(list), std::ref(m), &bar);
} else if (i % 4 == 2) {
thread[i] = std::thread(push_backThread, std::ref(list), std::ref(m), &bar);
} else if (i % 4 == 3) {
thread[i] = std::thread(push_frontThread, std::ref(list), std::ref(m), &bar);
}
}
t1 = std::chrono::high_resolution_clock::now();
pthread_barrier_wait(&bar);
pthread_barrier_wait(&bar);
t2 = std::chrono::high_resolution_clock::now();
for (int i = 0; i < numThreads; i++) {
thread[i].join();
}
duration = std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count();
std::cout << duration << std::endl;
pthread_barrier_destroy(&bar);
}
push_backor all of them? And fnally. Performance problems are better identified with programs like Linuxperf. Did you use it? \$\endgroup\$