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;
}

“Solved” problem: Brodal heaps are “optimal” Link to heading

• \(\push\): \(O(1)\) worst-case
• \(\pop\): \(O(\lg n)\) worst-case

More theoretical work on:

• I/O-complexity: reading few cache lines
• cache-oblivious: efficient across the cache hierarchy
• average vs worst case
• \(\mathsf{decreaseKey}\) using indirection

Important in practice:

• no random access
• efficient operations
• avoiding indirections

Binary Heaps: probably worse than you thought Link to heading

• \(O(\log_2 n)\) operations for \(\push\) and \(\pop\), but
• \(\pop\) randomly walks down the tree:
  • requires random accesses
  • 80ns cache miss!
  • Not good for SIMD

d-ary heap: fewer layers, but still bad Link to heading

• Branching factor 4 or 8, so \(\frac 12\) or \(\frac 13\) as many layers
  • Fewer memory accesses
  • But still \(\geq 1\) random access and cache miss

Splitting vs merging Link to heading

• Binary heaps merge: elements are inserted randomly and interleaved.
• Others split, like quicksort: elements are partitioned using pivots
  • Splitting is more efficient using SIMD

Avoiding cache-misses is possible! Link to heading

Move a cache line worth of elements at a time into/out of RAM, only using sequential scans.

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

The QuickHeap: inspired by quick select 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.

5. Slower than binary heap: 3-way rotates; scalar partitioning is slower than bubbling.

6. I/O-efficient; fasterer on large data; cache-oblivious

The SimdQuickHeap Link to heading

• Store each partition in its own layer.
• SIMD-based classification and partitioning.

Classification using SIMD Link to heading

• Quickly count the number of pivots \(>x\).

Partitioning using SIMD Link to heading

• Move values \(< p\) to the front and \(\geq p\) to the back.
  • AVX2: _mm256_permutevar8x32_epi32
  • AVX-512: _mm512_maskz_compress_epi64

Synthethic benchmarks Link to heading

Graph benchmarks Link to heading

Future work Link to heading

• Rebalancing to avoid worst-case inputs
• Reduce space consumption by using list-of-blocks
• De-amortizing SimdQuickHeap?

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