AnswerBun.com

Multi-threaded lock-free doubly linked list using free-list

Stack Overflow Asked by Bruce Shen on October 19, 2020

I want a concurrent data structure that works like a singly linked list and only needs append and remove_iterator operations. In the end, one thread will iterate all nodes. From my research, I got an implementation that has append, remove_value and search_value operations with singly-linked lists. It is based on Harris’ algorithm.

The problem is that in Harris’ algorithm, remove_value only marks a node logically deleted, without actually delete it. search_value actually do the chores of removing logically deleted nodes. But since I don’t have a search operation for my use case. I keep a long list with lots of logically deleted nodes. It is just not efficient for speed in multi-threading, because all the work of deleting nodes is put on the iterate operation within a single thread.

I wonder if there are any other implementations that fit my needs. Any recommendation is appreciated.

If not, I wonder if I can implement something for this special case using a free-list with a lock-free stack implementation. In this case, an append operation becomes pop free-list, either put value to the node or append to our list if empty. A remove_iterator operation becomes mark the node logically removed, and push the node pointer to free-list.

I think lock-free stack if fairly easy to implement. I can use some implementations online.


Some code in mind.

struct node_t {
    node_t *next;
    int deleted;
    val_t val;
};
struct list_t {
    node_t *head;
};
struct fl_node_t {
    node_t *padding_1;
    int padding_2;
    fl_node_t *next; // assume sizeof(val_t) >= sizeof(fl_node_t*);
};

struct free_list_t {
    fl_node_t * head;
};
void append(val_t val) {
    fl_node_t *fl_head;
    fl_node_t *fl_next;
    node_t *head;
    node_t *new_node
    /* Try insert to one of the node in free-list */
    if (free_list.head) {
        do {
            fl_head = free_list.head;
            next = fl_head->next;
        } while(!CAS(&free_list.head, fl_head, fl_next)); 
        if (fl_head) {
           fl_head->node->val = val; 
           return;
        }
    }
    /* Append to head */
    new_node = malloc(sizeof(node_t));
    new_node.val = val;
    new_node.deleted = 0;
    do {
        head = list.head;
        new_node.next = head;
    } while(!CAS(&list.head, head, new_node));

}
void remove(node_t *node) {
    fl_node_t *fl_node;
    fl_node_t *fl_head;

    /* Mark logically deleted */
    node->deleted = 1;
    fl_node = (fl_node_t*) node;

    /* Add to free-list */
    do {
        fl_head = free_list.head;
        fl_node->next =fl_head;
    } while(!CAS(&free_list.head, fl_head, fl_node)); 
}

2 Answers

I found gavra0's implementation on github. With a modification by adding a free-list (using lock-free stack implementation), I got some working code.

The repository is https://github.com/buszk/ConcLinkedList. And the implementation is in this link in the dev branch.

Correct answer by Bruce Shen on October 19, 2020

When it comes to Lock free and wait free data structures, rather than try to reinvent the wheel or fix something and spend ages trying to prove that it's right, use a proven existing implementation where possible.

Lock free implementations are notoriously hard to get right and difficult to prove right. What is right on one CPU architecture, may be wrong on another.

In practice, where we've had to use them for performance reasons they can go and go, and then one day blow up. We've had good success with implementations adapted from here

http://www.1024cores.net

He also has references to other libraries and provides good insight into concurrent programming. Well worth a read.

Answered by Matt on October 19, 2020

Add your own answers!

Related Questions

Appending a list in a list using a for loop

2  Asked on November 22, 2021 by syed-ahmed

 

Regular expression to find Specific character in a string

4  Asked on November 22, 2021 by user3061338

       

laravel count records based on each single date

1  Asked on November 22, 2021 by gulzar-ali

       

Change one property in CSS

2  Asked on November 22, 2021 by darek

 

Splitting values in a list and making variables of them

1  Asked on November 22, 2021 by premier12

     

JSX fragment has no corresponding closing tag

1  Asked on November 22, 2021 by chinwe-watkins

   

How to slow down window.location.href on AJAX request

3  Asked on November 22, 2021 by agiftel-longwave

     

Why list initialization disallow narrowing?

0  Asked on November 22, 2021 by alan-jian

   

How can i remove object from nested array?

2  Asked on November 22, 2021 by trajce12

 

How to save model architecture in PyTorch?

3  Asked on November 22, 2021

 

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir