9 ms·

AVX512 VBMI – remove spaces from text

152 points by pedro84 8y ago

CountHackulus 8y ago
This is really neat, I wonder if there's a way to keep a "remainder" around, kind of like Bresenham's algorithm, so that you can always do aligned reads from memory. The speedup on English text is really good, and I love the exploration into the AVX intrinsics.
- BeeOnRope 8y ago
  Unless I'm missing something it's the stores that are variably sized and hence become misaligned, not the reads?
jchw 8y ago
I was excited for AVX512 long ago but I've since heard that if you are jamming AVX512 instructions to every core you get a forcibly lower clockrate. In practice this sounds like it'd suggest using an AVX512 algorithm could actually be slower even when it's faster. If that's the case, I wonder what kind of performance gain you'd have to hit to beat a scalar or SSE-based vectorized algorithm.
- zwaps 8y ago
  Depends on the task and CPU, but especially on smaller machines the slowdown is not so large compared to potentially huge performance gains, ain't it?
- zamadatix 8y ago
  Depends which AVX512 instructions and how quickly you expect to bounce between AVX and scalar workloads. Generally if you can expect to spend a significant portion of your algorithm time in vector optimized code then the small clock drop isn't enough to erode the throughput gains.
- shereadsthenews 8y ago
  You also get a lower clock rate from running scalar code on many cores at once. Use of the 512-bit unit only makes the coefficient different. That said, the biggest mystery in this article is why you'd ever want to remove all whitespace from text. Why is that useful?
  - taspeotis 8y ago
    I dunno, spam filtering? sig nup now for che ap viag ra And then search for key words like “viagra.”
    - foepys 8y ago
      "Your flight via Graz is leaving on 5/2/2019"
      - dcbadacd 8y ago
        https://en.wikipedia.org/wiki/Scunthorpe_problem https://en.wikipedia.org/wiki/Scunthorpe_problem
  - jasonzemos 8y ago
    If one could remove spaces from JSON to create a so-called "Canonical JSON" one could obtain the same digest hash from the same data (even in combination with the hardware accelerated hashing offered by AVX!). Admittedly this is a strange case but I've run into it.
    - jandrese 8y ago
      Isn't this a problem if you're fed these two inputs: {mystring:"Hello World!"} {mystring:"Hello World !"} They aren't the same JSON.
      - marvy 8y ago
        also: {mystring:"HelloWorld!"}
- throwaway2048 8y ago
  There is also a huge delay for the core to shift into AVX512 mode, so interleaving it into regular non avx512 code can be a huge performance hit.
  - BeeOnRope 8y ago
    Well if by huge you mean 10ish microseconds, then yeah. There is also hysteresis built in so the transitions can only occur about once per millisecond. This puts a hard bound on the cost of the transitions themselves of about 1%. So no, I don't think the transitions are a big problem for any throughput case, although if you are counting microseconds for some type of low latency thing then sure it can matter. The bigger problem is usually the frequency reduction.
    - Twirrim 8y ago
      The amount of impact is heavily dependent on the class of CPU you use from Intel (gee, thanks Intel. Awesome way to make optimising code a pain in the arse). Bronze you probably really don't want to do AVX512 unless it's all heavily AVX512. Silver is better, but not great (which is what Cloudflare were using and ran in to). Gold or Platinum you're not likely to see much degradation from using AVX-512, even sparsely.
      - BeeOnRope 8y ago
        Are you talking specifically about the transition penalties which I was referring to? I am not aware of any strong variance in this behavior based on CPU class, and I would be surprised if it existed. I've always measured around 8 to 10 us for these transitions (there may be both a real time and "clock cycles" component to the transition time so it might vary a bit when measured in real time based on the CPU frequency). It sounds to be like you are talking more about AVX-512 downclocking. In any case, if your algorithm can be make heavy and effective use of AVX-512 it's going to be a win on almost any class of chip since you are looking at something like a 2x baseline speedup and more in many cases. If not, then yeah, proceed with caution.
