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/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);
84 string generateString(int len) {
85 std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
88 ret.push_back(validChar(rnd));
93 void initDelims(int len) {
96 string s(len - 1, '\0'); // find_first_of won't finish until last char
100 for (size_t i = 0; i < ffoDelimSize; ++i) {
101 // most delimiter sets are pretty small, but occasionally there could
103 auto n = rnd() % 8 + 1;
107 auto s = generateString(n);
109 // ~half of tests will find a hit
110 s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
112 ffoDelim.push_back(s);
116 } // anonymous namespace
118 BENCHMARK(FindSingleCharMemchr, n) {
119 StringPiece haystack(str);
120 FOR_EACH_RANGE (i, 0, n) {
121 doNotOptimizeAway(haystack.find('b'));
122 char x = haystack[0];
123 doNotOptimizeAway(&x);
127 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
129 StringPiece haystack(str);
130 folly::StringPiece needle(&c, &c + 1);
131 FOR_EACH_RANGE (i, 0, n) {
132 doNotOptimizeAway(haystack.find(needle));
133 char x = haystack[0];
134 doNotOptimizeAway(&x);
138 BENCHMARK_DRAW_LINE();
140 template <class Func>
141 void countHits(Func func, size_t n) {
142 StringPiece needles = "\r\n\1";
143 FOR_EACH_RANGE (i, 0, n) {
145 for (StringPiece left = file;
146 (p = func(left, needles)) != StringPiece::npos;
147 left.advance(p + 1)) {
150 doNotOptimizeAway(c);
154 template <class Func>
155 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
156 FOR_EACH_RANGE (i, 0, n) {
157 const StringPiece haystack = vstrp[i % kVstrSize];
158 doNotOptimizeAway(func(haystack, needles));
159 char x = haystack[0];
160 doNotOptimizeAway(&x);
164 const string delims1 = "b";
166 BENCHMARK(FindFirstOf1NeedlesBase, n) {
167 findFirstOfRange(delims1, detail::qfind_first_byte_of, n);
170 BENCHMARK_RELATIVE(FindFirstOf1NeedlesNoSSE, n) {
171 findFirstOfRange(delims1, detail::qfind_first_byte_of_nosse, n);
174 BENCHMARK_RELATIVE(FindFirstOf1NeedlesStd, n) {
175 findFirstOfRange(delims1, detail::qfind_first_byte_of_std, n);
178 BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
179 findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
182 BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
183 findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
186 BENCHMARK_DRAW_LINE();
188 const string delims2 = "bc";
190 BENCHMARK(FindFirstOf2NeedlesBase, n) {
191 findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
194 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
195 findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
198 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
199 findFirstOfRange(delims2, detail::qfind_first_byte_of_std, n);
202 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
203 findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
206 BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
207 findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
210 BENCHMARK_DRAW_LINE();
212 const string delims4 = "bcde";
214 BENCHMARK(FindFirstOf4NeedlesBase, n) {
215 findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
218 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
219 findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
222 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
223 findFirstOfRange(delims4, detail::qfind_first_byte_of_std, n);
226 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
227 findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
230 BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
231 findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
234 BENCHMARK_DRAW_LINE();
236 const string delims8 = "0123456b";
238 BENCHMARK(FindFirstOf8NeedlesBase, n) {
239 findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
242 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
243 findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
246 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
247 findFirstOfRange(delims8, detail::qfind_first_byte_of_std, n);
250 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
251 findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
254 BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
255 findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
258 BENCHMARK_DRAW_LINE();
260 const string delims16 = "0123456789bcdefg";
262 BENCHMARK(FindFirstOf16NeedlesBase, n) {
263 findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
266 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
267 findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
270 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
271 findFirstOfRange(delims16, detail::qfind_first_byte_of_std, n);
274 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
275 findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
278 BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
279 findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
282 BENCHMARK_DRAW_LINE();
284 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
286 BENCHMARK(FindFirstOf32NeedlesBase, n) {
287 findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
290 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
291 findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
294 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
295 findFirstOfRange(delims32, detail::qfind_first_byte_of_std, n);
298 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
299 findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
302 BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
303 findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
306 BENCHMARK_DRAW_LINE();
308 const string delims64 = "!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}) {