folly/test/RangeFindBenchmark.cpp

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