- gwern 8y ago
  Lemire has criticized this: https://lemire.me/blog/2018/08/13/the-dangers-of-avx-512-throttling-myth-or-reality/ https://lemire.me/blog/2018/08/13/the-dangers-of-avx-512-thr... OP doesn't seem to show any major problems in his microbenchmarking, which is a start.
  - wmu 8y ago
    TBH I didn't think about throttling. My (mis)understanding is that a single program which completes in a fraction of second on an almost-idle machine doesn't suffer from AVX512 throttling. Daniel has reviewed this problem in series of posts: - https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-throttling-a-3-impact/ https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-thr... - https://lemire.me/blog/2018/08/25/avx-512-throttling-heavy-instructions-are-maybe-not-so-dangerous/ https://lemire.me/blog/2018/08/25/avx-512-throttling-heavy-i...
    - BeeOnRope 8y ago
      On most chips released to date, AVX-512 always causes a lower frequency (the so-called L1 license) as soon as any instruction uses it: basically the chip needs to drop from the L0 (fastest) license to L1 (middle) before it even starts any AVX-512 (probably to power up the upper lanes of the ALUs, register file, etc). Below L1, there is an even lower frequency tier, L2, which behaves as you say: it doesn't drop to L2 unless there is a sustained use of heavy AVX-512 instructions. On the Cannonlake chip you used, however, the i3-8121U, I don't measure any AVX-512 throttling at all - regardless of what instructions are running, up to and including dense 512-bit FMAs, the chip is running at the full 3.2 GHz (1 active core) or 3.1 GHz (2 active cores) turbo speed at all times. This behavior was common in the past on client parts: e.g., most Skylake client parts run at full speed when using 256-bit AVX/AVX2 operations, but server parts and some higher-end desktop parts based on them had varying speed tiers. All of the initially released SKX (Skylake X) parts were based on the Skylake-SP server part and had the speed tiers (downclocking) for AVX-512, but maybe many or most future client parts won't if CNL is any indication.
      - wmu 8y ago
lostmsu 8y ago
Instead of generating shuffle at runtime, couldn't a table be used for shuffling lower and higher parts of the register separately, then merging the result? Also, for uncommon patterns, the register could be split further to make the shuffle table fit into L1. Also, I am not sure compiler can optimize that continue statement. The non-AVX version might be improved by removing the if alltogether, and replacing dst++ with dst = followed by dst += (src[i] == ' ' || src[i] == '\r' || src[i] == '\n') ? 0 : 1
- jsd1982 8y ago
  The ternary operator a?b:c is still a conditional operation and may result in a branch instruction, same as an if statement. I wouldn't think it would matter much how exactly the branch condition was spelled in C code. It'll get translated to low level IR and optimized at that level.
  - kccqzy 8y ago
    In this case, the GP is having code of the form a ? 0 : 1 which can usually be rewritten as !a Any worthwhile compiler should compile that into one instruction or two, like `setne` or something else.
    - lostmsu 8y ago
      I was hoping for a direct translation to CMOV. Anyway, the assembly has to be analyzed to be sure.
      - Karliss 8y ago
        No need to speculate. https://godbolt.org/z/AC2NKY https://godbolt.org/z/AC2NKY . Results significantly vary between compilers. In almost all cases there is at least one jump generated due to the way comparison with 3 values less than 32 is done. If the number is less than or equal to 32 compiler does a lookup in bitmask indicating which values to skip. Often Clang and MSVC generated a second jump.
terrycody 8y ago
what is the usage of these things?
pkaye 8y ago
What if you are working with unicode?
- loeg 8y ago
  This removes ascii spaces from ascii or ascii-compatible encodings (e.g., utf-8 and others). It doesn't handle the full complexity of unicode spaces, obviously.
