From e7e16f3d559015083a62f1343dcc90c04a9e88f2 Mon Sep 17 00:00:00 2001 From: Tom Jackson Date: Wed, 4 Feb 2015 10:52:34 -0800 Subject: [PATCH] Adding demonstrative test of O(n^2) string split case Summary: Even though the benchmark only keeps the first 10 lines, it gets slower the bigger the "file" is. ``` folly/gen/test/StringBenchmark.cpp relative time/iter iters/s ---------------------------------------------------------------------------- Lines_Gen(1e3) 5.53us 180.94K Lines_Gen(2e3) 66.43% 8.32us 120.21K Lines_Gen(3e3) 48.26% 11.45us 87.33K ``` Test Plan: Benchmarks Reviewed By: lesha@fb.com Subscribers: folly-diffs@, yfeldblum FB internal diff: D1823545 Tasks: 6155600 Signature: t1:1823545:1423023712:86fdb3dadbec44195e4b3596cf793cea80ae3a76 --- folly/gen/test/StringBenchmark.cpp | 15 +++++++++++++++ 1 file changed, 15 insertions(+) diff --git a/folly/gen/test/StringBenchmark.cpp b/folly/gen/test/StringBenchmark.cpp index fcc20d12..78c61900 100644 --- a/folly/gen/test/StringBenchmark.cpp +++ b/folly/gen/test/StringBenchmark.cpp @@ -35,6 +35,7 @@ static vector testStrVector = seq(1, testSize.load()) | eachTo() | as(); +static auto testFileContent = from(testStrVector) | unsplit('\n'); const char* const kLine = "The quick brown fox jumped over the lazy dog.\n"; const size_t kLineCount = 10000; @@ -212,6 +213,20 @@ BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 2000) BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 4000) BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 8000) +BENCHMARK_DRAW_LINE() +void Lines_Gen(size_t iters, int joinSize) { + size_t s = 0; + StringPiece content = testFileContent; + for (size_t i = 0; i < iters; ++i) { + s += lines(content.subpiece(0, joinSize)) | take(100) | count; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_PARAM(Lines_Gen, 1e3) +BENCHMARK_RELATIVE_PARAM(Lines_Gen, 2e3) +BENCHMARK_RELATIVE_PARAM(Lines_Gen, 3e3) + BENCHMARK_DRAW_LINE() fbstring records -- 2.34.1