SimdQuickHeap:

Ragnar {Groot Koerkamp} Link to heading

• Did IMO & ICPC; currently head-of-jury for NWERC.
• Some time at Google.
• Quit and solved all of projecteuler.net (700+) during Covid.
• PhD on high throughput bioinformatics @ ETH Zurich.
• Now postdoc @ KIT Karlsruhe.
  • Lots of sequenced DNA that needs processing.
  • Many static datasets, e.g. a 3GB human genome.
  • Revisiting basic algorithms and optimizing them to the limit.
  • Good in theory \(\neq\) fast in practice.
• Last year’s talk on 40x faster binary search: https://curiouscoding.nl/slides/p99

\[ \newcommand{\push}{\mathsf{push}} \newcommand{\pop}{\mathsf{pop}} \]

Motivation: spite Link to heading

• \(O(m \log^{2/3} n)\) shortest path is nice, but how about a faster queue?

Problem Statement: Priority Queues Link to heading

Operations:

• \(\push(x)\): Push the value \(x\) onto the priority queue.
• \(\pop()\): Remove the smallest value from the priority queue.

1
2
3
4
5
6
7
8
9

type T = u64;
trait PriorityQueue {
    /// Initialize an empty priority queue.
    fn new() -> Self;
    /// Push x to the queue.
    fn push(&mut self, x: T) -> Self;
    /// Return the smallest value from the queue.
    fn pop(&mut self) -> T;
}

Binary Heaps: probably worse than you thought Link to heading

Both \(\push\) and \(\pop\):

• \(O(\log_2 n)\) operations, but
• \(O(\log_2 n)\) I/O complexity for \(\pop\)!
  • Each \(\pop\) requires a random access to \(O(n)\) memory!
  • 80ns cache miss to RAM if we’re unlucky

(todo figure & plot)

Quad/Oct Heap: fewer layers, but still bad Link to heading

(todo figure & plot)

Good \(O(1/B)\) I/O complexity is possible Link to heading

Move a cache line worth of elements at a time into/out of RAM.

• Radix Heap (Johnson 1977)
• Sequence Heap (Sanders 2000)
• QuickHeap (Navarro and Paredes 2010; Navarro et al. 2011)

(todo plot)

The QuickHeap Link to heading

1. Use in-place quick select (Hoare 1961) to find the smallest element.
2. Store the pivots.
3. To \(\push\), bubble down the new element through all pivots
4. To \(\pop\), recursively partition the smallest part and return the leftmost element.

(todo fig & plot)

The SimdQuickHeap Link to heading

• Store each partition in its own layer
• use SIMD _mm256_permutevar8x32_epi32 or AVX-612 _mm512_maskz_compress_epi64 instructions for the partitioning
• Use SIMD-based linear-search over pivots to find the layer/partition to append to.

(todo fig & animated demo)

Synthethic benchmarks Link to heading

Graph benchmarks Link to heading

Conclusion Link to heading

• With XX input:

  • 2x speedup over radix heap
  • YY speedup over rust collections::BinaryHeap
  • ZZ ns per push/pop operation, down of AA

• Not limited by RAM (?)

• RAM is slow, caches are fast.

• Theoretical big-O complexities are useless here, since caches invalidate the RAM-model assumptions of constant-time access.

P99 CONF Link to heading

• X: @curious_coding
• Bsky: @curiouscoding.nl
• Blog: curiouscoding.nl
  • /posts/quickheap
  • /slides/quickheap

Bibliography Link to heading

References Link to heading