zwegner 8y ago
OK, I got nerd-sniped here. You can actually construct the indices for the shuffle fairly easily with PEXT. Basically, you have 6 64-bit masks, each corresponding to a different bit of the index of each byte in the 64-byte vector. So for mask 0, a bit is set in the mask if its index has bit (1 << 0) set, mask 1 has the same but for bit (1 << 1), etc. The masks have a simple pattern, that changes between 1 and 0 bits every (1 << i) bits. So for 3 bits the masks would be: 10101010, 11001100, 11110000. These masks are then extracted with PEXT for all the non-whitespace bytes. What this does is build up, bit by bit, the byte index of every non-whitespace byte, compressed down to the least-significant end, without the indices of whitespace bytes. I wasn't actually able to run this code, since I don't have an AVX-512 machine, but I'm pretty sure it should be faster. I put the code on github if anyone wants to try: https://github.com/zwegner/toys/blob/master/avx512-remove-spaces/avx512vbmi.cpp https://github.com/zwegner/toys/blob/master/avx512-remove-sp... const uint64_t index_masks[6] = { 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0, 0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000, }; const __m512i index_bits[6] = { _mm512_set1_epi8(1), _mm512_set1_epi8(2), _mm512_set1_epi8(4), _mm512_set1_epi8(8), _mm512_set1_epi8(16), _mm512_set1_epi8(32), }; ...later, inside the loop: mask = ~mask; __m512i indices = _mm512_set1_epi8(0); for (size_t index = 0; index < 6; index++) { uint64_t m = _pext_u64(index_masks[index], mask); indices = _mm512_mask_add_epi8(indices, m, indices, index_bits[index]); } output = _mm512_permutexvar_epi8(indices, input);
- nkurz 8y ago
  I'll run it for you on the same machine Wojciech is using and report back shortly. I'm getting a compiler error for your call to _pext_u64(), but I think it's just a matter of adjusting the compiler flags. OK, adding "-march=native" works (was only -mavx512vbmi). Oops, now ./unittest fails: [nate@nuc avx512-remove-spaces]$ ./unittest test 1 gap FAILED; len_ref=63, len=0 input: [ bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789#@] ref: [bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789#@] result: [] Did you maybe flip the args to _pext_u64() like I often do? I'll check back in a few minutes and see if you've committed a fix. Edit: Getting to my bedtime here. Send me email (in profile) if you'd like me to follow up with it tomorrow.
dragontamer 8y ago
I've been nerdsniped as well. I can't say I'm going to go ahead and try and solve it, but the methodology presented in the post seems suboptimal. The best method I personally think would work, is the "compaction algorithm" documented here: http://www.davidespataro.it/cuda-stream-compaction-efficient-implementation/ http://www.davidespataro.it/cuda-stream-compaction-efficient... True, that's a CUDA implementation, but AVX512 is closely related to GPU programmers. Effectively, you calculate the prefix sum of the "matches". The paper the above code is based on is very clear on how this works: http://www.cse.chalmers.se/~uffe/streamcompaction.pdf http://www.cse.chalmers.se/~uffe/streamcompaction.pdf Pay close attention to "figure 1" on page 2. That's the crux of the algorithm. Assuming 8-bit characters, you can generate a prefix-sum in just 6-steps (Each step is a constant, pre-defined byte-shift + Add). A prefix sum is best described by the following picture: https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-Steele_Prefix_Sum.svg https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-... Full Wikipedia page on Prefix Sum: https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum Prefix Sum is just 6-steps for a AVX512 register on 8-bit ints. That generates the full AVX512-space permute (ie: if the prefix sum is 5 for an element, that means that element belongs in index #5)., but AVX512 has "in lane" permutes only. I dunno how many steps you'd need to get a "in lane" permute into a "cross lane" permute... but it doesn't seem too difficult of a problem (and IIRC, I think i read a blogpost about how to convert the in-lane AVX512 permutes into a cross-lane one). I bet that the above sketch of the AVX512 algorithm can be implemented in less than 30 assembly instructions for the full AVX512 / 64-byte space, maybe less than 20. That should definitely run faster than the scalar version. ------- EDIT: Herp-derp. It doesn't seem like VPERMB is affected by AVX Lanes (!!). https://www.felixcloutier.com/x86/vpermb https://www.felixcloutier.com/x86/vpermb So I guess you can just run VPERMB at the end on the calculated prefix-sum. The end. ------- The Stream Compaction algorithm is a very important 1-dimentional work-balancing paradigm in the GPU programming world. It is used to select which rays are still active in a Raytracing scenario (so that all SIMD registers have something to do).
- zwegner 8y ago
  Interesting, I started out thinking along these lines, but once I figured out I could use PEXT, I just went with that. I think this approach needs some tweaks, though. Mainly that the vpermb at the end is the inverse of what we want--the bytes at dense indices get spread out to the sparse indices (it works analogously to gather, but we want scatter). I can't think of a way around this right now... That said, it's an interesting approach. I think the PEXTs would be the bottleneck in my code (looks like there's only one execution unit for them, whereas there's two for the VPADDs), and finding a way to parallelize all the VPADDs could lead to a nice speedup.
