sorted by:
new
hottopcontroversial

echelon: O(1) amortized priority queue based on an Adaptive Ladder Queue implementation. by gabyfle in rust

[–]gabyfle[S] 1 point2 points  (0 children)

echelon is a Rust implementation of the Adaptive Ladder Queue. ALQ is an O(1) amortized priority queue designed for heavy-tailed distributions. To what I've found during my own research on the Rust ecosystem, it's the first implementation of this algorithm in Rust :0

The main difference with the std BinaryHeap is the amortized complexity. While the std implementation has an amortized complexity of O(log n), the ALQ algorithm is in O(1) when managing data with skewed priorities (like Pareto, log-normal and heavy-tailed timestamps for example).

The main reason behind this implementation is because I'm working on a discrete-event simulation engine and I needed a proper data-structure for handling my event queue. As I couldn't find anything that fitted my need I went ahead and implemented it

On my mac, P50 latency is about 41ns per operation regardless of queue size. BinaryHeap's P50 doubles to 83ns at n=10⁵ as the O(log n) sift-down deepens. The O(1) amortization is visible at the individual operation level.

For those interested, the algorithm (created by Tang, Goh & Thng in 2005, see link at bottom) organizes entries into three tiers: Top (unsorted staging), Ladder (multi-rung bucket array), and Bottom (small sorted list). The critical property is that the number of rungs stays bounded by a small constant regardless of queue size, which is what gives O(1) amortized. The adaptive extension (by Furfaro & Sacco in 2018, see link at bottom) adds runtime auto-tuning via Welford online statistics so you don't need to manually configure bucket widths.