8 ms·

Removing characters from strings faster with AVX-512

146 points by mdb31 4y ago

mdb31 4y ago
Cool performance enhancement, with an accompanying implementation in a real-world library (https://github.com/lemire/despacer https://github.com/lemire/despacer). Still, what does it signal that vector extensions are required to get better string performance on x86? Wouldn't it be better if Intel invested their AVX transistor budget into simply making existing REPB prefixes a lot faster?
- janwas 4y ago
  Why is a large speedup from vectors surprising? Considering that the energy required for scheduling/dispatching an instruction on OoO cores dwarfs that of the actual operation (add/mul etc), amortizing over multiple elements (=SIMD) is an obvious win.
  - mdb31 4y ago
    Where do I say that the speedup is surprising? My question is whether Intel investing in AVX-512 is wise, given that: -Most existing code is not aware of AVX anyway; -Developers are especially wary of AVX-512, since they expect it to be discontinued soon. Consequently, wouldn't Intel be better off by using the silicon dedicated to AVX-512 to speed up instruction patterns that are actually used?
    - janwas 4y ago
      My point is that vector instructions are fundamentally necessary and thus "what does it signal" evaluates to "nothing surprising". Sure, REP STOSB/MOVSB make for a very compact memset/memcpy, but their performance varies depending on CPU feature flags, so you're going to want multiple codepaths anyway. And vector instructions are vastly more flexible than just those two. Also, I have not met developers who expect AVX-512 to be discontinued (the regrettable ADL situation notwithstanding; that's not a server CPU). AMD is actually adding AVX-512.
      - mdb31 4y ago
        > vector instructions are fundamentally necessary For which percentage of users? > AMD is actually adding AVX-512 Which is irrelevant to in-market support for that instruction set.
        XorNot 4y ago
        Why would it be irrelevant? Even the paucity of availability isn't really a problem - the big winners here are server users in data centers, not desktops or laptops. How much string parsing and munging is happening ingesting big datasets right now? If running a specially optimized function set on part of your fleet reduces utilization, that's direct cost savings you realize. If the AMD is then widening that support base, you're deeply favoring expanding usage while you scale up.
        _rtld_global_ro 4y ago
        Given Intel's AVX extension could cause silent failures on servers (very high work load for prolonged time, compare to end user computers), I'm not sure it would be a big win for servers either: https://arxiv.org/pdf/2102.11245.pdf https://arxiv.org/pdf/2102.11245.pdf.
        jcranmer 4y ago
        I'm downvoting you because the assertion you're implying--that use of AVX increases soft failure rates more than using non-AVX instructions would--is not sustained by the source you use as reference.
        tialaramex 4y ago
        Indeed, I'd summarise that source as "At Facebook sometimes weird stuff happens. We postulate it's not because of all the buggy code written by Software Engineers like us, it must be hardware. As well as lots of speculation about hypothetical widespread problems that would show we're actually not writing buggy software, here's a single concrete example where it was hardware". If anything I'd say that Core 59 is one of those exceptions that prove the rule. This is such a rare phenomenon that when it does happen you can do the work to pin it down and say yup, this CPU is busted - if it was really commonplace you'd constantly trip over these bugs and get nowhere. There probably isn't really, as that paper claims, a "systemic issue across generations" except that those generations are all running Facebook's buggy code.
    - mhh__ 4y ago
      AVX-512 is not going to be discontinued. Intel's reticence/struggling with having it on desktop is irritating but it's here to stay on servers for a long time. Writing code for a specific SIMD instruction set is non-trivial, but most code will get some benefit by being compiled for the right ISA. You don't get the really fancy instructions because the pattern matching in the compiler isn't very intelligent but quite a lot of stuff is going to benefit by magic. Even without cutting people without some AVX off, you can have a fast/slow path fairly easily.
