[libc++] Add a missing `<_Compare>` template argument.

[• Quuxplusone]

Summary

Sometimes _Compare is an lvalue reference type, so letting it be deduced is pretty much always wrong. (Well, less efficient than it could be, anyway.)

I did a manual audit for other offending calls (and I found none), by manually replacing _Compare __comp with a non-deducible typename __identity<_Compare>::type __comp in all the helper functions. My impression is that such a blanket change to the helpers would be unwelcome because it's so icky-looking. And perhaps also because it's an ABI break, in the sense that it would affect the mangling of the __sort specializations explicitly instantiated in src/algorithm.cpp — it's unclear to me whether we would care about that.

[curdeius]

Excuse my ignorance, but could you please explain why letting _Compare get deduced is wrong/suboptimal?
IIUC the case you mention is when e.g. __buffered_inplace_merge has _Compare being some non-ref type T, so then calling __half_inplace_merge will deduce its _Compare to be an lvalue ref T &. So far so good. But why/when is it bad?

[• Quuxplusone]

libcxx/include/algorithm

4487

@curdeius:

Excuse my ignorance, but could you please explain why letting _Compare get deduced is wrong/suboptimal?
IIUC the case you mention is when e.g. __buffered_inplace_merge has _Compare being some non-ref type T, so then calling __half_inplace_merge will deduce its _Compare to be an lvalue ref T &. So far so good. But why/when is it bad?

Other way around. (And I'm sure it's not your ignorance, just a brain fart. ;)) The trouble case is when _Compare is T&, and then passing __comp by value will make __half_inplace_merge deduce its _Compare as T and make a copy, when really we want __half_inplace_merge's _Compare to also be T&.

Basically, libc++ algorithms have an invariant that "_Compare is either an lvalue reference type or __debug_less<T&> (which works like reference_wrapper and is cheap to copy)." It would actually be very nice if we could just make the invariant that "_Compare is a value type that is cheap to copy (e.g. reference_wrapper<T>)," and then we'd never need to specify <_Compare> on any helper ever again...

[curdeius]

LGTM.

libcxx/include/algorithm

4487

Other way around. (And I'm sure it's not your ignorance, just a brain fart. ;))

Indeed, I somehow forcingly made myself think that the rule "3) If P is a reference type, the type referred to by P is used for deduction." for argument deduction is non existent.
Thank you.

[curdeius]

Hmm, just one thought, it could be tested using non-copyable comparators passed by (non-reduced) lvalue ref, nope? How did you find this "missed optimization"?

[• Quuxplusone]

libcxx/include/algorithm

4500

@curdeius wrote:

Hmm, just one thought, it could be tested using non-copyable comparators passed by (non-reduced) lvalue ref, nope? How did you find this "missed optimization"?

I believe comparators must be copyable by definition (or else it's library UB). I also believe it's unspecified how many times libc++ may copy them. Traditionally the STL copies comparators as liberally as it copies iterators or allocators; libc++'s reference dance is just for QoI. Arguably, any programmer who cares should be passing std::ref(myComparator) in the first place, instead of passing a heavyweight myComparator by value.

We could still add a QoI test for this in libcxx/test/libcxx/; leave the comparator copyable but have it count how many times it was copied, and then assert that the number of copies was 1. I'm not volunteering.

How did I find it? Just staring at the code. I've been staring at these helper-function calls a lot lately, because of constexpr algorithms and also because of ADL.

[zoecarver]

I think this makes sense, especially given that most other related algorithms also do this, and that __inplace_merge (__buffered_inplace_merge's only user) also specifies the template argument.

[ldionne]

I'd like to have other people's opinions on this, but wouldn't it make more sense to pass std::ref(comparator) down to implementation-detail algorithms inside the library, and let those assume that they can copy the predicate cheaply? That would give us what Arthur was suggesting would be better above:

It would actually be very nice if we could just make the invariant that "_Compare is a value type that is cheap to copy (e.g. reference_wrapper<T>)," and then we'd never need to specify <_Compare> on any helper ever again...

In other words, why not do just that?

[ldionne]

In all cases, I'm fine with this as it adds consistency with other implementation details. Arthur, feel free to implement what you hinted at and send a patch, we'll take a look and decide whether it adds clarity or not. As always, no obligation!

libcxx/include/algorithm

     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
     if (__len1 <= __len2)
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
             ::new ((void*)__p) value_type(_VSTD::move(*__i));
-        _VSTD::__half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
+        _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
             ::new ((void*)__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
-        _VSTD::__half_inplace_merge(_Rv(__p), _Rv(__buff),
+        typedef __invert<_Compare> _Inverted;
+        _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
                                     _RBi(__middle), _RBi(__first),
-                                    _RBi(__last), _VSTD::__invert<_Compare>(__comp));
+                                    _RBi(__last), _Inverted(__comp));
     }
 }
 
 template <class _Compare, class _BidirectionalIterator>
 void
 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {