https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69565
Bug ID: 69565
Summary: Heap operations could surely be faster
Product: gcc
Version: 5.3.0
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: morwenn29 at hotmail dot fr
Target Milestone: ---
Created attachment 37526
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=37526&action=edit
Benchmark heapsort for libc++ and libstdc++.
While implementing sorting algorithms, I decided to benchmark some standard
algorithms and was surprised to see that a heapsort written with libstdc++ (a
simple std::make_heap followed by a std::sort_heap) was consistently slower
than with libc++.
I extracted the code from both algorithms to benchmark them. Apparently, the
times are close enough for "big" types such as long double, but when it comes
to integers, libc++ is generally *really* faster than libstdc++. One notable
example is that libstdc++ seems to reach a worst case when all the values are
already equal while it looks like libc++'s best case.
I attached the results of the benchmarks for int since it's the one with the
biggest difference, but libc++ is consistently faster even with bigger types.
The code used for the benchmark is adapted from the following benchmark:
https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/bench.cpp
Considering these results, I believe that heap operations could be faster than
they currently are. It could be related to bug 51965 and bug 63706 for what
it's worth.
