[Bug libstdc++/107367] New: All standard library algorithms should detect whether they are contiguous iterators after C++20

[Bug libstdc++/107367] New: All standard library algorithms should detect whether they are contiguous iterators after C++20

[unlvsur at live dot com]

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

            Bug ID: 107367
           Summary: All standard library algorithms should detect whether
                    they are contiguous iterators after C++20
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: unlvsur at live dot com
  Target Milestone: ---

https://github.com/gcc-mirror/gcc/blob/00716b776200c2de6813ce706d2757eec4cb2735/libstdc%2B%2B-v3/include/bits/stl_algo.h#L3229

Take is_sorted for example:

  template<typename _ForwardIterator>
    _GLIBCXX20_CONSTEXPR
    inline bool
    is_sorted(_ForwardIterator __first, _ForwardIterator __last)
    { return std::is_sorted_until(__first, __last) == __last; }

It should be optimized to

  template<typename _ForwardIterator>
    _GLIBCXX20_CONSTEXPR
    inline bool
    is_sorted(_ForwardIterator __first, _ForwardIterator __last)
    { 
       if
constexpr(contiguous_iterator<_ForwardIterator>&&!is_pointer_v<_ForwardIterator>)
{
       return is_sorted(to_address(__first),to_address(__last));
}
else
{
 return std::is_sorted_until(__first, __last) == __last; 
}
 }

[Bug libstdc++/107367] All standard library algorithms should optimize to pointers internally when they are contiguous iterators after C++20

[unlvsur at live dot com]

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

--- Comment #1 from cqwrteur <unlvsur at live dot com> ---
This optimization will prevent duplications of templates over iterators and
pointers. (vector<int>::iterator and int* duplications for example)

For example:

https://godbolt.org/z/9zEajxxa8
vs
https://godbolt.org/z/n61vEddj1

579 vs 879

[Bug libstdc++/107367] All standard library algorithms should optimize to pointers internally when they are contiguous iterators after C++20

[unlvsur at live dot com]

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

--- Comment #2 from cqwrteur <unlvsur at live dot com> ---
(In reply to cqwrteur from comment #1)
> This optimization will prevent duplications of templates over iterators and
> pointers. (vector<int>::iterator and int* duplications for example)
> 
> For example:
> 
> https://godbolt.org/z/9zEajxxa8
> vs
> https://godbolt.org/z/n61vEddj1
> 
> 579 vs 879
For debugging. You can do something like this

template<typename ForwardIterator>
concept can_optimize_to_pointer_impl = 
#ifdef _GLIBCXX_DEBUG
false;
#else
std::contiguous_iterator<ForwardIterator>&&!std::is_pointer_v<ForwardIterator>;
#endif

template<typename ForwardIterator>
constexpr void my_sort(ForwardIterator first,ForwardIterator last)
{
    if constexpr(can_optimize_to_pointer_impl<ForwardIterator>)
    {
        std::sort(std::to_address(first),std::to_address(last));
    }
    else
    {
        std::sort(first,last);
    }
}

https://godbolt.org/z/jj38MoWen

[Bug libstdc++/107367] All standard library algorithms should optimize to pointers internally when they are contiguous iterators after C++20

[unlvsur at live dot com]

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

cqwrteur <unlvsur at live dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |MOVED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #3 from cqwrteur <unlvsur at live dot com> ---
moved and restart

[Bug libstdc++/107367] All standard library algorithms should optimize to pointers internally when they are contiguous iterators after C++20

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
*** Bug 113046 has been marked as a duplicate of this bug. ***

[Bug libstdc++/107367] All standard library algorithms should optimize to pointers internally when they are contiguous iterators after C++20

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-12-17
     Ever confirmed|0                           |1
           Keywords|                            |missed-optimization
         Resolution|MOVED                       |---
             Status|RESOLVED                    |NEW
           Severity|normal                      |enhancement