[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).

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

[arthur.j.odwyer at gmail dot com]

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

Arthur O'Dwyer <arthur.j.odwyer at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |arthur.j.odwyer at gmail dot com

--- Comment #15 from Arthur O'Dwyer <arthur.j.odwyer at gmail dot com> ---
FWIW, Clang supports `__is_trivially_equality_comparable(T)` as a compiler
builtin. It's true for most primitive types, true for structs with defaulted
`operator==` (as long as their data members are all trivially equality
comparable and the struct as a whole lacks any padding bits), and false for
types with user-provided `operator==`.
However, as of this writing the trait is false for `std::byte` and false for
enum types in general, precisely because it's permitted for the user to provide
an overloaded `operator==` for them. This was the conservative choice when the
feature was added in March 2023, but given how the feature has evolved, it
probably makes sense for Clang to revisit and permit it to Just Work for enums
too.

I bring this up because it would be cool for GCC to support the same builtin.
https://godbolt.org/z/dhTc64PzP
(libstdc++ optimizes int and byte but not S; libc++ optimizes int and S but not
byte)

The builtin is more powerful than anything overload-resolution-based, because
the builtin can tell the difference between "a member function exists" and "a
member function exists, defaulted, with the proper semantics."