[PATCH 3/3] libstdc++: Reuse predicates in std::search and std::is_permutation

[Jonathan Wakely]

On Thu, 25 Sept 2025 at 15:52, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
>
>
> On Thu, Sep 25, 2025 at 4:22 PM Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> Hoist construction of the call wrappers out of the loop when we're
>> repeatedly creating a call wrapper with the same bound arguments.
>>
>> We need to be careful about iterators that return proxy references,
>> because bind1st(pred, *first) could bind a reference to a prvalue proxy
>> reference returned by *first. That would then be an invalid reference by
>> the time we invoked the call wrapper.
>>
>> If we dereference the iterator first and store the result of that on the
>> stack, then we don't have a prvalue proxy reference, and can bind it (or
>> the value it refers to) into the call wrapper:
>>
>>   auto&& val = *first; // lifetime extension
>>   auto wrapper = bind1st(pred, val);
>>   for (;;)
>>     /* use wrapper */;
>>
>> This ensures that the reference returned from *first outlives the call
>> wrapper, whether it's a proxy reference or not.
>>
>> For C++98 compatibility in __search we can use __decltype(expr) instead
>> of auto&&.
>>
>> libstdc++-v3/ChangeLog:
>>
>>         * include/bits/stl_algobase.h (__search, __is_permutation):
>>         Reuse predicate instead of creating a new one each time.
>>         * include/bits/stl_algo.h (__is_permutation): Likewise.
>> ---
>>
>> Tested powerpc64le-linux and x86_64-linux.
>
> LGTM.
>>
>>
>> This part wasn't previously reviewed at all on the forge.
>>
>>  libstdc++-v3/include/bits/stl_algo.h     | 14 ++++--------
>>  libstdc++-v3/include/bits/stl_algobase.h | 29 +++++++++++-------------
>>  2 files changed, 18 insertions(+), 25 deletions(-)
>>
>> diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
>> index 7ff5dd84a97a..bbd1800af779 100644
>> --- a/libstdc++-v3/include/bits/stl_algo.h
>> +++ b/libstdc++-v3/include/bits/stl_algo.h
>> @@ -3531,18 +3531,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
>>
>>        for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
>>         {
>> -         if (__scan != std::__find_if(__first1, __scan,
>> -                                      __gnu_cxx::__ops::bind1st(__pred,
>> -                                                                *__scan)))
>> +         auto&& __scan_val = *__scan;
>> +         auto __scaneq = __gnu_cxx::__ops::bind1st(__pred, __scan_val);
>
> I have looked into regex_iterator, that is stashing but reports itself as forward iterator,
> so we cannot change __scan iterator while we use that reference, and this is not the case here.
>>
>>
>>
>> +         if (__scan != std::__find_if(__first1, __scan, __scaneq))
>>             continue; // We've seen this one before.
>>
>> -         auto __matches = std::__count_if(__first2, __last2,
>> -                                          __gnu_cxx::__ops::bind1st(__pred,
>> -                                                                    *__scan));
>> +         auto __matches = std::__count_if(__first2, __last2, __scaneq);
>>           if (0 == __matches
>> -             || std::__count_if(__scan, __last1,
>> -                                __gnu_cxx::__ops::bind1st(__pred, *__scan))
>> -             != __matches)
>> +               || std::__count_if(__scan, __last1, __scaneq) != __matches)
>>             return false;
>>         }
>>        return true;
>> diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
>> index 03f64fb3e6c3..443cbef76dee 100644
>> --- a/libstdc++-v3/include/bits/stl_algobase.h
>> +++ b/libstdc++-v3/include/bits/stl_algobase.h
>> @@ -2149,21 +2149,21 @@ _GLIBCXX_END_NAMESPACE_ALGO
>>        if (__first1 == __last1 || __first2 == __last2)
>>         return __first1;
>>
>> +      __decltype(*__first2) __first2_val(*__first2);
>
> Again __first2 is not modified. So looks good.
>>
>> +      __decltype(__gnu_cxx::__ops::bind2nd(__predicate, __first2_val))
>> +       __match_first = __gnu_cxx::__ops::bind2nd(__predicate, __first2_val);
>> +
>>        // Test for a pattern of length 1.
>>        _ForwardIterator2 __p1(__first2);
>>        if (++__p1 == __last2)
>> -       return std::__find_if(__first1, __last1,
>> -                             __gnu_cxx::__ops::bind2nd(__predicate,
>> -                                                       *__first2));
>> +       return std::__find_if(__first1, __last1, __match_first);
>>
>>        // General case.
>>        _ForwardIterator1 __current = __first1;
>>
>>        for (;;)
>>         {
>> -         __first1 =
>> -           std::__find_if(__first1, __last1,
>> -                          __gnu_cxx::__ops::bind2nd(__predicate, *__first2));
>> +         __first1 = std::__find_if(__first1, __last1, __match_first);
>>
>>           if (__first1 == __last1)
>>             return __last1;
>> @@ -2184,6 +2184,7 @@ _GLIBCXX_END_NAMESPACE_ALGO
>>         }
>>        return __first1;
>>      }
>> +#undef __match_first
>>
>>  #if __cplusplus >= 201103L
>>    template<typename _ForwardIterator1, typename _ForwardIterator2,
>> @@ -2208,18 +2209,14 @@ _GLIBCXX_END_NAMESPACE_ALGO
>>        std::advance(__last2, std::distance(__first1, __last1));
>>        for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
>>         {
>> -         if (__scan != std::__find_if(__first1, __scan,
>> -                                      __gnu_cxx::__ops::bind1st(__pred,
>> -                                                                *__scan)))
>> +         auto&& __scan_val = *__scan;
>> +         auto __scaneq = __gnu_cxx::__ops::bind1st(__pred, __scan_val);
>> +         if (__scan != std::__find_if(__first1, __scan, __scaneq))
>>             continue; // We've seen this one before.
>>
>> -         auto __matches
>> -           = std::__count_if(__first2, __last2,
>> -                             __gnu_cxx::__ops::bind1st(__pred, *__scan));
>> -         if (0 == __matches ||
>> -             std::__count_if(__scan, __last1,
>> -                             __gnu_cxx::__ops::bind1st(__pred, *__scan))
>> -             != __matches)
>> +         auto __matches = std::__count_if(__first2, __last2, __scaneq);
>> +         if (0 == __matches
>> +               || std::__count_if(__scan, __last1, __scaneq) != __matches)
>
> Here the extraction really benefits us.

Yeah this is the first case I found that I wanted to improve, and then
I found the other cases.