- 37ef_ced3 4y ago
  AVX-512 is an elegant, powerful, flexible set of masked vector instructions that is useful for many purposes. For example, low-cost neural net inference (https://NN-512.com https://NN-512.com). To suggest that Intel and AMD should instead make "existing REPB prefixes a lot faster" is missing the big picture. The masked compression instructions (one of which is used in Lemire's article) are endlessly useful, not just for stripping spaces out of a string!
  - mhh__ 4y ago
    Many people seem to think AVX-512 is just wider AVX, which is a shame. NN-512 is cool. I think the Go code is pretty ugly but I like the concept of the compiler a lot.
  - deleted 4y ago
    [deleted]
- ip26 4y ago
  Is it generally possible to convert rep str sequences to AVX? Could the hardware or compiler already be doing this? AVX is just the SIMD unit. I would argue the transistors were spent on SIMD, and the hitch is simply the best way to send str commands to the SIMD hardware.
  - nwmcsween 4y ago
    Why? IIRC something like 99% of string operations are on 20 chars or less. If you're hitting bottlenecks then optimize.
    - ip26 4y ago
      If you are arguing most string ops have just a few chars and therefore don’t use vectors… why do we need to spend silicon enhancing rep prefix in the first place?
gslin 4y ago
A problem is slowing down the CPU frequency significantly when AVX-512 is involved, e.g. https://en.wikichip.org/wiki/intel/xeon_gold/6262v https://en.wikichip.org/wiki/intel/xeon_gold/6262v this, which usually cancels out the benefit in the Real World (tm).
- mhh__ 4y ago
  Unless someone has data for the latest Intel chips (i.e. sapphire rapids) showing the opposite I'm inclined to think this is a meme from 2016/7 that needs to go the way of the dodo.
  - Twirrim 4y ago
    It was largely wrong then, too. Cloudflare, who really kicked off a large amount of the fuss, had "Bronze" class Xeon chips, that weren't designed or marketed for what they were attempting to use them for. They were only ever intended for small business stuff. Not large scale high performance operations. Their performance downclock for AVX-512 is way, way higher on Bronze.
    - NavinF 4y ago
      Weren’t those chips $10k each back then? Hardly anyone got gold Xeons.
      - Twirrim 4y ago
        Not even close. The blog post was 2017. Actually, I stand corrected, after double checking, Cloudflare were using Silver. Entry level data centre chips, instead of small business chips. Still not the kind of chips you'd buy for high performance infrastructure, and not intended to be used for such. Xeon Silver 4116s hit the market at $1,002.00. The Golds were $1,221.00. The performance differences are quite significant. For something that'll be in service for ~3-5 years, $200 is absolutely trivial by way of a per-chip increase. It's firmly in the "false economy" territory to be skimping on your chip costs. It's a bit more understandable in smaller businesses, but you just don't do it when you're operating at scale. Also remember: at the scales that Cloudflare are purchasing at, they won't be paying RRP. They'll be getting tidy discounts.
jquery 4y ago
I prefer AMDs approach that allows them to put more cores on the die instead of supporting a rarely used instruction set.
- fulafel 4y ago
  Zen 4 is rumored to have AVX512. AMD has in the past had support for wide SIMD instructions with half internal width implementation, so the die area requirements and instruction set support are somewhat orthogonal. There's many other interesting things in AVX512 besides the wide vectors.
  - pclmulqdq 4y ago
    AVX-512 finally gets a lot of things right about vector manipulation and plugged a lot of the holes in the instruction set. Part of me is upset that it came with the "512" name - they could have called it "AVX3" or "AVX Version 2" (since it's intel and they love confusing names).
    - atq2119 4y ago
      Agreed. Though I feel that for the most part, size-agnostic vector instructions a la SVE would be the way to go.
    - adrian_b 4y ago
      Actually AVX-512 predates AVX and Sandy Bridge. The original name of AVX-512 was "Larrabee New Instructions". Unlike with the other Intel instruction set extensions, the team which defined the "Larrabee New Instructions" included graphics experts hired from outside Intel, which is probably the reason why AVX-512 is a better SIMD instruction set than all the other designed by Intel. Unfortunately, Sandy Bridge (2011), instead of implementing a scaled-down version of the "Larrabee New Instructions", implemented the significantly worse AVX instruction set. A couple of years later, Intel Haswell (2013), added to AVX a few of the extra instructions of the "Larrabee New Instructions", e.g. fused multiply-add and memory gather instructions. The Haswell AVX2 was thus a great improvement over the Sandy Bridge AVX, but it remained far from having all the features that had already existed in LRBni (made public in 2009). After the Intel Larrabee project flopped, LRBni passed through a few name changes, until 2016, when it was renamed to AVX-512 after a small change in the binary encoding of the instructions. I also dislike the name "AVX-512", but my reason is different. "AVX-512" is made to sound like it is an evolution of AVX, while the truth is the other way around, AVX was an involution of LRBni, whose purpose was to maximize the profits of Intel by minimizing the CPU manufacturing costs, taking advantage of the fact that the competition was weak, so the buyers had to be content with the crippled Intel CPUs with AVX, because nobody offered anything better. The existence of AVX has caused a lot of additional work for many programmers, who had to write programs much more complex than it would have been possible with LRBni, which had from the beginning features designed to allow simplified programming, e.g. the mask registers that allow much simpler prologues and epilogues for loops and both gather loads and scatter stores for accessing the memory.
protoman3000 4y ago
Please correct me if I'm wrong, but wouldn't we normally scale these things instead on a GPU?
- curling_grad 4y ago
  Maybe because of IO costs?
- raphlinus 4y ago
  The short answer is no, but the long answer is that this is a very complex tradeoff space. Going forward, we may see more of these types of tasks moving to GPU, but for the moment it is generally not a good choice. The GPU is incredible at raw throughput, and this particular problem can actually implemented fairly straightforwardly (it's a stream compaction, which in turn can be expressed in terms of prefix sum). However, where the GPU absolutely falls down is when you want to interleave CPU and GPU computations. To give round numbers, the roundtrip latency is on the order of 100µs, and even aside from that, the memcpy back and forth between host and device memory might actually be slower than just solving the problem on the CPU. So you only win when the strings are very large, again using round numbers about a megabyte. Things change if you are able to pipeline a lot of useful computation on the GPU. This is an area of active research (including my own). Aaron Hsu has been doing groundbreaking work implementing an entire compiler on the GPU, and there's more recent work[1], implemented in Futhark, that suggests that that this approach is promising. I have a paper in the pipeline that includes an extraordinarily high performance (~12G elements/s) GPU implementation of the parentheses matching problem, which is the heart of parsing. If anyone would like to review a draft and provide comments, please add a comment to the GitHub issue[2] I'm using to track this. It's due very soon and I'm on a tight timeline to get all the measurements done, so actionable suggestions on how to improve the text would be most welcome. [1]: https://theses.liacs.nl/pdf/2020-2021-VoetterRobin.pdf https://theses.liacs.nl/pdf/2020-2021-VoetterRobin.pdf [2]: https://github.com/raphlinus/raphlinus.github.io/issues/66#issuecomment-1114035653 https://github.com/raphlinus/raphlinus.github.io/issues/66#i...
  - mwcampbell 4y ago
    > To give round numbers, the roundtrip latency is on the order of 100µs I can't help but notice that, at least in my experience on Windows, this is the same order of magnitude as for inter-process communication on the local machine. Tangent: That latency was my nemesis as a Windows screen reader developer; the platform accessibility APIs weren't well designed to take it into account. Windows 11 finally has a good solution for this problem (yes, I helped implement that while I was at Microsoft).
Andoryuuta 4y ago
Intel is removing AVX-512 support from their newer CPU's (Alder Lake +). :/ https://www.igorslab.de/en/intel-deactivated-avx-512-on-alder-lake-but-fully-questionable-interpretation-of-efficiency-news-editorial/ https://www.igorslab.de/en/intel-deactivated-avx-512-on-alde...
- mhh__ 4y ago
  You're forgetting about server CPUs, and we don't know yet about Raptor Lake.
  - Andoryuuta 4y ago
    Ah, yep. You're totally right. I didn't even consider server CPUs. Also, I thought I read somewhere that it was for all consumer CPUs starting at Alder Lake, but I have no idea where, so I could be entirely wrong. :)
- SemanticStrengh 4y ago
  And zen 4 is rumoured to add support for it ^^
- electricshampo1 4y ago
  This is only on the client side; server still has and will have AVX512 for the foreseeable future.
- PragmaticPulp 4y ago
  Server and workstation chips still have AVX-512. It’s only unsupported on CPUs with smaller E(fficeincy) cores. AVX-512 was never really supported in newer consumer CPUs with heterogeneous architecture. These CPUs have a mix of powerful cores and efficiency cores. The AVX-512 instructions were never added to the efficiency cores because it would use way too much die space and defeat the purpose of efficiency cores. There was previously a hidden option to disable the efficiency cores and enable AVX-512 on the remaining power cores, but the number of workloads that would warrant turning off a lot of your cores to speed up AVX-512 calculations is virtually non-existent in the consumer world (where these cheap CPUs are targeted). The whole journalism controversy around AVX-512 has been a bit of a joke because many of the same journalists tried to generate controversy when AVX-512 was first introduced and they realized that AVX-512 code would reduce the CPU clock speed. There were numerous articles about turning off AVX-512 on previous generation CPUs to avoid this downclocking and to make overclocks more stable.
gfody 4y ago
there's more whitespace above 0x20 https://en.m.wikipedia.org/wiki/Whitespace_character#Unicode https://en.m.wikipedia.org/wiki/Whitespace_character#Unicode
- brrrrrm 4y ago
  The complication involved with UTF-8 encoded space removal is immense and likely quite far out of scope.
steve76 4y ago
watmough 4y ago
This is really cool. I just got through doing some work with vectorization. On the simplest workload I have, splitting a 3 MByte text file into lines, writing a pointer to each string to an array, GCC will not vectorize the naive loop, though ICC might I guess. With simple vectorization to AVX512 (64 unsigned chars in a vector), finding all the line breaks goes from 1.3 msec to 0.1 msec, so a little better than a 10x speedup, still just on the one core, which keeps things simple. I was using Agner Fog's VCL 2, Apache licensed C++ Vector Class Library. It's super easy.
bertr4nd 4y ago
I love Daniel’s vectorized string processing posts. There’s always some clever trickery that’s hard for a guy like me (who mostly uses vector extensions for ML kernels) to get quickly. I found myself wondering if one could create a domain-specific language for specifying string processing tasks, and then automate some of the tricks with a compiler (possibly with human-specified optimization annotations). Halide did this sort of thing for image processing (and ML via TVM to some extent) and it was a pretty significant success.
tedunangst 4y ago
What would be a practical application of this? The linked post mentions a trim like operation, but in practice I only want to remove white space from the ends, not the interior of the string, and finding the ends is basically the whole problem. Or maybe I want to compress some json, but a simple approach won't work because there can be spaces inside string values which must be preserved.
- jandrewrogers 4y ago
  I agree that the whitespace in text example seems a bit contrived but I've done similar types of byte elision operations on binary streams (e.g. for compression purposes), which this could be trivially adapted to.
brrrrrm 4y ago
What's the generated assembly look like? I suspect clang isn't smart enough to store things into registers. The latency of VPCOMPRESSB seems quite high (according to the table here at least https://uops.info/table.html https://uops.info/table.html), so you'll probably want to induce a bit more pipelining by manually unrolling into the register variant. I don't have an AVX512 machine with VBMI2, but here's what my untested code might look like: __m512i spaces = _mm512_set1_epi8(' '); size_t i = 0; for (; i + (64 * 4 - 1) < howmany; i += 64 * 4) { // 4 input regs, 4 output regs, you can actually do up to 8 because there are 8 mask registers __m512i in0 = _mm512_loadu_si512(bytes + i); __m512i in1 = _mm512_loadu_si512(bytes + i + 64); __m512i in2 = _mm512_loadu_si512(bytes + i + 128); __m512i in3 = _mm512_loadu_si512(bytes + i + 192); __mmask64 mask0 = _mm512_cmpgt_epi8_mask (in0, spaces); __mmask64 mask1 = _mm512_cmpgt_epi8_mask (in1, spaces); __mmask64 mask2 = _mm512_cmpgt_epi8_mask (in2, spaces); __mmask64 mask3 = _mm512_cmpgt_epi8_mask (in3, spaces); auto reg0 = _mm512_maskz_compress_epi8 (mask0, x); auto reg1 = _mm512_maskz_compress_epi8 (mask1, x); auto reg2 = _mm512_maskz_compress_epi8 (mask2, x); auto reg3 = _mm512_maskz_compress_epi8 (mask3, x); _mm512_storeu_si512(bytes + pos, reg0); pos += _popcnt64(mask0); _mm512_storeu_si512(bytes + pos, reg1); pos += _popcnt64(mask1); _mm512_storeu_si512(bytes + pos, reg2); pos += _popcnt64(mask2); _mm512_storeu_si512(bytes + pos, reg3); pos += _popcnt64(mask3); } // old code can go here, since it handles a smaller size well You can probably do better by chunking up the input and using temporary memory (coalesced at the end).
GICodeWarrior 4y ago
Here's a list of processors supporting AVX-512: https://ark.intel.com/content/www/us/en/ark/search/featurefilter.html?productType=873&1_Filter-InstructionSetExtensions=3533 https://ark.intel.com/content/www/us/en/ark/search/featurefi... The author mentions it's difficult to identify which features are supported on which processor, but ark.intel.com has a quite good catalog.

146 points by mdb31 4y ago

Cool performance enhancement, with an accompanying implementation in a real-world library (https://github.com/lemire/despacer https://github.com/lemire/despacer). Still, what does it signal that vector extensions are required to get better string performance on x86? Wouldn't it be better if Intel invested their AVX transistor budget into simply making existing REPB prefixes a lot faster?

janwas 4y ago
Why is a large speedup from vectors surprising? Considering that the energy required for scheduling/dispatching an instruction on OoO cores dwarfs that of the actual operation (add/mul etc), amortizing over multiple elements (=SIMD) is an obvious win.
- mdb31 4y ago
  Where do I say that the speedup is surprising? My question is whether Intel investing in AVX-512 is wise, given that: -Most existing code is not aware of AVX anyway; -Developers are especially wary of AVX-512, since they expect it to be discontinued soon. Consequently, wouldn't Intel be better off by using the silicon dedicated to AVX-512 to speed up instruction patterns that are actually used?
  - janwas 4y ago
    My point is that vector instructions are fundamentally necessary and thus "what does it signal" evaluates to "nothing surprising". Sure, REP STOSB/MOVSB make for a very compact memset/memcpy, but their performance varies depending on CPU feature flags, so you're going to want multiple codepaths anyway. And vector instructions are vastly more flexible than just those two. Also, I have not met developers who expect AVX-512 to be discontinued (the regrettable ADL situation notwithstanding; that's not a server CPU). AMD is actually adding AVX-512.
    - mdb31 4y ago
      > vector instructions are fundamentally necessary For which percentage of users? > AMD is actually adding AVX-512 Which is irrelevant to in-market support for that instruction set.
      - XorNot 4y ago
        Why would it be irrelevant? Even the paucity of availability isn't really a problem - the big winners here are server users in data centers, not desktops or laptops. How much string parsing and munging is happening ingesting big datasets right now? If running a specially optimized function set on part of your fleet reduces utilization, that's direct cost savings you realize. If the AMD is then widening that support base, you're deeply favoring expanding usage while you scale up.
        _rtld_global_ro 4y ago
        Given Intel's AVX extension could cause silent failures on servers (very high work load for prolonged time, compare to end user computers), I'm not sure it would be a big win for servers either: https://arxiv.org/pdf/2102.11245.pdf https://arxiv.org/pdf/2102.11245.pdf.
        jcranmer 4y ago
        I'm downvoting you because the assertion you're implying--that use of AVX increases soft failure rates more than using non-AVX instructions would--is not sustained by the source you use as reference.
        tialaramex 4y ago
        Indeed, I'd summarise that source as "At Facebook sometimes weird stuff happens. We postulate it's not because of all the buggy code written by Software Engineers like us, it must be hardware. As well as lots of speculation about hypothetical widespread problems that would show we're actually not writing buggy software, here's a single concrete example where it was hardware". If anything I'd say that Core 59 is one of those exceptions that prove the rule. This is such a rare phenomenon that when it does happen you can do the work to pin it down and say yup, this CPU is busted - if it was really commonplace you'd constantly trip over these bugs and get nowhere. There probably isn't really, as that paper claims, a "systemic issue across generations" except that those generations are all running Facebook's buggy code.
  - mhh__ 4y ago
    AVX-512 is not going to be discontinued. Intel's reticence/struggling with having it on desktop is irritating but it's here to stay on servers for a long time. Writing code for a specific SIMD instruction set is non-trivial, but most code will get some benefit by being compiled for the right ISA. You don't get the really fancy instructions because the pattern matching in the compiler isn't very intelligent but quite a lot of stuff is going to benefit by magic. Even without cutting people without some AVX off, you can have a fast/slow path fairly easily.
37ef_ced3 4y ago
AVX-512 is an elegant, powerful, flexible set of masked vector instructions that is useful for many purposes. For example, low-cost neural net inference (https://NN-512.com https://NN-512.com). To suggest that Intel and AMD should instead make "existing REPB prefixes a lot faster" is missing the big picture. The masked compression instructions (one of which is used in Lemire's article) are endlessly useful, not just for stripping spaces out of a string!
- mhh__ 4y ago
  Many people seem to think AVX-512 is just wider AVX, which is a shame. NN-512 is cool. I think the Go code is pretty ugly but I like the concept of the compiler a lot.
- deleted 4y ago
  [deleted]
ip26 4y ago
Is it generally possible to convert rep str sequences to AVX? Could the hardware or compiler already be doing this? AVX is just the SIMD unit. I would argue the transistors were spent on SIMD, and the hitch is simply the best way to send str commands to the SIMD hardware.
- nwmcsween 4y ago
  Why? IIRC something like 99% of string operations are on 20 chars or less. If you're hitting bottlenecks then optimize.
  - ip26 4y ago
    If you are arguing most string ops have just a few chars and therefore don’t use vectors… why do we need to spend silicon enhancing rep prefix in the first place?

gslin 4y ago

A problem is slowing down the CPU frequency significantly when AVX-512 is involved, e.g. https://en.wikichip.org/wiki/intel/xeon_gold/6262v https://en.wikichip.org/wiki/intel/xeon_gold/6262v this, which usually cancels out the benefit in the Real World (tm).

mhh__ 4y ago
Unless someone has data for the latest Intel chips (i.e. sapphire rapids) showing the opposite I'm inclined to think this is a meme from 2016/7 that needs to go the way of the dodo.
- Twirrim 4y ago
  It was largely wrong then, too. Cloudflare, who really kicked off a large amount of the fuss, had "Bronze" class Xeon chips, that weren't designed or marketed for what they were attempting to use them for. They were only ever intended for small business stuff. Not large scale high performance operations. Their performance downclock for AVX-512 is way, way higher on Bronze.
  - NavinF 4y ago
    Weren’t those chips $10k each back then? Hardly anyone got gold Xeons.
    - Twirrim 4y ago
      Not even close. The blog post was 2017. Actually, I stand corrected, after double checking, Cloudflare were using Silver. Entry level data centre chips, instead of small business chips. Still not the kind of chips you'd buy for high performance infrastructure, and not intended to be used for such. Xeon Silver 4116s hit the market at $1,002.00. The Golds were $1,221.00. The performance differences are quite significant. For something that'll be in service for ~3-5 years, $200 is absolutely trivial by way of a per-chip increase. It's firmly in the "false economy" territory to be skimping on your chip costs. It's a bit more understandable in smaller businesses, but you just don't do it when you're operating at scale. Also remember: at the scales that Cloudflare are purchasing at, they won't be paying RRP. They'll be getting tidy discounts.

jquery 4y ago

I prefer AMDs approach that allows them to put more cores on the die instead of supporting a rarely used instruction set.

fulafel 4y ago
Zen 4 is rumored to have AVX512. AMD has in the past had support for wide SIMD instructions with half internal width implementation, so the die area requirements and instruction set support are somewhat orthogonal. There's many other interesting things in AVX512 besides the wide vectors.
- pclmulqdq 4y ago
  AVX-512 finally gets a lot of things right about vector manipulation and plugged a lot of the holes in the instruction set. Part of me is upset that it came with the "512" name - they could have called it "AVX3" or "AVX Version 2" (since it's intel and they love confusing names).
  - atq2119 4y ago
    Agreed. Though I feel that for the most part, size-agnostic vector instructions a la SVE would be the way to go.
  - adrian_b 4y ago
    Actually AVX-512 predates AVX and Sandy Bridge. The original name of AVX-512 was "Larrabee New Instructions". Unlike with the other Intel instruction set extensions, the team which defined the "Larrabee New Instructions" included graphics experts hired from outside Intel, which is probably the reason why AVX-512 is a better SIMD instruction set than all the other designed by Intel. Unfortunately, Sandy Bridge (2011), instead of implementing a scaled-down version of the "Larrabee New Instructions", implemented the significantly worse AVX instruction set. A couple of years later, Intel Haswell (2013), added to AVX a few of the extra instructions of the "Larrabee New Instructions", e.g. fused multiply-add and memory gather instructions. The Haswell AVX2 was thus a great improvement over the Sandy Bridge AVX, but it remained far from having all the features that had already existed in LRBni (made public in 2009). After the Intel Larrabee project flopped, LRBni passed through a few name changes, until 2016, when it was renamed to AVX-512 after a small change in the binary encoding of the instructions. I also dislike the name "AVX-512", but my reason is different. "AVX-512" is made to sound like it is an evolution of AVX, while the truth is the other way around, AVX was an involution of LRBni, whose purpose was to maximize the profits of Intel by minimizing the CPU manufacturing costs, taking advantage of the fact that the competition was weak, so the buyers had to be content with the crippled Intel CPUs with AVX, because nobody offered anything better. The existence of AVX has caused a lot of additional work for many programmers, who had to write programs much more complex than it would have been possible with LRBni, which had from the beginning features designed to allow simplified programming, e.g. the mask registers that allow much simpler prologues and epilogues for loops and both gather loads and scatter stores for accessing the memory.

protoman3000 4y ago

Please correct me if I'm wrong, but wouldn't we normally scale these things instead on a GPU?

curling_grad 4y ago
Maybe because of IO costs?
raphlinus 4y ago
The short answer is no, but the long answer is that this is a very complex tradeoff space. Going forward, we may see more of these types of tasks moving to GPU, but for the moment it is generally not a good choice. The GPU is incredible at raw throughput, and this particular problem can actually implemented fairly straightforwardly (it's a stream compaction, which in turn can be expressed in terms of prefix sum). However, where the GPU absolutely falls down is when you want to interleave CPU and GPU computations. To give round numbers, the roundtrip latency is on the order of 100µs, and even aside from that, the memcpy back and forth between host and device memory might actually be slower than just solving the problem on the CPU. So you only win when the strings are very large, again using round numbers about a megabyte. Things change if you are able to pipeline a lot of useful computation on the GPU. This is an area of active research (including my own). Aaron Hsu has been doing groundbreaking work implementing an entire compiler on the GPU, and there's more recent work[1], implemented in Futhark, that suggests that that this approach is promising. I have a paper in the pipeline that includes an extraordinarily high performance (~12G elements/s) GPU implementation of the parentheses matching problem, which is the heart of parsing. If anyone would like to review a draft and provide comments, please add a comment to the GitHub issue[2] I'm using to track this. It's due very soon and I'm on a tight timeline to get all the measurements done, so actionable suggestions on how to improve the text would be most welcome. [1]: https://theses.liacs.nl/pdf/2020-2021-VoetterRobin.pdf https://theses.liacs.nl/pdf/2020-2021-VoetterRobin.pdf [2]: https://github.com/raphlinus/raphlinus.github.io/issues/66#issuecomment-1114035653 https://github.com/raphlinus/raphlinus.github.io/issues/66#i...
- mwcampbell 4y ago
  > To give round numbers, the roundtrip latency is on the order of 100µs I can't help but notice that, at least in my experience on Windows, this is the same order of magnitude as for inter-process communication on the local machine. Tangent: That latency was my nemesis as a Windows screen reader developer; the platform accessibility APIs weren't well designed to take it into account. Windows 11 finally has a good solution for this problem (yes, I helped implement that while I was at Microsoft).

Andoryuuta 4y ago

Intel is removing AVX-512 support from their newer CPU's (Alder Lake +). :/ https://www.igorslab.de/en/intel-deactivated-avx-512-on-alder-lake-but-fully-questionable-interpretation-of-efficiency-news-editorial/ https://www.igorslab.de/en/intel-deactivated-avx-512-on-alde...

mhh__ 4y ago
You're forgetting about server CPUs, and we don't know yet about Raptor Lake.
- Andoryuuta 4y ago
  Ah, yep. You're totally right. I didn't even consider server CPUs. Also, I thought I read somewhere that it was for all consumer CPUs starting at Alder Lake, but I have no idea where, so I could be entirely wrong. :)
SemanticStrengh 4y ago
And zen 4 is rumoured to add support for it ^^
electricshampo1 4y ago
This is only on the client side; server still has and will have AVX512 for the foreseeable future.
PragmaticPulp 4y ago
Server and workstation chips still have AVX-512. It’s only unsupported on CPUs with smaller E(fficeincy) cores. AVX-512 was never really supported in newer consumer CPUs with heterogeneous architecture. These CPUs have a mix of powerful cores and efficiency cores. The AVX-512 instructions were never added to the efficiency cores because it would use way too much die space and defeat the purpose of efficiency cores. There was previously a hidden option to disable the efficiency cores and enable AVX-512 on the remaining power cores, but the number of workloads that would warrant turning off a lot of your cores to speed up AVX-512 calculations is virtually non-existent in the consumer world (where these cheap CPUs are targeted). The whole journalism controversy around AVX-512 has been a bit of a joke because many of the same journalists tried to generate controversy when AVX-512 was first introduced and they realized that AVX-512 code would reduce the CPU clock speed. There were numerous articles about turning off AVX-512 on previous generation CPUs to avoid this downclocking and to make overclocks more stable.

gfody 4y ago

there's more whitespace above 0x20 https://en.m.wikipedia.org/wiki/Whitespace_character#Unicode https://en.m.wikipedia.org/wiki/Whitespace_character#Unicode

brrrrrm 4y ago
The complication involved with UTF-8 encoded space removal is immense and likely quite far out of scope.

steve76 4y ago

watmough 4y ago

This is really cool. I just got through doing some work with vectorization. On the simplest workload I have, splitting a 3 MByte text file into lines, writing a pointer to each string to an array, GCC will not vectorize the naive loop, though ICC might I guess. With simple vectorization to AVX512 (64 unsigned chars in a vector), finding all the line breaks goes from 1.3 msec to 0.1 msec, so a little better than a 10x speedup, still just on the one core, which keeps things simple. I was using Agner Fog's VCL 2, Apache licensed C++ Vector Class Library. It's super easy.

bertr4nd 4y ago

I love Daniel’s vectorized string processing posts. There’s always some clever trickery that’s hard for a guy like me (who mostly uses vector extensions for ML kernels) to get quickly. I found myself wondering if one could create a domain-specific language for specifying string processing tasks, and then automate some of the tricks with a compiler (possibly with human-specified optimization annotations). Halide did this sort of thing for image processing (and ML via TVM to some extent) and it was a pretty significant success.

tedunangst 4y ago

What would be a practical application of this? The linked post mentions a trim like operation, but in practice I only want to remove white space from the ends, not the interior of the string, and finding the ends is basically the whole problem. Or maybe I want to compress some json, but a simple approach won't work because there can be spaces inside string values which must be preserved.

jandrewrogers 4y ago
I agree that the whitespace in text example seems a bit contrived but I've done similar types of byte elision operations on binary streams (e.g. for compression purposes), which this could be trivially adapted to.

brrrrrm 4y ago

What's the generated assembly look like? I suspect clang isn't smart enough to store things into registers. The latency of VPCOMPRESSB seems quite high (according to the table here at least https://uops.info/table.html https://uops.info/table.html), so you'll probably want to induce a bit more pipelining by manually unrolling into the register variant. I don't have an AVX512 machine with VBMI2, but here's what my untested code might look like: __m512i spaces = _mm512_set1_epi8(' '); size_t i = 0; for (; i + (64 * 4 - 1) < howmany; i += 64 * 4) { // 4 input regs, 4 output regs, you can actually do up to 8 because there are 8 mask registers __m512i in0 = _mm512_loadu_si512(bytes + i); __m512i in1 = _mm512_loadu_si512(bytes + i + 64); __m512i in2 = _mm512_loadu_si512(bytes + i + 128); __m512i in3 = _mm512_loadu_si512(bytes + i + 192); __mmask64 mask0 = _mm512_cmpgt_epi8_mask (in0, spaces); __mmask64 mask1 = _mm512_cmpgt_epi8_mask (in1, spaces); __mmask64 mask2 = _mm512_cmpgt_epi8_mask (in2, spaces); __mmask64 mask3 = _mm512_cmpgt_epi8_mask (in3, spaces); auto reg0 = _mm512_maskz_compress_epi8 (mask0, x); auto reg1 = _mm512_maskz_compress_epi8 (mask1, x); auto reg2 = _mm512_maskz_compress_epi8 (mask2, x); auto reg3 = _mm512_maskz_compress_epi8 (mask3, x); _mm512_storeu_si512(bytes + pos, reg0); pos += _popcnt64(mask0); _mm512_storeu_si512(bytes + pos, reg1); pos += _popcnt64(mask1); _mm512_storeu_si512(bytes + pos, reg2); pos += _popcnt64(mask2); _mm512_storeu_si512(bytes + pos, reg3); pos += _popcnt64(mask3); } // old code can go here, since it handles a smaller size well You can probably do better by chunking up the input and using temporary memory (coalesced at the end).

GICodeWarrior 4y ago

Here's a list of processors supporting AVX-512: https://ark.intel.com/content/www/us/en/ark/search/featurefilter.html?productType=873&1_Filter-InstructionSetExtensions=3533 https://ark.intel.com/content/www/us/en/ark/search/featurefi... The author mentions it's difficult to identify which features are supported on which processor, but ark.intel.com has a quite good catalog.