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

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely  ---
I'm guessing this probably regressed with r174100

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

[ryxi at stu dot xidian.edu.cn]

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

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

[redi at gcc dot gnu.org]

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

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

[ryxi at stu dot xidian.edu.cn]

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

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

[ryxi at stu dot xidian.edu.cn]

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)/.

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

[ryxi at stu dot xidian.edu.cn]

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
into the heap. So is_heap would return false most likely.
Then make_heap would be call and std::push_heap *won't* be
call.

It's easy to find out using gcov.

~~~
-:  272:  void
  100:  273:  push_heap()
-:  274:  {
  100:  275:if (!is_heap())
   99:  276:  make_heap();
-:  277:else
-:  278:  {
1:  279:const entry_cmp& m_cmp =
static_cast(*this);
1:  280:entry_pointer end = m_a_entries + m_size;
1:  281:std::push_heap(m_a_entries, end, m_cmp);
-:  282:  }
  100:  283:  }
~~~

This is certainly a bug making priority_queue::push O(n^2).
Since it works correctly in GCC 4.6, it's a regression.

Making a patch...

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

[redi at gcc dot gnu.org]

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 Wakely  ---
Benjamin doesn't work at Red Hat any more.

The PBDS containers are not really maintained, but I'll try to take a look.

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

[ryxi at stu dot xidian.edu.cn]

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

Xi Ruoyao  changed:

   What|Removed |Added

 CC||bkoz at redhat dot com,
   ||ryxi at stu dot xidian.edu.cn

--- Comment #1 from Xi Ruoyao  ---
A simple stupid test case:

~~~
#include 
#include 

__gnu_pbds::priority_queue pq;

extern "C" unsigned alarm (unsigned);

int main ()
{
  alarm(1);
  for (int i = 0; i < 100; i++)
pq.push(i);
  return 0;
}
~~~

$ g++-4.6 pr62045.cpp && ./a.out
$ g++-5.3 pr62045.cpp && ./a.out
Alarm clock
$ g++-6.3 pr62045.cpp && ./a.out
Alarm clock
$ g++-7-svn pr62045.cpp && ./a.out
Alarm clock

Start from r174100

2011-05-23  Benjamin Kosnik  

PR libstdc++/37144
PR libstdc++/28457
Interface changes for ext/pb_ds.
PB_DS_BASE_C_DEC to unique PB_DS_*_BASE macros.

Add Benjamin to cc list.

I think the call "is_heap()" is unnecessary since there are
"PB_DS_ASSERT_VALID"s around the call to "push_heap". If this
"is_heap" is necessary, this priority_queue won't work in
debug mode (-D_GLIBCXX_DEBUG).