Integer to string conversion benchmark

gistfile1.cpp

#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;
}