folly/test/RangeFindBenchmark.cpp

   1 /*
   2  * Copyright 2012-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/Range.h>
  18
  19 #include <algorithm>
  20 #include <iostream>
  21 #include <random>
  22 #include <string>
  23
  24 #include <folly/Benchmark.h>
  25 #include <folly/container/Foreach.h>
  26
  27 using namespace folly;
  28 using namespace std;
  29
  30 namespace {
  31
  32 std::string str;
  33 constexpr int kVstrSize = 16;
  34 std::vector<std::string> vstr;
  35 std::vector<StringPiece> vstrp;
  36 std::string file;
  37
  38 void initStr(int len) {
  39   str.clear();
  40   vstr.clear();
  41   vstrp.clear();
  42
  43   cout << "string length " << len << ':' << endl;
  44   str.reserve(len + 1);
  45   str.append(len, 'a');
  46   str.append(1, 'b');
  47
  48   // create 16 copies of str, each with a different 16byte alignment.
  49   // Useful because some implementations of find_first_of have different
  50   // behaviors based on byte alignment.
  51   for (int i = 0; i < kVstrSize; ++i) {
  52     string s(i, '$');
  53     s += str;
  54     if (i % 2) {
  55       // some find_first_of implementations have special (page-safe) logic
  56       // for handling the end of a string.  Flex that logic only sometimes.
  57       s += string(32, '$');
  58     }
  59     vstr.push_back(s);
  60     StringPiece sp(vstr.back());
  61     sp.advance(i);
  62     vstrp.push_back(sp);
  63   }
  64 }
  65
  66 std::mt19937 rnd;
  67 string ffoTestString;
  68 const size_t ffoDelimSize = 128;
  69 vector<string> ffoDelim;
  70
  71 void initFile(int len) {
  72   std::uniform_int_distribution<uint32_t> validChar(1, 64);
  73   file.clear();
  74   while (len--) {
  75     char ch = validChar(rnd);
  76     if (ch == '\r') {
  77       ch = '\n';
  78     }
  79     file.push_back(ch);
  80   }
  81 }
  82
  83 string generateString(int len) {
  84   std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
  85   string ret;
  86   while (len--) {
  87     ret.push_back(validChar(rnd));
  88   }
  89   return ret;
  90 }
  91
  92 void initDelims(int len) {
  93   ffoDelim.clear();
  94
  95   string s(len - 1, '\0'); // find_first_of won't finish until last char
  96   s.push_back('a');
  97   ffoTestString = s;
  98
  99   for (size_t i = 0; i < ffoDelimSize; ++i) {
 100     // most delimiter sets are pretty small, but occasionally there could
 101     // be a big one.
 102     auto n = rnd() % 8 + 1;
 103     if (n == 8) {
 104       n = 32;
 105     }
 106     auto s = generateString(n);
 107     if (rnd() % 2) {
 108       // ~half of tests will find a hit
 109       s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
 110     }
 111     ffoDelim.push_back(s);
 112   }
 113 }
 114
 115 } // namespace
 116
 117 BENCHMARK(FindSingleCharMemchr, n) {
 118   StringPiece haystack(str);
 119   FOR_EACH_RANGE (i, 0, n) {
 120     doNotOptimizeAway(haystack.find('b'));
 121     char x = haystack[0];
 122     doNotOptimizeAway(&x);
 123   }
 124 }
 125
 126 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
 127   const char c = 'b';
 128   StringPiece haystack(str);
 129   folly::StringPiece needle(&c, &c + 1);
 130   FOR_EACH_RANGE (i, 0, n) {
 131     doNotOptimizeAway(haystack.find(needle));
 132     char x = haystack[0];
 133     doNotOptimizeAway(&x);
 134   }
 135 }
 136
 137 BENCHMARK_DRAW_LINE();
 138
 139 template <class Func>
 140 void countHits(Func func, size_t n) {
 141   StringPiece needles = "\r\n\1";
 142   FOR_EACH_RANGE (i, 0, n) {
 143     size_t p, c = 0;
 144     for (StringPiece left = file;
 145          (p = func(left, needles)) != StringPiece::npos;
 146          left.advance(p + 1)) {
 147       ++c;
 148     }
 149     doNotOptimizeAway(c);
 150   }
 151 }
 152
 153 template <class Func>
 154 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
 155   FOR_EACH_RANGE (i, 0, n) {
 156     const StringPiece haystack = vstrp[i % kVstrSize];
 157     doNotOptimizeAway(func(haystack, needles));
 158     char x = haystack[0];
 159     doNotOptimizeAway(&x);
 160   }
 161 }
 162
 163 const string delims1 = "b";
 164
 165 BENCHMARK(FindFirstOf1NeedlesBase, n) {
 166   findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
 167 }
 168
 169 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
 170   findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
 171 }
 172
 173 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
 174   findFirstOfRange(delims1, detail::qfind_first_byte_of_std, n);
 175 }
 176
 177 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
 178   findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
 179 }
 180
 181 BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
 182   findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
 183 }
 184
 185 BENCHMARK_DRAW_LINE();
 186
 187 const string delims2 = "bc";
 188
 189 BENCHMARK(FindFirstOf2NeedlesBase, n) {
 190   findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
 191 }
 192
 193 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
 194   findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
 195 }
 196
 197 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
 198   findFirstOfRange(delims2, detail::qfind_first_byte_of_std, n);
 199 }
 200
 201 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
 202   findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
 203 }
 204
 205 BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
 206   findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
 207 }
 208
 209 BENCHMARK_DRAW_LINE();
 210
 211 const string delims4 = "bcde";
 212
 213 BENCHMARK(FindFirstOf4NeedlesBase, n) {
 214   findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
 215 }
 216
 217 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
 218   findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
 219 }
 220
 221 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
 222   findFirstOfRange(delims4, detail::qfind_first_byte_of_std, n);
 223 }
 224
 225 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
 226   findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
 227 }
 228
 229 BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
 230   findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
 231 }
 232
 233 BENCHMARK_DRAW_LINE();
 234
 235 const string delims8 = "0123456b";
 236
 237 BENCHMARK(FindFirstOf8NeedlesBase, n) {
 238   findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
 239 }
 240
 241 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
 242   findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
 243 }
 244
 245 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
 246   findFirstOfRange(delims8, detail::qfind_first_byte_of_std, n);
 247 }
 248
 249 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
 250   findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
 251 }
 252
 253 BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
 254   findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
 255 }
 256
 257 BENCHMARK_DRAW_LINE();
 258
 259 const string delims16 = "0123456789bcdefg";
 260
 261 BENCHMARK(FindFirstOf16NeedlesBase, n) {
 262   findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
 263 }
 264
 265 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
 266   findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
 267 }
 268
 269 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
 270   findFirstOfRange(delims16, detail::qfind_first_byte_of_std, n);
 271 }
 272
 273 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
 274   findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
 275 }
 276
 277 BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
 278   findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
 279 }
 280
 281 BENCHMARK_DRAW_LINE();
 282
 283 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
 284
 285 BENCHMARK(FindFirstOf32NeedlesBase, n) {
 286   findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
 287 }
 288
 289 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
 290   findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
 291 }
 292
 293 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
 294   findFirstOfRange(delims32, detail::qfind_first_byte_of_std, n);
 295 }
 296
 297 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
 298   findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
 299 }
 300
 301 BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
 302   findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
 303 }
 304
 305 BENCHMARK_DRAW_LINE();
 306
 307 const string delims64 =
 308     "!bcdefghijklmnopqrstuvwxyz_"
 309     "ABCDEFGHIJKLMNOPQRSTUVWXYZ-0123456789$";
 310
 311 BENCHMARK(FindFirstOf64NeedlesBase, n) {
 312   findFirstOfRange(delims64, detail::qfind_first_byte_of, n);
 313 }
 314
 315 BENCHMARK_RELATIVE(FindFirstOf64NeedlesNoSSE, n) {
 316   findFirstOfRange(delims64, detail::qfind_first_byte_of_nosse, n);
 317 }
 318
 319 BENCHMARK_RELATIVE(FindFirstOf64NeedlesStd, n) {
 320   findFirstOfRange(delims64, detail::qfind_first_byte_of_std, n);
 321 }
 322
 323 BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
 324   findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
 325 }
 326
 327 BENCHMARK_RELATIVE(FindFirstOf64NeedlesBitSet, n) {
 328   findFirstOfRange(delims64, detail::qfind_first_byte_of_bitset, n);
 329 }
 330
 331 BENCHMARK_DRAW_LINE();
 332
 333 template <class Func>
 334 void findFirstOfRandom(Func func, size_t iters) {
 335   for (size_t i = 0; i < iters; ++i) {
 336     auto test = i % ffoDelim.size();
 337     auto p = func(ffoTestString, ffoDelim[test]);
 338     doNotOptimizeAway(p);
 339   }
 340 }
 341
 342 BENCHMARK(FindFirstOfRandomBase, n) {
 343   findFirstOfRandom(detail::qfind_first_byte_of, n);
 344 }
 345
 346 BENCHMARK_RELATIVE(FindFirstOfRandomNoSSE, n) {
 347   findFirstOfRandom(detail::qfind_first_byte_of_nosse, n);
 348 }
 349
 350 BENCHMARK_RELATIVE(FindFirstOfRandomStd, n) {
 351   findFirstOfRandom(detail::qfind_first_byte_of_std, n);
 352 }
 353
 354 BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
 355   findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
 356 }
 357
 358 BENCHMARK_RELATIVE(FindFirstOfRandomBitSet, n) {
 359   findFirstOfRandom(detail::qfind_first_byte_of_bitset, n);
 360 }
 361
 362 BENCHMARK_DRAW_LINE();
 363
 364 BENCHMARK(CountDelimsBase, n) {
 365   countHits(detail::qfind_first_byte_of, n);
 366 }
 367
 368 BENCHMARK_RELATIVE(CountDelimsNoSSE, n) {
 369   countHits(detail::qfind_first_byte_of_nosse, n);
 370 }
 371
 372 BENCHMARK_RELATIVE(CountDelimsStd, n) {
 373   countHits(detail::qfind_first_byte_of_std, n);
 374 }
 375
 376 BENCHMARK_RELATIVE(CountDelimsByteSet, n) {
 377   countHits(detail::qfind_first_byte_of_byteset, n);
 378 }
 379
 380 BENCHMARK_RELATIVE(CountDelimsBitSet, n) {
 381   countHits(detail::qfind_first_byte_of_bitset, n);
 382 }
 383
 384 BENCHMARK_DRAW_LINE();
 385
 386 BENCHMARK(FindFirstOfOffsetRange, n) {
 387   StringPiece haystack(str);
 388   folly::StringPiece needles("bc");
 389   DCHECK_EQ(haystack.size() - 1, haystack.find_first_of(needles, 1)); // works!
 390   FOR_EACH_RANGE (i, 0, n) {
 391     size_t pos = i % 2; // not a constant to prevent optimization
 392     doNotOptimizeAway(haystack.find_first_of(needles, pos));
 393     char x = haystack[0];
 394     doNotOptimizeAway(&x);
 395   }
 396 }
 397
 398 BENCHMARK_DRAW_LINE();
 399
 400 int main(int argc, char** argv) {
 401   gflags::ParseCommandLineFlags(&argc, &argv, true);
 402
 403   for (int len : {1, 8, 10, 16, 32, 64, 128, 256, 10 * 1024, 1024 * 1024}) {
 404     initStr(len);
 405     initDelims(len);
 406     initFile(len);
 407     runBenchmarks();
 408   }
 409   return 0;
 410 }