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