<charconv>: instead of memcpy'ing the result you can calculate necessary buffer size ahead of time for integers

[toughengineer]

For integers instead of filling the buffer from right to left and memcpy'ing the result back so the most significant digit (that is written last) ends up in the leftmost position, you can calculate the necessary buffer size ahead of time and put all the digits exactly at their final destination place.

See example in libc++:
https://github.com/llvm/llvm-project/blob/f54402b63a4f5b0b4b15e0f82ce8ff8501b206e6/libcxx/include/charconv#L164-L168
straight from the Bit Twiddling Hacks:
https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10

memcpy usage here:

STL/stl/inc/charconv

Lines 137 to 146 in 550713e

	const ptrdiff_t _Digits_written = _Buff_end - _RNext;
	if (_Last - _First < _Digits_written) {
	return {_Last, errc::value_too_large};
	}
	_CSTD memcpy(_First, _RNext, static_cast<size_t>(_Digits_written));
	return {_First + _Digits_written, errc{}};
	}

[miscco]

As far as I know libc++ charconv implementation is derived from the STLs one.

The reason that code is not using the builtins is most likely that their support in MSVC was only merged recently (See #795)

[StephanTLavavej]

Thanks for the performance idea! MSVC's and libc++'s integer <charconv> implementations were independently written, which is why we're lacking this technique.

[toughengineer]

I'm glad to help.

After I submitted this issue I realized that writing to a buffer on the stack and then memcpy'ing to destination buffer may still be faster than calculating the needed length in advance.

The calculation uses log2 as counting bits instruction (which is several clocks on modern CPUs) and some multiplication+shifting+table lookup and fixup.

I tried to ask people who compared different implementations (e.g. to_chars/to_string and that of fmtlib, maybe @vitaut can comment on this) and got no definitive answer. So, I guess, one should investigate if it's really beneficial to spend time calculating the size in advance, and possibly take other considerations into account.

[vitaut]

I ran some benchmarks in http://www.zverovich.net/2020/06/13/fast-int-to-string-revisited.html. Size computation (https://github.com/fmtlib/fmt/blob/60c43e870387affb07de32ed4fc2794ac7a9f60d/include/fmt/format.h#L787) is a relatively insignificant factor compared to other optimizations (see the difference between format_to and format_int).

[StephanTLavavej]

Also, I have considered having different codepaths for "definitely enough space for the worst case" and "maybe not enough space, need to do precise bounds checking".

(Edit: @BillyONeal reminded me that we generate digits backwards, so even when there is plenty of space, we don't immediately know where to begin writing.)

(Edit x2: @BillyONeal also reminded me that Ryu's integer printing generates 2 digits at once, but the integer printing outside of Ryu generates only 1 digit at a time.)

[AlexGuteniev]

I've attempted the following function to determine length:

_UIntegral_digits function

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

template <class _UTy>
_NODISCARD int _UIntegral_digits(const _UTy _UVal) noexcept {
    if constexpr (sizeof(_UTy) == 1) {
        return 3 - (_UVal < 100) - (_UVal < 10);
    } else {
        const int _Binary_digits         = _Unsigned_integer_digits<_UTy> - _STD _Countl_zero(_UVal | 1);
        const int _Approx_decimal_digits = (_Binary_digits * 1233) >> 12;

        if constexpr (sizeof(_UTy) == 8) {
            static constexpr uint64_t _Decimal_powers[] = {
                0ull,
                10ull,
                100ull,
                1000ull,
                10000ull,
                100000ull,
                1000000ull,
                10000000ull,
                100000000ull,
                1000000000ull,
                10000000000ull,
                100000000000ull,
                1000000000000ull,
                10000000000000ull,
                100000000000000ull,
                1000000000000000ull,
                10000000000000000ull,
                100000000000000000ull,
                1000000000000000000ull,
                10000000000000000000ull,
            };

            return _Approx_decimal_digits + (_UVal >= _Decimal_powers[_Approx_decimal_digits]);
        } else if constexpr (sizeof(_UTy) == 4) {
            static constexpr uint32_t _Decimal_powers[] = {
                0,
                10,
                100,
                1000,
                10000,
                100000,
                1000000,
                10000000,
                100000000,
                1000000000,
            };

            return _Approx_decimal_digits + (_UVal >= _Decimal_powers[_Approx_decimal_digits]);
        } else {
            _STL_INTERNAL_STATIC_ASSERT(sizeof(_UTy) == 2);

            static constexpr uint16_t _Decimal_powers[] = {
                0,
                10,
                100,
                1000,
                10000,
            };

            return _Approx_decimal_digits + (_UVal >= _Decimal_powers[_Approx_decimal_digits]);
        }
    }
}

and in-place string fill using `_Resize_and_overwrite`.

And the benchmark as in #5606

integer_to_string.cpp

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#include <algorithm>
#include <array>
#include <benchmark/benchmark.h>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <random>
#include <type_traits>

using namespace std;

template <class T, double M, double S>
auto generate_array() {
    array<T, 2000> a;

    mt19937 gen;
    lognormal_distribution<double> dis(M, S);
    ranges::generate(a, [&] { return static_cast<T>(dis(gen)); });

    if constexpr (is_signed_v<T>) {
        bernoulli_distribution b(0.5);
        ranges::for_each(a, [&](T& v) { v *= (b(gen) ? -1 : 1); });
    }

    return a;
}

template <class T, double M, double S>
void integer_to_string(benchmark::State& state) {
    auto a = generate_array<T, M, S>();

    auto it = a.begin();
    for (auto _ : state) {
        auto i = *it;
        benchmark::DoNotOptimize(i);
        auto s = to_string(i);
        benchmark::DoNotOptimize(s);

        ++it;
        if (it == a.end()) {
            it = a.begin();
        }
    }
}

BENCHMARK(integer_to_string<uint8_t, 2.5, 1.5>);
BENCHMARK(integer_to_string<uint16_t, 5.0, 3.0>);
BENCHMARK(integer_to_string<uint32_t, 10.0, 6.0>);
BENCHMARK(integer_to_string<uint64_t, 20.0, 12.0>);

BENCHMARK(integer_to_string<int8_t, 2.5, 1.5>);
BENCHMARK(integer_to_string<int16_t, 5.0, 3.0>);
BENCHMARK(integer_to_string<int32_t, 10.0, 6.0>);
BENCHMARK(integer_to_string<int64_t, 20.0, 12.0>);

BENCHMARK_MAIN();

The results were not promising.