[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

[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 #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This optimization isn't valid if any iterator operations can throw, because
such an exception should terminate the loop early. Performing the algo on raw
pointers would alter the behaviour.

[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 #6 from cqwrteur <unlvsur at live dot com> ---
Your argument is not correct when you can just detect all the iterator methods
are noexcept. Plus, the standard does not need you to handle exceptions if
iterator throw it but to terminate.

Btw what is the point of contiguous_iterator if i am not allowed to use
std::to_address to optimize code? The whole point of contiguous_iterator is
that i am allowed to use pointer arithematics directly.

Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: redi at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Sent: Friday, June 28, 2024 7:41:47 AM
To: unlvsur@live.com <unlvsur@live.com>
Subject: [Bug libstdc++/107367] All standard library algorithms should optimize
to pointers internally when they are contiguous iterators after C++20

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This optimization isn't valid if any iterator operations can throw, because
such an exception should terminate the loop early. Performing the algo on raw
pointers would alter the behaviour.

--
You are receiving this mail because:
You are on the CC list for the bug.
You reported the bug.

[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 #7 from cqwrteur <unlvsur at live dot com> ---
I see similar side effects like what if someone adds a print statement in the
operator++ or operator * in a contiguous iterator and etc.

If I am not allowed to use std::to_address, what’s the point?