Skip to content

README.md

Latest commit

 

History

History
64 lines (43 loc) · 3.41 KB

README.md

File metadata and controls

64 lines (43 loc) · 3.41 KB

echelon

$O(1)$ amortized priority queue for Rust. Adaptive Ladder Queue implementation optimized for heavy-tailed distributions.

Ideal for discrete-event simulation, job scheduling, and network modeling where event timestamps follow Pareto, log-normal, or other heavy-tailed distributions that cause standard $O(\log n)$ structures to become bottlenecks.

Usage

use echelon::{TimestampQueue, Timestamp};

let mut q = TimestampQueue::new();
q.push(Timestamp::new(3.0), "third");
q.push(Timestamp::new(1.0), "first");
q.push(Timestamp::new(2.0), "second");

assert_eq!(q.pop().unwrap().1, "first");
assert_eq!(q.pop().unwrap().1, "second");
assert_eq!(q.pop().unwrap().1, "third");

Algorithm

Based on the Adaptive Ladder Queue (Furfaro & Sacco, 2018), which extends the original Ladder Queue (Tang, Goh & Thng, 2005) with runtime auto-tuning via Smart Spawn.

The queue organizes events into three tiers (Top, Ladder, Bottom) and achieves $O(1)$ amortized insert and delete-min as long as the mean priority increment $\mu > 0$ is finite, regardless of variance.

Benchmarks

Benchmarked using the HOLD model (Jones 1986) across $8$ distributions from Tang (2005) and Furfaro & Sacco (2018), queue sizes from $100$ to $10^6$, comparing against BinaryHeap and BTreeMap. Measured on an Apple M4 Pro (24 GB RAM, macOS 26.3).

You can run the benchmarks yourself using cargo bench.

Throughput ($5 \times 10^5$ hold operations, lower is better)

Queue size $n$ LadderQueue BinaryHeap Speedup
$10^2$ 20ms 19ms $0.95\times$
$10^3$ 17ms 24ms $1.4\times$
$10^4$ 17ms 33ms $1.9\times$
$10^5$ 18ms 49ms $2.7\times$
$10^6$ 18ms 69ms $\mathbf{3.8\times}$

Per-operation latency

Queue size $n$ LadderQueue $P_{50}$ BinaryHeap $P_{50}$
$10^3$ 41ns 42ns
$10^4$ 41ns 42ns
$10^5$ 41ns 83ns

LadderQueue's $P_{50}$ is $41\text{ns}$ regardless of queue size — the $O(1)$ amortization is visible at the individual operation level. BinaryHeap doubles at $n = 10^5$ as the $O(\log n)$ sift-down deepens.

References

  • W.T. Tang, R.S.M. Goh & I.L.J. Thng. Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation. ACM Trans. Model. Comput. Simul. 15(3), pp. 175-204, 2005. doi:10.1145/1103323.1103324
  • A. Furfaro & L. Sacco. Adaptive Ladder Queue: Achieving O(1) Amortized Access Time in Practice. In Proc. ACM SIGSIM-PADS '18, pp. 101-104, 2018. doi:10.1145/3200921.3200925
  • D.W. Jones. An empirical comparison of priority-queue and event-set implementations. Commun. ACM 29(4), pp. 300-311, 1986. doi:10.1145/5684.5686
  • R. Brown. Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem. Commun. ACM 31(10), pp. 1220-1227, 1988. doi:10.1145/63039.63045
  • K. Chung, J. Sang & V. Rego. A performance comparison of event calendar algorithms: An empirical approach. Software: Practice and Experience 23(10), pp. 1107-1138, 1993. doi:10.1002/spe.4380231005

License

Licensed under either of Apache License, Version 2.0 or MIT License at your option.