folly/test/RangeFindBenchmark.cpp

   1 /*
   2  * Copyright 2017 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/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
  84 string generateString(int len) {
  85   std::uniform_int_distribution<uint32_t> validChar(1, 255);  // no null-char
  86   string ret;
  87   while (len--) {
  88     ret.push_back(validChar(rnd));
  89   }
  90   return ret;
  91 }
  92
  93 void initDelims(int len) {
  94   ffoDelim.clear();
  95
  96   string s(len - 1, '\0');  // find_first_of won't finish until last char
  97   s.push_back('a');
  98   ffoTestString = s;
  99
 100   for (size_t i = 0; i < ffoDelimSize; ++i) {
 101     // most delimiter sets are pretty small, but occasionally there could
 102     // be a big one.
 103     auto n = rnd() % 8 + 1;
 104     if (n == 8) {
 105       n = 32;
 106     }
 107     auto s = generateString(n);
 108     if (rnd() % 2) {
 109       // ~half of tests will find a hit
 110       s[rnd() % s.size()] = 'a';  // yes, this could mean 'a' is a duplicate
 111     }
 112     ffoDelim.push_back(s);
 113   }
 114 }
 115
 116 }  // anonymous namespace
 117
 118 BENCHMARK(FindSingleCharMemchr, n) {
 119   StringPiece haystack(str);
 120   FOR_EACH_RANGE (i, 0, n) {
 121     doNotOptimizeAway(haystack.find('b'));
 122     char x = haystack[0];
 123     doNotOptimizeAway(&x);
 124   }
 125 }
 126
 127 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
 128   const char c = 'b';
 129   StringPiece haystack(str);
 130   folly::StringPiece needle(&c, &c + 1);
 131   FOR_EACH_RANGE (i, 0, n) {
 132     doNotOptimizeAway(haystack.find(needle));
 133     char x = haystack[0];
 134     doNotOptimizeAway(&x);
 135   }
 136 }
 137
 138 BENCHMARK_DRAW_LINE();
 139
 140 template <class Func>
 141 void countHits(Func func, size_t n) {
 142   StringPiece needles = "\r\n\1";
 143   FOR_EACH_RANGE (i, 0, n) {
 144     size_t p, c = 0;
 145     for (StringPiece left = file;
 146          (p = func(left, needles)) != StringPiece::npos;
 147          left.advance(p + 1)) {
 148       ++c;
 149     }
 150     doNotOptimizeAway(c);
 151   }
 152 }
 153
 154 template <class Func>
 155 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
 156   FOR_EACH_RANGE (i, 0, n) {
 157     const StringPiece haystack = vstrp[i % kVstrSize];
 158     doNotOptimizeAway(func(haystack, needles));
 159     char x = haystack[0];
 160     doNotOptimizeAway(&x);
 161   }
 162 }
 163
 164 const string delims1 = "b";
 165
 166 BENCHMARK(FindFirstOf1NeedlesBase, n) {
 167   findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
 168 }
 169
 170 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
 171   findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
 172 }
 173
 174 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
 175   findFirstOfRange(delims1, detail::qfind_first_byte_of_std, n);
 176 }
 177
 178 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
 179   findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
 180 }
 181
 182 BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
 183   findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
 184 }
 185
 186 BENCHMARK_DRAW_LINE();
 187
 188 const string delims2 = "bc";
 189
 190 BENCHMARK(FindFirstOf2NeedlesBase, n) {
 191   findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
 192 }
 193
 194 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
 195   findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
 196 }
 197
 198 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
 199   findFirstOfRange(delims2, detail::qfind_first_byte_of_std, n);
 200 }
 201
 202 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
 203   findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
 204 }
 205
 206 BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
 207   findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
 208 }
 209
 210 BENCHMARK_DRAW_LINE();
 211
 212 const string delims4 = "bcde";
 213
 214 BENCHMARK(FindFirstOf4NeedlesBase, n) {
 215   findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
 216 }
 217
 218 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
 219   findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
 220 }
 221
 222 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
 223   findFirstOfRange(delims4, detail::qfind_first_byte_of_std, n);
 224 }
 225
 226 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
 227   findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
 228 }
 229
 230 BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
 231   findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
 232 }
 233
 234 BENCHMARK_DRAW_LINE();
 235
 236 const string delims8 = "0123456b";
 237
 238 BENCHMARK(FindFirstOf8NeedlesBase, n) {
 239   findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
 240 }
 241
 242 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
 243   findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
 244 }
 245
 246 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
 247   findFirstOfRange(delims8, detail::qfind_first_byte_of_std, n);
 248 }
 249
 250 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
 251   findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
 252 }
 253
 254 BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
 255   findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
 256 }
 257
 258 BENCHMARK_DRAW_LINE();
 259
 260 const string delims16 = "0123456789bcdefg";
 261
 262 BENCHMARK(FindFirstOf16NeedlesBase, n) {
 263   findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
 264 }
 265
 266 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
 267   findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
 268 }
 269
 270 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
 271   findFirstOfRange(delims16, detail::qfind_first_byte_of_std, n);
 272 }
 273
 274 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
 275   findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
 276 }
 277
 278 BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
 279   findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
 280 }
 281
 282 BENCHMARK_DRAW_LINE();
 283
 284 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
 285
 286 BENCHMARK(FindFirstOf32NeedlesBase, n) {
 287   findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
 288 }
 289
 290 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
 291   findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
 292 }
 293
 294 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
 295   findFirstOfRange(delims32, detail::qfind_first_byte_of_std, n);
 296 }
 297
 298 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
 299   findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
 300 }
 301
 302 BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
 303   findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
 304 }
 305
 306 BENCHMARK_DRAW_LINE();
 307
 308 const string delims64 = "!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 }