Re:Parsing Series of Integers with SIMD (2018)
by plastic_teeth on Friday May 29, 2020 @04:25AM
(#23347605)
I haven't read this properly, and I'm not sure I totally understand the stuff being parsed, but here's my initial thought. Parsing a 4-digit span can be done with PEXT-sub-multiply, and range checking requires a extra few instructions.
initial: 0 0 0 0 3 4 1 2 (characters)
pext: 0 3 0 4 0 1 0 2 (characters)
sub: 0 3 0 4 0 1 0 2
multiply: 3412 412 12 2
Values below '0' will set high bits in the "sub" phase. Do another "sub" to check for values above '9', and branch.
Use of PEXT means potentially very fast handling of separators. Everything can be branchless.
Might not be as fast as SIMD but it should be better than a typical scalar approach.
Re:Parsing Series of Integers with SIMD (2018)
by nsajko on Friday May 29, 2020 @09:23AM
(#23349665)
A bit off-topic question: why do people use "parsing" instead of "lexing" or "tokenization" for denoting the analysis of strings from regular languages; considering lexing is just a trivial sub-case of parsing anything that includes the regular languages?
Perhaps more on topic: I think this can be even faster if one is willing to offload the heavy lifting to an FPGA, here's a result from 2016: https://www.miraclelinux.com/labs/pdf/fpga-en
Re:Parsing Series of Integers with SIMD (2018)
by gameswithgo on Friday May 29, 2020 @10:02AM
(#23350056)
Human language is flexible and imprecise. There is no compiler. English in particular is often interpreted in a descriptivist manner (meaning is defined based on how the public uses the words) rather than prescriptivist (meaning is defined by central authority).
Parsing is sometimes used to describe the translation of tokens to abstract syntax tree, sometimes it is used to describe both tokenzation and tree formation together, sometimes it is used to describe any process of taking in text and producing something more structured (Turbo Pascal for instance went straight from text -> machine code, was that parsing?)
Tokenzation is taking in text and producing something more structured, so it may be appropriate to call that a form of parsing too.
Many programmers would like for human language to be as strict and precise as programming, but absent some plan to cause that to happen it is better to go with the flow, and simply be as clear in your own communication as you can rather than quibbling about definitions of others all the time. You won't ever win.
Re:Parsing Series of Integers with SIMD (2018)
by htfy96 on Friday May 29, 2020 @10:49AM
(#23350550)
Curious if Intel BCD ops (https://en.wikipedia.org/wiki/Intel_BCD_opcode) are still a thing in today's SiMD world. Converting chars to BCD code then convert BCD to u32 sounds a little bit easier than this
Re:Parsing Series of Integers with SIMD (2018)
by gameswithgo on Friday May 29, 2020 @09:21AM
(#23349647)
AVX/AVX2 also cause downclocking, to various degrees depending on which instructions you use, and which CPU. Some older CPUs will downclock the entire CPU if even 1 core is doing AVX instructions, newer ones downclock just the core.
In general, when AVX-512 is used in any sensible way, the performance gain from it is rather large. It isn't just twice as wide as 256bit AVX, it also is much more flexible, allowing more efficient vectorization of many algorithms. You often get more than a 2x speedup, despite the increased downclocking.
And AVX-512 is present on the newest intel cpus.
Hopefully AMD will introduce it with the next generation, since their downclocking method is superior in some ways. (you could use AVX-512 with less care to be sure you are doing enough AVX-512 work at a time, but benchmarking is harder since clock speeds vary in real time depending on heat and other factors)
initial: 0 0 0 0 3 4 1 2 (characters)
pext: 0 3 0 4 0 1 0 2 (characters)
sub: 0 3 0 4 0 1 0 2
multiply: 3412 412 12 2
Values below '0' will set high bits in the "sub" phase. Do another "sub" to check for values above '9', and branch.
Use of PEXT means potentially very fast handling of separators. Everything can be branchless.
Might not be as fast as SIMD but it should be better than a typical scalar approach.
Perhaps more on topic: I think this can be even faster if one is willing to offload the heavy lifting to an FPGA, here's a result from 2016: https://www.miraclelinux.com/labs/pdf/fpga-en
Parsing is sometimes used to describe the translation of tokens to abstract syntax tree, sometimes it is used to describe both tokenzation and tree formation together, sometimes it is used to describe any process of taking in text and producing something more structured (Turbo Pascal for instance went straight from text -> machine code, was that parsing?)
Tokenzation is taking in text and producing something more structured, so it may be appropriate to call that a form of parsing too.
Many programmers would like for human language to be as strict and precise as programming, but absent some plan to cause that to happen it is better to go with the flow, and simply be as clear in your own communication as you can rather than quibbling about definitions of others all the time. You won't ever win.
In general, when AVX-512 is used in any sensible way, the performance gain from it is rather large. It isn't just twice as wide as 256bit AVX, it also is much more flexible, allowing more efficient vectorization of many algorithms. You often get more than a 2x speedup, despite the increased downclocking.
And AVX-512 is present on the newest intel cpus.
Hopefully AMD will introduce it with the next generation, since their downclocking method is superior in some ways. (you could use AVX-512 with less care to be sure you are doing enough AVX-512 work at a time, but benchmarking is harder since clock speeds vary in real time depending on heat and other factors)
Am I to take it that it is your opinion that any x86 CPU not manufactured by AMD is essentially dangerous and worthless?
Only AVX-512 downclocking is significant, 256 and 128bit not at all.