Integers?

[AlexGuteniev]

The to_bcd8 should beat an usual itoa implementation.

Wanna add integers API?

[TobiSchluter]

I was thinking the same thing when I was working on it just now.

A 32bit int can have at most 10 digits, a 64bit int 19 digits, so it doesn't map cleanly to what we have right now, though. Also, integers will have leading zeros whereas our significands have at most one, and cutting off the high digits would require one copy if using to_bcd8 (or maybe a bit-count followed by a shift, if it fits in a register)

[dtolnay]

This is the best variation I have found so far: dtolnay/itoa#66. 4-digit bcd using 32-bit multiplication (as opposed to bcd8 with 64-bit multiplications) can be done four at a time using u32x4 simd. This ends up being significantly faster than the best implementation I've found involving bcd8. Both are implemented in https://github.com/dtolnay/itoa-benchmark, you can reproduce this result by running cargo run --release bcd4:u64 bcd8:u64.

[vitaut]

This is a bit out of scope but I won't object to a PR.

[TobiSchluter]

@dtolnay is your benchmark repeating the same numbers of digits? Then you will get perfect branch prediction on the choice between the different BCD versions. This may or may not be realistic for your application.

I would think that indeed large integers are much rarer than short ones, so a realistic sampling would probably need to use a power law distribution or something.

[dtolnay]

The chart in the readme is done using a similar methodology as https://github.com/miloyip/itoa-benchmark's "Random" benchmark, which is to measure 100k values chosen randomly from {0, 1, 2, …, 9}, then a separate measurement for 100k values chosen randomly from {10, 11, …, 99}, etc through {1000000000, …, 4294967295}. So within each measurement the length is perfectly predicted.

Here is a different methodology that makes the length unpredictable: dtolnay/itoa-benchmark#17. It generates 100k values of mixed length. For uint32 this is 10k values of each length ranging from 1 through 10. The baseline is how long it takes to format these 100k values shuffled in random order. Then separately it measures formatting the same 100k values of mixed length plus another 100k values of a specific length, again all shuffled together. The measurement reported in the chart is the difference of this from baseline.

Example (using N=10 instead of N=100k): the nanoseconds reported for formatting 3-digit values would be the time for formatting the 20 values in [▯▯▯, ▯▯▯, ▯▯▯▯▯▯, ▯▯▯, ▯▯▯, ▯▯▯▯, ▯▯▯▯▯▯▯▯▯, ▯▯▯▯▯▯▯, ▯▯▯, ▯, ▯▯▯▯▯, ▯▯▯, ▯▯▯▯▯▯▯▯, ▯▯▯, ▯▯, ▯▯▯, ▯▯▯, ▯▯▯, ▯▯▯, ▯▯▯▯▯▯▯▯▯▯] minus the time for formatting the 10 values in [▯▯▯▯▯▯, ▯▯▯▯▯, ▯▯▯▯▯▯▯▯▯▯, ▯▯▯▯▯▯▯, ▯▯▯, ▯▯, ▯▯▯▯▯▯▯▯▯, ▯▯▯▯▯▯▯▯, ▯▯▯▯, ▯], divided by 10.

[TobiSchluter]

Here is a comparison of two straightforward extensions of zmij's SSE codes to handle integers (one peels of four digits out of an int64 and handles them separately, the other uses AVX256 to deal with the 20digit number).

This is based on Milo Yip's itoa benchmark, left plot is for int32, right is for int64. Each plot shows two parts: first benchmarks using fixed-length integers with the given numbers of digits, then three "random length" sets: a log-uniform distribution or more precisely "equal number of equidistributed samples for each number of digits over the whole range", and finally the same type of distribution but only for what I consider realistic output in human facing numbers 1-4 digits and 1-5 digits.

The other codes in the benchmark all specialize for short numbers, so win there (also SSE2 in spite of its name). For (unrealistic) random lengths our full-width code is a clear winner, other than that the picture is more complicated. You may ask: why is our code slower at 32bit, even with randoms? The other itoa codes switch over at >= 9 digits which in the test distribution is only 20% of cases as 32bit numbers can have ten digits at most -- and that case is probably overrepresented given that the largest int is < 5e9, so it would actually look worse if this were a proper log-uniform distribution.

Additionally, my version of our codes writes to a larger buffer than the other codes (16 or 32 bytes), fixing that would make the code a bit slower.

