---
_id: '7635'
abstract:
- lang: eng
  text: Concurrent programming can be notoriously complex and error-prone. Programming
    bugs can arise from a variety of sources, such as operation re-reordering, or
    incomplete understanding of the memory model. A variety of formal and model checking
    methods have been developed to address this fundamental difficulty. While technically
    interesting, existing academic methods are still hard to apply to the large codebases
    typical of industrial deployments, which limits their practical impact.
article_processing_charge: No
author:
- first_name: Nikita
  full_name: Koval, Nikita
  id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
  last_name: Koval
- first_name: Mariia
  full_name: Sokolova, Mariia
  id: 26217AE4-77FF-11EA-8101-AD24D49E41F4
  last_name: Sokolova
- first_name: Alexander
  full_name: Fedorov, Alexander
  last_name: Fedorov
- 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: Dmitry
  full_name: Tsitelov, Dmitry
  last_name: Tsitelov
citation:
  ama: 'Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. Testing concurrency
    on the JVM with Lincheck. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming, PPOPP</i>. Association for Computing Machinery;
    2020:423-424. doi:<a href="https://doi.org/10.1145/3332466.3374503">10.1145/3332466.3374503</a>'
  apa: 'Koval, N., Sokolova, M., Fedorov, A., Alistarh, D.-A., &#38; Tsitelov, D.
    (2020). Testing concurrency on the JVM with Lincheck. In <i>Proceedings of the
    ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i>
    (pp. 423–424). San Diego, CA, United States: Association for Computing Machinery.
    <a href="https://doi.org/10.1145/3332466.3374503">https://doi.org/10.1145/3332466.3374503</a>'
  chicago: Koval, Nikita, Mariia Sokolova, Alexander Fedorov, Dan-Adrian Alistarh,
    and Dmitry Tsitelov. “Testing Concurrency on the JVM with Lincheck.” In <i>Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
    PPOPP</i>, 423–24. Association for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3332466.3374503">https://doi.org/10.1145/3332466.3374503</a>.
  ieee: N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, and D. Tsitelov, “Testing
    concurrency on the JVM with Lincheck,” in <i>Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming, PPOPP</i>, San Diego, CA,
    United States, 2020, pp. 423–424.
  ista: 'Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. 2020. Testing concurrency
    on the JVM with Lincheck. Proceedings of the ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming, PPOPP. PPOPP: Principles and Practice of
    Parallel Programming, 423–424.'
  mla: Koval, Nikita, et al. “Testing Concurrency on the JVM with Lincheck.” <i>Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
    PPOPP</i>, Association for Computing Machinery, 2020, pp. 423–24, doi:<a href="https://doi.org/10.1145/3332466.3374503">10.1145/3332466.3374503</a>.
  short: N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, D. Tsitelov, in:, Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
    PPOPP, Association for Computing Machinery, 2020, pp. 423–424.
conference:
  end_date: 2020-02-26
  location: San Diego, CA, United States
  name: 'PPOPP: Principles and Practice of Parallel Programming'
  start_date: 2020-02-22
date_created: 2020-04-05T22:00:48Z
date_published: 2020-02-19T00:00:00Z
date_updated: 2024-02-28T12:53:46Z
day: '19'
department:
- _id: DaAl
doi: 10.1145/3332466.3374503
language:
- iso: eng
month: '02'
oa_version: None
page: 423-424
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
  Parallel Programming, PPOPP
publication_identifier:
  isbn:
  - '9781450368186'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing concurrency on the JVM with Lincheck
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '7636'
abstract:
- lang: eng
  text: "Balanced search trees typically use key comparisons to guide their operations,
    and achieve logarithmic running time. By relying on numerical properties of the
    keys, interpolation search achieves lower search complexity and better performance.
    Although interpolation-based data structures were investigated in the past, their
    non-blocking concurrent variants have received very little attention so far.\r\nIn
    this paper, we propose the first non-blocking implementation of the classic interpolation
    search tree (IST) data structure. For arbitrary key distributions, the data structure
    ensures worst-case O(log n + p) amortized time for search, insertion and deletion
    traversals. When the input key distributions are smooth, lookups run in expected
    O(log log n + p) time, and insertion and deletion run in expected amortized O(log
    log n + p) time, where p is a bound on the number of threads. To improve the scalability
    of concurrent insertion and deletion, we propose a novel parallel rebuilding technique,
    which should be of independent interest.\r\nWe evaluate whether the theoretical
    improvements translate to practice by implementing the concurrent interpolation
    search tree, and benchmarking it on uniform and nonuniform key distributions,
    for dataset sizes in the millions to billions of keys. Relative to the state-of-the-art
    concurrent data structures, the concurrent interpolation search tree achieves
    performance improvements of up to 15% under high update rates, and of up to 50%
    under moderate update rates. Further, ISTs exhibit up to 2X less cache-misses,
    and consume 1.2 -- 2.6X less memory compared to the next best alternative on typical
    dataset sizes. We find that the results are surprisingly robust to distributional
    skew, which suggests that our data structure can be a promising alternative to
    classic concurrent search structures."
