  Union-Find (or Disjoint-Set Union) is one of the fundamental problems in
computer science; it has been well-studied from both theoretical and practical
perspectives in the sequential case. Recently, there has been mounting interest
in analyzing this problem in the concurrent scenario, and several
asymptotically-efficient algorithms have been proposed. Yet, to date, there is
very little known about the practical performance of concurrent Union-Find.
  This work addresses this gap. We evaluate and analyze the performance of
several concurrent Union-Find algorithms and optimization strategies across a
wide range of platforms (Intel, AMD, and ARM) and workloads (social, random,
and road networks, as well as integrations into more complex algorithms). We
first observe that, due to the limited computational cost, the number of
induced cache misses is the critical determining factor for the performance of
existing algorithms. We introduce new techniques to reduce this cost by storing
node priorities implicitly and by using plain reads and writes in a way that
does not affect the correctness of the algorithms. Finally, we show that
Union-Find implementations are an interesting application for Transactional
Memory (TM): one of the fastest algorithm variants we discovered is a
sequential one that uses coarse-grained locking with the lock elision
optimization to reduce synchronization cost and increase scalability.
