folly/gen/test/StringBenchmark.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include <atomic>
  17 #include <glog/logging.h>
  18
  19 #include <folly/Benchmark.h>
  20 #include <folly/Foreach.h>
  21 #include <folly/String.h>
  22 #include <folly/gen/Base.h>
  23 #include <folly/gen/String.h>
  24
  25 using namespace folly;
  26 using namespace folly::gen;
  27 using std::pair;
  28 using std::set;
  29 using std::vector;
  30 using std::tuple;
  31
  32 namespace {
  33
  34 static std::atomic<int> testSize(1000);
  35 static vector<fbstring> testStrVector
  36   = seq(1, testSize.load())
  37   | eachTo<fbstring>()
  38   | as<vector>();
  39 static auto testFileContent = from(testStrVector) | unsplit('\n');
  40
  41 const char* const kLine = "The quick brown fox jumped over the lazy dog.\n";
  42 const size_t kLineCount = 10000;
  43 std::string bigLines;
  44 const size_t kSmallLineSize = 17;
  45 std::vector<std::string> smallLines;
  46
  47 void initStringResplitterBenchmark() {
  48   bigLines.reserve(kLineCount * strlen(kLine));
  49   for (size_t i = 0; i < kLineCount; ++i) {
  50     bigLines += kLine;
  51   }
  52   size_t remaining = bigLines.size();
  53   size_t pos = 0;
  54   while (remaining) {
  55     size_t n = std::min(kSmallLineSize, remaining);
  56     smallLines.push_back(bigLines.substr(pos, n));
  57     pos += n;
  58     remaining -= n;
  59   }
  60 }
  61
  62 size_t len(folly::StringPiece s) { return s.size(); }
  63
  64 }  // namespace
  65
  66 BENCHMARK(StringResplitter_Big, iters) {
  67   size_t s = 0;
  68   while (iters--) {
  69     s += from({bigLines}) | resplit('\n') | map(&len) | sum;
  70   }
  71   folly::doNotOptimizeAway(s);
  72 }
  73
  74 BENCHMARK_RELATIVE(StringResplitter_Small, iters) {
  75   size_t s = 0;
  76   while (iters--) {
  77     s += from(smallLines) | resplit('\n') | map(&len) | sum;
  78   }
  79   folly::doNotOptimizeAway(s);
  80 }
  81
  82 BENCHMARK_DRAW_LINE()
  83
  84 BENCHMARK(StringSplit_Old, iters) {
  85   size_t s = 0;
  86   std::string line(kLine);
  87   while (iters--) {
  88     std::vector<StringPiece> parts;
  89     split(' ', line, parts);
  90     s += parts.size();
  91   }
  92   folly::doNotOptimizeAway(s);
  93 }
  94
  95
  96 BENCHMARK_RELATIVE(StringSplit_Gen_Vector, iters) {
  97   size_t s = 0;
  98   StringPiece line(kLine);
  99   while (iters--) {
 100     s += (split(line, ' ') | as<vector>()).size();
 101   }
 102   folly::doNotOptimizeAway(s);
 103 }
 104
 105 BENCHMARK_DRAW_LINE()
 106
 107 BENCHMARK(StringSplit_Old_ReuseVector, iters) {
 108   size_t s = 0;
 109   std::string line(kLine);
 110   std::vector<StringPiece> parts;
 111   while (iters--) {
 112     parts.clear();
 113     split(' ', line, parts);
 114     s += parts.size();
 115   }
 116   folly::doNotOptimizeAway(s);
 117 }
 118
 119 BENCHMARK_RELATIVE(StringSplit_Gen_ReuseVector, iters) {
 120   size_t s = 0;
 121   StringPiece line(kLine);
 122   std::vector<StringPiece> parts;
 123   while (iters--) {
 124     parts.clear();
 125     split(line, ' ') | appendTo(parts);
 126     s += parts.size();
 127   }
 128   folly::doNotOptimizeAway(s);
 129 }
 130
 131 BENCHMARK_RELATIVE(StringSplit_Gen, iters) {
 132   size_t s = 0;
 133   StringPiece line(kLine);
 134   while (iters--) {
 135     s += split(line, ' ') | count;
 136   }
 137   folly::doNotOptimizeAway(s);
 138 }
 139
 140 BENCHMARK_RELATIVE(StringSplit_Gen_Take, iters) {
 141   size_t s = 0;
 142   StringPiece line(kLine);
 143   while (iters--) {
 144     s += split(line, ' ') | take(10) | count;
 145   }
 146   folly::doNotOptimizeAway(s);
 147 }
 148
 149 BENCHMARK_DRAW_LINE()
 150
 151 BENCHMARK(StringUnsplit_Old, iters) {
 152   size_t s = 0;
 153   while (iters--) {
 154     fbstring joined;
 155     join(',', testStrVector, joined);
 156     s += joined.size();
 157   }
 158   folly::doNotOptimizeAway(s);
 159 }
 160
 161 BENCHMARK_RELATIVE(StringUnsplit_Old_ReusedBuffer, iters) {
 162   size_t s = 0;
 163   fbstring joined;
 164   while (iters--) {
 165     joined.clear();
 166     join(',', testStrVector, joined);
 167     s += joined.size();
 168   }
 169   folly::doNotOptimizeAway(s);
 170 }
 171
 172 BENCHMARK_RELATIVE(StringUnsplit_Gen, iters) {
 173   size_t s = 0;
 174   StringPiece line(kLine);
 175   while (iters--) {
 176     fbstring joined = from(testStrVector) | unsplit(',');
 177     s += joined.size();
 178   }
 179   folly::doNotOptimizeAway(s);
 180 }
 181
 182 BENCHMARK_RELATIVE(StringUnsplit_Gen_ReusedBuffer, iters) {
 183   size_t s = 0;
 184   fbstring buffer;
 185   while (iters--) {
 186     buffer.clear();
 187     from(testStrVector) | unsplit(',', &buffer);
 188     s += buffer.size();
 189   }
 190   folly::doNotOptimizeAway(s);
 191 }
 192
 193 BENCHMARK_DRAW_LINE()
 194
 195 void StringUnsplit_Gen(size_t iters, size_t joinSize) {
 196   std::vector<fbstring> v;
 197   BENCHMARK_SUSPEND {
 198     FOR_EACH_RANGE(i, 0, joinSize) {
 199       v.push_back(to<fbstring>(rand()));
 200     }
 201   }
 202   size_t s = 0;
 203   fbstring buffer;
 204   while (iters--) {
 205     buffer.clear();
 206     from(v) | unsplit(',', &buffer);
 207     s += buffer.size();
 208   }
 209   folly::doNotOptimizeAway(s);
 210 }
 211
 212 BENCHMARK_PARAM(StringUnsplit_Gen, 1000)
 213 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 2000)
 214 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 4000)
 215 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 8000)
 216
 217 BENCHMARK_DRAW_LINE()
 218 void Lines_Gen(size_t iters, int joinSize) {
 219   size_t s = 0;
 220   StringPiece content = testFileContent;
 221   for (size_t i = 0; i < iters; ++i) {
 222     s += lines(content.subpiece(0, joinSize)) | take(100) | count;
 223   }
 224   folly::doNotOptimizeAway(s);
 225 }
 226
 227 BENCHMARK_PARAM(Lines_Gen, 1e3)
 228 BENCHMARK_RELATIVE_PARAM(Lines_Gen, 2e3)
 229 BENCHMARK_RELATIVE_PARAM(Lines_Gen, 3e3)
 230
 231 BENCHMARK_DRAW_LINE()
 232
 233 fbstring records
 234 = seq<size_t>(1, 1000)
 235   | mapped([](size_t i) {
 236       return folly::to<fbstring>(i, ' ', i * i, ' ', i * i * i);
 237     })
 238   | unsplit('\n');
 239
 240 BENCHMARK(Records_EachToTuple, iters) {
 241   size_t s = 0;
 242   for (size_t i = 0; i < iters; i += 1000) {
 243     s += split(records, '\n')
 244        | eachToTuple<int, size_t, StringPiece>(' ')
 245        | get<1>()
 246        | sum;
 247   }
 248   folly::doNotOptimizeAway(s);
 249 }
 250
 251 BENCHMARK_RELATIVE(Records_VectorStringPieceReused, iters) {
 252   size_t s = 0;
 253   std::vector<StringPiece> fields;
 254   for (size_t i = 0; i < iters; i += 1000) {
 255     s += split(records, '\n')
 256        | mapped([&](StringPiece line) {
 257            fields.clear();
 258            folly::split(' ', line, fields);
 259            CHECK(fields.size() == 3);
 260            return std::make_tuple(
 261              folly::to<int>(fields[0]),
 262              folly::to<size_t>(fields[1]),
 263              StringPiece(fields[2]));
 264          })
 265        | get<1>()
 266        | sum;
 267   }
 268   folly::doNotOptimizeAway(s);
 269 }
 270
 271 BENCHMARK_RELATIVE(Records_VectorStringPiece, iters) {
 272   size_t s = 0;
 273   for (size_t i = 0; i < iters; i += 1000) {
 274     s += split(records, '\n')
 275        | mapped([](StringPiece line) {
 276            std::vector<StringPiece> fields;
 277            folly::split(' ', line, fields);
 278            CHECK(fields.size() == 3);
 279            return std::make_tuple(
 280              folly::to<int>(fields[0]),
 281              folly::to<size_t>(fields[1]),
 282              StringPiece(fields[2]));
 283          })
 284        | get<1>()
 285        | sum;
 286   }
 287   folly::doNotOptimizeAway(s);
 288 }
 289
 290 BENCHMARK_RELATIVE(Records_VectorString, iters) {
 291   size_t s = 0;
 292   for (size_t i = 0; i < iters; i += 1000) {
 293     s += split(records, '\n')
 294        | mapped([](StringPiece line) {
 295            std::vector<std::string> fields;
 296            folly::split(' ', line, fields);
 297            CHECK(fields.size() == 3);
 298            return std::make_tuple(
 299              folly::to<int>(fields[0]),
 300              folly::to<size_t>(fields[1]),
 301              StringPiece(fields[2]));
 302          })
 303        | get<1>()
 304        | sum;
 305   }
 306   folly::doNotOptimizeAway(s);
 307 }
 308
 309 // Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz
 310 // ============================================================================
 311 // folly/gen/test/StringBenchmark.cpp              relative  time/iter  iters/s
 312 // ============================================================================
 313 // StringResplitter_Big                                       108.58us    9.21K
 314 // StringResplitter_Small                            10.60%     1.02ms   976.48
 315 // ----------------------------------------------------------------------------
 316 // StringSplit_Old                                            357.82ns    2.79M
 317 // StringSplit_Gen_Vector                           105.10%   340.46ns    2.94M
 318 // ----------------------------------------------------------------------------
 319 // StringSplit_Old_ReuseVector                                 96.45ns   10.37M
 320 // StringSplit_Gen_ReuseVector                      124.01%    77.78ns   12.86M
 321 // StringSplit_Gen                                  140.10%    68.85ns   14.52M
 322 // StringSplit_Gen_Take                             122.97%    78.44ns   12.75M
 323 // ----------------------------------------------------------------------------
 324 // StringUnsplit_Old                                           42.99us   23.26K
 325 // StringUnsplit_Old_ReusedBuffer                   100.48%    42.79us   23.37K
 326 // StringUnsplit_Gen                                 96.37%    44.61us   22.42K
 327 // StringUnsplit_Gen_ReusedBuffer                   116.96%    36.76us   27.20K
 328 // ----------------------------------------------------------------------------
 329 // StringUnsplit_Gen(1000)                                     44.71us   22.37K
 330 // StringUnsplit_Gen(2000)                           49.28%    90.72us   11.02K
 331 // StringUnsplit_Gen(4000)                           24.05%   185.91us    5.38K
 332 // StringUnsplit_Gen(8000)                           12.23%   365.42us    2.74K
 333 // ----------------------------------------------------------------------------
 334 // Records_EachToTuple                                        101.43us    9.86K
 335 // Records_VectorStringPieceReused                   93.72%   108.22us    9.24K
 336 // Records_VectorStringPiece                         37.14%   273.11us    3.66K
 337 // Records_VectorString                              16.70%   607.47us    1.65K
 338 // ============================================================================
 339
 340 int main(int argc, char *argv[]) {
 341   gflags::ParseCommandLineFlags(&argc, &argv, true);
 342   initStringResplitterBenchmark();
 343   runBenchmarks();
 344   return 0;
 345 }