---
OA_type: closed access
_id: '776'
abstract:
- lang: eng
  text: High-performance concurrent priority queues are essential for applications
    such as task scheduling and discrete event simulation. Unfortunately, even the
    best performing implementations do not scale past a number of threads in the single
    digits. This is because of the sequential bottleneck in accessing the elements
    at the head of the queue in order to perform a DeleteMin operation. In this paper,
    we present the SprayList, a scalable priority queue with relaxed ordering semantics.
    Starting from a non-blocking SkipList, the main innovation behind our design is
    that the DeleteMin operations avoid a sequential bottleneck by "spraying"
    themselves onto the head of the SkipList list in a coordinated fashion. The spraying
    is implemented using a carefully designed random walk, so that DeleteMin returns
    an element among the first O(plog3p) in the list, with high probability, where
    p is the number of threads. We prove that the running time of a DeleteMin operation
    is O(log3p), with high probability, independent of the size of the list. Our experiments
    show that the relaxed semantics allow the data structure to scale for high thread
    counts, comparable to a classic unordered SkipList. Furthermore, we observe that,
    for reasonably parallel workloads, the scalability benefits of relaxation considerably
    outweigh the additional work due to out-of-order execution.
acknowledgement: "Support is gratefully acknowledged from the National Science Foundation
  under grants CCF-1217921, CCF-1301926, and IIS-1447786, the Department of Energy
  under grant ER26116/DE-SC0008923, and the Oracle\r\nand Intel corporations."
article_processing_charge: No
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: Justin
  full_name: Kopinsky, Justin
  last_name: Kopinsky
- first_name: Jerry
  full_name: Li, Jerry
  last_name: Li
- first_name: Nir
  full_name: Shavit, Nir
  last_name: Shavit
citation:
  ama: 'Alistarh D-A, Kopinsky J, Li J, Shavit N. The SprayList: A scalable relaxed
    priority queue. In: <i>Proceedings of the 20th ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming</i>. ACM; 2015:11-20. doi:<a href="https://doi.org/10.1145/2688500.2688523">10.1145/2688500.2688523</a>'
  apa: 'Alistarh, D.-A., Kopinsky, J., Li, J., &#38; Shavit, N. (2015). The SprayList:
    A scalable relaxed priority queue. In <i>Proceedings of the 20th ACM SIGPLAN Symposium
    on Principles and Practice of Parallel Programming</i> (pp. 11–20). San Francisco,
    CA, United States: ACM. <a href="https://doi.org/10.1145/2688500.2688523">https://doi.org/10.1145/2688500.2688523</a>'
  chicago: 'Alistarh, Dan-Adrian, Justin Kopinsky, Jerry Li, and Nir Shavit. “The
    SprayList: A Scalable Relaxed Priority Queue.” In <i>Proceedings of the 20th ACM
    SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 11–20.
    ACM, 2015. <a href="https://doi.org/10.1145/2688500.2688523">https://doi.org/10.1145/2688500.2688523</a>.'
  ieee: 'D.-A. Alistarh, J. Kopinsky, J. Li, and N. Shavit, “The SprayList: A scalable
    relaxed priority queue,” in <i>Proceedings of the 20th ACM SIGPLAN Symposium on
    Principles and Practice of Parallel Programming</i>, San Francisco, CA, United
    States, 2015, pp. 11–20.'
  ista: 'Alistarh D-A, Kopinsky J, Li J, Shavit N. 2015. The SprayList: A scalable
    relaxed priority queue. Proceedings of the 20th ACM SIGPLAN Symposium on Principles
    and Practice of Parallel Programming. PPoPP: Principles and Practice of Parallel
    Pogramming, 11–20.'
  mla: 'Alistarh, Dan-Adrian, et al. “The SprayList: A Scalable Relaxed Priority Queue.”
    <i>Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of
    Parallel Programming</i>, ACM, 2015, pp. 11–20, doi:<a href="https://doi.org/10.1145/2688500.2688523">10.1145/2688500.2688523</a>.'
  short: D.-A. Alistarh, J. Kopinsky, J. Li, N. Shavit, in:, Proceedings of the 20th
    ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM,
    2015, pp. 11–20.
conference:
  end_date: 2015-02-11
  location: San Francisco, CA, United States
  name: 'PPoPP: Principles and Practice of Parallel Pogramming'
  start_date: 2015-02-07
date_created: 2018-12-11T11:48:26Z
date_published: 2015-01-24T00:00:00Z
date_updated: 2026-05-18T12:40:58Z
day: '24'
doi: 10.1145/2688500.2688523
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 11 - 20
publication: Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice
  of Parallel Programming
publication_identifier:
  isbn:
  - '9781450332057'
publication_status: published
publisher: ACM
publist_id: '6878'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The SprayList: A scalable relaxed priority queue'
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2015'
...