5 ms·
Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor
- carterschonwald 4y agoI’m just excited that sve hardware is starting to be available
- Thev00d00 4y agoThose those unaware this by Daniel Lemire of SimdJson fame. 0. https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson
- secondcoming 4y agoIs all this worth it when you may have only a few chars of whitespace at most? When I was looking at something related to this recently I noticed gcc doing a pretty cool optimisation [0], where it converted the whitespace chars into a bitfield and leveraged the `bt` instruction. It seems quite sensitive to the char string though and falls back to worse code easily (e.g add "\f\v" to the string) but it's easy to manually write the code so that gcc always generates the same. https://godbolt.org/z/Tzr8e7x6q https://godbolt.org/z/Tzr8e7x6q
- ape4 4y agoThe complexity almost looks like an April Fools joke.
- aseipp 4y agoNot really IMO. Seems pretty by the books SIMD optimization at the high level (main body vs manually peeled iteration for the tail), just using a nice instruction set. Straightforward vectorization of the original code. I suspect modern AVX is probably not much worse. You're more-or-less programming in assembly here using these intrinsics, using C for goodies like for loops, and at the moment that's about as good as you can do while scalable autovectorization is still WIP/NIH in most compilers, so it's not really surprising or noteworthy. For experienced SIMD programmers, this is the standard approach to getting data parallelism out of many "boring" algorithms.
- Cthulhu_ 4y agoBut if it's hidden behind a standard library's 'trim' functions it's all fine to me; I don't need to know how it works under the hood, but want to rely on the maintainer's knowledge that their implementation is as fast and efficient as possible on whichever architecture. Low level string operations happen so often under the hood in any application that 10x more code and complexity in an implementation is worth it if it increases efficiency.
- dr_zoidberg 4y agoIt's also 3.6 times faster, in a world where hardware updates get you 20-ish % improvements per generation.
- oceanplexian 4y agoIt doesn’t need to be “As fast as possible” it just needs to be faster than the I/O. For sure, congrats that it is X times faster but the writer doesn’t really describe performance in terms of real world constraints.
- jrockway 4y agoI/O is fast, and efficiency matters for every workload. The sooner your CPU is done running code, the sooner it can go into an energy saving state. Energy saving means a longer battery life on portable computers, and less cost in the server case. Remember that people are running algorithms like this "in the cloud" against millions of concurrent requests. The 40Gbps network card can keep the CPU busy, and users are waiting for you to be done. Writing efficient code to make 1 computer do the work of 2 is just operational cost savings 101. When I was at Google there was a "rules of thumb" page that described how much of your time X performance was worth. I always looked at that before micro-optimizing, but also always came out ahead. I remember a coworker and I redesigning one of our subsystems late on some Friday evening; the rules of thumb said that the performance improvement we predicted, at our scale, was worth a month of SWE time. We did it in 2 hours. So we came out ahead, and our system worked better. (I joked that my colleague and I would be taking 2 extra weeks of vacation.) TL;DR performance matters everywhere. The one user using an interactive tool on their workstation will appreciate their day not being wasted by random pauses. The person out and about on their phone will appreciate the additional battery life. And your company's bean counters will be quite happy to hear that your cloud bill or data center expense forecast for next year is down. Finally, it's fun! Truly a win/win. Make it fast!
- 2OEH8eoCRo0 4y agoNo matter how advanced we think we are we are still worrying about minutiae like trimming spaces from strings.
- fs111 4y agohumans putting text into form fields will never go away probably, so you will always have to do this at some point.
- 2OEH8eoCRo0 4y agoI'm aware. It's still interesting, especially since it all still boils down to machine instructions.
- tyingq 4y agoThis doesn't appear to implement trimming the front and back, just the entire string.
- ape4 4y agoYes, a much rarer thing.
- avian 4y ago> char * init_out{out}; Are the curly braces in the initialization some new C++ syntax? I haven't been keeping up with C++ developments in the last decade or so. Based on the code that follows I would expect char* init_out = out;
- unwind 4y agoYes, I was going to comment on that both code samples are C++, even though they are not clearly labelled as such. List initialization seems to be the recommended syntax to use nowadays in C++ [1]. I'm a fan of the type of optimization and exploration that Lemire often publishes, it's really cool and impressive. I just have a pet peeve about people lumping together C and C++ as if they're interchangable when they are (more clearly than ever, and growing further apart) not. [1]: https://en.cppreference.com/w/cpp/language/list_initialization https://en.cppreference.com/w/cpp/language/list_initializati...
- abbeyj 4y agoYes, it is called "Uniform Initialization". https://isocpp.org/wiki/faq/cpp11-language#uniform-init https://isocpp.org/wiki/faq/cpp11-language#uniform-init
- duped 4y agoThat's been around since C++11 although it's kind of weird to see it used for a char*
- owl57 4y agoA bit weird, but I would support a local style guide that limits initialization style choices to parens for calling non-initializer-list constructors and braces for everything else — for simplicity, consistency, less confusion with assignment, and that odd case where it would actually catch an error (unindended narrowing conversion).
- deleted 4y ago[deleted]
- chrisgd 4y agoThanks for sharing. Is understanding how best to utilize computer hardware part of a classic CS program or is most learned on the job? I studied Econ in college and been a python guy for last 8 years but have no knowledge of how the machine actually interacts with my code. Is there a formal name for understanding that?
- tveita 4y agoA course in high performance computing should include some material on computer architecture and SIMD, though the focus is more on parallel programming and GPU. To get into the right mindset for SIMD optimization, play Zachtronic games. You have a big pile of odd-shaped tools that take some input and output a result a few cycles later, you have limits on how many instructions can run at once, but maybe you can do something like a load each cycle for free. Run your benchmark, count the cycles, make a small tweak and test again.
- billythemaniam 4y agoCS program, but depends on the classes you take. For me, the main class was called "computer architecture". Classes about compilers, databases, servers, embedded programming, server clustering can all help to understand the machine. Of course, it can be learned on your own too. But generally this path is harder because it's hard to know what to study. The CS program will expose you to breadth of concepts.
- mydriasis 4y agoYou should work through Nand2Tetris :) it will give you an understanding of how computers work at a very, very low level.
- rektide 4y agoIt'd be fun to ask Daniel Lemire's undergrads if they learned about vector/simd instructions. It's hard for me to answer, because I was learning everything I could on the internet before undergrad, following each tiny micro-architectural tweak in minute detail. It makes it hard to remember what things college really provided & what was self-taught.
- 4y ago
- synergy20 4y agoSVE and SVE2 are similar to Intel's AVX512-etc for vector, I would use intrinsics instead of hand crafting ASM code, unless it's a performance bottleneck. And yes if you want to play with SVE, Amazon's own ARM chip is the best one available now, maybe the only one in fact, for the general public.
- evancox100 4y agoJust to be clear, SVE is similar to AVX512 but the “Scalable” part is that the length is not hard-coded to any set number of bits or elements. It is more like the vector computers of old, such as the Cray-1. This means there is no need for continually updating the instruction set with longer and longer versions of the same instructions. Hopefully this leads to a more stable base and wider adoption, we’ll see how that works in practice though!
- mort96 4y agoI'm not really convinced we need to continually update the instruction set with non-scalable vector instructions either tbh, it seems like we've stalled on 256 bit wide instructions to the point where AMD is emulating 512 bit instructions using 256 bit wide execution units and the performance benefits of 512 bit wide instructions even on Intel is marginal at best. That's not to say scalable instructions are a bad idea. It certainly makes it easier to make small CPUs which support all the software written for vector instructions without having to emulate 256 or 512 bit wide execution units.
- renox 4y agoI seem to remember reading that the 'scalable' part of SVM was lost as soon as you did loop unrolling.. I hope I'm wrong though!
- synergy20 4y agoyes,SVE is vector which is scalable and AVX is SIMD which has a few fixed width.
- diamondlovesyou 4y ago
- recursive 4y agoIn order for this to matter, you'd need to expect the possibility of strings with huge numbers of leading spaces. Why then would you use this naive algorithm for comparison? An obvious and more straight forward improvement would be to compare 4 bytes at a time with 0x20202020. (or maybe 8) There would be a maximum of 3 spaces to identify individually.
- rkunde 4y agoI was confused too but the author uses “trim” to mean “remove anywhere in the string”, rather than just from the beginning and end.
- layer8 4y agoWhat are the use cases for that, though?
- pkaye 4y agoMaybe for processing the code for an obfuscated C contest?
- xxpor 4y agoThere's a ton if you think of it as a byte array, rather than just a string. For example, network proxies that may remove various protocol TLV options from a packet.
- layer8 4y agoIs that an example of “remove all occurrences of a specific byte value from an array”? Wouldn’t packet processing require some sort of structural parsing?
- xxpor 4y agoPackets are usually parsed by casting a uint8_t * to a struct. Frequently, the part that needs to be removed is always at the same offset in the non-error case.
- sebazzz 4y agoIt is C, but it is assembly. That much is clear.