Search Results

Documents authored by Williams, Marvin

Artifact
Software
DOI: 10.4230/artifacts.27678
RagnarGrootKoerkamp/quickheap

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Abstract
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams. RagnarGrootKoerkamp/quickheap (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27678,
   title = {{RagnarGrootKoerkamp/quickheap}}, 
   author = {Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd;origin=https://github.com/RagnarGrootKoerkamp/quickheap;visit=swh:1:snp:e0266e2ec33db11f26f6e3085d18ce1756621d86;anchor=swh:1:rev:44e0d1819be4eb414f91b55a5a9ebc8fc7f57e49}{\texttt{swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd}} (visited on 2026-08-25)},
   url = {https://github.com/RagnarGrootKoerkamp/quickheap},
   doi = {10.4230/artifacts.27678},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.16
SimdQuickHeap: The QuickHeap Reconsidered

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Motivation. Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it has frequent cache misses and is hard to optimize using e.g. SIMD instructions. Contributions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all pivots adjacent in memory, with elements between consecutive pivots stored in dedicated buckets. This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity O(log n) per operation, which improves to O((1/W) log n) in non-degenerate cases, where W is the number of words in a SIMD register. In this case, the I/O-complexity is amortized O(1/B) per push and O((1/B) log₂(n/M)) per pop. Results. In synthetic benchmarks, the SimdQuickHeap is 1.2× to 1.7× as fast as the monotone radix heap, the next-best competitor, and 1.4× to 2.8× as fast as the superscalar sample queue, the fastest comparison-based priority queue. The SimdQuickHeap needs around 1.5log₂ n comparisons and log₂ n nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra’s shortest path algorithm and Jarník-Prim’s minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest.
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams. SimdQuickHeap: The QuickHeap Reconsidered. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:LIPIcs.ESA.2026.16,
  author =	{Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
  title =	{{SimdQuickHeap: The QuickHeap Reconsidered}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.16},
  URN =		{urn:nbn:de:0030-drops-271527},
  doi =		{10.4230/LIPIcs.ESA.2026.16},
  annote =	{Keywords: Heap, SIMD, Priority Queue}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.85
A Simple yet Exact Analysis of the MultiQueue

Authors: Stefan Walzer and Marvin Williams

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The MultiQueue is a relaxed concurrent priority queue consisting of n internal priority queues, where an insertion uses a random queue and a deletion considers two random queues and deletes the minimum from the one with the smaller minimum. The rank error of the deletion is the number of smaller elements in the MultiQueue. Alistarh et al. [Alistarh et al., 2017] have demonstrated in a sophisticated potential argument that the expected rank error remains bounded by 𝒪(n) over long sequences of deletions. In this paper we present a simpler analysis by identifying the stable distribution of an underlying Markov chain and with it the long-term distribution of the rank error exactly. Simple calculations then reveal the expected long-term rank error to be (5/6)n-1+1/(6n). Our arguments generalize to deletion schemes where the probability to delete from a given queue depends only on the rank of the queue. Specifically, this includes deleting from the best of c randomly selected queues for any c > 1.
Cite as

Stefan Walzer and Marvin Williams. A Simple yet Exact Analysis of the MultiQueue. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{walzer_et_al:LIPIcs.ESA.2025.85,
  author =	{Walzer, Stefan and Williams, Marvin},
  title =	{{A Simple yet Exact Analysis of the MultiQueue}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{85:1--85:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.85},
  URN =		{urn:nbn:de:0030-drops-245533},
  doi =		{10.4230/LIPIcs.ESA.2025.85},
  annote =	{Keywords: MultiQueue, concurrent data structure, stochastic process, Markov chain}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.81
Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues

Authors: Marvin Williams, Peter Sanders, and Roman Dementiev

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Priority queues with parallel access are an attractive data structure for applications like prioritized online scheduling, discrete event simulation, or greedy algorithms. However, a classical priority queue constitutes a severe bottleneck in this context, leading to very small throughput. Hence, there has been significant interest in concurrent priority queues with relaxed semantics. We investigate the complementary quality criteria rank error (how close are deleted elements to the global minimum) and delay (for each element x, how many elements with lower priority are deleted before x). In this paper, we introduce MultiQueues as a natural approach to relaxed priority queues based on multiple sequential priority queues. Their naturally high theoretical scalability is further enhanced by using three orthogonal ways of batching operations on the sequential queues. Experiments indicate that MultiQueues present a very good performance-quality tradeoff and considerably outperform competing approaches in at least one of these aspects. We employ a seemingly paradoxical technique of "wait-free locking" that might be of more general interest to convert sequential data structures to relaxed concurrent data structures.
Cite as

Marvin Williams, Peter Sanders, and Roman Dementiev. Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{williams_et_al:LIPIcs.ESA.2021.81,
  author =	{Williams, Marvin and Sanders, Peter and Dementiev, Roman},
  title =	{{Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{81:1--81:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.81},
  URN =		{urn:nbn:de:0030-drops-146627},
  doi =		{10.4230/LIPIcs.ESA.2021.81},
  annote =	{Keywords: concurrent data structure, priority queues, randomized algorithms, wait-free locking}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact