Add more benchmarks for various conversions
[folly.git] / folly / test / ConvBenchmark.cpp
1 /*
2  * Copyright 2016 Facebook, Inc.
3  *
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
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <folly/Conv.h>
18
19 #include <boost/lexical_cast.hpp>
20
21 #include <folly/Benchmark.h>
22 #include <folly/Foreach.h>
23
24 #include <array>
25 #include <limits>
26 #include <stdexcept>
27
28 using namespace std;
29 using namespace folly;
30
31 ////////////////////////////////////////////////////////////////////////////////
32 // Benchmarks for ASCII to int conversion
33 ////////////////////////////////////////////////////////////////////////////////
34 // @author: Rajat Goel (rajat)
35
36 static int64_t handwrittenAtoi(const char* start, const char* end) {
37
38   bool positive = true;
39   int64_t retVal = 0;
40
41   if (start == end) {
42     throw std::runtime_error("empty string");
43   }
44
45   while (start < end && isspace(*start)) {
46     ++start;
47   }
48
49   switch (*start) {
50     case '-':
51       positive = false;
52     case '+':
53       ++start;
54     default:
55       ;
56   }
57
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");
62     }
63     retVal = newRetVal;
64   }
65
66   if (start != end) {
67     throw std::runtime_error("extra chars at the end");
68   }
69
70   return positive ? retVal : -retVal;
71 }
72
73 static StringPiece pc1 = "1234567890123456789";
74
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()));
79   }
80 }
81
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()));
86   }
87 }
88
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())); }
94 }
95
96 void clibStrtoulMeasure(unsigned int n, unsigned int digits) {
97   auto p = pc1.subpiece(pc1.size() - digits, digits);
98   assert(*p.end() == 0);
99   char* endptr;
100   FOR_EACH_RANGE(i, 0, n) {
101     doNotOptimizeAway(strtoul(p.begin(), &endptr, 10));
102   }
103 }
104
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()));
110   }
111 }
112
113 // Benchmarks for unsigned to string conversion, raw
114
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";
127
128   uint32_t const length = digits10(value);
129   uint32_t next = length - 1;
130   while (value >= 100) {
131     auto const i = (value % 100) * 2;
132     value /= 100;
133     dst[next] = digits[i + 1];
134     dst[next - 1] = digits[i];
135     next -= 2;
136   }
137   // Handle last 1-2 digits
138   if (value < 10) {
139     dst[next] = '0' + uint32_t(value);
140   } else {
141     auto i = uint32_t(value) * 2;
142     dst[next] = digits[i + 1];
143     dst[next - 1] = digits[i];
144   }
145   return length;
146 }
147
148 void u64ToAsciiTableBM(unsigned int n, uint64_t value) {
149   // This is too fast, need to do 10 times per iteration
150   char buf[20];
151   FOR_EACH_RANGE(i, 0, n) {
152     doNotOptimizeAway(u64ToAsciiTable(value + n, buf));
153   }
154 }
155
156 unsigned u64ToAsciiClassic(uint64_t value, char* dst) {
157   // Write backwards.
158   char* next = (char*)dst;
159   char* start = next;
160   do {
161     *next++ = '0' + (value % 10);
162     value /= 10;
163   } while (value != 0);
164   unsigned length = next - start;
165
166   // Reverse in-place.
167   next--;
168   while (next > start) {
169     char swap = *next;
170     *next = *start;
171     *start = swap;
172     next--;
173     start++;
174   }
175   return length;
176 }
177
178 void u64ToAsciiClassicBM(unsigned int n, uint64_t value) {
179   // This is too fast, need to do 10 times per iteration
180   char buf[20];
181   FOR_EACH_RANGE(i, 0, n) {
182     doNotOptimizeAway(u64ToAsciiClassic(value + n, buf));
183   }
184 }
185
186 void u64ToAsciiFollyBM(unsigned int n, uint64_t value) {
187   // This is too fast, need to do 10 times per iteration
188   char buf[20];
189   FOR_EACH_RANGE(i, 0, n) {
190     doNotOptimizeAway(uint64ToBufferUnsafe(value + n, buf));
191   }
192 }
193
194 // Benchmark unsigned to string conversion
195
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); }
200 }
201
202 void u64ToStringFollyMeasure(unsigned int n, uint64_t value) {
203   FOR_EACH_RANGE(i, 0, n) { to<std::string>(value + n); }
204 }
205
206 // Benchmark uitoa with string append
207
208 void u2aAppendClassicBM(unsigned int n, uint64_t value) {
209   string s;
210   FOR_EACH_RANGE(i, 0, n) {
211     // auto buf = &s.back() + 1;
212     char buffer[20];
213     s.append(buffer, u64ToAsciiClassic(value, buffer));
214     doNotOptimizeAway(s.size());
215   }
216 }
217
218 void u2aAppendFollyBM(unsigned int n, uint64_t value) {
219   string s;
220   FOR_EACH_RANGE(i, 0, n) {
221     // auto buf = &s.back() + 1;
222     char buffer[20];
223     s.append(buffer, uint64ToBufferUnsafe(value, buffer));
224     doNotOptimizeAway(s.size());
225   }
226 }
227
228 template <class String>
229 struct StringIdenticalToBM {
230   StringIdenticalToBM() {}
231   void operator()(unsigned int n, size_t len) const {
232     String s;
233     BENCHMARK_SUSPEND { s.append(len, '0'); }
234     FOR_EACH_RANGE(i, 0, n) {
235       String result = to<String>(s);
236       doNotOptimizeAway(result.size());
237     }
238   }
239 };
240
241 template <class String>
242 struct StringVariadicToBM {
243   StringVariadicToBM() {}
244   void operator()(unsigned int n, size_t len) const {
245     String s;
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());
250     }
251   }
252 };
253
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;
262
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);
270   }
271 }
272
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);
277   }
278 }
279 BENCHMARK_DRAW_LINE();
280
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;
285
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();
291
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);
312
313 #undef DEFINE_BENCHMARK_GROUP
314
315 #define DEFINE_BENCHMARK_GROUP(n)                       \
316   BENCHMARK_PARAM(u64ToStringClibMeasure, n);           \
317   BENCHMARK_RELATIVE_PARAM(u64ToStringFollyMeasure, n); \
318   BENCHMARK_DRAW_LINE();
319
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);
340
341 #undef DEFINE_BENCHMARK_GROUP
342
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();
349
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);
369
370 #undef DEFINE_BENCHMARK_GROUP
371
372 #define DEFINE_BENCHMARK_GROUP(T, n)             \
373   BENCHMARK_PARAM(T##VariadicToBM, n);           \
374   BENCHMARK_RELATIVE_PARAM(T##IdenticalToBM, n); \
375   BENCHMARK_DRAW_LINE();
376
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);
383
384 #undef DEFINE_BENCHMARK_GROUP
385
386 namespace {
387
388 template <typename T>
389 inline void stringToTypeClassic(const char* str, uint32_t n) {
390   for (uint32_t i = 0; i < n; ++i) {
391     try {
392       auto val = to<T>(str);
393       doNotOptimizeAway(val);
394     } catch (const std::exception& e) {
395       doNotOptimizeAway(e.what());
396     }
397     doNotOptimizeAway(i);
398   }
399 }
400
401 template <typename T>
402 inline void ptrPairToIntClassic(StringPiece sp, uint32_t n) {
403   for (uint32_t i = 0; i < n; ++i) {
404     try {
405       auto val = to<T>(sp.begin(), sp.end());
406       doNotOptimizeAway(val);
407     } catch (const std::exception& e) {
408       doNotOptimizeAway(e.what());
409     }
410     doNotOptimizeAway(i);
411   }
412 }
413
414 constexpr uint32_t kArithNumIter = 10000;
415
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) {
420       try {
421         auto val = to<T>(in[j]);
422         doNotOptimizeAway(val);
423       } catch (const std::exception& e) {
424         doNotOptimizeAway(e.what());
425       }
426       doNotOptimizeAway(j);
427     }
428     doNotOptimizeAway(i);
429   }
430
431   return kArithNumIter * numItems;
432 }
433
434 } // namespace
435
436 namespace conv {
437
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}};
442
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,
449 }};
450 std::array<long long, 4> ll2UintGood{{1, 2, 3, 4}};
451 std::array<long long, 4> ll2UintBad{{-1, -2, -3, -4}};
452
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}};
457 }
458
459 using namespace conv;
460
461 #define STRING_TO_TYPE_BENCHMARK(type, name, pass, fail) \
462   BENCHMARK(stringTo##name##Classic, n) {                \
463     stringToTypeClassic<type>(pass, n);                  \
464   }                                                      \
465   BENCHMARK(stringTo##name##ClassicError, n) {           \
466     stringToTypeClassic<type>(fail, n);                  \
467   }
468
469 #define PTR_PAIR_TO_INT_BENCHMARK(type, name, pass, fail) \
470   BENCHMARK(ptrPairTo##name##Classic, n) {                \
471     ptrPairToIntClassic<type>(pass, n);                   \
472   }                                                       \
473   BENCHMARK(ptrPairTo##name##ClassicError, n) {           \
474     ptrPairToIntClassic<type>(fail, n);                   \
475   }
476
477 #define ARITH_TO_ARITH_BENCHMARK(type, name, pass, fail)        \
478   BENCHMARK_MULTI(name##Classic) {                              \
479     return arithToArithClassic<type>(pass.data(), pass.size()); \
480   }                                                             \
481   BENCHMARK_MULTI(name##ClassicError) {                         \
482     return arithToArithClassic<type>(fail.data(), fail.size()); \
483   }
484
485 #define INT_TO_ARITH_BENCHMARK(type, name, pass, fail) \
486   ARITH_TO_ARITH_BENCHMARK(type, intTo##name, pass, fail)
487
488 #define FLOAT_TO_ARITH_BENCHMARK(type, name, pass, fail) \
489   ARITH_TO_ARITH_BENCHMARK(type, floatTo##name, pass, fail)
490
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(
504     long long,
505     LongLongSigned,
506     " -8123456789123456789 ",
507     "-10000000000000000000000")
508 STRING_TO_TYPE_BENCHMARK(
509     unsigned long long,
510     LongLongUnsigned,
511     " 18123456789123456789 ",
512     "-4711")
513 BENCHMARK_DRAW_LINE();
514
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(
519     unsigned int,
520     IntUnsigned,
521     "4711",
522     "10000000000000000000000")
523 PTR_PAIR_TO_INT_BENCHMARK(
524     long long,
525     LongLongSigned,
526     "-8123456789123456789",
527     "-10000000000000000000000")
528 PTR_PAIR_TO_INT_BENCHMARK(
529     unsigned long long,
530     LongLongUnsigned,
531     "18123456789123456789",
532     "20000000000000000000")
533 BENCHMARK_DRAW_LINE();
534
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)
545
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
551
552 int main(int argc, char** argv) {
553   gflags::ParseCommandLineFlags(&argc, &argv, true);
554   folly::runBenchmarks();
555   return 0;
556 }