In Search of the Fastest Concurrent Union-Find Algorithm

Dan Alistarh, Alexander Fedorov, Nikita Koval

TL;DR

This paper tackles the practical performance of concurrent Union-Find algorithms, a fundamental problem in computer science. By extensively evaluating existing algorithms and introducing novel optimizations, they demonstrate that minimizing cache misses is paramount. Their findings reveal that a carefully optimized sequential algorithm leveraging hardware transactional memory (HTM) for lock elision emerges as the fastest practical solution.

What Problem Does This Paper Address?

The Union-Find (or Disjoint-Set Union) data structure is a cornerstone in computer science, essential for tasks like tracking connected components in graphs, finding minimum spanning trees, and detecting cycles. While its sequential version is well-understood and highly optimized, the concurrent version—where multiple threads operate on the data structure simultaneously—has seen less practical investigation. Despite theoretical advancements in concurrent Union-Find algorithms, there's a significant gap in understanding their real-world performance across different hardware architectures and workloads. This paper aims to bridge this gap by providing a comprehensive empirical study.

Methods

The authors conduct a thorough evaluation of various concurrent Union-Find algorithms and optimization strategies. Their approach involves:

  • Benchmarking Existing Algorithms: They implement and test several established concurrent Union-Find algorithms, focusing on different linking strategies (rank-based, pseudo-random) and path compaction techniques (splitting, halving, compression).
  • Introducing Novel Optimizations:
    • Implicit Priority Storage: They propose storing node priorities implicitly, often by using a single register for both parent pointers and priorities, reducing memory footprint and cache misses.
  • Plain Reads and Writes: They investigate using simple memory reads and writes (without explicit memory barriers or Compare-And-Swap operations) for certain updates, demonstrating that this can significantly improve performance without compromising correctness.
  • Immediate Parent Check (IPC): This optimization checks if parent pointers of two elements are already the same at the beginning of an operation, allowing for early exit and reducing unnecessary work.
  • Early Recognition (ER): This heuristic aims to detect when an operation can be terminated early by observing the progress of simultaneous climbs towards roots.
  • Exploring Hardware Transactional Memory (HTM): They integrate HTM with a coarse-grained locking strategy (lock elision) to see if it can provide scalability benefits for otherwise sequential algorithms.

Datasets

The paper evaluates algorithms on a variety of real-world and synthetic graph datasets for two main benchmarks:

  • Connected Components Benchmark:
    • USA-ROADS (real-world road network)
    • LIVE-JOURNAL (real-world social network)
    • POKEC (real-world social network)
    • RANDOM (Erdős-Rényi model)
    • HIGH-CONTENTION (synthetic graph with few nodes having many edges)
  • Boruvka's Algorithm (Minimum Spanning Tree) Benchmark:
    • USA-ROADS (real-world road network)
    • BERKELEY-STANFORD-WEB (hyperlink graph)
    • INTERNET-TOPOLOGY (Internet graph)
    • RANDOM (Erdős-Rényi model)
    • HIGH-CONTENTION (synthetic graph)

Key Insights and Ideas

  • Cache Misses are King: For Union-Find, the computational cost of operations is so low that memory access patterns, particularly cache misses, become the dominant performance bottleneck. Algorithms that minimize memory traffic inherently perform better.
  • Simplicity Can Be Fast: Counter-intuitively, a highly optimized sequential algorithm using hardware transactional memory (HTM) for lock elision proved to be one of the fastest concurrent solutions. This suggests that for this problem, avoiding complex concurrent synchronization primitives can be more beneficial.
  • Plain Writes are Viable: Using simple memory writes instead of more expensive atomic operations (like CAS) for certain parent updates can yield significant speedups (up to 40%), especially on Intel and AMD architectures, without sacrificing correctness.
  • IPC is a Big Win: The Immediate Parent Check (IPC) optimization consistently provides substantial performance improvements across various algorithms and architectures, highlighting its effectiveness in reducing redundant work.
  • NUMA Effects Matter: Performance scaling is significantly impacted by Non-Uniform Memory Access (NUMA) architectures, especially as the number of threads increases and threads start accessing memory across different sockets. AMD processors showed better scalability in multi-socket scenarios compared to Intel and ARM.

Key Results

  • Fastest Algorithm: An optimized sequential algorithm leveraging HTM for lock elision, combined with splitting path compaction and pseudo-random or rank priorities, emerged as the fastest variant across most tested scenarios.
  • Optimization Impact:
    • Plain writes (instead of CAS) provided up to a 40% speedup.
  • Immediate Parent Check (IPC) significantly improved performance for all tested algorithms.
  • Compression path compaction was generally inferior to splitting and halving due to higher cache miss rates.
  • Architectural Differences: While performance trends were similar across Intel, AMD, and ARM, AMD showed better multi-socket scalability. ARM's performance was less sensitive to algorithmic differences due to its slower processor relative to memory speed.
  • HTM Benefits: HTM-based solutions were significantly better in sparse graph scenarios, likely because transactions are less prone to touching the same memory locations, leading to fewer conflicts.

Limitations and Future Work

  • NUMA-Aware Algorithms: The paper acknowledges that current algorithms do not scale well beyond a certain number of sockets due to NUMA effects. Developing provably efficient concurrent NUMA-aware algorithms is identified as an exciting future research direction.
  • Theoretical Guarantees: While plain writes and IPC optimizations show practical benefits, the paper notes that further study is needed to understand the theoretical guarantees of the resulting algorithms, especially in the context of concurrent executions and common graph distributions.
  • Adversarial Inputs: The study primarily focuses on non-adversarial graph inputs. The performance on adversarial inputs, which can stress specific synchronization mechanisms, might differ.
  • Boruvka's Algorithm Scaling: The Boruvka's algorithm benchmark showed limited scaling due to internal synchronization, suggesting that further research into optimizing its concurrent execution is warranted.

Summary updated

Abstract

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.
BibTeX
@inproceedings{alistarh2019search,
  author = {Dan Alistarh and Alexander Fedorov and Nikita Koval},
  title = {{In Search of the Fastest Concurrent Union-Find Algorithm}},
  booktitle = {OPODIS},
  year = {2019},
  url = {https://openreview.net/forum?id=FwrCFFCPKfP},
}
Figure