4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ You said "performance compared to a std::list secured with a simple mutex is bad". Are you talking about performance measured for one thread or many threads? Next, that operations of your linked list you compared? push_back or all of them? And fnally. Performance problems are better identified with programs like Linux perf. Did you use it? \$\endgroup\$ – Sergei Kurenkov Mar 18 '16 at 11:46
  • \$\begingroup\$ ive edited the test-code (simple comparison of the execution time with std::chrono) \$\endgroup\$ – Domso Mar 18 '16 at 12:05
  • \$\begingroup\$ Writing an efficient lock free queue is actually very difficult. Its actually a good sign that you are comparing it with a queue using locks. \$\endgroup\$ – Martin York Mar 18 '16 at 17:05
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ IMO seperate header/implementation-files for templates add no benefit and make the linking more inconsistent. \$\endgroup\$ – Domso Oct 17 '16 at 7:12
  • \$\begingroup\$ but I agree, the some comments are not usefull (it was mostly a reminder) The horizontal line should divide the code in logical-scopes, which should help to understand the code better. But I agree, my comment-style is sometimes very confusing and bloated. Ill try to improve \$\endgroup\$ – Domso Oct 17 '16 at 7:20
  • \$\begingroup\$ I did remember about the first thing, which you're right about, so I've removed it. \$\endgroup\$ – Jamal Oct 17 '16 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.