folly/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
  17 #include <folly/String.h>
  18
  19 #include <boost/algorithm/string.hpp>
  20 #include <folly/Benchmark.h>
  21 #include <folly/Random.h>
  22 #include <cstdarg>
  23 #include <random>
  24
  25 using namespace folly;
  26 using namespace std;
  27
  28 BENCHMARK(libc_tolower, iters) {
  29   static const size_t kSize = 256;
  30   // This array is static to keep the compiler from optimizing the
  31   // entire function down to a no-op if it has an inlined impl of
  32   // tolower and thus is able to tell that there are no side-effects.
  33   // No side-effects + no writes to anything other than local variables
  34   // + no return value = no need to run any of the code in the function.
  35   // gcc, for example, makes that optimization with -O2.
  36   static char input[kSize];
  37   for (size_t i = 0; i < kSize; i++) {
  38     input[i] = (char)(i & 0xff);
  39   }
  40   for (auto i = iters; i > 0; i--) {
  41     for (size_t offset = 0; offset < kSize; offset++) {
  42       input[offset] = tolower(input[offset]);
  43     }
  44   }
  45 }
  46
  47 BENCHMARK(folly_toLowerAscii, iters) {
  48   static const size_t kSize = 256;
  49   static char input[kSize];
  50   for (size_t i = 0; i < kSize; i++) {
  51     input[i] = (char)(i & 0xff);
  52   }
  53   for (auto i = iters; i > 0; i--) {
  54     folly::toLowerAscii(input, kSize);
  55   }
  56 }
  57
  58 // A simple benchmark that tests various output sizes for a simple
  59 // input; the goal is to measure the output buffer resize code cost.
  60 void stringPrintfOutputSize(int iters, int param) {
  61   string buffer;
  62   BENCHMARK_SUSPEND { buffer.resize(param, 'x'); }
  63
  64   for (int64_t i = 0; i < iters; ++i) {
  65     string s = stringPrintf("msg: %d, %d, %s", 10, 20, buffer.c_str());
  66   }
  67 }
  68
  69 // The first few of these tend to fit in the inline buffer, while the
  70 // subsequent ones cross that limit, trigger a second vsnprintf, and
  71 // exercise a different codepath.
  72 BENCHMARK_PARAM(stringPrintfOutputSize, 1)
  73 BENCHMARK_PARAM(stringPrintfOutputSize, 4)
  74 BENCHMARK_PARAM(stringPrintfOutputSize, 16)
  75 BENCHMARK_PARAM(stringPrintfOutputSize, 64)
  76 BENCHMARK_PARAM(stringPrintfOutputSize, 256)
  77 BENCHMARK_PARAM(stringPrintfOutputSize, 1024)
  78
  79 // Benchmark simple stringAppendf behavior to show a pathology Lovro
  80 // reported (t5735468).
  81 BENCHMARK(stringPrintfAppendfBenchmark, iters) {
  82   for (unsigned int i = 0; i < iters; ++i) {
  83     string s;
  84     BENCHMARK_SUSPEND { s.reserve(300000); }
  85     for (int j = 0; j < 300000; ++j) {
  86       stringAppendf(&s, "%d", 1);
  87     }
  88   }
  89 }
  90
  91 namespace {
  92 fbstring cbmString;
  93 fbstring cbmEscapedString;
  94 fbstring cEscapedString;
  95 fbstring cUnescapedString;
  96 const size_t kCBmStringLength = 64 << 10;
  97 const uint32_t kCPrintablePercentage = 90;
  98
  99 fbstring uribmString;
 100 fbstring uribmEscapedString;
 101 fbstring uriEscapedString;
 102 fbstring uriUnescapedString;
 103 const size_t kURIBmStringLength = 256;
 104 const uint32_t kURIPassThroughPercentage = 50;
 105
 106 fbstring hexlifyInput;
 107 fbstring hexlifyOutput;
 108 const size_t kHexlifyLength = 1024;
 109
 110 void initBenchmark() {
 111   std::mt19937 rnd;
 112
 113   // C escape
 114   std::uniform_int_distribution<uint32_t> printable(32, 126);
 115   std::uniform_int_distribution<uint32_t> nonPrintable(0, 160);
 116   std::uniform_int_distribution<uint32_t> percentage(0, 99);
 117
 118   cbmString.reserve(kCBmStringLength);
 119   for (size_t i = 0; i < kCBmStringLength; ++i) {
 120     unsigned char c;
 121     if (percentage(rnd) < kCPrintablePercentage) {
 122       c = printable(rnd);
 123     } else {
 124       c = nonPrintable(rnd);
 125       // Generate characters in both non-printable ranges:
 126       // 0..31 and 127..255
 127       if (c >= 32) {
 128         c += (126 - 32) + 1;
 129       }
 130     }
 131     cbmString.push_back(c);
 132   }
 133
 134   cbmEscapedString = cEscape<fbstring>(cbmString);
 135
 136   // URI escape
 137   std::uniform_int_distribution<uint32_t> passthrough('a', 'z');
 138   std::string encodeChars = " ?!\"',+[]";
 139   std::uniform_int_distribution<uint32_t> encode(0, encodeChars.size() - 1);
 140
 141   uribmString.reserve(kURIBmStringLength);
 142   for (size_t i = 0; i < kURIBmStringLength; ++i) {
 143     unsigned char c;
 144     if (percentage(rnd) < kURIPassThroughPercentage) {
 145       c = passthrough(rnd);
 146     } else {
 147       c = encodeChars[encode(rnd)];
 148     }
 149     uribmString.push_back(c);
 150   }
 151
 152   uribmEscapedString = uriEscape<fbstring>(uribmString);
 153
 154   // hexlify
 155   hexlifyInput.resize(kHexlifyLength);
 156   Random::secureRandom(&hexlifyInput[0], kHexlifyLength);
 157   folly::hexlify(hexlifyInput, hexlifyOutput);
 158 }
 159
 160 BENCHMARK(BM_cEscape, iters) {
 161   while (iters--) {
 162     cEscapedString = cEscape<fbstring>(cbmString);
 163     doNotOptimizeAway(cEscapedString.size());
 164   }
 165 }
 166
 167 BENCHMARK(BM_cUnescape, iters) {
 168   while (iters--) {
 169     cUnescapedString = cUnescape<fbstring>(cbmEscapedString);
 170     doNotOptimizeAway(cUnescapedString.size());
 171   }
 172 }
 173
 174 BENCHMARK(BM_uriEscape, iters) {
 175   while (iters--) {
 176     uriEscapedString = uriEscape<fbstring>(uribmString);
 177     doNotOptimizeAway(uriEscapedString.size());
 178   }
 179 }
 180
 181 BENCHMARK(BM_uriUnescape, iters) {
 182   while (iters--) {
 183     uriUnescapedString = uriUnescape<fbstring>(uribmEscapedString);
 184     doNotOptimizeAway(uriUnescapedString.size());
 185   }
 186 }
 187
 188 BENCHMARK(BM_unhexlify, iters) {
 189   // iters/sec = bytes output per sec
 190   std::string unhexed;
 191   folly::StringPiece hex = hexlifyOutput;
 192   for (; iters >= hex.size(); iters -= hex.size()) {
 193     folly::unhexlify(hex, unhexed);
 194   }
 195   iters -= iters % 2; // round down to an even number of chars
 196   hex = hex.subpiece(0, iters);
 197   folly::unhexlify(hex, unhexed);
 198 }
 199
 200 } // namespace
 201
 202 //////////////////////////////////////////////////////////////////////
 203
 204 BENCHMARK(splitOnSingleChar, iters) {
 205   static const std::string line = "one:two:three:four";
 206   for (size_t i = 0; i < iters << 4; ++i) {
 207     std::vector<StringPiece> pieces;
 208     folly::split(':', line, pieces);
 209   }
 210 }
 211
 212 BENCHMARK(splitOnSingleCharFixed, iters) {
 213   static const std::string line = "one:two:three:four";
 214   for (size_t i = 0; i < iters << 4; ++i) {
 215     StringPiece a, b, c, d;
 216     folly::split(':', line, a, b, c, d);
 217   }
 218 }
 219
 220 BENCHMARK(splitOnSingleCharFixedAllowExtra, iters) {
 221   static const std::string line = "one:two:three:four";
 222   for (size_t i = 0; i < iters << 4; ++i) {
 223     StringPiece a, b, c, d;
 224     folly::split<false>(':', line, a, b, c, d);
 225   }
 226 }
 227
 228 BENCHMARK(splitStr, iters) {
 229   static const std::string line = "one-*-two-*-three-*-four";
 230   for (size_t i = 0; i < iters << 4; ++i) {
 231     std::vector<StringPiece> pieces;
 232     folly::split("-*-", line, pieces);
 233   }
 234 }
 235
 236 BENCHMARK(splitStrFixed, iters) {
 237   static const std::string line = "one-*-two-*-three-*-four";
 238   for (size_t i = 0; i < iters << 4; ++i) {
 239     StringPiece a, b, c, d;
 240     folly::split("-*-", line, a, b, c, d);
 241   }
 242 }
 243
 244 BENCHMARK(boost_splitOnSingleChar, iters) {
 245   static const std::string line = "one:two:three:four";
 246   bool (*pred)(char) = [](char c) -> bool { return c == ':'; };
 247   for (size_t i = 0; i < iters << 4; ++i) {
 248     std::vector<boost::iterator_range<std::string::const_iterator>> pieces;
 249     boost::split(pieces, line, pred);
 250   }
 251 }
 252
 253 BENCHMARK(joinCharStr, iters) {
 254   static const std::vector<std::string> input = {
 255       "one", "two", "three", "four", "five", "six", "seven"};
 256   for (size_t i = 0; i < iters << 4; ++i) {
 257     std::string output;
 258     folly::join(':', input, output);
 259   }
 260 }
 261
 262 BENCHMARK(joinStrStr, iters) {
 263   static const std::vector<std::string> input = {
 264       "one", "two", "three", "four", "five", "six", "seven"};
 265   for (size_t i = 0; i < iters << 4; ++i) {
 266     std::string output;
 267     folly::join(":", input, output);
 268   }
 269 }
 270
 271 BENCHMARK(joinInt, iters) {
 272   static const auto input = {123, 456, 78910, 1112, 1314, 151, 61718};
 273   for (size_t i = 0; i < iters << 4; ++i) {
 274     std::string output;
 275     folly::join(":", input, output);
 276   }
 277 }
 278
 279 int main(int argc, char** argv) {
 280   gflags::ParseCommandLineFlags(&argc, &argv, true);
 281   initBenchmark();
 282   folly::runBenchmarks();
 283   return 0;
 284 }
 285
 286 /*
 287 Results on x86_64:
 288 ============================================================================
 289 folly/test/StringBenchmark.cpp                  relative  time/iter  iters/s
 290 ============================================================================
 291 libc_tolower                                               773.30ns    1.29M
 292 folly_toLowerAscii                                          65.04ns   15.38M
 293 stringPrintfOutputSize(1)                                  224.67ns    4.45M
 294 stringPrintfOutputSize(4)                                  231.53ns    4.32M
 295 stringPrintfOutputSize(16)                                 286.54ns    3.49M
 296 stringPrintfOutputSize(64)                                 305.47ns    3.27M
 297 stringPrintfOutputSize(256)                                  1.48us  674.45K
 298 stringPrintfOutputSize(1024)                                 5.89us  169.72K
 299 stringPrintfAppendfBenchmark                                34.43ms    29.04
 300 BM_cEscape                                                 461.51us    2.17K
 301 BM_cUnescape                                               328.19us    3.05K
 302 BM_uriEscape                                                 4.36us  229.25K
 303 BM_uriUnescape                                               2.22us  450.64K
 304 splitOnSingleChar                                            1.46us  687.21K
 305 splitOnSingleCharFixed                                     133.02ns    7.52M
 306 splitOnSingleCharFixedAllowExtra                            74.35ns   13.45M
 307 splitStr                                                     2.36us  424.00K
 308 splitStrFixed                                              282.38ns    3.54M
 309 boost_splitOnSingleChar                                      2.83us  353.12K
 310 joinCharStr                                                  2.65us  376.93K
 311 joinStrStr                                                   2.64us  378.09K
 312 joinInt                                                      3.89us  257.37K
 313 ============================================================================
 314 */