2 * Copyright 2016 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/Conv.h>
19 #include <boost/lexical_cast.hpp>
21 #include <folly/Benchmark.h>
22 #include <folly/Foreach.h>
29 using namespace folly;
31 ////////////////////////////////////////////////////////////////////////////////
32 // Benchmarks for ASCII to int conversion
33 ////////////////////////////////////////////////////////////////////////////////
34 // @author: Rajat Goel (rajat)
36 static int64_t handwrittenAtoi(const char* start, const char* end) {
42 throw std::runtime_error("empty string");
45 while (start < end && isspace(*start)) {
58 while (start < end && *start >= '0' && *start <= '9') {
59 auto const newRetVal = retVal * 10 + (*start++ - '0');
60 if (newRetVal < retVal) {
61 throw std::runtime_error("overflow");
67 throw std::runtime_error("extra chars at the end");
70 return positive ? retVal : -retVal;
73 static StringPiece pc1 = "1234567890123456789";
75 void handwrittenAtoiMeasure(unsigned int n, unsigned int digits) {
76 auto p = pc1.subpiece(pc1.size() - digits, digits);
77 FOR_EACH_RANGE(i, 0, n) {
78 doNotOptimizeAway(handwrittenAtoi(p.begin(), p.end()));
82 void follyAtoiMeasure(unsigned int n, unsigned int digits) {
83 auto p = pc1.subpiece(pc1.size() - digits, digits);
84 FOR_EACH_RANGE(i, 0, n) {
85 doNotOptimizeAway(folly::to<int64_t>(p.begin(), p.end()));
89 void clibAtoiMeasure(unsigned int n, unsigned int digits) {
90 auto p = pc1.subpiece(pc1.size() - digits, digits);
91 assert(*p.end() == 0);
92 static_assert(sizeof(long) == 8, "64-bit long assumed");
93 FOR_EACH_RANGE(i, 0, n) { doNotOptimizeAway(atol(p.begin())); }
96 void clibStrtoulMeasure(unsigned int n, unsigned int digits) {
97 auto p = pc1.subpiece(pc1.size() - digits, digits);
98 assert(*p.end() == 0);
100 FOR_EACH_RANGE(i, 0, n) {
101 doNotOptimizeAway(strtoul(p.begin(), &endptr, 10));
105 void lexicalCastMeasure(unsigned int n, unsigned int digits) {
106 auto p = pc1.subpiece(pc1.size() - digits, digits);
107 assert(*p.end() == 0);
108 FOR_EACH_RANGE(i, 0, n) {
109 doNotOptimizeAway(boost::lexical_cast<uint64_t>(p.begin()));
113 // Benchmarks for unsigned to string conversion, raw
115 unsigned u64ToAsciiTable(uint64_t value, char* dst) {
116 static const char digits[201] =
117 "00010203040506070809"
118 "10111213141516171819"
119 "20212223242526272829"
120 "30313233343536373839"
121 "40414243444546474849"
122 "50515253545556575859"
123 "60616263646566676869"
124 "70717273747576777879"
125 "80818283848586878889"
126 "90919293949596979899";
128 uint32_t const length = digits10(value);
129 uint32_t next = length - 1;
130 while (value >= 100) {
131 auto const i = (value % 100) * 2;
133 dst[next] = digits[i + 1];
134 dst[next - 1] = digits[i];
137 // Handle last 1-2 digits
139 dst[next] = '0' + uint32_t(value);
141 auto i = uint32_t(value) * 2;
142 dst[next] = digits[i + 1];
143 dst[next - 1] = digits[i];
148 void u64ToAsciiTableBM(unsigned int n, uint64_t value) {
149 // This is too fast, need to do 10 times per iteration
151 FOR_EACH_RANGE(i, 0, n) {
152 doNotOptimizeAway(u64ToAsciiTable(value + n, buf));
156 unsigned u64ToAsciiClassic(uint64_t value, char* dst) {
158 char* next = (char*)dst;
161 *next++ = '0' + (value % 10);
163 } while (value != 0);
164 unsigned length = next - start;
168 while (next > start) {
178 void u64ToAsciiClassicBM(unsigned int n, uint64_t value) {
179 // This is too fast, need to do 10 times per iteration
181 FOR_EACH_RANGE(i, 0, n) {
182 doNotOptimizeAway(u64ToAsciiClassic(value + n, buf));
186 void u64ToAsciiFollyBM(unsigned int n, uint64_t value) {
187 // This is too fast, need to do 10 times per iteration
189 FOR_EACH_RANGE(i, 0, n) {
190 doNotOptimizeAway(uint64ToBufferUnsafe(value + n, buf));
194 // Benchmark unsigned to string conversion
196 void u64ToStringClibMeasure(unsigned int n, uint64_t value) {
197 // FOLLY_RANGE_CHECK_TO_STRING expands to std::to_string, except on Android
198 // where std::to_string is not supported
199 FOR_EACH_RANGE(i, 0, n) { FOLLY_RANGE_CHECK_TO_STRING(value + n); }
202 void u64ToStringFollyMeasure(unsigned int n, uint64_t value) {
203 FOR_EACH_RANGE(i, 0, n) { to<std::string>(value + n); }
206 // Benchmark uitoa with string append
208 void u2aAppendClassicBM(unsigned int n, uint64_t value) {
210 FOR_EACH_RANGE(i, 0, n) {
211 // auto buf = &s.back() + 1;
213 s.append(buffer, u64ToAsciiClassic(value, buffer));
214 doNotOptimizeAway(s.size());
218 void u2aAppendFollyBM(unsigned int n, uint64_t value) {
220 FOR_EACH_RANGE(i, 0, n) {
221 // auto buf = &s.back() + 1;
223 s.append(buffer, uint64ToBufferUnsafe(value, buffer));
224 doNotOptimizeAway(s.size());
228 template <class String>
229 struct StringIdenticalToBM {
230 StringIdenticalToBM() {}
231 void operator()(unsigned int n, size_t len) const {
233 BENCHMARK_SUSPEND { s.append(len, '0'); }
234 FOR_EACH_RANGE(i, 0, n) {
235 String result = to<String>(s);
236 doNotOptimizeAway(result.size());
241 template <class String>
242 struct StringVariadicToBM {
243 StringVariadicToBM() {}
244 void operator()(unsigned int n, size_t len) const {
246 BENCHMARK_SUSPEND { s.append(len, '0'); }
247 FOR_EACH_RANGE(i, 0, n) {
248 String result = to<String>(s, nullptr);
249 doNotOptimizeAway(result.size());
254 static size_t bigInt = 11424545345345;
255 static size_t smallInt = 104;
256 static char someString[] = "this is some nice string";
257 static char otherString[] = "this is a long string, so it's not so nice";
258 static char reallyShort[] = "meh";
259 static std::string stdString = "std::strings are very nice";
260 static float fValue = 1.2355;
261 static double dValue = 345345345.435;
263 BENCHMARK(preallocateTestNoFloat, n) {
264 for (size_t i = 0; i < n; ++i) {
265 auto val1 = to<std::string>(bigInt, someString, stdString, otherString);
266 auto val3 = to<std::string>(reallyShort, smallInt);
267 auto val2 = to<std::string>(bigInt, stdString);
268 auto val4 = to<std::string>(bigInt, stdString, dValue, otherString);
269 auto val5 = to<std::string>(bigInt, someString, reallyShort);
273 BENCHMARK(preallocateTestFloat, n) {
274 for (size_t i = 0; i < n; ++i) {
275 auto val1 = to<std::string>(stdString, ',', fValue, dValue);
276 auto val2 = to<std::string>(stdString, ',', dValue);
279 BENCHMARK_DRAW_LINE();
281 static const StringIdenticalToBM<std::string> stringIdenticalToBM;
282 static const StringVariadicToBM<std::string> stringVariadicToBM;
283 static const StringIdenticalToBM<fbstring> fbstringIdenticalToBM;
284 static const StringVariadicToBM<fbstring> fbstringVariadicToBM;
286 #define DEFINE_BENCHMARK_GROUP(n) \
287 BENCHMARK_PARAM(u64ToAsciiClassicBM, n); \
288 BENCHMARK_RELATIVE_PARAM(u64ToAsciiTableBM, n); \
289 BENCHMARK_RELATIVE_PARAM(u64ToAsciiFollyBM, n); \
290 BENCHMARK_DRAW_LINE();
292 DEFINE_BENCHMARK_GROUP(1);
293 DEFINE_BENCHMARK_GROUP(12);
294 DEFINE_BENCHMARK_GROUP(123);
295 DEFINE_BENCHMARK_GROUP(1234);
296 DEFINE_BENCHMARK_GROUP(12345);
297 DEFINE_BENCHMARK_GROUP(123456);
298 DEFINE_BENCHMARK_GROUP(1234567);
299 DEFINE_BENCHMARK_GROUP(12345678);
300 DEFINE_BENCHMARK_GROUP(123456789);
301 DEFINE_BENCHMARK_GROUP(1234567890);
302 DEFINE_BENCHMARK_GROUP(12345678901);
303 DEFINE_BENCHMARK_GROUP(123456789012);
304 DEFINE_BENCHMARK_GROUP(1234567890123);
305 DEFINE_BENCHMARK_GROUP(12345678901234);
306 DEFINE_BENCHMARK_GROUP(123456789012345);
307 DEFINE_BENCHMARK_GROUP(1234567890123456);
308 DEFINE_BENCHMARK_GROUP(12345678901234567);
309 DEFINE_BENCHMARK_GROUP(123456789012345678);
310 DEFINE_BENCHMARK_GROUP(1234567890123456789);
311 DEFINE_BENCHMARK_GROUP(12345678901234567890U);
313 #undef DEFINE_BENCHMARK_GROUP
315 #define DEFINE_BENCHMARK_GROUP(n) \
316 BENCHMARK_PARAM(u64ToStringClibMeasure, n); \
317 BENCHMARK_RELATIVE_PARAM(u64ToStringFollyMeasure, n); \
318 BENCHMARK_DRAW_LINE();
320 DEFINE_BENCHMARK_GROUP(1);
321 DEFINE_BENCHMARK_GROUP(12);
322 DEFINE_BENCHMARK_GROUP(123);
323 DEFINE_BENCHMARK_GROUP(1234);
324 DEFINE_BENCHMARK_GROUP(12345);
325 DEFINE_BENCHMARK_GROUP(123456);
326 DEFINE_BENCHMARK_GROUP(1234567);
327 DEFINE_BENCHMARK_GROUP(12345678);
328 DEFINE_BENCHMARK_GROUP(123456789);
329 DEFINE_BENCHMARK_GROUP(1234567890);
330 DEFINE_BENCHMARK_GROUP(12345678901);
331 DEFINE_BENCHMARK_GROUP(123456789012);
332 DEFINE_BENCHMARK_GROUP(1234567890123);
333 DEFINE_BENCHMARK_GROUP(12345678901234);
334 DEFINE_BENCHMARK_GROUP(123456789012345);
335 DEFINE_BENCHMARK_GROUP(1234567890123456);
336 DEFINE_BENCHMARK_GROUP(12345678901234567);
337 DEFINE_BENCHMARK_GROUP(123456789012345678);
338 DEFINE_BENCHMARK_GROUP(1234567890123456789);
339 DEFINE_BENCHMARK_GROUP(12345678901234567890U);
341 #undef DEFINE_BENCHMARK_GROUP
343 #define DEFINE_BENCHMARK_GROUP(n) \
344 BENCHMARK_PARAM(clibAtoiMeasure, n); \
345 BENCHMARK_RELATIVE_PARAM(lexicalCastMeasure, n); \
346 BENCHMARK_RELATIVE_PARAM(handwrittenAtoiMeasure, n); \
347 BENCHMARK_RELATIVE_PARAM(follyAtoiMeasure, n); \
348 BENCHMARK_DRAW_LINE();
350 DEFINE_BENCHMARK_GROUP(1);
351 DEFINE_BENCHMARK_GROUP(2);
352 DEFINE_BENCHMARK_GROUP(3);
353 DEFINE_BENCHMARK_GROUP(4);
354 DEFINE_BENCHMARK_GROUP(5);
355 DEFINE_BENCHMARK_GROUP(6);
356 DEFINE_BENCHMARK_GROUP(7);
357 DEFINE_BENCHMARK_GROUP(8);
358 DEFINE_BENCHMARK_GROUP(9);
359 DEFINE_BENCHMARK_GROUP(10);
360 DEFINE_BENCHMARK_GROUP(11);
361 DEFINE_BENCHMARK_GROUP(12);
362 DEFINE_BENCHMARK_GROUP(13);
363 DEFINE_BENCHMARK_GROUP(14);
364 DEFINE_BENCHMARK_GROUP(15);
365 DEFINE_BENCHMARK_GROUP(16);
366 DEFINE_BENCHMARK_GROUP(17);
367 DEFINE_BENCHMARK_GROUP(18);
368 DEFINE_BENCHMARK_GROUP(19);
370 #undef DEFINE_BENCHMARK_GROUP
372 #define DEFINE_BENCHMARK_GROUP(T, n) \
373 BENCHMARK_PARAM(T##VariadicToBM, n); \
374 BENCHMARK_RELATIVE_PARAM(T##IdenticalToBM, n); \
375 BENCHMARK_DRAW_LINE();
377 DEFINE_BENCHMARK_GROUP(string, 32);
378 DEFINE_BENCHMARK_GROUP(string, 1024);
379 DEFINE_BENCHMARK_GROUP(string, 32768);
380 DEFINE_BENCHMARK_GROUP(fbstring, 32);
381 DEFINE_BENCHMARK_GROUP(fbstring, 1024);
382 DEFINE_BENCHMARK_GROUP(fbstring, 32768);
384 #undef DEFINE_BENCHMARK_GROUP
388 template <typename T>
389 inline void stringToTypeClassic(const char* str, uint32_t n) {
390 for (uint32_t i = 0; i < n; ++i) {
392 auto val = to<T>(str);
393 doNotOptimizeAway(val);
394 } catch (const std::exception& e) {
395 doNotOptimizeAway(e.what());
397 doNotOptimizeAway(i);
401 template <typename T>
402 inline void ptrPairToIntClassic(StringPiece sp, uint32_t n) {
403 for (uint32_t i = 0; i < n; ++i) {
405 auto val = to<T>(sp.begin(), sp.end());
406 doNotOptimizeAway(val);
407 } catch (const std::exception& e) {
408 doNotOptimizeAway(e.what());
410 doNotOptimizeAway(i);
414 constexpr uint32_t kArithNumIter = 10000;
416 template <typename T, typename U>
417 inline size_t arithToArithClassic(const U* in, uint32_t numItems) {
418 for (uint32_t i = 0; i < kArithNumIter; ++i) {
419 for (uint32_t j = 0; j < numItems; ++j) {
421 auto val = to<T>(in[j]);
422 doNotOptimizeAway(val);
423 } catch (const std::exception& e) {
424 doNotOptimizeAway(e.what());
426 doNotOptimizeAway(j);
428 doNotOptimizeAway(i);
431 return kArithNumIter * numItems;
438 std::array<int, 4> int2ScharGood{{-128, 127, 0, -50}};
439 std::array<int, 4> int2ScharBad{{-129, 128, 255, 10000}};
440 std::array<int, 4> int2UcharGood{{0, 1, 254, 255}};
441 std::array<int, 4> int2UcharBad{{-128, -1000, 256, -1}};
443 std::array<long long, 4> ll2SintOrFloatGood{{-2, -1, 0, 1}};
444 std::array<long long, 4> ll2SintOrFloatBad{{
445 std::numeric_limits<long long>::min() / 5,
446 std::numeric_limits<long long>::min() / 2,
447 std::numeric_limits<long long>::max() / 2,
448 std::numeric_limits<long long>::max() / 5,
450 std::array<long long, 4> ll2UintGood{{1, 2, 3, 4}};
451 std::array<long long, 4> ll2UintBad{{-1, -2, -3, -4}};
453 std::array<double, 4> double2FloatGood{{1.0, 1.25, 2.5, 1000.0}};
454 std::array<double, 4> double2FloatBad{{1e100, 1e101, 1e102, 1e103}};
455 std::array<double, 4> double2IntGood{{1.0, 10.0, 100.0, 1000.0}};
456 std::array<double, 4> double2IntBad{{1e100, 1.25, 2.5, 100.00001}};
459 using namespace conv;
461 #define STRING_TO_TYPE_BENCHMARK(type, name, pass, fail) \
462 BENCHMARK(stringTo##name##Classic, n) { \
463 stringToTypeClassic<type>(pass, n); \
465 BENCHMARK(stringTo##name##ClassicError, n) { \
466 stringToTypeClassic<type>(fail, n); \
469 #define PTR_PAIR_TO_INT_BENCHMARK(type, name, pass, fail) \
470 BENCHMARK(ptrPairTo##name##Classic, n) { \
471 ptrPairToIntClassic<type>(pass, n); \
473 BENCHMARK(ptrPairTo##name##ClassicError, n) { \
474 ptrPairToIntClassic<type>(fail, n); \
477 #define ARITH_TO_ARITH_BENCHMARK(type, name, pass, fail) \
478 BENCHMARK_MULTI(name##Classic) { \
479 return arithToArithClassic<type>(pass.data(), pass.size()); \
481 BENCHMARK_MULTI(name##ClassicError) { \
482 return arithToArithClassic<type>(fail.data(), fail.size()); \
485 #define INT_TO_ARITH_BENCHMARK(type, name, pass, fail) \
486 ARITH_TO_ARITH_BENCHMARK(type, intTo##name, pass, fail)
488 #define FLOAT_TO_ARITH_BENCHMARK(type, name, pass, fail) \
489 ARITH_TO_ARITH_BENCHMARK(type, floatTo##name, pass, fail)
491 STRING_TO_TYPE_BENCHMARK(bool, BoolNum, " 1 ", "2")
492 STRING_TO_TYPE_BENCHMARK(bool, BoolStr, "true", "xxxx")
493 BENCHMARK_DRAW_LINE();
494 STRING_TO_TYPE_BENCHMARK(float, FloatNum, " 3.14 ", "3e5000x")
495 STRING_TO_TYPE_BENCHMARK(float, FloatStr, "-infinity", "xxxx")
496 STRING_TO_TYPE_BENCHMARK(double, DoubleNum, " 3.14 ", "3e5000x")
497 STRING_TO_TYPE_BENCHMARK(double, DoubleStr, "-infinity", "xxxx")
498 BENCHMARK_DRAW_LINE();
499 STRING_TO_TYPE_BENCHMARK(signed char, CharSigned, " -47 ", "1000")
500 STRING_TO_TYPE_BENCHMARK(unsigned char, CharUnsigned, " 47 ", "-47")
501 STRING_TO_TYPE_BENCHMARK(int, IntSigned, " -4711 ", "-10000000000000000000000")
502 STRING_TO_TYPE_BENCHMARK(unsigned int, IntUnsigned, " 4711 ", "-4711")
503 STRING_TO_TYPE_BENCHMARK(
506 " -8123456789123456789 ",
507 "-10000000000000000000000")
508 STRING_TO_TYPE_BENCHMARK(
511 " 18123456789123456789 ",
513 BENCHMARK_DRAW_LINE();
515 PTR_PAIR_TO_INT_BENCHMARK(signed char, CharSigned, "-47", "1000")
516 PTR_PAIR_TO_INT_BENCHMARK(unsigned char, CharUnsigned, "47", "1000")
517 PTR_PAIR_TO_INT_BENCHMARK(int, IntSigned, "-4711", "-10000000000000000000000")
518 PTR_PAIR_TO_INT_BENCHMARK(
522 "10000000000000000000000")
523 PTR_PAIR_TO_INT_BENCHMARK(
526 "-8123456789123456789",
527 "-10000000000000000000000")
528 PTR_PAIR_TO_INT_BENCHMARK(
531 "18123456789123456789",
532 "20000000000000000000")
533 BENCHMARK_DRAW_LINE();
535 INT_TO_ARITH_BENCHMARK(signed char, CharSigned, int2ScharGood, int2ScharBad)
536 INT_TO_ARITH_BENCHMARK(unsigned char, CharUnsigned, int2UcharGood, int2UcharBad)
537 INT_TO_ARITH_BENCHMARK(int, IntSigned, ll2SintOrFloatGood, ll2SintOrFloatBad)
538 INT_TO_ARITH_BENCHMARK(unsigned int, IntUnsigned, ll2UintGood, ll2UintBad)
539 BENCHMARK_DRAW_LINE();
540 INT_TO_ARITH_BENCHMARK(float, Float, ll2SintOrFloatGood, ll2SintOrFloatBad)
541 BENCHMARK_DRAW_LINE();
542 FLOAT_TO_ARITH_BENCHMARK(float, Float, double2FloatGood, double2FloatBad)
543 BENCHMARK_DRAW_LINE();
544 FLOAT_TO_ARITH_BENCHMARK(int, Int, double2IntGood, double2IntBad)
546 #undef STRING_TO_TYPE_BENCHMARK
547 #undef PTR_PAIR_TO_INT_BENCHMARK
548 #undef ARITH_TO_ARITH_BENCHMARK
549 #undef INT_TO_ARITH_BENCHMARK
550 #undef FLOAT_TO_ARITH_BENCHMARK
552 int main(int argc, char** argv) {
553 gflags::ParseCommandLineFlags(&argc, &argv, true);
554 folly::runBenchmarks();