The size of a data structure (i.e., the number of elements in it) is a
widely used property. However, for concurrent programs,
obtaining a correct size efficiently is non-trivial, and in fact, there
exists no mechanism for that in the literature.
We start by reviewing desired properties for concurrent data
structures in general, and continue to the challenges in achieving
them when designing a concurrent size operation. We then present
the first methodology for adding a concurrent size operation
which is both correct (linearizable) and efficient (wait-free and
with time complexity independent of data-structure size) to sets
and dictionaries. A Java evaluation demonstrates that our size
operation executes faster by orders of magnitude compared to
existing linearizable solutions.