Const-me 8y ago
Interesting but his scalar code is slow. When you care about performance, better to implement such algorithm so it reads bytes one by one, but move blocks with memmove when switching from write to skip state. Pathological case (skipping every other character) is slightly slower, but on real data it’s much faster overall. Unfortunately I don’t have AVX512 hardware so I can’t test.
- wmu 8y ago
  I was wondering if you like to contribute better scalar code? I'll be happy to include your (or anybody else) code and then compare different approaches.
  - aqrit 8y ago
    Try some of these :p https://gist.github.com/aqrit/6e73ca6ff52f72a2b121d584745f89f3 https://gist.github.com/aqrit/6e73ca6ff52f72a2b121d584745f89...
    - wmu 8y ago
      Thank you! :)
    - wmu 8y ago
      Thank you again! Take a look: https://github.com/WojciechMula/toys/tree/master/avx512-remove-spaces https://github.com/WojciechMula/toys/tree/master/avx512-remo... Your AVX2 is better in benchmarks than Zach's AVX512VBMI, wow. I have to admit that looked at the code but got lost. :) Will need more time to digest it. However, in despacing English texts and CSV, Zach's variant is still faster.

152 points by pedro84 8y ago

This is really neat, I wonder if there's a way to keep a "remainder" around, kind of like Bresenham's algorithm, so that you can always do aligned reads from memory. The speedup on English text is really good, and I love the exploration into the AVX intrinsics.

BeeOnRope 8y ago
Unless I'm missing something it's the stores that are variably sized and hence become misaligned, not the reads?

jchw 8y ago

I was excited for AVX512 long ago but I've since heard that if you are jamming AVX512 instructions to every core you get a forcibly lower clockrate. In practice this sounds like it'd suggest using an AVX512 algorithm could actually be slower even when it's faster. If that's the case, I wonder what kind of performance gain you'd have to hit to beat a scalar or SSE-based vectorized algorithm.

zwaps 8y ago
Depends on the task and CPU, but especially on smaller machines the slowdown is not so large compared to potentially huge performance gains, ain't it?
zamadatix 8y ago
Depends which AVX512 instructions and how quickly you expect to bounce between AVX and scalar workloads. Generally if you can expect to spend a significant portion of your algorithm time in vector optimized code then the small clock drop isn't enough to erode the throughput gains.
shereadsthenews 8y ago
You also get a lower clock rate from running scalar code on many cores at once. Use of the 512-bit unit only makes the coefficient different. That said, the biggest mystery in this article is why you'd ever want to remove all whitespace from text. Why is that useful?
- taspeotis 8y ago
  I dunno, spam filtering? sig nup now for che ap viag ra And then search for key words like “viagra.”
  - foepys 8y ago
    "Your flight via Graz is leaving on 5/2/2019"
    - dcbadacd 8y ago
      https://en.wikipedia.org/wiki/Scunthorpe_problem https://en.wikipedia.org/wiki/Scunthorpe_problem
