2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/Range.h>
18 #include <folly/Benchmark.h>
19 #include <folly/Foreach.h>
25 using namespace folly;
31 constexpr int kVstrSize = 16;
32 std::vector<std::string> vstr;
33 std::vector<StringPiece> vstrp;
36 void initStr(int len) {
41 cout << "string length " << len << ':' << endl;
46 // create 16 copies of str, each with a different 16byte alignment.
47 // Useful because some implementations of find_first_of have different
48 // behaviors based on byte alignment.
49 for (int i = 0; i < kVstrSize; ++i) {
53 // some find_first_of implementations have special (page-safe) logic
54 // for handling the end of a string. Flex that logic only sometimes.
58 StringPiece sp(vstr.back());
66 const size_t ffoDelimSize = 128;
67 vector<string> ffoDelim;
69 void initFile(int len) {
70 std::uniform_int_distribution<uint32_t> validChar(1, 64);
73 char ch = validChar(rnd);
82 string generateString(int len) {
83 std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
86 ret.push_back(validChar(rnd));
91 void initDelims(int len) {
94 string s(len - 1, '\0'); // find_first_of won't finish until last char
98 for (size_t i = 0; i < ffoDelimSize; ++i) {
99 // most delimiter sets are pretty small, but occasionally there could
101 auto n = rnd() % 8 + 1;
105 auto s = generateString(n);
107 // ~half of tests will find a hit
108 s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
110 ffoDelim.push_back(s);
114 } // anonymous namespace
116 BENCHMARK(FindSingleCharMemchr, n) {
117 StringPiece haystack(str);
118 FOR_EACH_RANGE (i, 0, n) {
119 doNotOptimizeAway(haystack.find('b'));
120 char x = haystack[0];
121 doNotOptimizeAway(&x);
125 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
127 StringPiece haystack(str);
128 folly::StringPiece needle(&c, &c + 1);
129 FOR_EACH_RANGE (i, 0, n) {
130 doNotOptimizeAway(haystack.find(needle));
131 char x = haystack[0];
132 doNotOptimizeAway(&x);
136 BENCHMARK_DRAW_LINE();
138 template <class Func>
139 void countHits(Func func, size_t n) {
140 StringPiece needles = "\r\n\1";
141 FOR_EACH_RANGE (i, 0, n) {
143 for (StringPiece left = file;
144 (p = func(left, needles)) != StringPiece::npos;
145 left.advance(p + 1)) {
148 doNotOptimizeAway(c);
152 template <class Func>
153 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
154 FOR_EACH_RANGE (i, 0, n) {
155 const StringPiece haystack = vstrp[i % kVstrSize];
156 doNotOptimizeAway(func(haystack, needles));
157 char x = haystack[0];
158 doNotOptimizeAway(&x);
162 const string delims1 = "b";
164 BENCHMARK(FindFirstOf1NeedlesBase, n) {
165 findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
168 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
169 findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
172 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
173 findFirstOfRange(delims1, detail::qfind_first_byte_of_std, n);
176 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
177 findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
180 BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
181 findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
184 BENCHMARK_DRAW_LINE();
186 const string delims2 = "bc";
188 BENCHMARK(FindFirstOf2NeedlesBase, n) {
189 findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
192 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
193 findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
196 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
197 findFirstOfRange(delims2, detail::qfind_first_byte_of_std, n);
200 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
201 findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
204 BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
205 findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
208 BENCHMARK_DRAW_LINE();
210 const string delims4 = "bcde";
212 BENCHMARK(FindFirstOf4NeedlesBase, n) {
213 findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
216 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
217 findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
220 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
221 findFirstOfRange(delims4, detail::qfind_first_byte_of_std, n);
224 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
225 findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
228 BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
229 findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
232 BENCHMARK_DRAW_LINE();
234 const string delims8 = "0123456b";
236 BENCHMARK(FindFirstOf8NeedlesBase, n) {
237 findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
240 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
241 findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
244 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
245 findFirstOfRange(delims8, detail::qfind_first_byte_of_std, n);
248 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
249 findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
252 BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
253 findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
256 BENCHMARK_DRAW_LINE();
258 const string delims16 = "0123456789bcdefg";
260 BENCHMARK(FindFirstOf16NeedlesBase, n) {
261 findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
264 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
265 findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
268 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
269 findFirstOfRange(delims16, detail::qfind_first_byte_of_std, n);
272 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
273 findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
276 BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
277 findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
280 BENCHMARK_DRAW_LINE();
282 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
284 BENCHMARK(FindFirstOf32NeedlesBase, n) {
285 findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
288 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
289 findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
292 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
293 findFirstOfRange(delims32, detail::qfind_first_byte_of_std, n);
296 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
297 findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
300 BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
301 findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
304 BENCHMARK_DRAW_LINE();
306 const string delims64 = "!bcdefghijklmnopqrstuvwxyz_"
307 "ABCDEFGHIJKLMNOPQRSTUVWXYZ-0123456789$";
309 BENCHMARK(FindFirstOf64NeedlesBase, n) {
310 findFirstOfRange(delims64, detail::qfind_first_byte_of, n);
313 BENCHMARK_RELATIVE(FindFirstOf64NeedlesNoSSE, n) {
314 findFirstOfRange(delims64, detail::qfind_first_byte_of_nosse, n);
317 BENCHMARK_RELATIVE(FindFirstOf64NeedlesStd, n) {
318 findFirstOfRange(delims64, detail::qfind_first_byte_of_std, n);
321 BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
322 findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
325 BENCHMARK_RELATIVE(FindFirstOf64NeedlesBitSet, n) {
326 findFirstOfRange(delims64, detail::qfind_first_byte_of_bitset, n);
329 BENCHMARK_DRAW_LINE();
331 template <class Func>
332 void findFirstOfRandom(Func func, size_t iters) {
333 for (size_t i = 0; i < iters; ++i) {
334 auto test = i % ffoDelim.size();
335 auto p = func(ffoTestString, ffoDelim[test]);
336 doNotOptimizeAway(p);
340 BENCHMARK(FindFirstOfRandomBase, n) {
341 findFirstOfRandom(detail::qfind_first_byte_of, n);
344 BENCHMARK_RELATIVE(FindFirstOfRandomNoSSE, n) {
345 findFirstOfRandom(detail::qfind_first_byte_of_nosse, n);
348 BENCHMARK_RELATIVE(FindFirstOfRandomStd, n) {
349 findFirstOfRandom(detail::qfind_first_byte_of_std, n);
352 BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
353 findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
356 BENCHMARK_RELATIVE(FindFirstOfRandomBitSet, n) {
357 findFirstOfRandom(detail::qfind_first_byte_of_bitset, n);
360 BENCHMARK_DRAW_LINE();
362 BENCHMARK(CountDelimsBase, n) {
363 countHits(detail::qfind_first_byte_of, n);
366 BENCHMARK_RELATIVE(CountDelimsNoSSE, n) {
367 countHits(detail::qfind_first_byte_of_nosse, n);
370 BENCHMARK_RELATIVE(CountDelimsStd, n) {
371 countHits(detail::qfind_first_byte_of_std, n);
374 BENCHMARK_RELATIVE(CountDelimsByteSet, n) {
375 countHits(detail::qfind_first_byte_of_byteset, n);
378 BENCHMARK_RELATIVE(CountDelimsBitSet, n) {
379 countHits(detail::qfind_first_byte_of_bitset, n);
382 BENCHMARK_DRAW_LINE();
384 BENCHMARK(FindFirstOfOffsetRange, n) {
385 StringPiece haystack(str);
386 folly::StringPiece needles("bc");
387 DCHECK_EQ(haystack.size() - 1, haystack.find_first_of(needles, 1)); // works!
388 FOR_EACH_RANGE (i, 0, n) {
389 size_t pos = i % 2; // not a constant to prevent optimization
390 doNotOptimizeAway(haystack.find_first_of(needles, pos));
391 char x = haystack[0];
392 doNotOptimizeAway(&x);
396 BENCHMARK_DRAW_LINE();
398 int main(int argc, char** argv) {
399 gflags::ParseCommandLineFlags(&argc, &argv, true);
401 for (int len : {1, 8, 10, 16, 32, 64, 128, 256, 10*1024, 1024*1024}) {