Remove unnecessary branch in Range::find_first_of(Range,size_t)

Summary:
Added benchmarks.

Before:

folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
string length 10:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       2.15ns  464.16M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       1.42ns  704.22M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       3.72ns  268.70M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       5.00ns  199.96M

After:

string length 10:
FindFirstOfRange                                             1.36ns  732.92M
FindFirstOfOffsetRange                                       1.36ns  732.61M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.38ns  727.16M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.79ns  558.40M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       2.73ns  366.44M

Test Plan: fbconfig folly && fbmake runtests

Reviewed By: delong.j@fb.com

FB internal diff: D660125

diff --git a/folly/Range.h b/folly/Range.h
index 2264d2533df29e3617a8ba7ff86a609f38bfb167..e214bee91c86f57197c240bd8bc19c1b52bb0c66 100644 (file)
--- a/folly/Range.h
+++ b/folly/Range.h
@@ -387,7 +387,7 @@ public:
 
   size_type find_first_of(Range needles, size_t pos) const {
     if (pos > size()) return std::string::npos;
-    size_type ret = qfind_first_of(pos ? subpiece(pos) : *this, needles);
+    size_type ret = qfind_first_of(subpiece(pos), needles);
     return ret == npos ? ret : ret + pos;
   }
 

diff --git a/folly/test/RangeFindBenchmark.cpp b/folly/test/RangeFindBenchmark.cpp
index 868618f4d31942a53d6149d0cbee645646ec0a62..5f58db0aa0b628e9b8ec1ee8f31a43323d107e08 100644 (file)
--- a/folly/test/RangeFindBenchmark.cpp
+++ b/folly/test/RangeFindBenchmark.cpp
@@ -48,7 +48,7 @@ BENCHMARK(FindSingleCharMemchr, n) {
 }
 
 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
-  char c = 'b';
+  const char c = 'b';
   StringPiece haystack(str);
   folly::StringPiece needle(&c, &c + 1);
   FOR_EACH_RANGE (i, 0, n) {
@@ -58,6 +58,29 @@ BENCHMARK_RELATIVE(FindSingleCharRange, n) {
   }
 }
 
+BENCHMARK_DRAW_LINE();
+
+BENCHMARK(FindFirstOfRange, n) {
+  StringPiece haystack(str);
+  folly::StringPiece needle("ab");
+  FOR_EACH_RANGE (i, 0, n) {
+    doNotOptimizeAway(haystack.find_first_of(needle));
+    char x = haystack[0];
+    doNotOptimizeAway(&x);
+  }
+}
+
+BENCHMARK(FindFirstOfOffsetRange, n) {
+  StringPiece haystack(str);
+  folly::StringPiece needle("ab");
+  FOR_EACH_RANGE (i, 0, n) {
+    size_t pos = i / 2; // not a constant to prevent optimization
+    doNotOptimizeAway(haystack.find_first_of(needle, pos));
+    char x = haystack[0];
+    doNotOptimizeAway(&x);
+  }
+}
+
 int main(int argc, char** argv) {
   google::ParseCommandLineFlags(&argc, &argv, true);