Binary heaps cache-miss on nearly every pop. This talk covers SimdQuickHeap, which revisits QuickHeap and partitions data QuickSort/QuickSelect-style instead of storing a tree. It gets good I/O-complexity and a data layout that vectorizes with SIMD, making it up to 10x faster than binary and d-ary heaps and 2x faster than radix heaps, with the gap widening as n grows.
Ragnar is a postdoc in high throughput bioinformatics at the Karlsruhe Institute of Technology. His work is on writing high performance libraries for fundamental tasks in bioinformatics, such as minimal perfect hashing, and designing algorithms and datastructures that are optimized for modern hardware. Ragnar is author of the blog curiouscoding.nl.
