Re: Add three way lower_bound

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 1547 bytes --]

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


[-- Attachment #2: lower_bound.cc --]
[-- Type: text/x-c++src, Size: 647 bytes --]

#include <algorithm>
#include <testsuite_performance.h>

int main()
{
  using namespace __gnu_test;
  using namespace std;

  time_counter time;
  resource_counter resource;

  int iarr[1000000];
  for (int i = 0; i != 1000000; ++i)
    iarr[i] = i;

  int jfound = 0;
  start_counters(time, resource);
  for (int j = 0; j != 100; ++j)
    {
      int found = 0;
      for (int i = 0; i != 1000000; ++i)
	found += lower_bound(iarr + 0, iarr + 1000000, i) == iarr + i;
      jfound += found == 1000000;
    }

  stop_counters(time, resource);

  report_performance(__FILE__, "lower_bound (int)", time, resource);
  return jfound == 1000 ? 0 : 1;
}