Long-linked multithreading

Question

I have a question with an algorithm. There are 10 threads in the system, and you are given a list of links with 10K elements. How do you synchronize threads (add deletion, etc.) to optimize performance? Using a mutex for a list is not recommended, as it will slow down.

Answer 1

A linked list of struct data assumes that all operations follow sequential rules. See parallel linked list

No matter what mechanism you use to implement it, the interface and expected behavior imply consistent logic.

Answer 2

If all positions are available at the same frequency, and you can change the node list, you can add a mutex for each node:

typedef struct node{ char* data; struct listNode *next; pthread_mutex_t lock; } listNode ; 

The size of the node data also depends. If it is very small, this can cause overhead due to the storage, creation and removal of mutexes.

If this is overhead or cannot change the node, you can split the list into (for example) 100 groups of 100 elements and use a mutex for each group

Answer 3

You can use futex for Linux system call for synchronization.

Answer 4

It depends on the operation you want to do in the list of links, and if the list is sorted.

• If you are concerned that 2 threads are changing the value of some node, add mutex for each hole, as mentioned here.
• If you are worried about working with the list (add, delete): it depends, if you do more reading than writing, use the write lock of the reader if each thread works with a part of the list than you can only allow access to the relevant topic

Answer 5

I believe Evans answer is correct. But I would suggest using spinlocks instead of mutexes . Spinlocks are more effective in case of low concurrency and short lock holding times.

 typedef struct ListNode { void * data; struct ListNode * next; pthread_spinlock_t lock; } ListNode; 

Answer 6

The correct solution depends heavily on the frequency of work with the object you want to synchronize (a list in your case). Operations on a container - creating a container, modifying a container, bypassing a container, and modifying an object. If, for example, the list is mainly moved and read, it may be that the list is the wrong container for the job. Perhaps you really need some kind of map (also called a dictionary) that provides very quick read access if you have a key value. In this case, there is no workaround at all, and it may be that synchronizing the entire map container becomes the most effective, simply because we changed the type of container.

Answer 7

Firstly, assuming that adding / removing elements to the list is not a cause of multithreading (instead, the taxation process is the logic for defining / creating these elements). If the insertion / deletion time of the list is a bottleneck, perhaps you should review your data structure.

Further, assuming that each thread will not interact with each other (one thread does not delete the record that was inserted by the other) and that each thread has a finite amount of work. Each thread does not touch the actual linked list; instead, each thread supports two additional lists.

It works as follows:

• Each thread starts and creates two additional lists of records for deletion and insertion.

• Given that the stream is not sorted when the stream is completed, we can simply add lists of additional elements for each stream to the beginning or end of the existing list.

• Next, for deleted items, we combine the list of items to remove from each stream, and then we look at the original linked list and delete the items as they occur (performance here can be improved by using hashtable for the list of items to be deleted.

This works very well, provided that the two assumptions at the beginning are considered true. This also means that there is no need for mutexes or locks, your main list is updated only at the end with one thread after all threads are merged back into the main thread.