[Bug libstdc++/69565] New: Heap operations could surely be faster

[morwenn29 at hotmail dot fr]

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.