https://lemire.me/blog/2023/03/10/trimming-spaces-from-strings-faster-with-sve-on-an-amazon-graviton-3-processor/ Skip to content Daniel Lemire's blog Daniel Lemire is a computer science professor at the Data Science Laboratory of the Universite du Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering. He is a techno-optimist and a free-speech advocate. Menu and widgets * My home page * My papers * My software Subscribe Join over 12,500 subscribers: Email Address [ ] [ ] [Subscribe by email] You can also follow this blog on telegram. You can find me on twitter as @lemire or on Mastodon. Search for: [ ] [Search] Support my work! I do not accept any advertisement. However, you can you can sponsor my open-source work on GitHub. Recent Posts * Science and Technology links (March 11 2023) * Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor * Float-parsing benchmark: Regular Visual Studio, ClangCL and Linux GCC * ARM vs Intel on Amazon's cloud: A URL Parsing Benchmark * Regular Visual Studio versus ClangCL Recent Comments * Daniel Lemire on Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor * Daniel Lemire on Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor * Evan on Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor * Evan on Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor * Daniel Lemire on Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor Pages * A short history of technology * About me * Book recommendations * Cognitive biases * Interviews and talks * My bets * My favorite articles * My favorite quotes * My readers * My sayings * Predictions * Privacy Policy * Recommended video games * Terms of use * Write good papers Archives Archives [Select Month ] Boring stuff * Log in * Entries feed * Comments feed * WordPress.org Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor Programmers sometimes need to trim, or remove, characters, such as spaces from strings. It might be a surprising expensive task. In C/ C++, the following function is efficient: size_t trimspaces(const char *s, size_t len, char *out) { char * init_out{out}; for(size_t i = 0; i < len; i++) { *out = s[i]; out += (s[i] != ' '); } return out - init_out; } Basically, we write all characters from the input, but we only increment the pointer if the input is not a space. Amazon makes available new ARM-based systems relying on their Graviton 3 processors. These processors support advanced instructions called "SVE". One very nice family of instructions to 'compact' values (effectively, remove unwanted values). I put it to good use when filtering out integer values from arrays. Unfortunately, the SVE compact instructions cannot be directly applied to the problem of pruning spaces in strings, because they only operate on larger words (e.g., 32-bit words). But, fortunately, it is possible to load bytes directly into 32-bit values so that each byte value occupies 32-bit in memory using intrinsics functions such as svld1sb_u32. As you would expect, you can also do the reverse, and take an array of 32-bit values, and automatically convert it to a byte array (e.g., using svst1b_u32). Thus I can take my byte array (a string), load it into temporary 32-bit vectors, prune these vectors, and then store the result as a byte array, back to a string. The following C code is a reasonable implementation of this idea: size_t sve_trimspaces(const char *s, size_t len, char *out) { uint8_t *out8 = reinterpret_cast(out); size_t i = 0; for (; i + svcntw() <= len; i += svcntw()) { svuint32_t input = svld1sb_u32(svptrue_b32(), (const int8_t *)s + i); svbool_t matches = svcmpne_n_u32(svptrue_b32(), input, 32); svuint32_t compressed = svcompact_u32(matches, input); svst1b_u32(svptrue_b32(), out8, compressed); out8 += svcntp_b32(svptrue_b32(), matches); } if (i < len) { svbool_t read_mask = svwhilelt_b32(i, len); svuint32_t input = svld1sb_u32(read_mask, (const int8_t *)s + i); svbool_t matches = svcmpne_n_u32(read_mask, input, 32); svuint32_t compressed = svcompact_u32(matches, input); svst1b_u32(read_mask, out8, compressed); out8 += svcntp_b32(read_mask, matches); } return out8 - reinterpret_cast(out); } Is it faster? Using GCC 12 on a Graviton 3, I get that the SVE approach is 3.6 times faster and it uses 6 times fewer instructions. The SVE code is not six times faster, because it is retiring fewer instructions per cycle. My code is available. conventional code 1.8 cycles/bytes 7 instructions/byte SVE code 0.5 cycles/bytes 1.1 instructions/byte Published by [2ca999] Daniel Lemire A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire Posted on March 10, 2023March 13, 2023Author Daniel LemireCategories 10 thoughts on "Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor" 1. [439756] Bill says: March 13, 2023 at 2:28 pm I wonder if it would speed up Unicode whitespace removal or could be twisted into removing all whitespace type of characters (VT, HT, NL, CR, ...)? Reply 1. [2ca999] Daniel Lemire says: March 13, 2023 at 2:59 pm It can be generalized, yes. Note that the functions described in the blog post will work correctly with UTF-8 inputs. Reply 2. [b29538] Evan says: March 13, 2023 at 7:11 pm The documentation I have seen shows that SVE does not need a drain operation, it can instead be predicated to do a partial operation for the remainder elements. See slides 32 and 33 of this SVE presentation for an example of what I mean. Is there a specific reason why you coded it do work in two steps? I could see this being a naive translation from SIMD (NEON) style to SVE, but I don't think it is leveraging the full benefits of SVE predication. Reply 1. [2ca999] Daniel Lemire says: March 13, 2023 at 7:56 pm See slides 32 and 33 of this SVE presentation for an example of what I mean. If you write it in this manner, you will have an additional intrinsic function per loop (and the accompanying instruction) compared to my solution (focus on the main loop). Is there a specific reason why you coded it do work in two steps? For better performance. I have added the single-loop function to my benchmark, you can test it out and verify that it is slower. Reply 1. [b29538] Evan says: March 13, 2023 at 8:13 pm Thanks for the response, I suspected that may be the reason why. What if you use the optimization given on slide 34 to elide the i < len comparison? Does it catch back up? Sorry I do not have access right now to test it myself Reply 1. [2ca999] Daniel Lemire says: March 13, 2023 at 9:01 pm I have added the one loop alternative you pointed to. The performance is slightly improved but still very much inferior to the two-loop approach. I should point out that my expectation is that my implementation with a loop and a trail is probably too simple and could be optimized further (at the cost of greater code complexity). scalar cycles/bytes 1.75 sve one loop cycles/bytes 0.70 sve one loop alt cycles/bytes 0.66 sve cycles/bytes 0.47 So, unfortunately, the pretty code that ARM is displaying on their slides is likely not optimal. Of course, this could change with future compilers and/or processors. For example, the compiler could do the unrolling for you. Reply 2. [b29538] Evan says: March 13, 2023 at 8:17 pm Also sorry for saying it was a somehow bad or naive translation from neon, clearly not the case. Enjoyed the post, thanks for sharing. Reply 1. [2ca999] Daniel Lemire says: March 13, 2023 at 9:04 pm Also sorry for saying it was a somehow bad or naive translation from neon, clearly not the case. You might be interested in going back in time to how I started with SVE: https://lemire.me/blog/2022/06/23/ filtering-numbers-quickly-with-sve-on-amazon-graviton-3-processors / You might notice that my early code matched the ARM slides more than my recent code. So, in some sense, what looked to you like "naive" code is, from my point of view, more sophisticated (optimized) code...i.e., it will run faster. Reply 3. [b29538] Evan says: March 13, 2023 at 7:13 pm Also why does the second operation use svcmpeq while the loop uses svcmpne? Reply 1. [2ca999] Daniel Lemire says: March 13, 2023 at 7:57 pm A typographical error. Thanks for pointing it out. Reply Leave a Reply Cancel reply Your email address will not be published. To create code blocks or other preformatted text, indent by four spaces: This will be displayed in a monospaced font. The first four spaces will be stripped off, but all other whitespace will be preserved. Markdown is turned off in code blocks: [This is not a link](http://example.com) To create not a block, but an inline code span, use backticks: Here is some inline `code`. For more help see http://daringfireball.net/projects/markdown/syntax [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment * [ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. Receive Email Notifications? [no, do not subscribe ] [instantly ] Or, you can subscribe without commenting. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] You may subscribe to this blog by email. Post navigation Previous Previous post: Float-parsing benchmark: Regular Visual Studio, ClangCL and Linux GCC Next Next post: Science and Technology links (March 11 2023) Terms of use Proudly powered by WordPress