A back-to-basics empirical study of priority queues

Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

The theory community has proposed several new heap variants in the recent past which have remained largely untested experimentally. We take the field back to the drawing board, with straightforward implementations of both classic and novel structures using only standard, well-known optimizations. We study the behavior of each structure on a variety of inputs, including artificial workloads, workloads generated by running algorithms on real map data, and workloads from a discrete event simulator used in recent systems networking research. We provide observations about which characteristics are most correlated to performance. For example, we find that the L1 cache miss rate appears to be strongly correlated with wallclock time. We also provide observations about how the input sequence affects the relative performance of the different heap variants. For example, we show (both theoretically and in practice) that certain random insertion-deletion sequences are degenerate and can lead to misleading results. Overall, our findings suggest that while the conventional wisdom holds in some cases, it is sorely mistaken in others.

Original languageEnglish (US)
Title of host publication2014 Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014
EditorsCatherine C. McGeoch, Ulrich Meyer
PublisherSociety for Industrial and Applied Mathematics Publications
Pages61-72
Number of pages12
ISBN (Electronic)9781611973198
DOIs
StatePublished - Jan 1 2014
Event16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014 - Portland, United States
Duration: Jan 5 2014Jan 5 2014

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
ISSN (Print)2164-0300

Other

Other16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014
CountryUnited States
CityPortland
Period1/5/141/5/14

All Science Journal Classification (ASJC) codes

  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A back-to-basics empirical study of priority queues'. Together they form a unique fingerprint.

  • Cite this

    Larkin, D. H., Sen, S., & Tarjan, R. E. (2014). A back-to-basics empirical study of priority queues. In C. C. McGeoch, & U. Meyer (Eds.), 2014 Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014 (pp. 61-72). (Proceedings of the Workshop on Algorithm Engineering and Experiments). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611973198.7