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 <cstdarg>
  21 #include <folly/Benchmark.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 void initBenchmark() {
 106   std::mt19937 rnd;
 107
 108   // C escape
 109   std::uniform_int_distribution<uint32_t> printable(32, 126);
 110   std::uniform_int_distribution<uint32_t> nonPrintable(0, 160);
 111   std::uniform_int_distribution<uint32_t> percentage(0, 99);
 112
 113   cbmString.reserve(kCBmStringLength);
 114   for (size_t i = 0; i < kCBmStringLength; ++i) {
 115     unsigned char c;
 116     if (percentage(rnd) < kCPrintablePercentage) {
 117       c = printable(rnd);
 118     } else {
 119       c = nonPrintable(rnd);
 120       // Generate characters in both non-printable ranges:
 121       // 0..31 and 127..255
 122       if (c >= 32) {
 123         c += (126 - 32) + 1;
 124       }
 125     }
 126     cbmString.push_back(c);
 127   }
 128
 129   cbmEscapedString = cEscape<fbstring>(cbmString);
 130
 131   // URI escape
 132   std::uniform_int_distribution<uint32_t> passthrough('a', 'z');
 133   std::string encodeChars = " ?!\"',+[]";
 134   std::uniform_int_distribution<uint32_t> encode(0, encodeChars.size() - 1);
 135
 136   uribmString.reserve(kURIBmStringLength);
 137   for (size_t i = 0; i < kURIBmStringLength; ++i) {
 138     unsigned char c;
 139     if (percentage(rnd) < kURIPassThroughPercentage) {
 140       c = passthrough(rnd);
 141     } else {
 142       c = encodeChars[encode(rnd)];
 143     }
 144     uribmString.push_back(c);
 145   }
 146
 147   uribmEscapedString = uriEscape<fbstring>(uribmString);
 148 }
 149
 150 BENCHMARK(BM_cEscape, iters) {
 151   while (iters--) {
 152     cEscapedString = cEscape<fbstring>(cbmString);
 153     doNotOptimizeAway(cEscapedString.size());
 154   }
 155 }
 156
 157 BENCHMARK(BM_cUnescape, iters) {
 158   while (iters--) {
 159     cUnescapedString = cUnescape<fbstring>(cbmEscapedString);
 160     doNotOptimizeAway(cUnescapedString.size());
 161   }
 162 }
 163
 164 BENCHMARK(BM_uriEscape, iters) {
 165   while (iters--) {
 166     uriEscapedString = uriEscape<fbstring>(uribmString);
 167     doNotOptimizeAway(uriEscapedString.size());
 168   }
 169 }
 170
 171 BENCHMARK(BM_uriUnescape, iters) {
 172   while (iters--) {
 173     uriUnescapedString = uriUnescape<fbstring>(uribmEscapedString);
 174     doNotOptimizeAway(uriUnescapedString.size());
 175   }
 176 }
 177
 178 } // namespace
 179
 180 //////////////////////////////////////////////////////////////////////
 181
 182 BENCHMARK(splitOnSingleChar, iters) {
 183   static const std::string line = "one:two:three:four";
 184   for (size_t i = 0; i < iters << 4; ++i) {
 185     std::vector<StringPiece> pieces;
 186     folly::split(':', line, pieces);
 187   }
 188 }
 189
 190 BENCHMARK(splitOnSingleCharFixed, iters) {
 191   static const std::string line = "one:two:three:four";
 192   for (size_t i = 0; i < iters << 4; ++i) {
 193     StringPiece a, b, c, d;
 194     folly::split(':', line, a, b, c, d);
 195   }
 196 }
 197
 198 BENCHMARK(splitOnSingleCharFixedAllowExtra, iters) {
 199   static const std::string line = "one:two:three:four";
 200   for (size_t i = 0; i < iters << 4; ++i) {
 201     StringPiece a, b, c, d;
 202     folly::split<false>(':', line, a, b, c, d);
 203   }
 204 }
 205
 206 BENCHMARK(splitStr, iters) {
 207   static const std::string line = "one-*-two-*-three-*-four";
 208   for (size_t i = 0; i < iters << 4; ++i) {
 209     std::vector<StringPiece> pieces;
 210     folly::split("-*-", line, pieces);
 211   }
 212 }
 213
 214 BENCHMARK(splitStrFixed, iters) {
 215   static const std::string line = "one-*-two-*-three-*-four";
 216   for (size_t i = 0; i < iters << 4; ++i) {
 217     StringPiece a, b, c, d;
 218     folly::split("-*-", line, a, b, c, d);
 219   }
 220 }
 221
 222 BENCHMARK(boost_splitOnSingleChar, iters) {
 223   static const std::string line = "one:two:three:four";
 224   bool (*pred)(char) = [](char c) -> bool { return c == ':'; };
 225   for (size_t i = 0; i < iters << 4; ++i) {
 226     std::vector<boost::iterator_range<std::string::const_iterator>> pieces;
 227     boost::split(pieces, line, pred);
 228   }
 229 }
 230
 231 BENCHMARK(joinCharStr, iters) {
 232   static const std::vector<std::string> input = {
 233       "one", "two", "three", "four", "five", "six", "seven"};
 234   for (size_t i = 0; i < iters << 4; ++i) {
 235     std::string output;
 236     folly::join(':', input, output);
 237   }
 238 }
 239
 240 BENCHMARK(joinStrStr, iters) {
 241   static const std::vector<std::string> input = {
 242       "one", "two", "three", "four", "five", "six", "seven"};
 243   for (size_t i = 0; i < iters << 4; ++i) {
 244     std::string output;
 245     folly::join(":", input, output);
 246   }
 247 }
 248
 249 BENCHMARK(joinInt, iters) {
 250   static const auto input = {123, 456, 78910, 1112, 1314, 151, 61718};
 251   for (size_t i = 0; i < iters << 4; ++i) {
 252     std::string output;
 253     folly::join(":", input, output);
 254   }
 255 }
 256
 257 int main(int argc, char** argv) {
 258   gflags::ParseCommandLineFlags(&argc, &argv, true);
 259   initBenchmark();
 260   folly::runBenchmarks();
 261   return 0;
 262 }
 263
 264 /*
 265 Results on x86_64:
 266 ============================================================================
 267 folly/test/StringBenchmark.cpp                  relative  time/iter  iters/s
 268 ============================================================================
 269 libc_tolower                                               773.30ns    1.29M
 270 folly_toLowerAscii                                          65.04ns   15.38M
 271 stringPrintfOutputSize(1)                                  224.67ns    4.45M
 272 stringPrintfOutputSize(4)                                  231.53ns    4.32M
 273 stringPrintfOutputSize(16)                                 286.54ns    3.49M
 274 stringPrintfOutputSize(64)                                 305.47ns    3.27M
 275 stringPrintfOutputSize(256)                                  1.48us  674.45K
 276 stringPrintfOutputSize(1024)                                 5.89us  169.72K
 277 stringPrintfAppendfBenchmark                                34.43ms    29.04
 278 BM_cEscape                                                 461.51us    2.17K
 279 BM_cUnescape                                               328.19us    3.05K
 280 BM_uriEscape                                                 4.36us  229.25K
 281 BM_uriUnescape                                               2.22us  450.64K
 282 splitOnSingleChar                                            1.46us  687.21K
 283 splitOnSingleCharFixed                                     133.02ns    7.52M
 284 splitOnSingleCharFixedAllowExtra                            74.35ns   13.45M
 285 splitStr                                                     2.36us  424.00K
 286 splitStrFixed                                              282.38ns    3.54M
 287 boost_splitOnSingleChar                                      2.83us  353.12K
 288 joinCharStr                                                  2.65us  376.93K
 289 joinStrStr                                                   2.64us  378.09K
 290 joinInt                                                      3.89us  257.37K
 291 ============================================================================
 292 */