SIMD Binary Heap Operations

Summary

SIMD binary heap operations Author: Wojciech Muła Added on:2025-01-18 Introduction Binary heap is a binary tree data structure having some interesting properties. One of them is an array-friendly memory layout, achieved by building (almost) complete binary tree. A binary heap keeps at index 0 the maximum value, or the minimum one depending on convention — let's stick to maximum heaps. There is exactly one invariant: a child node, if exist, keep a value less than the parent node. For comparison, in the case of binary search trees, we have more strict rules: the left child keeps a smaller value than the parent's value, and the right child keeps a bigger value. A non-root node stored at index i have the parent node at index floor[(i − 1)/2], and children nodes at indices 2 ⋅ i + 1 and 2 ⋅ i + 2. In this text we cover two procedures related to heaps: is_heap — checks if an array is proper heap, push_heap — adds a new element to the heap, The procedure is_heap is vectorizable and using SIMD instructions brings profit. We also show that it is possible to define this function using forward iterators rather random iterators, as the C++ standard imposes. The procedure push_heap can be expressed with gather and scatter, but performance is terrible. For the sake of completeness, we show the AVX-512 implementation. There is also one more crucial method for heaps: removing the maximum value, pop_heap. However, it is difficult to vectorize, and benefits from vectorization would likely be worse than in the case of push_heap. is_heap The easiest approach to check if the given array is a proper heap is scanning the array from beginning, calculate the left and right children indices and then compare their values according to the invariant. We stop scanning, when both children indices are out of the array bounds. However, this algorithm is not suitable for vectorization. What we need is sequential scan over array. We need two pointers: one pointing parents and another pointing childre...