2016/03/16 by Jakob Gruber, Gruber, Jakob, Jesper Larsson Träff +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems #Real-Time Systems Scheduling
paper · pdf · doi:10.48550/arxiv.1603.05047
openalex publication_date 2016/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A number of concurrent, relaxed priority queues have recently been proposed and implemented. Results are commonly reported for a throughput benchmark that uses a uniform distribution of keys drawn from a large integer range, and mostly for single systems. We have conducted more extensive benchmarking of three recent, relaxed priority queues on four different types of systems with different key ranges and distributions. While we can show superior throughput and scalability for our own k-LSM priority queue for the uniform key distribution, the picture changes drastically for other distributions, both with respect to achieved throughput and relative merit of the priority queues. The throughput benchmark alone is thus not sufficient to characterize the performance of concurrent priority queues. Our benchmark code and k-LSM priority queue are publicly available to foster future comparison.