[Bug libstdc++/62045] New: __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> is too slow

["tobias.polzer+gcc at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045

            Bug ID: 62045
           Summary: __gnu_pbds::priority_queue<int, less<int>,
                    binary_heap_tag> is too slow
           Product: gcc
           Version: 4.9.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tobias.polzer+gcc at gmail dot com

The documentation calls binary heaps the '"best-in-kind" for primitive types'
however __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> seems to
perform abysmally slow. This is shown in the test suite, e.g. here:
https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_based_data_structures_test.html#performance.priority_queue.int_push
where all other heaps vanish in comparison.

I had a short look at it in gdb and found that in a push, it executes

277 if (!is_heap())
276     make_heap();

in ext/pb_ds/detail/binary_heap_/binary_heap_.hpp, where is_heap and make_heap
both come from the std namespace and need linear time in the size of the
container. Even more peculiar, is_heap returns false, while I think is_heap
should be an invariant of the data structure?