Re: Confused by <bits/predefined_ops.h>

[Jonathan Wakely <jwakely at redhat dot com>]

On 19/01/17 08:32 +0000, Jonathan Wakely wrote:
> On 18/01/17 22:17 +0100, François Dumont wrote:
> > Hi
> >
> > Names of functions and struct in this file are surely not what I am 
> > most proud of in libstdc++. I even think that I confess it when I 
> > proposed the patch :-)
> >
> > As those elements are purely internal and we rarely need to be touch 
> > I don't consider it as a big issue but if you want to rename 
> > everything don't hesitate.
> >
> > Note that I also have this patch pending:
> >
> > https://gcc.gnu.org/ml/libstdc++/2015-10/msg00071.html
> >
> > But I can surely rework it on top of your changes unless you just 
> > want me to forget it.
>
> It looks good, let's return to it in stage 1 for gcc 8.
>
> Any thoughts on the questions repeated below?

That patch provides one of the benefits of these predefined ops: we
can centralise where we do Debug Mode checks, to try and abort on
invalid orderings.

That's nice, but the cons of the predefined ops seem to outweigh the
pros quite heavily:

The code is much harder to understand (even with better names).

The code is considerably slower, because the __iter_comp_iter
functions make copies of the functors, and all the internal algorithms
(the ones with __ prefixes) make copies of the functors.  Because the
code needs to work in C++98 we can't rely on rvalue references
everywhere, and because we're creating rvalues with the
__iter_comp_iter() functions we can't take lvalue reference arguments,
so we must make copies. This sucks. See PR 67085 and PR 70898. I've
improved things by adding _GLIBCXX_MOVE which helps because moves can
be faster than copies, but it would be even better to not do any moves
or copies. And sometimes the comparison function needs to be called in
a loop, so then we can't move it.

The attached patch rips out the predefined ops from <bits/stl_heap.h>
and makes the code more efficient, and IMHO simpler (we only have to
deal with functions that compare values, not some that compare
iterators and some that compare values and some that compare iterators
with values!)

This means the __is_heap and other internal functions can have a
_Compare& argument, and not copy anything.

All that's needed for this to work is a functor like std::less<void>.

What do we lose by making this change? i.e. reverting the predefined
ops changes to stl_heap.h?

The __heap_less function won't work with iterators that return proxies
or rvalues, but since heaps only work with RandomAccessIterators I
don't really care about that. We could solve it for C++11 and later
using forwarding references anyway, so only C++98 would not support
it.

We wouldn't be able to check the comparison objects aas easily in
Debug Mode. That's unfortunate, but normal mode must *not* get slower
in order to accomodate extra Debug Mode checks. That's not acceptable.

Anything else?

Attachment: no_predefined_ops_in_heaps.patch
Description: Text document