jeaiii/itoa

Fast integer to ascii / integer to string conversion

itoa - Fast integer to ascii / integer to string conversion

• newest version: jeaiii_to_text.h
• 0 dependency header only - as in absolutely no dependencies on ANY other headers
• fast - fasted tested on vs2019 in x86 and x64 for all digit lengths, uniform random bits, and uniform random digit lengths (latest version is even 25% faster than before) using https://github.com/jeaiii/itoa-benchmark
• small - simple code that produces good compiled code even in debug builds (no nested functions)
• compiles on clang, msvc, and gcc as C++11 or later
• written to specialize well based on integer type (size, signed, unsigned) and possible values determined at compile time
• Thanks to Junekey Jeon for the great write-up here, providing better insight into more rigorous mathematical foundations which eliminated an unneeded addition, and renewing my interest into making an even faster version

Check it out vs. {fmt} on godbolt.org

Disclaimer: This is not a good way to benchmark. It's not very repeatable and google benchmark is compiled in debug, although fmt being mostly header is optimized and inlined well. The performance charts below are much more accurate.

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
BM_fmt           16.6 ns         10.5 ns     75504520
BM_jea           10.2 ns         4.13 ns    159688774

Click for interactive performance charts

The last column is uniform random length numbers from 1 to N digits - worst case for branch prediction based on number of digits

itoa's Issues

C conversion/adaptation of jeaiii_to_text.h compared to C conversion/adaptation of itoa_jeaiii.cpp not as much faster as hoped

See MoarVM/MoarVM#1800. Obviously there's lots of overhead, but the readme mentioned a 25% speedup for the new version, and I'm seeing nowhere near that (with gcc 13.2.1 in linux, compiling with -O3 -march=native, on a Zen 2). Do you see anything obviously problematic in my conversion?

warnings emitted by msvc

When compiling with MSVC I'm getting warnings:
jeaiii_to_text.h(147): warning C4305: '/=': truncation from 'jeaiii::u32' to 'U'
jeaiii_to_text.h(209): warning C4305: '/=': truncation from 'jeaiii::u32' to 'U'

Replacing

n /= u32(1e8);

by

n = U(n /u32(1e8));

solves it.

How hard would it be to provide a C version of jeaiii_to_text.h?

I don't think `n` can ever be < 10 here

itoa/include/itoa/jeaiii_to_text.h

Line 150 in 84f25b8

b = n < 10 ? b + 1 : b + 2;

all 9 digits numbers should be handled above (and ~4/10ths of the 10 digits numbers) so this should be like:

itoa/include/itoa/jeaiii_to_text.h

Lines 209 to 213 in 84f25b8

	if (n < u32(1e2))
	{
	*reinterpret_cast<pair*>(b) = digits.dd[n];
	b += 2;
	}

Clarify roles of the two implementations

Just found this library and am quite surprised by how much of a performance improvement it made for our project!

However, while the interface of the functions is indeed so simple as to be mostly self explanatory, I am unsure about the roles of itoa_jeaiii.cpp and to_chars.cpp, i.e. which one to choose when, seeing that they basically offer the same functionality...

Thanks!

Features: zero-padding and fixed-point

I wanted to see how hard it might be to extend this to get fixed length zero-padded responses.

The other use-case is slightly less common but it can be often helpful to represent a fixed-point decimal number with a standard integer type like int32_t or int64_t where the number is stored as N * 10^D where D is the number of decimal digits supported. I was trying to think of how one could utilize your same approach but with the added issue of inserting the decimal place and potentially having leading zeros after the decimal but before the first digit.

Finally there is the fixed length, fixed-point decimal number, where you want to render the same number fixed-point decimal number but with a fixed number of decimal places and zero padding in the front for the rest

Mostly just thoughts on how this could be extended, I could provide naïve solutions to each of these if its helpful

Issue in integer to string conversion

This failed to convert this number: 3890001770327310336.

This resulted in 3890001770227310336 (Diff of 10'000'000)

Versions for uint8_t, int8_t, uint16_t and int16_t

This is a fantastic, really fast algorithm, that even seems to beat Vitaut's. Many thanks for making this available.

My issue is actually a feature request. For completion, do you think that beyond the currently available implementations for uint32_t, int32_t, uint64_t and int64_t, would it be possible to add, in the future, implementations also for uint8_t, int8_t, uint16_t and int16_t?

It would be amazing to have those, for really fast conversion of low-latency batches of data.

FYI, we're using this in MoarVM

I just merged MoarVM/MoarVM#1618 which uses this implementation. Thought you might like to know, thanks for this!

GCC warning due to ASCII art

The ASCII art on "to_text_from_integer.h" generates a compiler warning with GCC 8:

itoa/to_text_from_integer.h:39:1: warning: multi-line comment [-Wcomment]
 //    /\   \     \     \     \
 ^

If you comment that line on the header file you also get a warning on the next one. I think it is due to the use of the character "\".

remove usage of template variable `mask` to support c++11

Clang missing-braces

There is an warning from Clang 6.

itoa_jeaiii.cpp:65:35: error: suggest braces around initialization of subobject [-Werror,-Wmissing-braces]
static const pair s_pairs[] = { P('0'), P('1'), P('2'), P('3'), P('4'), P('5'), P('6'), P('7'), P('8'), P('9') };
                                ~~^~~~
                                {
itoa_jeaiii.cpp:64:14: note: expanded from macro 'P'
#define P(T) T, '0',  T, '1', T, '2', T, '3', T, '4', T, '5', T, '6', T, '7', T, '8', T, '9'
             ^~~~~~