---
_id: '12735'
abstract:
- lang: eng
  text: "Asynchronous programming has gained significant popularity over the last
    decade: support for this programming pattern is available in many popular languages
    via libraries and native language implementations, typically in the form of coroutines
    or the async/await construct. Instead of programming via shared memory, this concept
    assumes implicit synchronization through message passing. The key data structure
    enabling such communication is the rendezvous channel. Roughly, a rendezvous channel
    is a blocking queue of size zero, so both send(e) and receive() operations wait
    for each other, performing a rendezvous when they meet. To optimize the message
    passing pattern, channels are usually equipped with a fixed-size buffer, so sends
    do not suspend and put elements into the buffer until its capacity is exceeded.
    This primitive is known as a buffered channel.\r\n\r\nThis paper presents a fast
    and scalable algorithm for both rendezvous and buffered channels. Similarly to
    modern queues, our solution is based on an infinite array with two positional
    counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add
    instruction to update them. Yet, the algorithm requires non-trivial modifications
    of this classic pattern, in order to support the full channel semantics, such
    as buffering and cancellation of waiting requests. We compare the performance
    of our solution to that of the Kotlin implementation, as well as against other
    academic proposals, showing up to 9.8× speedup. To showcase its expressiveness
    and performance, we also integrated the proposed algorithm into the standard Kotlin
    Coroutines library, replacing the previous channel implementations."
article_processing_charge: No
arxiv: 1
author:
- first_name: Nikita
  full_name: Koval, Nikita
  id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
  last_name: Koval
- 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: Roman
  full_name: Elizarov, Roman
  last_name: Elizarov
citation:
  ama: 'Koval N, Alistarh D-A, Elizarov R. Fast and scalable channels in Kotlin Coroutines.
    In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
    Parallel Programming</i>. Association for Computing Machinery; 2023:107-118. doi:<a
    href="https://doi.org/10.1145/3572848.3577481">10.1145/3572848.3577481</a>'
  apa: 'Koval, N., Alistarh, D.-A., &#38; Elizarov, R. (2023). Fast and scalable channels
    in Kotlin Coroutines. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming</i> (pp. 107–118). Montreal, QC, Canada:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3572848.3577481">https://doi.org/10.1145/3572848.3577481</a>'
  chicago: Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Fast and Scalable
    Channels in Kotlin Coroutines.” In <i>Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming</i>, 107–18. Association for
    Computing Machinery, 2023. <a href="https://doi.org/10.1145/3572848.3577481">https://doi.org/10.1145/3572848.3577481</a>.
  ieee: N. Koval, D.-A. Alistarh, and R. Elizarov, “Fast and scalable channels in
    Kotlin Coroutines,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming</i>, Montreal, QC, Canada, 2023, pp. 107–118.
  ista: 'Koval N, Alistarh D-A, Elizarov R. 2023. Fast and scalable channels in Kotlin
    Coroutines. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice
    of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel
    Programming, 107–118.'
  mla: Koval, Nikita, et al. “Fast and Scalable Channels in Kotlin Coroutines.” <i>Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>,
    Association for Computing Machinery, 2023, pp. 107–18, doi:<a href="https://doi.org/10.1145/3572848.3577481">10.1145/3572848.3577481</a>.
  short: N. Koval, D.-A. Alistarh, R. Elizarov, in:, Proceedings of the ACM SIGPLAN
    Symposium on Principles and Practice of Parallel Programming, Association for
    Computing Machinery, 2023, pp. 107–118.
conference:
  end_date: 2023-03-01
  location: Montreal, QC, Canada
  name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
  start_date: 2023-02-25
date_created: 2023-03-19T23:00:58Z
date_published: 2023-02-25T00:00:00Z
date_updated: 2023-03-20T07:29:28Z
day: '25'
department:
- _id: DaAl
doi: 10.1145/3572848.3577481
external_id:
  arxiv:
  - '2211.04986'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2211.04986
month: '02'
oa: 1
oa_version: Preprint
page: 107-118
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
  Parallel Programming
publication_identifier:
  isbn:
  - '9798400700156'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast and scalable channels in Kotlin Coroutines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '12736'
abstract:
- lang: eng
  text: Although a wide variety of handcrafted concurrent data structures have been
    proposed, there is considerable interest in universal approaches (Universal Constructions
    or UCs) for building concurrent data structures. UCs (semi-)automatically convert
    a sequential data structure into a concurrent one. The simplest approach uses
    locks [3, 6] that protect a sequential data structure and allow only one process
    to access it at a time. However, the resulting data structure is blocking. Most
    work on UCs instead focuses on obtaining non-blocking progress guarantees such
    as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have
    appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware
    UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et
    al.
acknowledgement: 'This work was supported by: the Natural Sciences and Engineering
  Research Council of Canada (NSERC) Discovery Program grant: RGPIN-2019-04227, and
  the Canada Foundation for Innovation John R. Evans Leaders Fund (CFI-JELF) with
  equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512.'
article_processing_charge: No
author:
- first_name: Vitaly
  full_name: Aksenov, Vitaly
  last_name: Aksenov
- first_name: Trevor A
  full_name: Brown, Trevor A
  id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
  last_name: Brown
- first_name: Alexander
  full_name: Fedorov, Alexander
  id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
  last_name: Fedorov
- first_name: Ilya
  full_name: Kokorin, Ilya
  last_name: Kokorin
citation:
  ama: Aksenov V, Brown TA, Fedorov A, Kokorin I. <i>Unexpected Scaling in Path Copying
    Trees</i>. Association for Computing Machinery; 2023:438-440. doi:<a href="https://doi.org/10.1145/3572848.3577512">10.1145/3572848.3577512</a>
  apa: 'Aksenov, V., Brown, T. A., Fedorov, A., &#38; Kokorin, I. (2023). <i>Unexpected
    scaling in path copying trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming</i> (pp. 438–440). Montreal,
    QB, Canada: Association for Computing Machinery. <a href="https://doi.org/10.1145/3572848.3577512">https://doi.org/10.1145/3572848.3577512</a>'
  chicago: Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. <i>Unexpected
    Scaling in Path Copying Trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming</i>. Association for Computing
    Machinery, 2023. <a href="https://doi.org/10.1145/3572848.3577512">https://doi.org/10.1145/3572848.3577512</a>.
  ieee: V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, <i>Unexpected scaling
    in path copying trees</i>. Association for Computing Machinery, 2023, pp. 438–440.
  ista: Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path
    copying trees, Association for Computing Machinery,p.
  mla: Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” <i>Proceedings
    of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>,
    Association for Computing Machinery, 2023, pp. 438–40, doi:<a href="https://doi.org/10.1145/3572848.3577512">10.1145/3572848.3577512</a>.
  short: V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path
    Copying Trees, Association for Computing Machinery, 2023.
conference:
  end_date: 2023-03-01
  location: Montreal, QB, Canada
  name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
  start_date: 2023-02-25
date_created: 2023-03-19T23:00:58Z
date_published: 2023-02-25T00:00:00Z
date_updated: 2023-03-20T07:57:27Z
day: '25'
department:
- _id: DaAl
- _id: GradSch
doi: 10.1145/3572848.3577512
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/3572848.3577512
month: '02'
oa: 1
oa_version: Published Version
page: 438-440
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
  Parallel Programming
publication_identifier:
  isbn:
  - '9798400700156'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Unexpected scaling in path copying trees
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...