Skip to main content

A Back-to-Basics Empirical Study of Priority Queues

Author(s): Larkin, Daniel H; Sen, Siddhartha; Tarjan, Robert E

To refer to this page use:
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.
Publication Date: 2014
Citation: Larkin, Daniel H, Sen, Siddhartha, Tarjan, Robert E. (A Back-to-Basics Empirical Study of Priority Queues
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Workshop on Algorithm Engineering and Experiments
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.