Remove unused code

[hiraditya]

Summary

Worked with Sebastian Pop

[sebpop]

Let's also add a testcase and show the performance improvement.

[mclow.lists]

/me wonders what the perf difference when _LIBCPP_UNROLL_LOOPS is defined or not.

I think this (_LIBCPP_UNROLL_LOOPS) falls squarely into Chandler's request that we complain to him when the compiler generates sub-optimal code, instead of doing things like manually unrolling loops.

[mclow.lists]

__search is the only place where _LIBCPP_UNROLL_LOOPS is currently used.

[sebpop]

In D26991#606764, @mclow.lists wrote:

/me wonders what the perf difference when _LIBCPP_UNROLL_LOOPS is defined or not.

I think this (_LIBCPP_UNROLL_LOOPS) falls squarely into Chandler's request that we complain to him when the compiler generates sub-optimal code, instead of doing things like manually unrolling loops.

I think we should remove all the code in the ifdef: it looks to me like this code was left in from a previous "experiment", as it never gets executed unless one compiles the code with -D_LIBCPP_UNROLL_LOOPS, which seems wrong. Let's push this cleanup in a separate commit.

[mclow.lists]

There are no uses of _LIBCPP_UNROLL_LOOPS in LLVM (other than the ones in <algorithm>.

Googling for _LIBCPP_UNROLL_LOOPS on github finds the ones in libc++, and no others.
I think I'll just take it out, and see what happens.

[hiraditya]

@mclow.lists
I can remove this and update this patch with the load hoisted, if this is okay.

[hiraditya]

Removed unused code.

[mclow.lists]

This looks fine to me - though I wonder if the compiler can hoist *__first2 w/o us helping it.

[mclow.lists]

libcxx/include/algorithm

1499 ↗

(On Diff #79463)

I just realized that we can't do this.
This imposes a requirement that the value_type be copy-constructible.

With this in place, we can't search a sequence of move-only types.

[hiraditya]

libcxx/include/algorithm

1499 ↗

(On Diff #79463)

Ok, I'll remove this change while pushing. I'll change the subject as well, because now this patch is just removing the unused code.
Thanks for the review.

[hiraditya]

libcxx/include/algorithm

1499 ↗

(On Diff #79463)

Are we allowed to call __search on a type which is not copy-constructible?

libcxx/trunk/include/algorithm

__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
     // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
     const _D2 __len2 = __last2 - __first2;
     if (__len2 == 0)
         return make_pair(__first1, __first1);
     const _D1 __len1 = __last1 - __first1;
     if (__len1 < __len2)
         return make_pair(__last1, __last1);
     const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here
+
     while (true)
     {
-#if !_LIBCPP_UNROLL_LOOPS
         while (true)
         {
             if (__first1 == __s)
                 return make_pair(__last1, __last1);
             if (__pred(*__first1, *__first2))
                 break;
             ++__first1;
         }
-#else  // !_LIBCPP_UNROLL_LOOPS
-        for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
-        {
-            if (__pred(*__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            ++__first1;
-        }
-        switch (__s - __first1)
-        {
-        case 3:
-            if (__pred(*__first1, *__first2))
-                break;
-            ++__first1;
-        case 2:
-            if (__pred(*__first1, *__first2))
-                break;
-            ++__first1;
-        case 1:
-            if (__pred(*__first1, *__first2))
-                break;
-        case 0:
-            return make_pair(__last1, __last1);
-        }
-    __phase2:
-#endif  // !_LIBCPP_UNROLL_LOOPS
+
         _RandomAccessIterator1 __m1 = __first1;
         _RandomAccessIterator2 __m2 = __first2;
-#if !_LIBCPP_UNROLL_LOOPS
          while (true)
          {
              if (++__m2 == __last2)
                  return make_pair(__first1, __first1 + __len2);
              ++__m1;          // no need to check range on __m1 because __s guarantees we have enough source
              if (!__pred(*__m1, *__m2))
              {
                  ++__first1;
                  break;
              }
          }
-#else  // !_LIBCPP_UNROLL_LOOPS
-        ++__m2;
-        ++__m1;
-        for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
-        {
-            if (!__pred(*__m1, *__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            ++__m1;
-            ++__m2;
-        }
-        switch (__last2 - __m2)
-        {
-        case 3:
-            if (!__pred(*__m1, *__m2))
-                break;
-            ++__m1;
-            ++__m2;
-        case 2:
-            if (!__pred(*__m1, *__m2))
-                break;
-            ++__m1;
-            ++__m2;
-        case 1:
-            if (!__pred(*__m1, *__m2))
-                break;
-        case 0:
-            return make_pair(__first1, __first1 + __len2);
-        }
-    __continue:
-        ++__first1;
-#endif  // !_LIBCPP_UNROLL_LOOPS
     }
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator1
 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
        _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)