2 * Copyright 2015 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 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);
30 size_t qfind_first_byte_of_nosse(const StringPiece haystack,
31 const StringPiece needles);
34 using namespace folly;
40 constexpr int kVstrSize = 16;
41 std::vector<std::string> vstr;
42 std::vector<StringPiece> vstrp;
45 void initStr(int len) {
46 cout << "string length " << len << ':' << endl;
52 // create 16 copies of str, each with a different 16byte alignment.
53 // Useful because some implementations of find_first_of have different
54 // behaviors based on byte alignment.
55 for (int i = 0; i < kVstrSize; ++i) {
59 // some find_first_of implementations have special (page-safe) logic
60 // for handling the end of a string. Flex that logic only sometimes.
64 StringPiece sp(vstr.back());
72 const size_t ffoDelimSize = 128;
73 vector<string> ffoDelim;
75 void initFile(int len) {
76 std::uniform_int_distribution<uint32_t> validChar(1, 64);
79 char ch = validChar(rnd);
88 string generateString(int len) {
89 std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
92 ret.push_back(validChar(rnd));
97 void initDelims(int len) {
100 string s(len - 1, '\0'); // find_first_of won't finish until last char
104 for (size_t i = 0; i < ffoDelimSize; ++i) {
105 // most delimiter sets are pretty small, but occasionally there could
107 auto n = rnd() % 8 + 1;
111 auto s = generateString(n);
113 // ~half of tests will find a hit
114 s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
116 ffoDelim.push_back(s);
120 } // anonymous namespace
122 BENCHMARK(FindSingleCharMemchr, n) {
123 StringPiece haystack(str);
124 FOR_EACH_RANGE (i, 0, n) {
125 doNotOptimizeAway(haystack.find('b'));
126 char x = haystack[0];
127 doNotOptimizeAway(&x);
131 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
133 StringPiece haystack(str);
134 folly::StringPiece needle(&c, &c + 1);
135 FOR_EACH_RANGE (i, 0, n) {
136 doNotOptimizeAway(haystack.find(needle));
137 char x = haystack[0];
138 doNotOptimizeAway(&x);
142 BENCHMARK_DRAW_LINE();
144 // it's useful to compare our custom implementations vs. the standard library
145 inline size_t qfind_first_byte_of_std(const StringPiece haystack,
146 const StringPiece needles) {
147 return qfind_first_of(haystack, needles, asciiCaseSensitive);
150 template <class Func>
151 void countHits(Func func, size_t n) {
152 StringPiece needles = "\r\n\1";
153 FOR_EACH_RANGE (i, 0, n) {
155 for (StringPiece left = file;
156 (p = func(left, needles)) != StringPiece::npos;
157 left.advance(p + 1)) {
160 doNotOptimizeAway(n);
164 template <class Func>
165 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
166 FOR_EACH_RANGE (i, 0, n) {
167 const StringPiece haystack = vstr[i % kVstrSize];
168 doNotOptimizeAway(func(haystack, needles));
169 char x = haystack[0];
170 doNotOptimizeAway(&x);
174 const string delims1 = "b";
176 BENCHMARK(FindFirstOf1NeedlesBase, n) {
177 findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
180 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
181 findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
184 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
185 findFirstOfRange(delims1, qfind_first_byte_of_std, n);
188 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
189 findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
192 BENCHMARK_DRAW_LINE();
194 const string delims2 = "bc";
196 BENCHMARK(FindFirstOf2NeedlesBase, n) {
197 findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
200 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
201 findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
204 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
205 findFirstOfRange(delims2, qfind_first_byte_of_std, n);
208 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
209 findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
212 BENCHMARK_DRAW_LINE();
214 const string delims4 = "bcde";
216 BENCHMARK(FindFirstOf4NeedlesBase, n) {
217 findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
220 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
221 findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
224 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
225 findFirstOfRange(delims4, qfind_first_byte_of_std, n);
228 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
229 findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, 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, qfind_first_byte_of_std, n);
248 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
249 findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
252 BENCHMARK_DRAW_LINE();
254 const string delims16 = "0123456789bcdefg";
256 BENCHMARK(FindFirstOf16NeedlesBase, n) {
257 findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
260 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
261 findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
264 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
265 findFirstOfRange(delims16, qfind_first_byte_of_std, n);
268 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
269 findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
272 BENCHMARK_DRAW_LINE();
274 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
276 BENCHMARK(FindFirstOf32NeedlesBase, n) {
277 findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
280 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
281 findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
284 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
285 findFirstOfRange(delims32, qfind_first_byte_of_std, n);
288 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
289 findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
292 BENCHMARK_DRAW_LINE();
294 const string delims64 = "!bcdefghijklmnopqrstuvwxyz_"
295 "ABCDEFGHIJKLMNOPQRSTUVWXYZ-0123456789$";
297 BENCHMARK(FindFirstOf64NeedlesBase, n) {
298 findFirstOfRange(delims64, detail::qfind_first_byte_of, n);
301 BENCHMARK_RELATIVE(FindFirstOf64NeedlesNoSSE, n) {
302 findFirstOfRange(delims64, detail::qfind_first_byte_of_nosse, n);
305 BENCHMARK_RELATIVE(FindFirstOf64NeedlesStd, n) {
306 findFirstOfRange(delims64, qfind_first_byte_of_std, n);
309 BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
310 findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
313 BENCHMARK_DRAW_LINE();
315 template <class Func>
316 void findFirstOfRandom(Func func, size_t iters) {
317 for (size_t i = 0; i < iters; ++i) {
318 auto test = i % ffoDelim.size();
319 auto p = func(ffoTestString, ffoDelim[test]);
320 doNotOptimizeAway(p);
324 BENCHMARK(FindFirstOfRandomBase, n) {
325 findFirstOfRandom(detail::qfind_first_byte_of, n);
328 BENCHMARK_RELATIVE(FindFirstOfRandomNoSSE, n) {
329 findFirstOfRandom(detail::qfind_first_byte_of_nosse, n);
332 BENCHMARK_RELATIVE(FindFirstOfRandomStd, n) {
333 findFirstOfRandom(qfind_first_byte_of_std, n);
336 BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
337 findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
340 BENCHMARK_DRAW_LINE();
342 BENCHMARK(CountDelimsBase, n) {
343 countHits(detail::qfind_first_byte_of, n);
346 BENCHMARK_RELATIVE(CountDelimsNoSSE, n) {
347 countHits(detail::qfind_first_byte_of_nosse, n);
350 BENCHMARK_RELATIVE(CountDelimsStd, n) {
351 countHits(qfind_first_byte_of_std, n);
354 BENCHMARK_RELATIVE(CountDelimsByteSet, n) {
355 countHits(detail::qfind_first_byte_of_byteset, n);
358 BENCHMARK_DRAW_LINE();
360 BENCHMARK(FindFirstOfOffsetRange, n) {
361 StringPiece haystack(str);
362 folly::StringPiece needles("bc");
363 DCHECK_EQ(haystack.size() - 1, haystack.find_first_of(needles, 1)); // works!
364 FOR_EACH_RANGE (i, 0, n) {
365 size_t pos = i % 2; // not a constant to prevent optimization
366 doNotOptimizeAway(haystack.find_first_of(needles, pos));
367 char x = haystack[0];
368 doNotOptimizeAway(&x);
372 BENCHMARK_DRAW_LINE();
374 int main(int argc, char** argv) {
375 gflags::ParseCommandLineFlags(&argc, &argv, true);
377 for (int len : {1, 8, 10, 16, 32, 64, 128, 256, 10*1024, 1024*1024}) {