hiraditya created this revision.
hiraditya added reviewers: mclow.lists, EricWF.
hiraditya added subscribers: sebpop, cfe-commits.
Improving string::find such that it ultimately gets converted to calls to
memchr and memcmp. This is an intermediate patch to see if there is an interest
in this optimization. I'm planning to propagate this change to similar
functions string::rfind ... etc.
Worked in collaboration with Sebastian Pop.
https://reviews.llvm.org/D27068
Files:
libcxx/benchmarks/string.bench.cpp
libcxx/include/__string
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>
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()
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