So while there still are some cheap optimization options, I think specialized codes clearly win.

[TobiSchluter]

Wow, I dug some more to understand how the scalar codes can be so good at the unpredictable tests. I noticed that there are jumps in the fastest codes that decide even between 1-4 digits -- but there are no prediction misses. The issue was the size of the benchmark: the branch prediction on my Zen5 can actually memorize the entire sequence of jumps for the data sets! Here's the plot with a properly sized benchmark. zmij wins, and it wins significantly -- provided the number of digits is not predictable. The plot now includes signed and unsigned integers, just to make sure that there are no trivial mistakes.

Edit: fixed inlining, so no jump in the zmij codes on random signed tests any longer. I could have probably simply used @dtolnay's benchmark :)

[TobiSchluter]

A little update that includes 128bit ints. Seems like this is really going somewhere. As soon as there is any variation in number of digits, this code easily beats all other codes decisively. You will see that the "zmij" data points are labelled v1 (SSE2), v2 (SSE4.1) and v3 (AVX2), this refers to the microarchitecture levels. I was surprised to see that fmt is almost exponential in the number of digits when dealing with 128bit numbers.

I tried @dtolnay's benchmark as well, and I'm within range of all the Rust codes in spite of 1. the FFI interface and the fact that 2. the Rust codes don't left-align -- they return a slice which begins at the first non-zero digit. An extension of the benchmark to include negative numbers shows the dangers of that approach: while our times remain practically the same, the other codes get multiple times slower.

Anyway, @vitaut I can clean this up, and also add a NEON path, if you're interested. I can also base it against fmt, but I've no idea what that would entail. It's not constexpr friendly which might be a showstopper.

ps 128bit are a lot of digits, but in order to have some sensible output with varying numbers of digits, I use a column with 28-34 digits. This range straddles the threshold out of a single AVX2 register, so it isn't to the benefit of the code. Another observation (not shown): gcc really struggles with register allocation when doing 128bit math, that's why I updated to g++14 and made these plots with clang-21 (previous plots were g++13). Finally, I'm happy to have finally found a case where 256bit registers actually lead to a speedup.

Edit: added a SSE2 implementation. Beats everything else out of the water but getting rid of the leading zeros costs ~1ns in the absence of proper shuffles.

Edit2: added a scalar fallback and used fmt's integer length evaluation isntead the simd bit-counting approach from our float code. Even the scalar fallback is faster than any competing code for all cases with non-fixed length except unsigned 64bit integers with one or two digits.

Edit3: feature complete now with a NEON implementation. I was adventurous so I used neon2sse to test it. It's fun to look at the benchmarks, neon2sse beats the scalar implementation in most cases. sse2neon makes some unnecessary alignment checks which trip up clang (but not gcc), and I removed those checks. Otherwise, the signed random variants would deteriorate significantly.

[TobiSchluter]

My benchmarks and my code are now live here https://github.com/TobiSchluter/itoa-benchmark

To my surprise, on my Zen5 these codes come out on top on all benchmarks except Milo Yip's original fixed length benchmark. Even the non-SIMD fallback implementation is competitive.

I will get them submission-ready from now on. I think I mostly need an integration into zmij's test suite, some self-contained benchmark, a C implementation, and the relevant changes to zmij's documentation. @vitaut anything else obvious.

[vitaut]

Thanks for the detailed investigation and apologies for the slow reply. The findings are quite interesting. A PR adding integer conversion support would be welcome, especially with a benchmark against one of the faster existing methods, similar to the benchmark we have for doubles.

Separately, it would be good to investigate what is happening with 128-bit conversion in {fmt}. It is probably easy to fix.

[vitaut]

BTW what is r1-2 etc in the diagrams?

[TobiSchluter]

@vitaut saw your update to fmt. Nice.

I've been a bit absorbed, because I was working on an AVX-512 version, and just now I found something that seems to actually beat Champagne-Lemire (they branch, so they are easy to beat if one sets up the benchmark carefully, but that's not what I mean), so I hope I can get my mind free enough to process it into a usable form. I hope to update the repo and the plots early in the week, and then get to preparing a PR.

It turned out to be a more interesting problem than I expected. Or should I say time-consuming. There are lots of small optimizations.

[TobiSchluter]

PS @vitaut forgot to say: r1-2 is log-uniform for numbers with one to two digits etc