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 <limits>
  25 #include <stdexcept>
  26
  27 using namespace std;
  28 using namespace folly;
  29
  30 ////////////////////////////////////////////////////////////////////////////////
  31 // Benchmarks for ASCII to int conversion
  32 ////////////////////////////////////////////////////////////////////////////////
  33 // @author: Rajat Goel (rajat)
  34
  35 static int64_t handwrittenAtoi(const char* start, const char* end) {
  36
  37   bool positive = true;
  38   int64_t retVal = 0;
  39
  40   if (start == end) {
  41     throw std::runtime_error("empty string");
  42   }
  43
  44   while (start < end && isspace(*start)) {
  45     ++start;
  46   }
  47
  48   switch (*start) {
  49     case '-':
  50       positive = false;
  51     case '+':
  52       ++start;
  53     default:
  54       ;
  55   }
  56
  57   while (start < end && *start >= '0' && *start <= '9') {
  58     auto const newRetVal = retVal * 10 + (*start++ - '0');
  59     if (newRetVal < retVal) {
  60       throw std::runtime_error("overflow");
  61     }
  62     retVal = newRetVal;
  63   }
  64
  65   if (start != end) {
  66     throw std::runtime_error("extra chars at the end");
  67   }
  68
  69   return positive ? retVal : -retVal;
  70 }
  71
  72 static StringPiece pc1 = "1234567890123456789";
  73
  74 void handwrittenAtoiMeasure(unsigned int n, unsigned int digits) {
  75   auto p = pc1.subpiece(pc1.size() - digits, digits);
  76   FOR_EACH_RANGE(i, 0, n) {
  77     doNotOptimizeAway(handwrittenAtoi(p.begin(), p.end()));
  78   }
  79 }
  80
  81 void follyAtoiMeasure(unsigned int n, unsigned int digits) {
  82   auto p = pc1.subpiece(pc1.size() - digits, digits);
  83   FOR_EACH_RANGE(i, 0, n) {
  84     doNotOptimizeAway(folly::to<int64_t>(p.begin(), p.end()));
  85   }
  86 }
  87
  88 void clibAtoiMeasure(unsigned int n, unsigned int digits) {
  89   auto p = pc1.subpiece(pc1.size() - digits, digits);
  90   assert(*p.end() == 0);
  91   static_assert(sizeof(long) == 8, "64-bit long assumed");
  92   FOR_EACH_RANGE(i, 0, n) { doNotOptimizeAway(atol(p.begin())); }
  93 }
  94
  95 void clibStrtoulMeasure(unsigned int n, unsigned int digits) {
  96   auto p = pc1.subpiece(pc1.size() - digits, digits);
  97   assert(*p.end() == 0);
  98   char* endptr;
  99   FOR_EACH_RANGE(i, 0, n) {
 100     doNotOptimizeAway(strtoul(p.begin(), &endptr, 10));
 101   }
 102 }
 103
 104 void lexicalCastMeasure(unsigned int n, unsigned int digits) {
 105   auto p = pc1.subpiece(pc1.size() - digits, digits);
 106   assert(*p.end() == 0);
 107   FOR_EACH_RANGE(i, 0, n) {
 108     doNotOptimizeAway(boost::lexical_cast<uint64_t>(p.begin()));
 109   }
 110 }
 111
 112 // Benchmarks for unsigned to string conversion, raw
 113
 114 unsigned u64ToAsciiTable(uint64_t value, char* dst) {
 115   static const char digits[201] =
 116       "00010203040506070809"
 117       "10111213141516171819"
 118       "20212223242526272829"
 119       "30313233343536373839"
 120       "40414243444546474849"
 121       "50515253545556575859"
 122       "60616263646566676869"
 123       "70717273747576777879"
 124       "80818283848586878889"
 125       "90919293949596979899";
 126
 127   uint32_t const length = digits10(value);
 128   uint32_t next = length - 1;
 129   while (value >= 100) {
 130     auto const i = (value % 100) * 2;
 131     value /= 100;
 132     dst[next] = digits[i + 1];
 133     dst[next - 1] = digits[i];
 134     next -= 2;
 135   }
 136   // Handle last 1-2 digits
 137   if (value < 10) {
 138     dst[next] = '0' + uint32_t(value);
 139   } else {
 140     auto i = uint32_t(value) * 2;
 141     dst[next] = digits[i + 1];
 142     dst[next - 1] = digits[i];
 143   }
 144   return length;
 145 }
 146
 147 void u64ToAsciiTableBM(unsigned int n, uint64_t value) {
 148   // This is too fast, need to do 10 times per iteration
 149   char buf[20];
 150   FOR_EACH_RANGE(i, 0, n) {
 151     doNotOptimizeAway(u64ToAsciiTable(value + n, buf));
 152   }
 153 }
 154
 155 unsigned u64ToAsciiClassic(uint64_t value, char* dst) {
 156   // Write backwards.
 157   char* next = (char*)dst;
 158   char* start = next;
 159   do {
 160     *next++ = '0' + (value % 10);
 161     value /= 10;
 162   } while (value != 0);
 163   unsigned length = next - start;
 164
 165   // Reverse in-place.
 166   next--;
 167   while (next > start) {
 168     char swap = *next;
 169     *next = *start;
 170     *start = swap;
 171     next--;
 172     start++;
 173   }
 174   return length;
 175 }
 176
 177 void u64ToAsciiClassicBM(unsigned int n, uint64_t value) {
 178   // This is too fast, need to do 10 times per iteration
 179   char buf[20];
 180   FOR_EACH_RANGE(i, 0, n) {
 181     doNotOptimizeAway(u64ToAsciiClassic(value + n, buf));
 182   }
 183 }
 184
 185 void u64ToAsciiFollyBM(unsigned int n, uint64_t value) {
 186   // This is too fast, need to do 10 times per iteration
 187   char buf[20];
 188   FOR_EACH_RANGE(i, 0, n) {
 189     doNotOptimizeAway(uint64ToBufferUnsafe(value + n, buf));
 190   }
 191 }
 192
 193 // Benchmark unsigned to string conversion
 194
 195 void u64ToStringClibMeasure(unsigned int n, uint64_t value) {
 196   // FOLLY_RANGE_CHECK_TO_STRING expands to std::to_string, except on Android
 197   // where std::to_string is not supported
 198   FOR_EACH_RANGE(i, 0, n) { FOLLY_RANGE_CHECK_TO_STRING(value + n); }
 199 }
 200
 201 void u64ToStringFollyMeasure(unsigned int n, uint64_t value) {
 202   FOR_EACH_RANGE(i, 0, n) { to<std::string>(value + n); }
 203 }
 204
 205 // Benchmark uitoa with string append
 206
 207 void u2aAppendClassicBM(unsigned int n, uint64_t value) {
 208   string s;
 209   FOR_EACH_RANGE(i, 0, n) {
 210     // auto buf = &s.back() + 1;
 211     char buffer[20];
 212     s.append(buffer, u64ToAsciiClassic(value, buffer));
 213     doNotOptimizeAway(s.size());
 214   }
 215 }
 216
 217 void u2aAppendFollyBM(unsigned int n, uint64_t value) {
 218   string s;
 219   FOR_EACH_RANGE(i, 0, n) {
 220     // auto buf = &s.back() + 1;
 221     char buffer[20];
 222     s.append(buffer, uint64ToBufferUnsafe(value, buffer));
 223     doNotOptimizeAway(s.size());
 224   }
 225 }
 226
 227 template <class String>
 228 struct StringIdenticalToBM {
 229   StringIdenticalToBM() {}
 230   void operator()(unsigned int n, size_t len) const {
 231     String s;
 232     BENCHMARK_SUSPEND { s.append(len, '0'); }
 233     FOR_EACH_RANGE(i, 0, n) {
 234       String result = to<String>(s);
 235       doNotOptimizeAway(result.size());
 236     }
 237   }
 238 };
 239
 240 template <class String>
 241 struct StringVariadicToBM {
 242   StringVariadicToBM() {}
 243   void operator()(unsigned int n, size_t len) const {
 244     String s;
 245     BENCHMARK_SUSPEND { s.append(len, '0'); }
 246     FOR_EACH_RANGE(i, 0, n) {
 247       String result = to<String>(s, nullptr);
 248       doNotOptimizeAway(result.size());
 249     }
 250   }
 251 };
 252
 253 static size_t bigInt = 11424545345345;
 254 static size_t smallInt = 104;
 255 static char someString[] = "this is some nice string";
 256 static char otherString[] = "this is a long string, so it's not so nice";
 257 static char reallyShort[] = "meh";
 258 static std::string stdString = "std::strings are very nice";
 259 static float fValue = 1.2355;
 260 static double dValue = 345345345.435;
 261
 262 BENCHMARK(preallocateTestNoFloat, n) {
 263   for (size_t i = 0; i < n; ++i) {
 264     auto val1 = to<std::string>(bigInt, someString, stdString, otherString);
 265     auto val3 = to<std::string>(reallyShort, smallInt);
 266     auto val2 = to<std::string>(bigInt, stdString);
 267     auto val4 = to<std::string>(bigInt, stdString, dValue, otherString);
 268     auto val5 = to<std::string>(bigInt, someString, reallyShort);
 269   }
 270 }
 271
 272 BENCHMARK(preallocateTestFloat, n) {
 273   for (size_t i = 0; i < n; ++i) {
 274     auto val1 = to<std::string>(stdString, ',', fValue, dValue);
 275     auto val2 = to<std::string>(stdString, ',', dValue);
 276   }
 277 }
 278 BENCHMARK_DRAW_LINE();
 279
 280 static const StringIdenticalToBM<std::string> stringIdenticalToBM;
 281 static const StringVariadicToBM<std::string> stringVariadicToBM;
 282 static const StringIdenticalToBM<fbstring> fbstringIdenticalToBM;
 283 static const StringVariadicToBM<fbstring> fbstringVariadicToBM;
 284
 285 #define DEFINE_BENCHMARK_GROUP(n)                 \
 286   BENCHMARK_PARAM(u64ToAsciiClassicBM, n);        \
 287   BENCHMARK_RELATIVE_PARAM(u64ToAsciiTableBM, n); \
 288   BENCHMARK_RELATIVE_PARAM(u64ToAsciiFollyBM, n); \
 289   BENCHMARK_DRAW_LINE();
 290
 291 DEFINE_BENCHMARK_GROUP(1);
 292 DEFINE_BENCHMARK_GROUP(12);
 293 DEFINE_BENCHMARK_GROUP(123);
 294 DEFINE_BENCHMARK_GROUP(1234);
 295 DEFINE_BENCHMARK_GROUP(12345);
 296 DEFINE_BENCHMARK_GROUP(123456);
 297 DEFINE_BENCHMARK_GROUP(1234567);
 298 DEFINE_BENCHMARK_GROUP(12345678);
 299 DEFINE_BENCHMARK_GROUP(123456789);
 300 DEFINE_BENCHMARK_GROUP(1234567890);
 301 DEFINE_BENCHMARK_GROUP(12345678901);
 302 DEFINE_BENCHMARK_GROUP(123456789012);
 303 DEFINE_BENCHMARK_GROUP(1234567890123);
 304 DEFINE_BENCHMARK_GROUP(12345678901234);
 305 DEFINE_BENCHMARK_GROUP(123456789012345);
 306 DEFINE_BENCHMARK_GROUP(1234567890123456);
 307 DEFINE_BENCHMARK_GROUP(12345678901234567);
 308 DEFINE_BENCHMARK_GROUP(123456789012345678);
 309 DEFINE_BENCHMARK_GROUP(1234567890123456789);
 310 DEFINE_BENCHMARK_GROUP(12345678901234567890U);
 311
 312 #undef DEFINE_BENCHMARK_GROUP
 313
 314 #define DEFINE_BENCHMARK_GROUP(n)                       \
 315   BENCHMARK_PARAM(u64ToStringClibMeasure, n);           \
 316   BENCHMARK_RELATIVE_PARAM(u64ToStringFollyMeasure, n); \
 317   BENCHMARK_DRAW_LINE();
 318
 319 DEFINE_BENCHMARK_GROUP(1);
 320 DEFINE_BENCHMARK_GROUP(12);
 321 DEFINE_BENCHMARK_GROUP(123);
 322 DEFINE_BENCHMARK_GROUP(1234);
 323 DEFINE_BENCHMARK_GROUP(12345);
 324 DEFINE_BENCHMARK_GROUP(123456);
 325 DEFINE_BENCHMARK_GROUP(1234567);
 326 DEFINE_BENCHMARK_GROUP(12345678);
 327 DEFINE_BENCHMARK_GROUP(123456789);
 328 DEFINE_BENCHMARK_GROUP(1234567890);
 329 DEFINE_BENCHMARK_GROUP(12345678901);
 330 DEFINE_BENCHMARK_GROUP(123456789012);
 331 DEFINE_BENCHMARK_GROUP(1234567890123);
 332 DEFINE_BENCHMARK_GROUP(12345678901234);
 333 DEFINE_BENCHMARK_GROUP(123456789012345);
 334 DEFINE_BENCHMARK_GROUP(1234567890123456);
 335 DEFINE_BENCHMARK_GROUP(12345678901234567);
 336 DEFINE_BENCHMARK_GROUP(123456789012345678);
 337 DEFINE_BENCHMARK_GROUP(1234567890123456789);
 338 DEFINE_BENCHMARK_GROUP(12345678901234567890U);
 339
 340 #undef DEFINE_BENCHMARK_GROUP
 341
 342 #define DEFINE_BENCHMARK_GROUP(n)                      \
 343   BENCHMARK_PARAM(clibAtoiMeasure, n);                 \
 344   BENCHMARK_RELATIVE_PARAM(lexicalCastMeasure, n);     \
 345   BENCHMARK_RELATIVE_PARAM(handwrittenAtoiMeasure, n); \
 346   BENCHMARK_RELATIVE_PARAM(follyAtoiMeasure, n);       \
 347   BENCHMARK_DRAW_LINE();
 348
 349 DEFINE_BENCHMARK_GROUP(1);
 350 DEFINE_BENCHMARK_GROUP(2);
 351 DEFINE_BENCHMARK_GROUP(3);
 352 DEFINE_BENCHMARK_GROUP(4);
 353 DEFINE_BENCHMARK_GROUP(5);
 354 DEFINE_BENCHMARK_GROUP(6);
 355 DEFINE_BENCHMARK_GROUP(7);
 356 DEFINE_BENCHMARK_GROUP(8);
 357 DEFINE_BENCHMARK_GROUP(9);
 358 DEFINE_BENCHMARK_GROUP(10);
 359 DEFINE_BENCHMARK_GROUP(11);
 360 DEFINE_BENCHMARK_GROUP(12);
 361 DEFINE_BENCHMARK_GROUP(13);
 362 DEFINE_BENCHMARK_GROUP(14);
 363 DEFINE_BENCHMARK_GROUP(15);
 364 DEFINE_BENCHMARK_GROUP(16);
 365 DEFINE_BENCHMARK_GROUP(17);
 366 DEFINE_BENCHMARK_GROUP(18);
 367 DEFINE_BENCHMARK_GROUP(19);
 368
 369 #undef DEFINE_BENCHMARK_GROUP
 370
 371 #define DEFINE_BENCHMARK_GROUP(T, n)             \
 372   BENCHMARK_PARAM(T##VariadicToBM, n);           \
 373   BENCHMARK_RELATIVE_PARAM(T##IdenticalToBM, n); \
 374   BENCHMARK_DRAW_LINE();
 375
 376 DEFINE_BENCHMARK_GROUP(string, 32);
 377 DEFINE_BENCHMARK_GROUP(string, 1024);
 378 DEFINE_BENCHMARK_GROUP(string, 32768);
 379 DEFINE_BENCHMARK_GROUP(fbstring, 32);
 380 DEFINE_BENCHMARK_GROUP(fbstring, 1024);
 381 DEFINE_BENCHMARK_GROUP(fbstring, 32768);
 382
 383 #undef DEFINE_BENCHMARK_GROUP
 384
 385 int main(int argc, char** argv) {
 386   gflags::ParseCommandLineFlags(&argc, &argv, true);
 387   folly::runBenchmarks();
 388   return 0;
 389 }