Modeling and Analyzing the Performance of Lock-Free Data Structures
Aras Atalar, Paul Renaud-Goud, Philippas Tsigas · Chalmers Research (Chalmers University of Technology) · 2014
This paper considers the modeling and the analysis of the performance of lock-free concurrent datastructures. Lock-free designs employ an optimistic conflict control approach, allowing several processesto access the shared data object at the same time. The operations on these data structures are typicallydesigned as compositions of retry loops.Our main contribution is a new way of modeling and analyzing a general class of lock-free algorithms,achieving predictions of throughput that are close to what we observe in practice. In our model weintroduce two key metrics that shape the performance of lock-free algorithms: (i) expansion in executiontime of a retry due to memory congestion and (ii) number of wasted retries. We show how to computethese two metrics, and how to combine them, to calculate the throughput of an arguably large class oflock-free algorithms. Our analysis also captures the throughput performance of a lock-free algorithm whenexecuted as part of a larger parallel application. This part of our analysis leads to an analytical methodfor calculating a good back-off strategy to finely tune the performance of a lock-free application. Ourexperimental results, based on a set of widely used concurrent data structures and on abstract lock-freedesigns, show that our analysis follows closely the actual code behavior.To the best of our knowledge, this is the first attempt to make ends meet between theoretical boundson performance and actual measured throughput.