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