Potential efficiency improvement to std::make_heap and std::pop_heap functions.

[Vamsi Krishna Reddy Satti]

I think I'm convinced that the current implementation stands good for now. Thanks again!
________________________________
From: Marc Glisse <marc.glisse@inria.fr>
Sent: 25 July 2020 08:55 PM
To: Vamsi Krishna Reddy Satti <vamsi3@outlook.com>
Cc: libstdc++@gcc.gnu.org <libstdc++@gcc.gnu.org>
Subject: Re: Potential efficiency improvement to std::make_heap and std::pop_heap functions.

On Sat, 25 Jul 2020, Vamsi Krishna Reddy Satti via Libstdc++ wrote:

> Thank you for the links. I realize now that the code was intentional approach to minimize comparisons made. I was not aware of this idea earlier.

Note that wikipedia also claims that the method used in libstdc++ may not
be such a good idea.

> Also, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69565 might be explained by the fact that the benchmark was done over integers.
> libc++ implements the mentioned heap operations using Floyd's method (the one I was suggesting here). Since comparisons are cheap
> for integers, the benchmarks favoured libc++ implementation.
>
> It probably seems via. bug 69565 that my original suggestion makes sense for data types where comparison is cheap like the primitive types.
> Does it make sense to use a normal siftUp / heapifyUp operation instead of __adjust_heap for primitive types separately?

Maybe. We don't want to have 50 different versions of the code, but 2
might be ok. However, we need

- a clear way to choose which version to use

- make sure that each case is used by real-world code (not just an
artificial benchmark). Do many real programs use a heap of plain int with
the default comparison? (I have no idea)

- a large performance gap on at least one microbenchmark in each
direction, showing that both versions are really useful.

- benchmarks showing that we don't regress (too much) in cases other than
the microbenchmark above. For instance, make_heap+sort_heap from libstdc++
looks faster when compiled with clang instead of gcc, but that's just for
randomly shuffled data, gcc's version is faster for data with less
entropy. So it is important to look at several scenarios.


Improving the general code seems more tempting to me than getting a
specialized version, and both require a similar amount of benchmarking.

(https://github.com/Ripser/ripser may be a nice real-world program whose
performance highly depends on heap operations, at least on some datasets)

--
Marc Glisse