https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #8 from Jonathan Wakely ---
I'm guessing this probably regressed with r174100
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #6 from Xi Ruoyao ---
Created attachment 40941
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=40941=edit
performance test result with the patch
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #7 from Jonathan Wakely ---
Please note that libstdc++ patches need to be sent to the libstdc++ list as
well, see the policies at https://gcc.gnu.org/lists.html
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #5 from Xi Ruoyao ---
Patch proposal:
https://gcc.gnu.org/ml/gcc-patches/2017-03/msg00516.html
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #4 from Xi Ruoyao ---
> This is certainly a bug making priority_queue::push O(n^2).
> Since it works correctly in GCC 4.6, it's a regression.
Sorry. s/O(n^2)/O(n)/.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #3 from Xi Ruoyao ---
Both Tobias' and my thought was wrong. In the entry of
__gnu_pbds::detail::binary_heap::push_heap, the array
m_a_entries[0..m_size-2] contains a heap, and
m_a_entries[m_size-1] contains the element being pushed
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
Jonathan Wakely changed:
What|Removed |Added
CC|bkoz at redhat dot com |
--- Comment #2 from Jonathan
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
Xi Ruoyao changed:
What|Removed |Added
CC||bkoz at redhat dot com,
|
