This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by Quuxplusone on Dec 18 2020, 12:55 PM.

Details

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.

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Dec 18 2020, 12:55 PM
Quuxplusone created this revision.
Herald added a reviewer: Restricted Project. · View Herald TranscriptDec 18 2020, 12:55 PM

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?

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 accepted this revision.Dec 21 2020, 1:00 AM

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.

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"?

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.

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.

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 accepted this revision.Jan 12 2021, 10:31 AM

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!

This revision is now accepted and ready to land.Jan 12 2021, 10:31 AM