Integer to string conversion benchmark
#include <chrono> | |
#include <cstdint> | |
#include <iostream> | |
#include <random> | |
#include <sstream> | |
using namespace std; | |
using namespace std::chrono; | |
const uint64_t P01 = 10; | |
const uint64_t P02 = 100; | |
const uint64_t P03 = 1000; | |
const uint64_t P04 = 10000; | |
const uint64_t P05 = 100000; | |
const uint64_t P06 = 1000000; | |
const uint64_t P07 = 10000000; | |
const uint64_t P08 = 100000000; | |
const uint64_t P09 = 1000000000; | |
const uint64_t P10 = 10000000000; | |
const uint64_t P11 = 100000000000; | |
const uint64_t P12 = 1000000000000; | |
uint32_t digits10(uint64_t v) | |
{ | |
if (v < P01) | |
return 1; | |
if (v < P02) | |
return 2; | |
if (v < P03) | |
return 3; | |
if (v < P12) { | |
if (v < P08) { | |
if (v < P06) { | |
if (v < P04) | |
return 4; | |
return 5 + (v >= P05); | |
} | |
return 7 + (v >= P07); | |
} | |
if (v < P10) { | |
return 9 + (v >= P09); | |
} | |
return 11 + (v >= P11); | |
} | |
return 12 + digits10(v / P12); | |
} | |
uint32_t facebook_digits10_test(uint64_t value, char *dst) | |
{ | |
static const char digits[201] = | |
"0001020304050607080910111213141516171819" | |
"2021222324252627282930313233343536373839" | |
"4041424344454647484950515253545556575859" | |
"6061626364656667686970717273747576777879" | |
"8081828384858687888990919293949596979899"; | |
uint32_t const length = digits10(value); | |
uint32_t next = length - 1; | |
while (value >= 100) { | |
auto const i = (value % 100) * 2; | |
value /= 100; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
next -= 2; | |
} | |
// Handle last 1-2 digits | |
if (value < 10) { | |
dst[next] = '0' + uint32_t(value); | |
} else { | |
auto i = uint32_t(value) * 2; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
} | |
return length; | |
} | |
uint32_t facebook_fixed_test(uint64_t value, char *dst) | |
{ | |
static auto const length = numeric_limits<uint64_t>::digits10; | |
auto next = length - 1; | |
static const char digits[201] = | |
"0001020304050607080910111213141516171819" | |
"2021222324252627282930313233343536373839" | |
"4041424344454647484950515253545556575859" | |
"6061626364656667686970717273747576777879" | |
"8081828384858687888990919293949596979899"; | |
while (value >= 100) { | |
auto const i = (value % 100) * 2; | |
value /= 100; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
next -= 2; | |
} | |
// Handle last 1-2 digits | |
if (value < 10) { | |
dst[next] = '0' + uint32_t(value); | |
return length - next; | |
} | |
auto i = uint32_t(value) * 2; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
return length - next + 1; | |
} | |
uint32_t facebook_fixed_small_test(uint64_t value, char *dst) | |
{ | |
static auto const length = numeric_limits<uint64_t>::digits10; | |
auto next = length - 1; | |
if (value < 10) goto small; | |
static const char digits[201] = | |
"0001020304050607080910111213141516171819" | |
"2021222324252627282930313233343536373839" | |
"4041424344454647484950515253545556575859" | |
"6061626364656667686970717273747576777879" | |
"8081828384858687888990919293949596979899"; | |
while (value >= 100) { | |
auto const i = (value % 100) * 2; | |
value /= 100; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
next -= 2; | |
} | |
// Handle last 1-2 digits | |
if (value < 10) { | |
small: | |
dst[next] = '0' + uint32_t(value); | |
return length - next; | |
} | |
auto i = uint32_t(value) * 2; | |
dst[next] = digits[i + 1]; | |
dst[next - 1] = digits[i]; | |
return length - next + 1; | |
} | |
uint32_t lwan_test(uint64_t value, char *buffer) | |
{ | |
char *p = buffer + numeric_limits<uint64_t>::digits10 - 1; | |
*p = '\0'; | |
do { | |
*--p = (char) ('0' + value % 10); | |
} while (value /= 10); | |
return (unsigned int) (numeric_limits<uint64_t>::digits10 - | |
(unsigned int) (p - buffer) - 1); | |
} | |
uint32_t lwan_lut_test(uint64_t value, char *buffer) | |
{ | |
char *p = buffer + numeric_limits<uint64_t>::digits10 - 1; | |
*p = '\0'; | |
do { | |
*--p = "0123456789"[value % 10]; | |
} while (value /= 10); | |
return (unsigned int) (numeric_limits<uint64_t>::digits10 - | |
(unsigned int) (p - buffer) - 1); | |
} | |
uint32_t snprintf_test(uint64_t value, char *buffer) | |
{ | |
return snprintf(buffer, numeric_limits<uint64_t>::digits10, "%lld", value); | |
} | |
static void strreverse(char* begin, char* end) | |
{ | |
char aux; | |
while (end > begin) | |
aux = *end, *end-- = *begin, *begin++ = aux; | |
} | |
uint32_t naive_test(uint64_t value, char *str) | |
{ | |
char *wstr = str; | |
// Conversion. Number is reversed. | |
do | |
*wstr++ = "01234567890"[value % 10]; | |
while (value /= 10); | |
*wstr = '\0'; | |
// Reverse string | |
strreverse(str, wstr - 1); | |
return wstr - str; | |
} | |
void test(const vector<uint64_t>& vector, const char *name, uint32_t (*func)(uint64_t v, char *buffer)) | |
{ | |
char buf[3 * sizeof(uint64_t)]; | |
int checksum = 0; | |
cout << name << ": "; | |
auto start = system_clock::now(); | |
for (size_t run = 0; run < 50; run++) { | |
for (uint64_t value : vector) | |
checksum += func(value, buf); | |
} | |
auto end = system_clock::now(); | |
cout << " " << duration_cast<microseconds>(end - start).count(); | |
cout << " us (checksum = " << checksum << ")\n"; | |
} | |
int main(void) | |
{ | |
mt19937 random_engine; | |
vector<uint64_t> vector(1000000); | |
random_engine.seed(0xdeadbeef); | |
for (auto power = 100000000000L; power >= 1; power /= 10) { | |
uniform_int_distribution<uint64_t> distribution(0, power); | |
for (auto i = vector.size(); i != 0; i--) | |
vector[i] = distribution(random_engine); | |
cout << "For values in interval [0," << power << "]:\n"; | |
test(vector, "lwan", lwan_test); | |
test(vector, "lwan_lut", lwan_lut_test); | |
test(vector, "facebook_digits10", facebook_digits10_test); | |
test(vector, "facebook_fixed", facebook_fixed_test); | |
test(vector, "facebook_fixed_small", facebook_fixed_small_test); | |
test(vector, "snprintf", snprintf_test); | |
test(vector, "naive", naive_test); | |
cout << "\n"; | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment