This is an educational parallel algorithm collection in C of some samples of the book "The Art of Multiprocessor Programming (M. Herlihy, N. Shavit)" .
- LLSCLockFreeQueue
- "Bringing Practical LockFree Synchronization to 64Bit Applications" by Simon Doherty, Maurice Herlihy, Victor Luchangco, Mark Moir
- CASLockFreeQueue
- "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" by M. Michael and M. Scott
- CoarseGrainedSynchroList
- Coarse-Grained Synchronization Singly-linked List
- FineGrainedSynchroList
- Fine-Grained Synchronization Singly-linked List
- LazySynchroList
- Lazy Synchronization Singly-linked List
- NonBlockingList
- "A Pragmatic Implementation of Non-Blocking Linked-Lists" by Timothy L. Harris
- LockFreeList
- "Lock-Free Linked Lists and Skip Lists" by Mikhail Fomitchev, Eric Ruppert
- Skiplist
- LazySkiplist
- "A Simple Optimistic skip-list Algorithm" by Maurice Herlihy, Yossi Lev, Victor Luchangco, Nir Shavit
- LockFreeSkiplist
- "A Lock-Free concurrent skiplist with wait-free search" by Maurice Herlihy & Nir Shavit
- Hash
- (Chain) Hash Table
- OpenAddressHash
- Open-Addressed Hash Table
- StripedHash
- Striped Hash Table
- RefinableHash
- Refinable Hash Table
- CuckooHash
- "Cuckoo Hashing" by R.Pagh, F.F.Rodler
- ConcurrentCuckooHash
- Concurrent Cuckoo Hash Table
$ make $ make test $ ./queue/LLSCLockFreeQueue -h simple algorithm test bench usage: ./queue/LLSCLockFreeQueue [Options<default>] -t number_of_thread<10> -n number_of_item<1000> -v :verbose -V :debug mode -h :help Some programs have other options. Please check each.
By default, run 10 threads, and each thread inserts and deletes 1000 items.
$ ./queue/LLSCLockFreeQueue <<simple algorithm test bench>> RESULT: test OK condition => 10 threads run 1000 items inserted and deleted / thread, total 10000 items performance => interval = 0.006693 [sec] thread info: ave. = 0.002807[sec], min = 0.000832[sec], max = 0.004397[sec] You can change the number of items and the number of threads.
$ ./queue/LLSCLockFreeQueue -t 20 -n 10000 <<simple algorithm test bench>> RESULT: test OK condition => 20 threads run 10000 items inserted and deleted / thread, total 200000 items performance => interval = 0.102954 [sec] thread info: ave. = 0.050064[sec], min = 0.008257[sec], max = 0.059089[sec] You can see how to work in the LLSCLockFreeQueue program.
$ ./queue/LLSCLockFreeQueue -t 2 -n 4 -V <<simple algorithm test bench>> thread[1] add: 5 [5] thread[1] add: 6 [5][6] thread[1] add: 7 [5][6][7] thread[1] add: 8 [5][6][7][8] thread[0] add: 1 [5][6][7][8][1] thread[0] add: 2 [5][6][7][8][1][2] thread[0] add: 3 [5][6][7][8][1][2][3] thread[0] add: 4 [5][6][7][8][1][2][3][4] thread[0] delete: 5 [6][7][8][1][2][3][4] thread[0] delete: 6 [7][8][1][2][3][4] thread[0] delete: 7 [8][1][2][3][4] thread[0] delete: 8 [1][2][3][4] thread[1] delete: 1 [2][3][4] thread[1] delete: 2 [3][4] thread[1] delete: 3 [4] thread[1] delete: 4 thread(0) end 0.002006[sec] thread(1) end 0.006205[sec] RESULT: test OK condition => 2 threads run 4 items inserted and deleted / thread, total 8 items performance => interval = 0.006519 [sec] thread info: ave. = 0.004106[sec], min = 0.002006[sec], max = 0.006205[sec] Run the LLSCLockFreeQueue_test. You can see more easily how to work this program.
$ ./queue/LLSCLockFreeQueue_test [0] [0][1] [0][1][2] [0][1][2][3] [0][1][2][3][4] [0][1][2][3][4][5] [0][1][2][3][4][5][6] [0][1][2][3][4][5][6][7] [0][1][2][3][4][5][6][7][8] [0][1][2][3][4][5][6][7][8][9] [1][2][3][4][5][6][7][8][9] [2][3][4][5][6][7][8][9] [3][4][5][6][7][8][9] [4][5][6][7][8][9] [5][6][7][8][9] [6][7][8][9] [7][8][9] [8][9] [9]