Post

New preprint: The SimdQuickHeap is the fastest priority queue by far! 2x faster than a radix heap and up to 10x faster than binary heaps. arxiv.org/abs/2604.25681 with Marvin Williams and Johannes Breitling:

arxiv.orgSimdQuickHeap: The QuickHeap ReconsideredPriority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is ...

Ragnar {Groot Koerkamp}

@curiouscoding.nl

29 Apr

The data structure has some similarities to QuickSelect and is pretty simple: repeatedly partition the list of values using random pivots until the smallest is left, and store each part in its own array. New elements are compared to the pivots and pushed to the right layer.

Ragnar {Groot Koerkamp}

@curiouscoding.nl

With AVX-512, the SimdQuickHeap is consistently 2x faster than the radix heap and other engineered heaps that are I/O-efficient, and up to 10x faster than the binary heap and other tree-based heaps.

29/4/26, 10:57 pm0 reposts2 likes

Ragnar {Groot Koerkamp}

@curiouscoding.nl

29 Apr

As often: the SimdQuickHeap is a conceptually very simple data structure that thus can be easily optimized using SIMD, leading to pretty big speed gains. github.com/RagnarGrootKoerkamp/QuickHeap

github.comGitHub - RagnarGrootKoerkamp/quickheap: The fastest priority queueThe fastest priority queue. Contribute to RagnarGrootKoerkamp/quickheap development by creating an account on GitHub.