Add three way lower_bound

[François Dumont]

On 01/09/22 08:47, Jonathan Wakely wrote:
>
>
> On Wed, 23 Jun 2021, 21:34 François Dumont via Libstdc++, 
> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>
>     Hi
>
>     Following the message to propose an alternative lower_bound and the
>     reply to use three way comparison I try to implement this.
>
>     Before going further I wonder if this is something possible ?
>
>     The purpose of the:
>
>     if constexpr (three_way_comparable<>)
>
>     is to make sure that we use it only if there is a proper <=> operator
>     defined. Afai understood what is in <compare> we can have the
>     __synth3way for any type as long as < exist. But I think that if
>     <=> is
>     implemented in terms of < then it might be too expensive, the actual
>     lower_bound might already be implemented this way.
>
>     My main concerns is of course Standard conformity, could it be ok ?
>
>
>
> I don't think so. For a built-in type like int I don't think using <=> 
> will be faster.

I could not believe it so I wrote the small bench attached and it turns 
out that indeed, performance are very bad.

In pre- <=> mode:

lower_bound.cc-thread        lower_bound (int)             657r 657u    
0s         0mem    0pf

With <=> support:

lower_bound.cc-thread        lower_bound (int)            8621r 8620u    
0s         0mem    0pf

Now I wonder if it is <=> implementation that is making it so bad, I'll 
try to find out.

Thanks for the feedback

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: lower_bound.cc
Type: text/x-c++src
Size: 647 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20220907/8fa3b079/attachment-0001.bin>