[Bug libstdc++/109150] New: std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[Bug libstdc++/109150] New: std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

            Bug ID: 109150
           Summary: std::fill should use __gnu_cxx::__is_scalar overloads
                    for all scalars
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

std::fill and std::fill_n have optimized implementations for simple types, but
dispatching on std::__is_scalar which is not true for enumeration types or
pointer-to-member types.

  template<typename _ForwardIterator, typename _Tp>
    _GLIBCXX20_CONSTEXPR
    inline typename
    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
    __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
              const _Tp& __value)
    {
      const _Tp __tmp = __value;
      for (; __first != __last; ++__first)
        *__first = __tmp;
    }

Where __is_scalar doesn't match the semantics of std::is_scalar, but rather:

  template<typename _Tp>
    struct __is_scalar
    : public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> >
    { };

We should enable this optimization for more types. Maybe use the same set of
types matches by std::is_scalar? Or all types that are trivially copy
constructible and trivially copy assignable?

I think the point of the optimization is so the compiler knows that __tmp
doesn't alias anything in the iterator range. But if the iterators value type
is not _Tp, this optimization might actually be wrong (the value type's
assignment operator might care about the identity of _Tp).

Review this, decide whether the traits in cpp_type_traits.h make sense to keep,
or should be reimplemented in terms of <type_traits> and/or built-ins.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-03-15

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This terminates with an exception, but I think it's valid.

#include <algorithm>

const int global = 0;

struct X {
  void operator=(const int& i) { if (&i != &global) throw 1; }
};

int main()
{
  X x;
  std::fill(&x, &x+1, global);
}

So I think the std::fill (and std::fill_n) optimizations need to consider the
iterator's value type as well as the _Tp type.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Another example of how the optimization is non-conforming, as I just
rediscovered:

#include <algorithm>
#include <assert.h>

struct X {
  int i = 0;

  X& operator=(int ii)
  {
    i = ii + 1;
    return *this;
  }
};

int main()
{
  X x[2];
  std::fill_n(x, 2, x[0].i);
  assert(x[1].i == 2);
}

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think we can use this condition:

      const bool __load_outside_loop =
#if __has_builtin(__is_trivially_constructible) \
      && __has_builtin(__is_trivially_assignable)
            __is_trivially_constructible(_Tp, const _Tp&)
            && __is_trivially_assignable(__decltype(*__first), const _Tp&)
#else
            __is_trivially_copyable(_Tp)
            && __is_same(_Tp, __typeof__(*__first))
#endif
            && sizeof(_Tp) <= sizeof(long long);

We need to know that making a copy of the object has no side effects, i.e. is
trivial.
We need to know that assigning the object to *__first is a trivial assignment.
And we probably don't want to make a local copy if it's very large.

This will disable the optimization when it's not correct to use it, as in
comment 1 and comment 2, and will enable it for other scalar types like enums,
and for sufficiently small structs where the assignment is trivial.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[arthur.j.odwyer at gmail dot com]

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

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

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

--- Comment #4 from Arthur O'Dwyer <arthur.j.odwyer at gmail dot com> ---
@jwakely #3: FWIW, I agree with that logic and that if-condition... as long as
we're all on the same page that we ought to act as if
`__is_trivially_assignable(T, U)` means "take the bit-pattern from the U (or
the thing referenced by U, if U is a reference type) and put it into the T (or
the thing referenced by T, if T is a reference type)." This isn't what the
trait means today (see P3279,
https://quuxplusone.github.io/blog/2024/05/15/false-advertising/ etc), but I'm
thrilled that everyone's going along with the idea, because I really think
that's where we need to get to as a language.

The if-condition will have trouble *for now* with `Leopard`-like types, but
such types are pathological and I am thrilled for library authors to act as if
the trait's going to get fixed soon. :)

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I don't think we're on the same page at all.

I'm intending to use the trait to mean that the assignment is known to call no
operation that is not trivial, as defined in the standard today.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Arthur O'Dwyer from comment #4)
> The if-condition will have trouble *for now* with `Leopard`-like types

What trouble? I don't care if there's some confusing deleted assignment, I care
that the assignment *first = tmp is equivalent to *first = val, where tmp is a
const lvalue of the same type as val.

*first = tmp and *first = val do the same thing for your Leopard type, and that
assignment is trivial, which is all that matters.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2024-June/65
                   |                            |5267.html

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Patch posted: https://gcc.gnu.org/pipermail/gcc-patches/2024-June/655267.html

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 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:b3743181899c5490a94c4dbde56a69ab77a40f11

commit r15-1549-gb3743181899c5490a94c4dbde56a69ab77a40f11
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jun 19 16:14:56 2024 +0100

    libstdc++: Fix std::fill and std::fill_n optimizations [PR109150]

    As noted in the PR, the optimization used for scalar types in std::fill
    and std::fill_n is non-conforming, because it doesn't consider that
    assigning a scalar type might have non-trivial side effects which are
    affected by the optimization.

    By changing the condition under which the optimization is done we ensure
    it's only performed when safe to do so, and we also enable it for
    additional types, which was the original subject of the PR.

    Instead of two overloads using __enable_if<__is_scalar<T>::__value, R>
    we can combine them into one and create a local variable which is either
    a local copy of __value or another reference to it, depending on whether
    the optimization is allowed.

    This removes a use of std::__is_scalar, which is a step towards fixing
    PR 115497 by removing std::__is_pointer from <bits/cpp_type_traits.h>

    libstdc++-v3/ChangeLog:

            PR libstdc++/109150
            * include/bits/stl_algobase.h (__fill_a1): Combine the
            !__is_scalar and __is_scalar overloads into one and rewrite the
            condition used to decide whether to perform the load outside the
            loop.
            * testsuite/25_algorithms/fill/109150.cc: New test.
            * testsuite/25_algorithms/fill_n/109150.cc: New test.

[Bug libstdc++/109150] std::fill should use __gnu_cxx::__is_scalar overloads for all scalars

[redi at gcc dot gnu.org]

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

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk for now, but I think this should be backported because the
current code on the branches is non-conforming.