- jasonzemos 8y ago
  If one could remove spaces from JSON to create a so-called "Canonical JSON" one could obtain the same digest hash from the same data (even in combination with the hardware accelerated hashing offered by AVX!). Admittedly this is a strange case but I've run into it.
  - jandrese 8y ago
    Isn't this a problem if you're fed these two inputs: {mystring:"Hello World!"} {mystring:"Hello World !"} They aren't the same JSON.
    - marvy 8y ago
      also: {mystring:"HelloWorld!"}
throwaway2048 8y ago
There is also a huge delay for the core to shift into AVX512 mode, so interleaving it into regular non avx512 code can be a huge performance hit.
- BeeOnRope 8y ago
  Well if by huge you mean 10ish microseconds, then yeah. There is also hysteresis built in so the transitions can only occur about once per millisecond. This puts a hard bound on the cost of the transitions themselves of about 1%. So no, I don't think the transitions are a big problem for any throughput case, although if you are counting microseconds for some type of low latency thing then sure it can matter. The bigger problem is usually the frequency reduction.
  - Twirrim 8y ago
    The amount of impact is heavily dependent on the class of CPU you use from Intel (gee, thanks Intel. Awesome way to make optimising code a pain in the arse). Bronze you probably really don't want to do AVX512 unless it's all heavily AVX512. Silver is better, but not great (which is what Cloudflare were using and ran in to). Gold or Platinum you're not likely to see much degradation from using AVX-512, even sparsely.
    - BeeOnRope 8y ago
      Are you talking specifically about the transition penalties which I was referring to? I am not aware of any strong variance in this behavior based on CPU class, and I would be surprised if it existed. I've always measured around 8 to 10 us for these transitions (there may be both a real time and "clock cycles" component to the transition time so it might vary a bit when measured in real time based on the CPU frequency). It sounds to be like you are talking more about AVX-512 downclocking. In any case, if your algorithm can be make heavy and effective use of AVX-512 it's going to be a win on almost any class of chip since you are looking at something like a 2x baseline speedup and more in many cases. If not, then yeah, proceed with caution.
gwern 8y ago
Lemire has criticized this: https://lemire.me/blog/2018/08/13/the-dangers-of-avx-512-throttling-myth-or-reality/ https://lemire.me/blog/2018/08/13/the-dangers-of-avx-512-thr... OP doesn't seem to show any major problems in his microbenchmarking, which is a start.
- wmu 8y ago
  TBH I didn't think about throttling. My (mis)understanding is that a single program which completes in a fraction of second on an almost-idle machine doesn't suffer from AVX512 throttling. Daniel has reviewed this problem in series of posts: - https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-throttling-a-3-impact/ https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-thr... - https://lemire.me/blog/2018/08/25/avx-512-throttling-heavy-instructions-are-maybe-not-so-dangerous/ https://lemire.me/blog/2018/08/25/avx-512-throttling-heavy-i...
  - BeeOnRope 8y ago
    On most chips released to date, AVX-512 always causes a lower frequency (the so-called L1 license) as soon as any instruction uses it: basically the chip needs to drop from the L0 (fastest) license to L1 (middle) before it even starts any AVX-512 (probably to power up the upper lanes of the ALUs, register file, etc). Below L1, there is an even lower frequency tier, L2, which behaves as you say: it doesn't drop to L2 unless there is a sustained use of heavy AVX-512 instructions. On the Cannonlake chip you used, however, the i3-8121U, I don't measure any AVX-512 throttling at all - regardless of what instructions are running, up to and including dense 512-bit FMAs, the chip is running at the full 3.2 GHz (1 active core) or 3.1 GHz (2 active cores) turbo speed at all times. This behavior was common in the past on client parts: e.g., most Skylake client parts run at full speed when using 256-bit AVX/AVX2 operations, but server parts and some higher-end desktop parts based on them had varying speed tiers. All of the initially released SKX (Skylake X) parts were based on the Skylake-SP server part and had the speed tiers (downclocking) for AVX-512, but maybe many or most future client parts won't if CNL is any indication.
    - wmu 8y ago

lostmsu 8y ago

