Print indd

A theoretical comparison between (α) and (β) shows that the best-case
execution time of a lock-free software variant is approximately equal to the
execution time of the critical section of a lock-based variant without the time
for acquiring and releasing the lock. The average time of the lock-free variant is

---

CaCAO: Complex and Compositional Atomic Operations
143
dependent on the interfering concurrency and the thereby necessary retries (as
well as other factors like run-time background traffic). Whereas for the lock-free
variant the average execution time is linear in the number of retries, the average
lock-based execution time is linear in the number of concurrent contenders for
the lock.
This comparison shows that - whereas in the best-case a lock-free imple-
mentation is always better - in the average case there can be a cross-over point
between the lock-based and lock-free implementations. If the concurrency depen-
dent retry rate is greater than a threshold, the lock-based implementation yields
better performance and vice versa. A design time decision between (
α) and (β)
would be necessary by the programmer. In Sect.
6
we talk about a more dynamic
decision making as future work.