[Bug c++/101485] New: Calling std::equal with std::byte* does not use memcmp

[Bug c++/101485] New: Calling std::equal with std::byte* does not use memcmp

[dennis-hezel at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

            Bug ID: 101485
           Summary: Calling std::equal with std::byte* does not use memcmp
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dennis-hezel at gmx dot de
  Target Milestone: ---

See https://godbolt.org/z/fKbhqe1sz

```
#include <algorithm>

auto equal_with_bytes(std::byte* b1, std::byte* e1, std::byte* b2) {
  return std::equal(b1, e1, b2);
}

auto equal_with_chars(unsigned char* b1, unsigned char* e1, unsigned char* b2)
{
  return std::equal(b1, e1, b2);
}
```

In the above code `equal_with_chars` invokes `memcmp` while `equal_with_bytes`
does not, although it would be eligble.

The problematic code seems to be in `stl_algobase.h`

```
  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
      const bool __simple = ((__is_integer<_ValueType1>::__value
                              || __is_pointer<_ValueType1>::__value)
                             && __memcmpable<_II1, _II2>::__value);
      return std::__equal<__simple>::equal(__first1, __last1, __first2);
    } 
```

since `std::byte` is neither an integer nor a pointer.

Suggested fix: Extend the condition with a check for `std::byte`

```
__is_integer<_ValueType1>::__value || __is_pointer<_ValueType1>::__value ||
__is_byte<_ValueType1>::__value
```

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=93059
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-07-18

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
We can use is_same_v<_ValueType1, byte> instead, which is more efficient to
compile than instantiating __is_byte unconditionally.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

Jan Schultke <janschultke at googlemail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |janschultke at googlemail dot com

--- Comment #2 from Jan Schultke <janschultke at googlemail dot com> ---
Would it be wrong to extend the definition to all enumeration types instead of
just std::byte? I don't see what could be wrong about memcmping enumerations,
given that this is correct for integers, and enumerations always have integer
underlying types.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
#include <algorithm>

enum E { e };
bool operator==(E, E) { return false; }

int main()
{
  E e[1];
  return std::equal(e, e+1, e);
}

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
It's valid for std::byte because we know what equality means for std::byte.

You could maaaaaaybe do something like:

template<typename T>
concept is_sane_enum = is_enum_v<T> && (!requires { &operator==(E,E); });

but I'm not confident enough that it wouldn't miss some cases and allow
std::equal to do use memcmp when it shouldn't.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #5 from Jan Schultke <janschultke at googlemail dot com> ---
&operator==(E,E); is not a valid expression, but I understand what you're
trying to do there. Perhaps you can test by converting to a function pointer
bool(*)(E,E).

It would surely miss cases like an operator== with an always-defaulted third
parameter, or one where the return type is contextually convertible to bool,
but not exactly bool, or:

template <std::same_as<E> T>
bool operator==(T, T) { return false; }

... or other cases. You would really need some way to detect whether an
expression (x == y) uses any overloaded operators, and I don't see how you
could do that (without additional intrinsics).

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jan Schultke from comment #5)
> It would surely miss cases like an operator== with an always-defaulted third
> parameter,

That's not valid, operator== must have two parameters.

> or one where the return type is contextually convertible to bool,

Yes, int operator==(E, E) is valid.

> but not exactly bool, or:
> 
> template <std::same_as<E> T>
> bool operator==(T, T) { return false; }

That is valid to declare, but doesn't get called. I think the built-in
candidate is a better match.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
A better version of the concept sketched above:

template<typename T>
concept is_sane_enum = std::is_enum_v<T> && (!requires {
  []<std::convertible_to<bool> U>(U (*)(T, T)){}(&operator==);
});

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #8 from Jan Schultke <janschultke at googlemail dot com> ---
It is a tiny bit pessimistic if it uses std::convertible_to instead of
std::__boolean_testable or what it was called.

I cannot come up with an example that produces a false positive though (which
is crucial for correctness), and if we cover 99% of enums, that's still much
better than just std::byte. Nice job.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I'm still not willing to use that though.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #10 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:fab60eaa94b50b1eea84f0d001004c851d4c781b

commit r15-1715-gfab60eaa94b50b1eea84f0d001004c851d4c781b
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jun 28 11:14:39 2024 +0100

    libstdc++: Extend std::equal memcmp optimization to std::byte [PR101485]

    We optimize std::equal to memcmp for integers and pointers, which means
    that std::byte comparisons generate bigger code than char comparisons.

    We can't use memcmp for arbitrary enum types, because they could have an
    overloaded operator== that has custom semantics, but we know that
    std::byte doesn't do that.

    libstdc++-v3/ChangeLog:

            PR libstdc++/101485
            * include/bits/stl_algobase.h (__equal_aux1): Check for
            std::byte as well.
            * testsuite/25_algorithms/equal/101485.cc: New test.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|---                         |15.0
         Resolution|---                         |FIXED

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk, thanks for the report.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #12 from Jan Schultke <janschultke at googlemail dot com> ---
On a language evolution note, https://wg21.link/P2825 would let you detect
whether an equality comparison for enumerations is overloaded by checking
whether

> declcall(E{} == E{})

... is well-formed. If this makes it into C++26, the solution could be
broadened to all enumerations robustly.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Yes I've read it but it's not clear to me that it's SFINAE-friendly when the
expression resolves to a built-in like that.

[Bug libstdc++/101485] Calling std::equal with std::byte* does not use memcmp

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101485

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Gašper has confirmed that the intention is for it to be SFINAE-friendly, so
declcall would work here (and for [comparisons.general],
[comparisons.three.way], and [range.cmp], although P2434 might make it
unnecessary for those).