This document is about performance measurement review on regular concurrent linked list and hand-over-hand protocol linked list.
Section#1: Regular concurrent linked list or named as coarse-grained synchronization[4].
In this review, following two structures are used in C:
An integer type of variable: key, and a char type of variable are in the node; its value ‘T’ means tail node, ‘H’ means head node, and ‘M’ means member in the list. The nature of the regular concurrent linked list is when accessing the node in the list, the whole list is locked, and lock is released after finishing the accessing. For example, when one node is added or deleted in the list, the entire list would be locked. After the action, the lock is released.
The test is about adding 1 million nodes on each thread. In total, 4 threads are to adding 4 million nodes in the list. Below numbers and image present the details:
The result is similar like the book[1] introduced. The average time taken of adding one million nodes is growing significantly when the threads added.
Section #2: Hand-over-hand locking[3] linked list (named as fine-grained synchronization[2]). Due to scaling issue in the regular concurrent linked list, the review is to introduce hand-over-hand protocol linked list. Hand-over-hand locking is about lock the previous and current nodes in the list first, and then release the previous node next when traveling the list. In the progress, there are always 2 nodes locked. In each node, we have a lock variable. Detailed structure is present below:
Section#3: Design of the test:
1. A loop of 1000 to 9000 times of adding integer numbers to an ordered linked list.
2. Total of 3 threads to add integer numbers. Above 1000 loops mean adding 3000 nodes into the list, and 9000 loops mean to add 27000 nodes in total into the list.
3. The integer numbers are random numbers; when duplicates occur, only one is kept in the list.
4. The head and tail nodes are set by key and name(key: -2147483648, name:’H’; key: 2147483647, name: ‘T’). The setting suggests that the head node is the first node in the list, and the tail node is the last one.
After establishing design, the tests began. Every test, the result looks like this:
After 1000 ~ 9000 times of adding nodes into the list, the result looks like on the below.
The conclusion:
A) Coarse-grained protocol is faster than fined-grained protocol when adding the nodes into the list.
B) Fined-grained protocol used to add nodes into the list costs more resources than the regular linked list. The major reason is because the too many locks are opened and closed in the process.
References:
[1] R. Arpaci-Dusseau and A. Arpaci-Dusseau, “Lock-Based Concurrent Data Structures,” in Operating Systems: Three Easy Pieces, Chapter 29, p. 9: https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks-usage.pdf.
[2] W. Herlihy and N. Shavit, The Art of Multiprocessor Programming Second edition(Morgan Kaufmann, 2021).
[3] “Concurrent Data Structures” by Mark Moir and Nir Shavit. In Handbook of Data
Structures and Applications (Editors D. Metha and S.Sahni). Chapman and Hall/CRC Press,
2004. Available: http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf.
[4] T. Kelly, “Programming Workbench: Hand-Over-Hand Locking for Highly Concurrent Collections,” ;login:, vol. 45, no. 361 (FALL 2020): https://www.usenix.org/system/files/login/articles/login_fall20_14_kelly.pdf