Index: libcxx/benchmarks/string.bench.cpp
===================================================================
--- /dev/null
+++ libcxx/benchmarks/string.bench.cpp
@@ -0,0 +1,32 @@
+#include <unordered_set>
+#include <vector>
+#include <cstdint>
+
+#include "benchmark/benchmark_api.h"
+#include "GenerateInput.hpp"
+
+constexpr std::size_t MAX_STRING_LEN = 8<<14;
+
+// Benchmark the first loop of string search: we do not want the string to match
+// until the end of s1.
+static void BM_StringFindPhase1(benchmark::State& state) {
+  // Benchmark following the length of s1.
+  std::string s1(state.range(0), '-');
+  std::string s2(8, '*');
+  while (state.KeepRunning())
+    benchmark::DoNotOptimize(s1.find(s2));
+}
+BENCHMARK(BM_StringFindPhase1)->Range(10,MAX_STRING_LEN);
+
+// Benchmark the __phase2 part of string search: we want the strings s1 and s2
+// to match from the first char in s1.
+static void BM_StringFindPhase2(benchmark::State& state) {
+  std::string s1(MAX_STRING_LEN, '-');
+  // Benchmark following the length of s2.
+  std::string s2(state.range(0), '-');
+  while (state.KeepRunning())
+    benchmark::DoNotOptimize(s1.find(s2));
+}
+BENCHMARK(BM_StringFindPhase2)->Range(1,MAX_STRING_LEN);
+
+BENCHMARK_MAIN()
Index: libcxx/include/__string
===================================================================
--- libcxx/include/__string
+++ libcxx/include/__string
@@ -538,25 +538,63 @@
     return static_cast<_SizeT>(__r - __p);
 }
 
+template <class _RandomAccessIterator, class _Traits>
+_LIBCPP_CONSTEXPR_AFTER_CXX11
+_RandomAccessIterator
+__search_substring(_RandomAccessIterator __first1, _RandomAccessIterator __last1,
+                   _RandomAccessIterator __first2, _RandomAccessIterator __last2)
+{
+    using __iterator_traits = iterator_traits<_RandomAccessIterator>;
+    typedef typename __iterator_traits::difference_type __difference_type;
+
+    // Take advantage of knowing source and pattern lengths.
+    // Stop short when source is smaller than pattern.
+    __difference_type __len2 = __last2 - __first2;
+    if (__len2 == 0)
+        return __first1;
+    __difference_type __len1 = __last1 - __first1;
+    if (__len1 < __len2)
+        return __last1;
+
+    // First element of __first2 is loop invariant.
+    typename __iterator_traits::value_type __f2 = *__first2;
+    while (true)
+    {
+      __len1 = __last1 - __first1;
+      if (__len1 < __len2)
+          return __last1;
+
+      __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
+      if (__first1 == _RandomAccessIterator(0))
+        return __last1;
+
+      // Comparing __first2 as well because the first pointer will be aligned
+      // and we dont know if __first1+1 is going to be aligned.
+      if (_Traits::compare(__first1, __first2, __len2) == 0)
+        return __first1;
+
+        ++__first1;
+    }
+}
+
 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 __str_find(const _CharT *__p, _SizeT __sz, 
        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 {
-    if (__pos > __sz || __sz - __pos < __n)
+    if (__pos > __sz)
         return __npos;
-    if (__n == 0)
+
+    if (__n == 0) // There is nothing to search, just return __pos
         return __pos;
-    const _CharT* __r = 
-        _VSTD::__search(__p + __pos, __p + __sz,
-                        __s, __s + __n, _Traits::eq,
-                        random_access_iterator_tag(), random_access_iterator_tag()).first;
+
+    const _CharT* __r = __search_substring<const _CharT*, _Traits>(__p + __pos, __p + __sz,
+                                                                   __s, __s + __n);
     if (__r == __p + __sz)
         return __npos;
     return static_cast<_SizeT>(__r - __p);
 }
 
-
 // __str_rfind
 
 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>