quickheap 0.1.0

A SIMD-accelerated priority queue
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

[![crates.io](https://img.shields.io/crates/v/quickheap.svg)](https://crates.io/crates/quickheap)
[![docs.rs](https://img.shields.io/docsrs/quickheap.svg?label=docs.rs)](https://docs.rs/quickheap)
[![arXiv preprint](https://img.shields.io/badge/arxiv-10.48550/ARXIV.2604.25681-green)](https://doi.org/10.48550/ARXIV.2604.25681)

# SimdQuickHeap: A fast SIMD-based priority queue

The SimdQuickHeap is, as the name suggests, a **fast priority queue**.
It has some similarities to QuickSelect, and uses SIMD for fast partitioning and
insertion of elements.

Unlike the classic binary heap (and $d$-ary heap variants), it is I/O-efficient
and **does not suffer from bad cache-locality** when the size of the queue exceeds
the cache.

Currently, it only supports `i32`, `u32`, `i64`, and `u64` keys and requires
either AVX2 or AVX-512.
See the preprint for details and benchmarks:

> SimdQuickHeap: The QuickHeap Reconsidered
> Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams, Arxiv 2026
> https://doi.org/10.48550/ARXIV.2604.25681

An older blogpost can be found here:
https://curiouscoding.nl/posts/quickheap.

## Example

``` sh
cargo add quickheap
```

```rust
let mut q = quickheap::SimdQuickHeap::<u64>::default();
q.push(4);
q.push(1);
q.push(7);
assert_eq!(q.pop(), Some(1));
q.push(7);
q.push(3);
assert_eq!(q.pop(), Some(3));
assert_eq!(q.pop(), Some(4));
assert_eq!(q.pop(), Some(7));
assert_eq!(q.pop(), Some(7));
assert_eq!(q.pop(), None);
```

## Results

Below you can see the results for 32-bit and 64-bit data when we first push `n`
elements and then how long it takes on average to do a pair of push and pop
operations. Note that the y-axis is normalized by `log_2(n)` as well.

The SimdQuickHeap is around 2x faster than the Radix heap, and up to 10x faster
than the binary heap and d-ary heap.

![plot with results](./plot.svg)

## Running the benchmarks

Benchmarks can be found in the [bench/](bench/) directory, and Rust FFI wrappers around
external C++ implementations can be found in [ext/](ext/), with submodules
containing the original C++ sources in nested `third_party` directories.
(Run `git submodule update --init --recursive` to initialize them.)
Run `just bench-small plot-all` (see the [`justfile`](justfile)) for a small subset of
the experiments. Note that these need nightly Rust for some unstable convenience features.
If you get linker errors, comment out the `.flag("-flto")` in `ext/{s3q-sys,sequence-heap-sys,boost-heap-sys}/build.rs`.