...
- Performance
- measure time for different number of threads
- compare the different approaches
- Correctness (harder to check)
- linearizability
- thread safety
- no deadlocks no livelocks
- the number/size of elements enqueued has to be equal to the sum of number/size of elements dequeued, evicted and remaining in the buffer at the end of the test:
- enqueued = dequeued + evicted + remaining
The general structure of a test application for RingBuffer has:
...
Results
Comparing the number or size of elements added in 1min for the three implementations (see Figure Figures below), it was observed that the lock-based implementation is the most inefficient, while the other two implementation give similar results, with some variations for smaller number of threads, where the one that uses a lock for dequeue and eviction proves to be better. The tests use the "Limit by number" strategy for the buffer size.
slightly better results for the completely lock-free implementation, as expected. The figures are based on the average values of three runs for each case.
References
[1] Maurice Herlihy, Nir Shavit, "The Art of Multiprocessor Programming, Revised Reprint"
[2] Maged M. Michael, Michael L. Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"
[3] ConcurrentLinkedQueue implementation in Java
[4] CMR buffer specifications
[5] Calculation of object sizes
...