folly/gen/test/StringBenchmark.cpp

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