folly/test/RangeFindBenchmark.cpp

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