folly/gen/test/StringBenchmark.cpp

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