2 * Copyright 2013 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_memchr(const StringPiece& haystack,
28 const StringPiece& needles);
30 size_t qfind_first_byte_of_byteset(const StringPiece& haystack,
31 const StringPiece& needles);
33 size_t qfind_first_byte_of_nosse(const StringPiece& haystack,
34 const StringPiece& needles);
37 using namespace folly;
43 constexpr int kVstrSize = 16;
44 std::vector<std::string> vstr;
45 std::vector<StringPiece> vstrp;
47 void initStr(int len) {
48 cout << "string length " << len << ':' << endl;
54 // create 16 copies of str, each with a different 16byte alignment.
55 // Useful because some implementations of find_first_of have different
56 // behaviors based on byte alignment.
57 for (int i = 0; i < kVstrSize; ++i) {
61 // some find_first_of implementations have special (page-safe) logic
62 // for handling the end of a string. Flex that logic only sometimes.
66 StringPiece sp(vstr.back());
74 const size_t ffoDelimSize = 128;
75 vector<string> ffoDelim;
77 string generateString(int len) {
78 std::uniform_int_distribution<uint32_t> validChar(1, 255); // no null-char
81 ret.push_back(validChar(rnd));
86 void initDelims(int len) {
89 string s(len - 1, '\0'); // find_first_of won't finish until last char
93 for (int i = 0; i < ffoDelimSize; ++i) {
94 // most delimiter sets are pretty small, but occasionally there could
96 auto n = rnd() % 8 + 1;
100 auto s = generateString(n);
102 // ~half of tests will find a hit
103 s[rnd() % s.size()] = 'a'; // yes, this could mean 'a' is a duplicate
105 ffoDelim.push_back(s);
109 } // anonymous namespace
111 BENCHMARK(FindSingleCharMemchr, n) {
112 StringPiece haystack(str);
113 FOR_EACH_RANGE (i, 0, n) {
114 doNotOptimizeAway(haystack.find('b'));
115 char x = haystack[0];
116 doNotOptimizeAway(&x);
120 BENCHMARK_RELATIVE(FindSingleCharRange, n) {
122 StringPiece haystack(str);
123 folly::StringPiece needle(&c, &c + 1);
124 FOR_EACH_RANGE (i, 0, n) {
125 doNotOptimizeAway(haystack.find(needle));
126 char x = haystack[0];
127 doNotOptimizeAway(&x);
131 BENCHMARK_DRAW_LINE();
133 // it's useful to compare our custom implementations vs. the standard library
134 inline size_t qfind_first_byte_of_std(const StringPiece& haystack,
135 const StringPiece& needles) {
136 return qfind_first_of(haystack, needles, asciiCaseSensitive);
139 template <class Func>
140 void findFirstOfRange(StringPiece needles, Func func, size_t n) {
141 FOR_EACH_RANGE (i, 0, n) {
142 const StringPiece& haystack = vstr[i % kVstrSize];
143 doNotOptimizeAway(func(haystack, needles));
144 char x = haystack[0];
145 doNotOptimizeAway(&x);
149 const string delims2 = "bc";
151 BENCHMARK(FindFirstOf2NeedlesBase, n) {
152 findFirstOfRange(delims2, detail::qfind_first_byte_of, n);
155 BENCHMARK_RELATIVE(FindFirstOf2NeedlesNoSSE, n) {
156 findFirstOfRange(delims2, detail::qfind_first_byte_of_nosse, n);
159 BENCHMARK_RELATIVE(FindFirstOf2NeedlesStd, n) {
160 findFirstOfRange(delims2, qfind_first_byte_of_std, n);
163 BENCHMARK_RELATIVE(FindFirstOf2NeedlesMemchr, n) {
164 findFirstOfRange(delims2, detail::qfind_first_byte_of_memchr, n);
167 BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
168 findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
171 BENCHMARK_DRAW_LINE();
173 const string delims4 = "bcde";
175 BENCHMARK(FindFirstOf4NeedlesBase, n) {
176 findFirstOfRange(delims4, detail::qfind_first_byte_of, n);
179 BENCHMARK_RELATIVE(FindFirstOf4NeedlesNoSSE, n) {
180 findFirstOfRange(delims4, detail::qfind_first_byte_of_nosse, n);
183 BENCHMARK_RELATIVE(FindFirstOf4NeedlesStd, n) {
184 findFirstOfRange(delims4, qfind_first_byte_of_std, n);
187 BENCHMARK_RELATIVE(FindFirstOf4NeedlesMemchr, n) {
188 findFirstOfRange(delims4, detail::qfind_first_byte_of_memchr, n);
191 BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
192 findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
195 BENCHMARK_DRAW_LINE();
197 const string delims8 = "0123456b";
199 BENCHMARK(FindFirstOf8NeedlesBase, n) {
200 findFirstOfRange(delims8, detail::qfind_first_byte_of, n);
203 BENCHMARK_RELATIVE(FindFirstOf8NeedlesNoSSE, n) {
204 findFirstOfRange(delims8, detail::qfind_first_byte_of_nosse, n);
207 BENCHMARK_RELATIVE(FindFirstOf8NeedlesStd, n) {
208 findFirstOfRange(delims8, qfind_first_byte_of_std, n);
211 BENCHMARK_RELATIVE(FindFirstOf8NeedlesMemchr, n) {
212 findFirstOfRange(delims8, detail::qfind_first_byte_of_memchr, n);
215 BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
216 findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
219 BENCHMARK_DRAW_LINE();
221 const string delims16 = "0123456789bcdefg";
223 BENCHMARK(FindFirstOf16NeedlesBase, n) {
224 findFirstOfRange(delims16, detail::qfind_first_byte_of, n);
227 BENCHMARK_RELATIVE(FindFirstOf16NeedlesNoSSE, n) {
228 findFirstOfRange(delims16, detail::qfind_first_byte_of_nosse, n);
231 BENCHMARK_RELATIVE(FindFirstOf16NeedlesStd, n) {
232 findFirstOfRange(delims16, qfind_first_byte_of_std, n);
235 BENCHMARK_RELATIVE(FindFirstOf16NeedlesMemchr, n) {
236 findFirstOfRange(delims16, detail::qfind_first_byte_of_memchr, n);
239 BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
240 findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
243 BENCHMARK_DRAW_LINE();
245 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
247 BENCHMARK(FindFirstOf32NeedlesBase, n) {
248 findFirstOfRange(delims32, detail::qfind_first_byte_of, n);
251 BENCHMARK_RELATIVE(FindFirstOf32NeedlesNoSSE, n) {
252 findFirstOfRange(delims32, detail::qfind_first_byte_of_nosse, n);
255 BENCHMARK_RELATIVE(FindFirstOf32NeedlesStd, n) {
256 findFirstOfRange(delims32, qfind_first_byte_of_std, n);
259 BENCHMARK_RELATIVE(FindFirstOf32NeedlesMemchr, n) {
260 findFirstOfRange(delims32, detail::qfind_first_byte_of_memchr, n);
263 BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
264 findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
267 BENCHMARK_DRAW_LINE();
269 const string delims64 = "!bcdefghijklmnopqrstuvwxyz_"
270 "ABCDEFGHIJKLMNOPQRSTUVWXYZ-0123456789$";
272 BENCHMARK(FindFirstOf64NeedlesBase, n) {
273 findFirstOfRange(delims64, detail::qfind_first_byte_of, n);
276 BENCHMARK_RELATIVE(FindFirstOf64NeedlesNoSSE, n) {
277 findFirstOfRange(delims64, detail::qfind_first_byte_of_nosse, n);
280 BENCHMARK_RELATIVE(FindFirstOf64NeedlesStd, n) {
281 findFirstOfRange(delims64, qfind_first_byte_of_std, n);
284 BENCHMARK_RELATIVE(FindFirstOf64NeedlesMemchr, n) {
285 findFirstOfRange(delims64, detail::qfind_first_byte_of_memchr, n);
288 BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
289 findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
292 BENCHMARK_DRAW_LINE();
294 template <class Func>
295 void findFirstOfRandom(Func func, size_t iters) {
296 for (int i = 0; i < iters; ++i) {
297 auto test = i % ffoDelim.size();
298 auto p = func(ffoTestString, ffoDelim[test]);
299 doNotOptimizeAway(p);
303 BENCHMARK(FindFirstOfRandomBase, n) {
304 findFirstOfRandom(detail::qfind_first_byte_of, n);
307 BENCHMARK_RELATIVE(FindFirstOfRandomNoSSE, n) {
308 findFirstOfRandom(detail::qfind_first_byte_of_nosse, n);
311 BENCHMARK_RELATIVE(FindFirstOfRandomStd, n) {
312 findFirstOfRandom(qfind_first_byte_of_std, n);
315 BENCHMARK_RELATIVE(FindFirstOfRandomMemchr, n) {
316 findFirstOfRandom(detail::qfind_first_byte_of_memchr, n);
319 BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
320 findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
323 BENCHMARK_DRAW_LINE();
325 BENCHMARK(FindFirstOfOffsetRange, n) {
326 StringPiece haystack(str);
327 folly::StringPiece needles("bc");
328 DCHECK_EQ(haystack.size() - 1, haystack.find_first_of(needles, 1)); // works!
329 FOR_EACH_RANGE (i, 0, n) {
330 size_t pos = i % 2; // not a constant to prevent optimization
331 doNotOptimizeAway(haystack.find_first_of(needles, pos));
332 char x = haystack[0];
333 doNotOptimizeAway(&x);
337 BENCHMARK_DRAW_LINE();
339 int main(int argc, char** argv) {
340 google::ParseCommandLineFlags(&argc, &argv, true);
342 for (int len : {1, 8, 10, 16, 32, 64, 128, 256, 10*1024, 1024*1024}) {