Instead of generating shuffle at runtime, couldn't a table be used for shuffling lower and higher parts of the register separately, then merging the result? Also, for uncommon patterns, the register could be split further to make the shuffle table fit into L1. Also, I am not sure compiler can optimize that continue statement. The non-AVX version might be improved by removing the if alltogether, and replacing dst++ with dst = followed by dst += (src[i] == ' ' || src[i] == '\r' || src[i] == '\n') ? 0 : 1

jsd1982 8y ago
The ternary operator a?b:c is still a conditional operation and may result in a branch instruction, same as an if statement. I wouldn't think it would matter much how exactly the branch condition was spelled in C code. It'll get translated to low level IR and optimized at that level.
- kccqzy 8y ago
  In this case, the GP is having code of the form a ? 0 : 1 which can usually be rewritten as !a Any worthwhile compiler should compile that into one instruction or two, like `setne` or something else.
  - lostmsu 8y ago
    I was hoping for a direct translation to CMOV. Anyway, the assembly has to be analyzed to be sure.
    - Karliss 8y ago
      No need to speculate. https://godbolt.org/z/AC2NKY https://godbolt.org/z/AC2NKY . Results significantly vary between compilers. In almost all cases there is at least one jump generated due to the way comparison with 3 values less than 32 is done. If the number is less than or equal to 32 compiler does a lookup in bitmask indicating which values to skip. Often Clang and MSVC generated a second jump.

terrycody 8y ago

what is the usage of these things?

pkaye 8y ago

What if you are working with unicode?

loeg 8y ago
This removes ascii spaces from ascii or ascii-compatible encodings (e.g., utf-8 and others). It doesn't handle the full complexity of unicode spaces, obviously.

zwegner 8y ago

OK, I got nerd-sniped here. You can actually construct the indices for the shuffle fairly easily with PEXT. Basically, you have 6 64-bit masks, each corresponding to a different bit of the index of each byte in the 64-byte vector. So for mask 0, a bit is set in the mask if its index has bit (1 << 0) set, mask 1 has the same but for bit (1 << 1), etc. The masks have a simple pattern, that changes between 1 and 0 bits every (1 << i) bits. So for 3 bits the masks would be: 10101010, 11001100, 11110000. These masks are then extracted with PEXT for all the non-whitespace bytes. What this does is build up, bit by bit, the byte index of every non-whitespace byte, compressed down to the least-significant end, without the indices of whitespace bytes. I wasn't actually able to run this code, since I don't have an AVX-512 machine, but I'm pretty sure it should be faster. I put the code on github if anyone wants to try: https://github.com/zwegner/toys/blob/master/avx512-remove-spaces/avx512vbmi.cpp https://github.com/zwegner/toys/blob/master/avx512-remove-sp... const uint64_t index_masks[6] = { 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0, 0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000, }; const __m512i index_bits[6] = { _mm512_set1_epi8(1), _mm512_set1_epi8(2), _mm512_set1_epi8(4), _mm512_set1_epi8(8), _mm512_set1_epi8(16), _mm512_set1_epi8(32), }; ...later, inside the loop: mask = ~mask; __m512i indices = _mm512_set1_epi8(0); for (size_t index = 0; index < 6; index++) { uint64_t m = _pext_u64(index_masks[index], mask); indices = _mm512_mask_add_epi8(indices, m, indices, index_bits[index]); } output = _mm512_permutexvar_epi8(indices, input);

nkurz 8y ago
I'll run it for you on the same machine Wojciech is using and report back shortly. I'm getting a compiler error for your call to _pext_u64(), but I think it's just a matter of adjusting the compiler flags. OK, adding "-march=native" works (was only -mavx512vbmi). Oops, now ./unittest fails: [nate@nuc avx512-remove-spaces]$ ./unittest test 1 gap FAILED; len_ref=63, len=0 input: [ bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789#@] ref: [bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789#@] result: [] Did you maybe flip the args to _pext_u64() like I often do? I'll check back in a few minutes and see if you've committed a fix. Edit: Getting to my bedtime here. Send me email (in profile) if you'd like me to follow up with it tomorrow.

