4 ms·

Parsing Series of Integers with SIMD (2018)

67 points by lelf 6y ago

29athrowaway 6y ago
There's substantial difference between AVX and SSE. You can get a performance boost just by compiling with AVX2 or AVX512 support.
- saagarjha 6y ago
  Be careful with AVX-512, especially if you are driving it on multiple cores.
- gameswithgo 6y ago
  you can get one by compiling with sse support too.
  - 29athrowaway 6y ago
    https://software.intel.com/content/www/us/en/develop/articles/how-intel-avx2-improves-performance-on-server-applications.html https://software.intel.com/content/www/us/en/develop/article...
- rurban 6y ago
  AVX-512 not really, as it punishes you with downclocking. It's only available on the slow, insecure legacy CPU's from Intel, not on any modern CPU.
  - gameswithgo 6y ago
    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)
  - qubex 6y ago
    > It’s only available on the slow, insecure legacy CPU’s from Intel, not on any modern CPU. Am I to take it that it is your opinion that any x86 CPU not manufactured by AMD is essentially dangerous and worthless?
    - rurban 6y ago
      High security risk esp. Why bother with AVX-512? It's not portable, and has questionable advantages. Only AVX-512 downclocking is significant, 256 and 128bit not at all.
plastic_teeth 6y ago
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.
nsajko 6y ago
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 https://www.miraclelinux.com/labs/pdf/fpga-en
- pubby 6y ago
  Lexing/tokenization implies creating tokens to pass to another parser. This is more general than that.
- gameswithgo 6y ago
  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.
htfy96 6y ago
Curious if Intel BCD ops (https://en.wikipedia.org/wiki/Intel_BCD_opcode 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

67 points by lelf 6y ago

There's substantial difference between AVX and SSE. You can get a performance boost just by compiling with AVX2 or AVX512 support.

saagarjha 6y ago
Be careful with AVX-512, especially if you are driving it on multiple cores.
gameswithgo 6y ago
you can get one by compiling with sse support too.
- 29athrowaway 6y ago
  https://software.intel.com/content/www/us/en/develop/articles/how-intel-avx2-improves-performance-on-server-applications.html https://software.intel.com/content/www/us/en/develop/article...
rurban 6y ago
AVX-512 not really, as it punishes you with downclocking. It's only available on the slow, insecure legacy CPU's from Intel, not on any modern CPU.
- gameswithgo 6y ago
  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)
- qubex 6y ago
  > It’s only available on the slow, insecure legacy CPU’s from Intel, not on any modern CPU. Am I to take it that it is your opinion that any x86 CPU not manufactured by AMD is essentially dangerous and worthless?
  - rurban 6y ago
    High security risk esp. Why bother with AVX-512? It's not portable, and has questionable advantages. Only AVX-512 downclocking is significant, 256 and 128bit not at all.

plastic_teeth 6y ago

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.

nsajko 6y ago

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 https://www.miraclelinux.com/labs/pdf/fpga-en

pubby 6y ago
Lexing/tokenization implies creating tokens to pass to another parser. This is more general than that.
gameswithgo 6y ago
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.

htfy96 6y ago

Curious if Intel BCD ops (https://en.wikipedia.org/wiki/Intel_BCD_opcode 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