---
_id: '7605'
abstract:
- lang: eng
  text: '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. '
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Alexander
  full_name: Fedorov, Alexander
  last_name: Fedorov
- first_name: Nikita
  full_name: Koval, Nikita
  id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
  last_name: Koval
citation:
  ama: 'Alistarh D-A, Fedorov A, Koval N. In search of the fastest concurrent union-find
    algorithm. In: <i>23rd International Conference on Principles of Distributed Systems</i>.
    Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:15:1-15:16. doi:<a
    href="https://doi.org/10.4230/LIPIcs.OPODIS.2019.15">10.4230/LIPIcs.OPODIS.2019.15</a>'
  apa: 'Alistarh, D.-A., Fedorov, A., &#38; Koval, N. (2020). In search of the fastest
    concurrent union-find algorithm. In <i>23rd International Conference on Principles
    of Distributed Systems</i> (Vol. 153, p. 15:1-15:16). Neuchatal, Switzerland:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2019.15">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>'
  chicago: Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of
    the Fastest Concurrent Union-Find Algorithm.” In <i>23rd International Conference
    on Principles of Distributed Systems</i>, 153:15:1-15:16. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2019.15">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>.
  ieee: D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent
    union-find algorithm,” in <i>23rd International Conference on Principles of Distributed
    Systems</i>, Neuchatal, Switzerland, 2020, vol. 153, p. 15:1-15:16.
  ista: 'Alistarh D-A, Fedorov A, Koval N. 2020. In search of the fastest concurrent
    union-find algorithm. 23rd International Conference on Principles of Distributed
    Systems. OPODIS: International Conference on Principles of Distributed Systems,
    LIPIcs, vol. 153, 15:1-15:16.'
  mla: Alistarh, Dan-Adrian, et al. “In Search of the Fastest Concurrent Union-Find
    Algorithm.” <i>23rd International Conference on Principles of Distributed Systems</i>,
    vol. 153, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16,
    doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2019.15">10.4230/LIPIcs.OPODIS.2019.15</a>.
  short: D.-A. Alistarh, A. Fedorov, N. Koval, in:, 23rd International Conference
    on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020, p. 15:1-15:16.
conference:
  end_date: 2019-12-19
  location: Neuchatal, Switzerland
  name: 'OPODIS: International Conference on Principles of Distributed Systems'
  start_date: 2019-12-17
corr_author: '1'
date_created: 2020-03-22T23:00:46Z
date_published: 2020-02-01T00:00:00Z
date_updated: 2025-07-10T11:54:46Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2019.15
external_id:
  arxiv:
  - '1911.06347'
file:
- access_level: open_access
  checksum: d66f07ecb609d9f02433e39f80a447e9
  content_type: application/pdf
  creator: dernst
  date_created: 2020-03-23T09:22:48Z
  date_updated: 2020-07-14T12:48:01Z
  file_id: '7609'
  file_name: 2019_LIPIcs_Alistarh.pdf
  file_size: 13074131
  relation: main_file
file_date_updated: 2020-07-14T12:48:01Z
has_accepted_license: '1'
intvolume: '       153'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '02'
oa: 1
oa_version: Published Version
page: 15:1-15:16
publication: 23rd International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959771337'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: In search of the fastest concurrent union-find algorithm
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 153
year: '2020'
...