Create a gist now

Instantly share code, notes, and snippets.

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