Stl: <charconv>: Investigate using KholdStare/qnd-integer-parsing-experiments SIMD

[StephanTLavavej]

See "Faster Integer Parsing" and KholdStare/qnd-integer-parsing-experiments.

KholdStare has graciously licensed this code under the Boost Software License. :smile_cat:

[expnkx]

tbh I seriously doubt whether it can work for from_chars since his fast integer parsing only works when you know how long your string and you must ensure every character is a digit before running the algorithm. In this case, no, we do not know.

I have not seen any good algorithm to deal with infinite length input. Someone could also put a bunch of zeros before the input to screw your algorithm.

Maybe put some zeros before the string would work?

[sylveon]

uhhh from_chars takes an explicit length?

[expnkx]

uhhh from_chars takes an explicit length?

The problem is that the standard library expects the from_chars to fail at the point it cannot parse which means you have to do some kind of verification before the algorithm. Unlike division, multiplication is very cheap, verification would take more time than running the algorithm. The verification process can also exploit the CPU pipeline to make use of every resource and get your parsing result simultaneously.

Until someone finds out a good SIMD verification method to do verification, it is generally pointless to use SIMD for acceleration.

std::to_chars also have issues since you do not know exactly your buffer size is and you cannot do to_chars I/O buffer or string buffer in place which is another huge performance lost.

In general, charconv is not good at doing anything. You better do it by yourself if you know your data.

[KholdStare]

Hi,

I've made a new commit to the repo with some preliminary SIMD verification: https://github.com/KholdStare/qnd-integer-parsing-experiments/commit/205fa91171d120b70d5a37933ffec12390979f39

Unfortunately the instructions that would be perfect don't exist so I had to cobble some things together. No we can parse from 1 to 16 chars with SIMD, with input validation. The two "wishlist" instructions would be "count trailing zeros" for __m128i type, and a left shift with a non-immediate value. I had to emulate both, and unfortunately there is one branch now. The running time is ~2.5 ns for any number of digits up to 16, up from 0.75ns for exactly 16 digits.

I'll continue thinking about other ways to do the same thing, with some other SSE instructions - I'm sure there's a way to get that lower.

[Kristine1975]

re. validation: this function from Daniel Lemire's fast_float library (Apache 2.0) validates 8 characters at once. It's only for base 10, though:

https://github.com/lemire/fast_float/blob/7eae925b51fd0f570ccd5c880c12e3e27a23b86f/include/fast_float/ascii_number.h#L27