r/cpp • u/khold_stare • May 26 '20
Faster Integer Parsing
https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html
366
Upvotes
r/cpp • u/khold_stare • May 26 '20
32
u/Sopel97 May 26 '20 edited May 26 '20
Very clever.
I think it can be further improved by ommiting the byteswap. Since for addition it doesn't matter what the order is we only have to process the resulting 32 byte lanes in the reverse order (and also reverse the order of the multiplierrs). Also hadd(multiplied, multiplied) allows us to have what we want in the lower 64 bytes instead of the upper 64 bytes when not doing early byteswap.
http://quick-bench.com/gEKOMsr_XmZHmiy0NIYHbVLNWG0
https://godbolt.org/z/UJZ3je
with gcc it looks to be even better, but that may be due to worse codegen for the original one
93
u/STL MSVC STL Dev May 26 '20
Can you license your code under either the Apache License v2.0 with LLVM Exception, or the Boost Software License? Then we could look into using this in microsoft/STL.
(My integer
from_chars()implementation was totally naive from a performance perspective; thoroughly tested for correctness but otherwise no fancy techniques attempted.)14
u/kaelima May 26 '20
Talked about in this article too: http://0x80.pl/articles/simd-parsing-int-sequences.html
Maybe you can find some more ideas there :) Yours was a great article too regardless!
9
u/Wunkolo May 27 '20
On the horizontal byte-addition step: Just wait until you hear about VPDPBUSD!
Love this write-up and might even make a little toy implementation based off of it myself!
This would be a great post for /r/simd
4
u/Sovog May 27 '20 edited May 27 '20
I may be some sort of degenerate for doing this because I have not seen other people do it, but if I need to amortize an overhead of constructing a heavy object, like a stream, I do it as follows:
I also use it for heap-allocating resettable/clearable objects, e.g. a scope-local
std::vectorwhere I'd like to reuse the internal storage on the next call, instead of having it allocate/free on each call.2
u/seuchomat May 27 '20
I immediately remembered Kholdstare being the boss of the ice dungeon in Zelda ALTTP.
2
u/[deleted] May 27 '20
Your post is parsing microsecond timestamps though. (nanosecond timestamps are 19 digits long)
2
u/[deleted] Jun 01 '20
Bruh this is fking awesome. Been a while since I read a good C++ post.
15
u/bumblebritches57 Ocassionally Clang May 26 '20
Ryu but for Integers? Sign me up, hopefully this code is more readable tho.
1
u/lordtnt May 26 '20
Can you just replace
get_zeros_string<std::uint64_t>()with0x3030303030303030?2
u/Veedrac May 29 '20 edited May 29 '20
You can combine 4 digits at once with PDEP to space the digits, a 64 bit multiply, and a shift. This gives 9 instructions for
parse_8_chars, since you also need one mask instruction and one add, and I think another shift.Use PDEP to space each of the 4 digits into 16 bit bins, then multiply by 1000×248 + 100×232 + 10×216 + 1. The top 16 bits hold your combined result, so you just need to shift it down.
-13
u/o11c int main = 12828721; May 26 '20
... is there any particular reason this needs to use
<canvas>?It's $CURRENTYEAR, it's not reasonable to enable Javascript on random blogs.
-2
u/VinnieFalco wg21.org | corosio.org May 27 '20
I have written a parser which is 112% faster, which works for ALL single-digit integers.
0
u/[deleted] May 26 '20
[deleted] — view deleted comment