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