No performance difference in iterative and recursive binary heap push implemenations

help
1

I've written a Binary Heap with a recursive and iterative push function. I'd expect the iterative one to be marginally faster than the recurisve implementation. However, benchmarking both says otherwise. Criterion shows no performance improvement.

pub struct BinHeap<T: PartialOrd> {
    heap: Vec<T>,
}
impl<T: PartialOrd> BinHeap<T> {
    pub fn push(&mut self, elem: T) {
        self.heap.push(elem);
        self.bubble_up(self.heap.len() - 1);
    }
    pub fn push_rec(&mut self, elem: T) {
        self.heap.push(elem);
        self.bubble_up_rec(self.heap.len() - 1);
    }
    fn bubble_up_rec(&mut self, i: usize) {
        if i > 0 {
            let pi = ((i - 1) / 2) as usize;
            if self.heap[pi] < self.heap[i] {
                self.heap.swap(pi, i);
                self.bubble_up_rec(pi);
            }
        }
    }
    fn bubble_up(&mut self, mut i: usize) {
        while i > 0 {
            let pi = ((i - 1) / 2) as usize;
            if self.heap[pi] >= self.heap[i] {
                return;
            }
            self.heap.swap(pi, i);
            i = pi;
        }
    }
}

Any thoughts on why there's no performance difference in the two?

2

Your recursive version is tail-recursive, which allows the compiler to optimize it to the equivalent of a loop.

2 Likes
3

Can confirm they produce (nearly) identical assembly. Godbolt.

4 Likes
4

Just read about Tail Call Optimization, very cool. @zirconium-n @SkiFire13 Thanks for the insight! . Might keep the recursive one due to its simplicity.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.