From d6c4dda1280917cb0d9429bad75d08bb49290488 Mon Sep 17 00:00:00 2001 From: Soren Lassen Date: Sun, 16 Dec 2012 13:46:32 -0800 Subject: [PATCH] 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 --- folly/Range.h | 2 +- folly/test/RangeFindBenchmark.cpp | 25 ++++++++++++++++++++++++- 2 files changed, 25 insertions(+), 2 deletions(-) diff --git a/folly/Range.h b/folly/Range.h index 2264d253..e214bee9 100644 --- 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 868618f4..5f58db0a 100644 --- 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); -- 2.34.1