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>
24 #include <folly/Benchmark.h>
25 #include <folly/container/Foreach.h>
27 using namespace folly;
33 constexpr int kVstrSize = 16;
34 std::vector<std::string> vstr;
35 std::vector<StringPiece> vstrp;
38 void initStr(int len) {
43 cout << "string length " << len << ':' << endl;
48 // create 16 copies of str, each with a different 16byte alignment.
49 // Useful because some implementations of find_first_of have different
50 // behaviors based on byte alignment.
51 for (int i = 0; i < kVstrSize; ++i) {
55 // some find_first_of implementations have special (page-safe) logic
56 // for handling the end of a string. Flex that logic only sometimes.
60 StringPiece sp(vstr.back());
68 const size_t ffoDelimSize = 128;
69 vector<string> ffoDelim;
71 void initFile(int len) {
72 std::uniform_int_distribution<uint32_t> validChar(1, 64);
75 char ch = validChar(rnd);
83 string generateString(int len) {
84 std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
87 ret.push_back(validChar(rnd));
92 void initDelims(int len) {
95 string s(len - 1, '\0'); // find_first_of won't finish until last char
99 for (size_t i = 0; i < ffoDelimSize; ++i) {
100 // most delimiter sets are pretty small, but occasionally there could
102 auto n = rnd() % 8 + 1;
106 auto s = generateString(n);
108 // ~half of tests will find a hit
109 s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
111 ffoDelim.push_back(s);
117 BENCHMARK(FindSingleCharMemchr, n) {
118 StringPiece haystack(str);
119 FOR_EACH_RANGE (i, 0, n) {
120 doNotOptimizeAway(haystack.find('b'));
121 char x = haystack[0];
122 doNotOptimizeAway(&x);
126 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
128 StringPiece haystack(str);
129 folly::StringPiece needle(&c, &c + 1);
130 FOR_EACH_RANGE (i, 0, n) {
131 doNotOptimizeAway(haystack.find(needle));
132 char x = haystack[0];
133 doNotOptimizeAway(&x);
137 BENCHMARK_DRAW_LINE();
139 template <class Func>
140 void countHits(Func func, size_t n) {
141 StringPiece needles = "\r\n\1";
142 FOR_EACH_RANGE (i, 0, n) {
144 for (StringPiece left = file;
145 (p = func(left, needles)) != StringPiece::npos;
146 left.advance(p + 1)) {
149 doNotOptimizeAway(c);
153 template <class Func>
154 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
155 FOR_EACH_RANGE (i, 0, n) {
156 const StringPiece haystack = vstrp[i % kVstrSize];
157 doNotOptimizeAway(func(haystack, needles));
158 char x = haystack[0];
159 doNotOptimizeAway(&x);
163 const string delims1 = "b";
165 BENCHMARK(FindFirstOf1NeedlesBase, n) {
166 findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
169 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
170 findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
173 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
174 findFirstOfRange(delims1, detail::qfind_first_byte_of_std, n);
177 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
178 findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
181 BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
182 findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
185 BENCHMARK_DRAW_LINE();
187 const string delims2 = "bc";
189 BENCHMARK(FindFirstOf2NeedlesBase, n) {
190 findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
193 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
194 findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
197 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
198 findFirstOfRange(delims2, detail::qfind_first_byte_of_std, n);
201 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
202 findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
205 BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
206 findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
209 BENCHMARK_DRAW_LINE();
211 const string delims4 = "bcde";
213 BENCHMARK(FindFirstOf4NeedlesBase, n) {
214 findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
217 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
218 findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
221 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
222 findFirstOfRange(delims4, detail::qfind_first_byte_of_std, n);
225 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
226 findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
229 BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
230 findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
233 BENCHMARK_DRAW_LINE();
235 const string delims8 = "0123456b";
237 BENCHMARK(FindFirstOf8NeedlesBase, n) {
238 findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
241 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
242 findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
245 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
246 findFirstOfRange(delims8, detail::qfind_first_byte_of_std, n);
249 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
250 findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
253 BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
254 findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
257 BENCHMARK_DRAW_LINE();
259 const string delims16 = "0123456789bcdefg";
261 BENCHMARK(FindFirstOf16NeedlesBase, n) {
262 findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
265 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
266 findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
269 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
270 findFirstOfRange(delims16, detail::qfind_first_byte_of_std, n);
273 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
274 findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
277 BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
278 findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
281 BENCHMARK_DRAW_LINE();
283 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
285 BENCHMARK(FindFirstOf32NeedlesBase, n) {
286 findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
289 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
290 findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
293 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
294 findFirstOfRange(delims32, detail::qfind_first_byte_of_std, n);
297 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
298 findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
301 BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
302 findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
305 BENCHMARK_DRAW_LINE();
307 const string delims64 =
308 "!bcdefghijklmnopqrstuvwxyz_"
309 "ABCDEFGHIJKLMNOPQRSTUVWXYZ-0123456789$";
311 BENCHMARK(FindFirstOf64NeedlesBase, n) {
312 findFirstOfRange(delims64, detail::qfind_first_byte_of, n);
315 BENCHMARK_RELATIVE(FindFirstOf64NeedlesNoSSE, n) {
316 findFirstOfRange(delims64, detail::qfind_first_byte_of_nosse, n);
319 BENCHMARK_RELATIVE(FindFirstOf64NeedlesStd, n) {
320 findFirstOfRange(delims64, detail::qfind_first_byte_of_std, n);
323 BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
324 findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
327 BENCHMARK_RELATIVE(FindFirstOf64NeedlesBitSet, n) {
328 findFirstOfRange(delims64, detail::qfind_first_byte_of_bitset, n);
331 BENCHMARK_DRAW_LINE();
333 template <class Func>
334 void findFirstOfRandom(Func func, size_t iters) {
335 for (size_t i = 0; i < iters; ++i) {
336 auto test = i % ffoDelim.size();
337 auto p = func(ffoTestString, ffoDelim[test]);
338 doNotOptimizeAway(p);
342 BENCHMARK(FindFirstOfRandomBase, n) {
343 findFirstOfRandom(detail::qfind_first_byte_of, n);
346 BENCHMARK_RELATIVE(FindFirstOfRandomNoSSE, n) {
347 findFirstOfRandom(detail::qfind_first_byte_of_nosse, n);
350 BENCHMARK_RELATIVE(FindFirstOfRandomStd, n) {
351 findFirstOfRandom(detail::qfind_first_byte_of_std, n);
354 BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
355 findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
358 BENCHMARK_RELATIVE(FindFirstOfRandomBitSet, n) {
359 findFirstOfRandom(detail::qfind_first_byte_of_bitset, n);
362 BENCHMARK_DRAW_LINE();
364 BENCHMARK(CountDelimsBase, n) {
365 countHits(detail::qfind_first_byte_of, n);
368 BENCHMARK_RELATIVE(CountDelimsNoSSE, n) {
369 countHits(detail::qfind_first_byte_of_nosse, n);
372 BENCHMARK_RELATIVE(CountDelimsStd, n) {
373 countHits(detail::qfind_first_byte_of_std, n);
376 BENCHMARK_RELATIVE(CountDelimsByteSet, n) {
377 countHits(detail::qfind_first_byte_of_byteset, n);
380 BENCHMARK_RELATIVE(CountDelimsBitSet, n) {
381 countHits(detail::qfind_first_byte_of_bitset, n);
384 BENCHMARK_DRAW_LINE();
386 BENCHMARK(FindFirstOfOffsetRange, n) {
387 StringPiece haystack(str);
388 folly::StringPiece needles("bc");
389 DCHECK_EQ(haystack.size() - 1, haystack.find_first_of(needles, 1)); // works!
390 FOR_EACH_RANGE (i, 0, n) {
391 size_t pos = i % 2; // not a constant to prevent optimization
392 doNotOptimizeAway(haystack.find_first_of(needles, pos));
393 char x = haystack[0];
394 doNotOptimizeAway(&x);
398 BENCHMARK_DRAW_LINE();
400 int main(int argc, char** argv) {
401 gflags::ParseCommandLineFlags(&argc, &argv, true);
403 for (int len : {1, 8, 10, 16, 32, 64, 128, 256, 10 * 1024, 1024 * 1024}) {