15 ms·
Optimizing compilers reload vector constants needlessly
- inetknght 4y agoI haven't (yet) read the article, but I will. But the headline... > Optimizing compilers reload vector constants needlessly ...is absolutely true. I wrote some code that just does bit management (shifting, or, and, xor, popcount) on a byte-level. Compiler produced vectorized instructions that provided about a 30% speed-up. But when I looked at it... it was definitely not as good as it could be, and one of the big things was frequently reloading/broadcasting constants like 0x0F or 0xCC or similar. Another thing it would do is to sometimes drop down to normal (not-SIMD) instructions. This was with both `-O2` and `-O3`, and also with `-march=native` I ended up learning how to use SIMD intrinsics and hand-wrote it all... and achieved about a 600% speedup. The code reached about 90% of the performance of the bus to RAM which was what I theorized "should" be the limiting factor: bitwise operations like this are extremely fast and the slowest point point was popcount which didn't have a native instruction on the hardware I was targeting (AVX2). This was with GCC 6.3 if I recall, about 5 years ago.
- jeffreyrogers 4y agoThat's basically the problem the article describes although he's using vector intrinsics too and it still reloads and broadcasts the constant before each loop.
- pclmulqdq 4y agoWhen I have used intrinsics, the compiler at least has a hope of getting this right, particularly when you use patterns like: __m256i mask = _mm256_set1_epi8(0x0f) If you just used the intrinsic that sets the register to a constant over and over, it often repeats the instruction. The compilers just aren't that smart about SIMD yet.
- jeffreyrogers 4y agoHe sets it once like this before the loops. __m256i c = _mm256_set1_epi32(10001); And then the disassembly has mov eax, 10001 vpbroadcastd ymm1, eax before each loop.
- pclmulqdq 4y agoYeah, if the compiler runs out of registers it will do this - it's better than spilling the constant to memory. Register allocation is one thing that compilers are still much worse at than humans, and you see it in SIMD code a lot.
- DannyBee 4y agoEh. Compilers are only worse because we don't care. Optimal register allocation + spilling is easily doable now on today's machines/algorithms. We just don't bother because it's not truly worth it in most cases (IE we get most of the performance for a very low cost)
- DannyBee 4y agoThere are three reasons it reloads constants: 1. It thinks it is cheaper than keeping them in a register ( this is known as rematerialization). It will reload constants that it lets it keep something else in a register, and it's cheaper to do this. 2. It thinks something could affect the constant. 3. It thinks it must move it through memory to use it, and then it thinks the memory was clobbered. In this case, it definitely knows it is a constant, and it can't prove that both loops always execute, so it places it in the path where it is only executed once per loop, because it believes it will be cheaper. I can still make at least gcc do weird things if i prove to it the loop executes once. In that case, what is happening in gcc is that constant propagation is propagating the vector constant forward into both loops. Something later (that has a machine cost model) is expected to commonize it if it is cheaper, but never does.
- DannyBee 4y agoYou can see it get propagated through as a constant at the high level here: https://godbolt.org/z/jxWKcnTT1 https://godbolt.org/z/jxWKcnTT1 That is normal and what i would expect to happen. You can see in lower level RTL dumps, nothing chooses to commonize it. That seems a bit weird, since it should have a cost model that says this isn't free.
- caf 4y agoI believe it's possible to report this as a "missed optimisation" bug.
- DannyBee 4y agoYes. A lot of the intrinsics also look like (at least in gcc), they are marked always inline but not pure/const. it's probably worthwhile marking those that take memory as pure/const. That way, it's obvious the value is readonly even when it's inlined. (otherwise, the compiler will have to prove it in the inlined code, which is not always possible)
- deleted 4y ago[deleted]
- phkahler 4y ago>> This was with both `-O2` and `-O3`, and also with `-march=native` Until very recently GCC didn't do vectorization at -O2 usless you told it to.
- inetknght 4y agoThat's true. I definitely omitted a bunch of other flags that were added including the flags to turn on vectorizations
- an1sotropy 4y agoCan you recommend any favorite resources for learning how to use SIMD intrinsics?
- teux 4y agoNot OP but also work with this. There’s some tutorials but honestly the best thing is to just use them. Write an image processing routine that does something like apply a gaussian blur to a black and white image. The c++ code for this is everywhere. You have a fixed kernel (2d matrix) and you have to do repeat multiplication and addition to each pixel for each element in the kernel. Write it in C++ or Rust. Then read the Arm SIMD manual, find the instructions that do the math you want, and switch it over to intrinsics. You are doing the same exact operations with the intrinsics as the raw c++. Just 8 or 16 of them at a single time. Run them side by side for parity and to check speed, tweak the simd, etc. Arm has good (well ,okay) documentation https://developer.arm.com/documentation/den0018/a/?lang=en https://developer.arm.com/documentation/den0018/a/?lang=en https://arm-software.github.io/acle/neon_intrinsics/advsimd.html https://arm-software.github.io/acle/neon_intrinsics/advsimd.... * Edit: you also have to do this on a supported architecture. Raspberry pi’s have a neon core at least in the 3’s. Not sure about the 4’s but I believe so too!
- corysama 4y agoAdding on: Go to https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Start with SSE, SSE2, SSE3 Write small functions in https://godbolt.org/ https://godbolt.org/ . Watch the assembly and the program output.
- inetknght 4y ago> https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Intel's Intrinsics Guide is exactly what I used and it was before I learned about Compiler Explorer. I already had a large and thorough suite of unit tests for inputs and expected outputs, including happy and sad paths. So it was pretty easy to poke around and learn what works, what doesn't. It was definitely time intensive (took about three months for about 50 lines of code) but it also saved the company a few million dollars in hardware (DNA analysis software to compare a couple TiB of data requires a _lot_ of performance). I have since moved to a different company, partly because I never saw a bonus for saving all that money. The intrinsics guide does good to show what's available but it does not do a good job of documenting how each instruction actually works... many intrinsics are missing pseudocode and some pseudocode can have ambiguous cases. I used GDB in assembly mode to compare that table against the register content instruction-by-instruction to figure out where I misunderstood something if something went awry. Frustratingly, some operations are available in 64-bits but not bigger, some in 128-bits but not bigger, etc. So I wrote up a rough draft in LibreOffice Calc with 64, 128, and 256 columns to follow the bits around every intended operation. I then correlated against the intrinsics guide to determine what instructions are available to me in what bit sizes. For a given test run, each row in the spreadsheet was colored by what the original data contained, another row for what I needed the answer to be for that test case, then auto-color another row's cell green or red if the register after a candidate set of instructions did or didn't match the desired output. Any time I had to move columns around (the data was 4-bits wide), I'd color a set of 4 columns to follow where they go during swizzling.
- teux 4y agoI often hand write neon (and other vectorised architecture) intrinsics/assembly for my job, optimising image and signal processing routines. We have seen many many 3 digit percentage speedups from bare c/c++ code. I got into the nastiest discussion on reddit where people were swearing up and down it was impossible to beat the compiler, and handwritten assembly was useless/pretentious/dangerous. I was downvoted massively. Sigh. Anyways, that was a year ago. Thanks for another point of validation for that. It clearly didn’t hurt my feelings. :) I never come across people in the wild that actually do this also, it’s such a niche area of expertise.
- astrange 4y agoTell them to read the ffmpeg code. All the platform-specific/SIMD stuff is done in asm. This isn't only because it's faster, it's honestly easier to read than intrinsics anyway. What it does lack is debugability.
- teux 4y agoFor debugging you can actually use gdb in assembly tui mode and step through the instructions! You can even get it hooked up in vs code and remote debug an embedded target using the full IDE. Full register view, watch registers for changes, breakpoints, step instruction to instruction. Pipelining and optimisations can make the intrinsics a bit fucky though, have to make sure it’s -O0 and a proper debug compilation. I have line by line debugged raw assembly many times. It’s just a pain to initially set up. Honestly not very different from c/c++ debugging once running.
- astrange 4y agoSure, but gdb doesn't know what the function parameters are, or on some platforms where functions start and end, crashes don't have source lines, and ASan doesn't work. (though of course valgrind does)
- variadix 4y agoI don’t know if this is frowned upon or not among assembly programmers, but I often just use naked functions in C with asm bodies, which gdb will provide the args for, rather than linking against a separate assembly file.
- BoardsOfCanada 4y agoSeems like the compiler puts the test for the first loop before loading the constant the first time, and therefor needs to load it again before the second loop. So the "tradeoff" is that if neither loop runs it will load the constant zero times. Of course this isn't what a human would do but at least there is some kind of sliver of logic to it. (Like if vpbroadcastd was a 2000 cycle instruction this pattern might have made sense)
- ArchD 4y agoIn this modified version where the for-loops get converted to do-loops (possibly unsafe/incorrect behavior), unnecessary multiple vpbroadcastd's for ymm1 are still done: https://godbolt.org/z/61jYejsra https://godbolt.org/z/61jYejsra With the original, for-loop version, it could be argued that in case no loop iteration gets run at all, the vpbroadcastd's can be totally skipped, and to generate extra code for different cases of whether each loop is empty to avoid unnecessary vpbroadcastd's is not worth it (e.g. the greater icache pressure resulting from longer code). With the do-loop variant, both loops will get at least one iteration so the compiler really could just unconditionally do the vpbroadcastd once before the first loop. It somehow fails to realize that ymm1 did not get clobbered between the two vpbroadcastd's.
- stephc_int13 4y agoMy experience with optimizing compilers is that generated code is often frustratingly close to optimal (given the source is well written and taking account the constraints of the target arch). It is perfectly reasonable to take a look at the output on Godbolt, tweak it a bit and call it a day. Maintaining a full assembly language version of the same code is rarely justifiable. And yet, I understand the itch, especially because there are quite often some low-hanging fruits to grab.
- evancox100 4y agoThis may be true for scalar code but it seems like the compilers still aren’t quite there with vector code.
- metadat 4y agoFor anyone who, like me, need / wants a refresher primer on vectorization: https://stackoverflow.com/questions/1422149/what-is-vectorization https://stackoverflow.com/questions/1422149/what-is-vectoriz...
- jeffbee 4y agoMoving the constant to file or anonymous namespace scope solves the issue. It's too bad that intrinsics are not `constexpr` because I have a powerful urge to hang a `constinit` in front of this line.
- gumby 4y agoDisturbing that this works, as it shouldn't do the reload even if the constant is passed in as a parameter.
- leni536 4y agoIn this particular case the broadcasting instruction can be replaced with builtin operations, allowing constexpr. https://godbolt.org/z/Td6vG9cqG https://godbolt.org/z/Td6vG9cqG edit: uh, the constant requires some hand adjustment edit2: fixed version https://godbolt.org/z/4Px5Mbsx4 https://godbolt.org/z/4Px5Mbsx4, and I just don't get this. gcc really just wants to load that constant twice.
- mzs 4y agoAre you sure? I see this twice in the dis on the right: mov eax, 10001 vpbroadcastd ymm1, eax
- JoeAltmaier 4y agoIntel had an optimizing compiler that was amazing. But unless you were intel-only it made life harder to switch compilers for that platform.
- berkut 4y agoYeah, I haven't used ICC for 7 years now, but at the time it was much better than clang/gcc at keeping SSE/AVX intrinsic types in registers through function calls (i.e. clang/gcc used to spill out onto the stack and re-load), and things like this in the article.
- cwzwarich 4y agoWere you testing on the same platform? The Microsoft ABI has callee-save XMM registers, whereas the Linux/macOS ABI does not. Regardless, it would be nice if more compilers could do interprocedural register allocation in cases where all callers are known.
- tester756 4y agoI've heard similar opinions that people could just recompile their soft and receive significant speed boost
- acdha 4y agoI periodically wonder whether Itanium or even the Pentium 4 would have been more successful had Intel released icc under an open source license. I’m assuming that they were trying to keep AMD from using it but I’m still not sure it was worth it from the number of times I knew scientists to avoid it because it was hard to share.
- phkahler 4y agoThe optimization here would be CSE or hoisting, or both? I'm guessing the problem is those are performed prior to vectorization. In other words, I suspect an invariant calculation inside consecutive loops but that is not vectorized will be pulled out of the loops and also moved prior to them and executed just once.
- JonChesterfield 4y agoAt a guess, constant rematerialision failing to cross basic block boundaries. Feels like a plausible thing for a heuristic to miss. E.g. sink the constant into the loop so it's available when optimising that block, then fail to hoist it back out afterwards because constant materialisation is cheap.
- foota 4y agoMaybe it's trying to avoid using SSE in the case where there's no loop? SSE on some older platforms had a cost just from using it, so it might be possible.
- Narishma 4y agoThis is AVX though, not SSE.
- marmada 4y agoI have a theory that in another decade ML models will do this better than any optimizing compiler -- similar to a hand written chess engine vs alpha go.
- exabrial 4y agoSide note: I really really like the blog theme and the complete lack of bulk on this blog. No react.js, 4500 NPM modules for a SPA or other crap and it loads instantly. Guess what? It's jquery.
- dmitrygr 4y agoProbably a holdover from older assumptions that using/loading a constant is free or cheap enough to be considered free.
- beagle3 4y agoSomewhat related: Can anyone recommend a (r)introduction to modern vector programming on CPUs? I was last fluent in the SSE2 days, but an awful lot has happened since - and while I did go over the list of modern vector primitives (AVX2, not yet AVX512), what I'm missing is use cases - every such primitive has 4-5 common use cases that are the reason it was included, and I would really like to know what they are ....