The Java developers kit requires a size() operation for all objects. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a highly scalable wait-free implementation of a concurrent size() operation based on a new lock-free interrupting snapshots algorithm for the classical atomic snapshot problem. This is perhaps the ﬁrst example of the potential benefit from using atomic snapshots in real industrial code (the concurrency package is currently deployed on over 10 million desktops). The key idea behind the new algorithm is to allow snapshot scans to interrupt each other until they agree on a shared linearization point with respect to updates, rather than trying, as was done in the past, to have them coordinate the collecting of a shared global view. As we show, the new algorithm scales well, significantly outperforming existing implementations.
Interrupting snapshots and the Java™ size() method. Yehuda Afek, Nir Shavit, and Moran Tzafrir. DISC 2009. (Talk slides.)
The source code is available in C++ and Java.