acknowledgement: "This project has received funding from the European Research Council
  (ERC) under the European Union Horizon 2020 research and innovation program, grant
  agreement No 805223, ERC Starting Grant ScaleML. We acknowledge the support of the
  Natural Sciences and\r\nEngineering Research Council of Canada (NSERC). "
article_processing_charge: No
author:
- first_name: Trevor A
  full_name: Brown, Trevor A
  id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
  last_name: Brown
- first_name: Aleksandar
  full_name: Prokopec, Aleksandar
  last_name: Prokopec
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
citation:
  ama: 'Brown TA, Prokopec A, Alistarh D-A. Non-blocking interpolation search trees
    with doubly-logarithmic running time. In: <i>Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming</i>. Association for Computing
    Machinery; 2020:276-291. doi:<a href="https://doi.org/10.1145/3332466.3374542">10.1145/3332466.3374542</a>'
  apa: 'Brown, T. A., Prokopec, A., &#38; Alistarh, D.-A. (2020). Non-blocking interpolation
    search trees with doubly-logarithmic running time. In <i>Proceedings of the ACM
    SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp.
    276–291). San Diego, CA, United States: Association for Computing Machinery. <a
    href="https://doi.org/10.1145/3332466.3374542">https://doi.org/10.1145/3332466.3374542</a>'
  chicago: Brown, Trevor A, Aleksandar Prokopec, and Dan-Adrian Alistarh. “Non-Blocking
    Interpolation Search Trees with Doubly-Logarithmic Running Time.” In <i>Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>,
    276–91. Association for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3332466.3374542">https://doi.org/10.1145/3332466.3374542</a>.
  ieee: T. A. Brown, A. Prokopec, and D.-A. Alistarh, “Non-blocking interpolation
    search trees with doubly-logarithmic running time,” in <i>Proceedings of the ACM
    SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, San
    Diego, CA, United States, 2020, pp. 276–291.
  ista: 'Brown TA, Prokopec A, Alistarh D-A. 2020. Non-blocking interpolation search
    trees with doubly-logarithmic running time. Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming. PPOPP: Principles and Practice
    of Parallel Programming, 276–291.'
  mla: Brown, Trevor A., et al. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic
    Running Time.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice
    of Parallel Programming</i>, Association for Computing Machinery, 2020, pp. 276–91,
    doi:<a href="https://doi.org/10.1145/3332466.3374542">10.1145/3332466.3374542</a>.
  short: T.A. Brown, A. Prokopec, D.-A. Alistarh, in:, Proceedings of the ACM SIGPLAN
    Symposium on Principles and Practice of Parallel Programming, Association for
    Computing Machinery, 2020, pp. 276–291.
conference:
  end_date: 2020-02-26
  location: San Diego, CA, United States
  name: 'PPOPP: Principles and Practice of Parallel Programming'
  start_date: 2020-02-22
date_created: 2020-04-05T22:00:49Z
date_published: 2020-02-19T00:00:00Z
date_updated: 2024-02-28T12:55:14Z
day: '19'
department:
- _id: DaAl
doi: 10.1145/3332466.3374542
ec_funded: 1
external_id:
  isi:
  - '000564476500020'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/3332466.3374542
month: '02'
oa: 1
oa_version: Published Version
page: 276-291
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
  Parallel Programming
publication_identifier:
  isbn:
  - '9781450368186'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Non-blocking interpolation search trees with doubly-logarithmic running time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...