dragontamer 8y ago

I've been nerdsniped as well. I can't say I'm going to go ahead and try and solve it, but the methodology presented in the post seems suboptimal. The best method I personally think would work, is the "compaction algorithm" documented here: http://www.davidespataro.it/cuda-stream-compaction-efficient-implementation/ http://www.davidespataro.it/cuda-stream-compaction-efficient... True, that's a CUDA implementation, but AVX512 is closely related to GPU programmers. Effectively, you calculate the prefix sum of the "matches". The paper the above code is based on is very clear on how this works: http://www.cse.chalmers.se/~uffe/streamcompaction.pdf http://www.cse.chalmers.se/~uffe/streamcompaction.pdf Pay close attention to "figure 1" on page 2. That's the crux of the algorithm. Assuming 8-bit characters, you can generate a prefix-sum in just 6-steps (Each step is a constant, pre-defined byte-shift + Add). A prefix sum is best described by the following picture: https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-Steele_Prefix_Sum.svg https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-... Full Wikipedia page on Prefix Sum: https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum Prefix Sum is just 6-steps for a AVX512 register on 8-bit ints. That generates the full AVX512-space permute (ie: if the prefix sum is 5 for an element, that means that element belongs in index #5)., but AVX512 has "in lane" permutes only. I dunno how many steps you'd need to get a "in lane" permute into a "cross lane" permute... but it doesn't seem too difficult of a problem (and IIRC, I think i read a blogpost about how to convert the in-lane AVX512 permutes into a cross-lane one). I bet that the above sketch of the AVX512 algorithm can be implemented in less than 30 assembly instructions for the full AVX512 / 64-byte space, maybe less than 20. That should definitely run faster than the scalar version. ------- EDIT: Herp-derp. It doesn't seem like VPERMB is affected by AVX Lanes (!!). https://www.felixcloutier.com/x86/vpermb https://www.felixcloutier.com/x86/vpermb So I guess you can just run VPERMB at the end on the calculated prefix-sum. The end. ------- The Stream Compaction algorithm is a very important 1-dimentional work-balancing paradigm in the GPU programming world. It is used to select which rays are still active in a Raytracing scenario (so that all SIMD registers have something to do).

zwegner 8y ago
Interesting, I started out thinking along these lines, but once I figured out I could use PEXT, I just went with that. I think this approach needs some tweaks, though. Mainly that the vpermb at the end is the inverse of what we want--the bytes at dense indices get spread out to the sparse indices (it works analogously to gather, but we want scatter). I can't think of a way around this right now... That said, it's an interesting approach. I think the PEXTs would be the bottleneck in my code (looks like there's only one execution unit for them, whereas there's two for the VPADDs), and finding a way to parallelize all the VPADDs could lead to a nice speedup.

Const-me 8y ago

Interesting but his scalar code is slow. When you care about performance, better to implement such algorithm so it reads bytes one by one, but move blocks with memmove when switching from write to skip state. Pathological case (skipping every other character) is slightly slower, but on real data it’s much faster overall. Unfortunately I don’t have AVX512 hardware so I can’t test.

wmu 8y ago
I was wondering if you like to contribute better scalar code? I'll be happy to include your (or anybody else) code and then compare different approaches.
- aqrit 8y ago
  Try some of these :p https://gist.github.com/aqrit/6e73ca6ff52f72a2b121d584745f89f3 https://gist.github.com/aqrit/6e73ca6ff52f72a2b121d584745f89...
  - wmu 8y ago
    Thank you! :)
  - wmu 8y ago
    Thank you again! Take a look: https://github.com/WojciechMula/toys/tree/master/avx512-remove-spaces https://github.com/WojciechMula/toys/tree/master/avx512-remo... Your AVX2 is better in benchmarks than Zach's AVX512VBMI, wow. I have to admit that looked at the code but got lost. :) Will need more time to digest it. However, in despacing English texts and CSV, Zach's variant is still faster.