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