[libcxx]: Unroll std::find on AIX

[etiotto]

Summary

This patch specializes the std::find implementation on AIX to unroll the while loop in that function for RandomAccessIterators.

[Mordante]

This patch increases the maintenance burden for libc++, so before accepting this patch I would like to know more about the benefits it brings.
Can you provide some benchmarks for these changes?
Why would these changes only be beneficial for AIX and not for other platforms?

[ldionne]

Echoing @Mordante 's feedback here - we will either take this patch for everyone if it benefits everyone, or not take it at all. If you do some benchmarking and are able to show that it's an improvement (and is worth the added complexity + code size), then I'd be OK with making this change for everyone. But it has to be backed.

[xbolva00]

Just curious, why you cannot use:

#if defined(AIX)
#pragma unroll 4
#endif
for(….)

[xbolva00]

it seems like we dont specialize std::find to use memchr if possible?

[lebedev.ri]

Echoing @xbolva00's comment, why is compiler's hand being forced here in the first place?
I'm disheartened by seeing such changes, because there's clearly no cost modelling here,
and it is assumed that one size fits all. If this is beneficial, then this is certainly
a LLVM bug. In particular, LoopFullUnrollPass says `will not try to unroll loop with
runtime trip count -unroll-runtime not given`, and LoopUnrollPass says:
`Bailout for multi-exit handling when latch exit has >1 predecessor.
Multiple exit/exiting blocks in loop and multi-exit unrolling not enabled!`

Fixing those instead would benefit everyone.

libcxx/include/algorithm

while (__n > 0)
          --__n;
     }
     return __first;
 }
 #endif
 
 // find
 
+#if defined(_AIX)
+
+template <class _InputIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator
+__find(_InputIterator __first, _InputIterator __last, const _Tp& __value_, input_iterator_tag)
+{
+    for (; __first != __last; ++__first)
+        if (*__first == __value_)
+            break;
+    return __first;
+}
+
+template <class _RandomAccessIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIterator
+__find(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
+{
+    typename iterator_traits<_RandomAccessIterator>::difference_type __d = (__last - __first);
+    while (__d >= 4) {
+        if (*__first == __value_)
+            return __first;
+        ++__first;
+
+        if (*__first == __value_)
+            return __first;
+        ++__first;
+
+        if (*__first == __value_)
+            return __first;
+        ++__first;
+
+        if (*__first == __value_)
+            return __first;
+        ++__first;
+
+        __d -= 4;
+    }
+
+    for (; __first != __last; ++__first)
+        if (*__first == __value_)
+            break;
+    return __first;
+}
+
+template <class _InputIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator
+find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
+{
+    return __find(__first, __last, __value_, typename iterator_traits<_InputIterator>::iterator_category());
+}
+
+#else
+
 template <class _InputIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _InputIterator
 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
 {
     for (; __first != __last; ++__first)
         if (*__first == __value_)
             break;
     return __first;
 }
+#endif
 
 // find_if
 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _InputIterator
 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)