8 ms·

Do not taunt happy fun branch predictor (2023)

283 points by fanf2 2y ago

CrazyStat 2y ago
(2023) Discussion at the time: https://news.ycombinator.com/item?id=34520498 https://news.ycombinator.com/item?id=34520498
- dang 2y ago
  Thanks! Macroexpanded: Do not taunt happy fun branch predictor - https://news.ycombinator.com/item?id=34520498 https://news.ycombinator.com/item?id=34520498 - Jan 2023 (171 comments) (Reposts are fine after a year or so; links to past threads are just to satisfy extra-curious readers)
jcranmer 2y ago
> After checking for loop termination, we fall through into the foo function (without a branch!) Literally just reading this line made me go "well, there's your problem." I thought this was going to be something deep about fancy branch predictor heuristics, but it turns out to be a violation of basic heuristics. Folks, don't think you're going to get amazing speedups by using mismatched call/ret instructions. The branch predictor keeping a shadow stack of return addresses is something that's been around for decades.
- vlovich123 2y ago
  And yet they also showed how they did actually accomplish this and other optimizations. It’s an informative read.
- adwn 2y ago
  It's great that you're so knowledgeable about branch predictor behavior, but many people aren't and for them this is new, maybe even valuable, information. I guess this article's just not for you then, and that's okay.
  - akira2501 2y ago
    I don't think the complaint is that the article exists, it's that it perhaps needs more context. The article does not present the level of skill assumed about the reader or of the author, so comments like these help put that in perspective. The commentary from "old salts" isn't meant to insult or discourage you but to inform your world view with hard earned experience. It all has a value that's greater than the sum of it's parts and there's no good reason to be critical or reactionary about it.
    - patrick451 2y ago
      If you're actually an old salt, it will be immediately obvious when an article is not meant for your level of expertise. Whining that "the article needs more context" is like Michelangelo complaining that a coloring book didn't warn him it was for six year old children.
- quotemstr 2y ago
  And this will screw up program execution more profoundly (i.e.crash) on systems with architectural shadow call stacks as a security feature.
  - astrobe_ 2y ago
    Speaking of "security feature", this insanely complex behavior (for a CPU) is a recipe for disasters like Specter and Meltdown.
- chasil 2y ago
  On the one hand, a design goal of RISC is to improve the performance of compiled code at the expense of most other things. As such, this sort of hazard should be documented, but the designers should be able to assume that anyone directly writing assembler has read the documentation. On the other hand, Sophie Wilson wrote an implementation of BBC BASIC for the original ARM (but it didn't have a branch predictor). While that is 32-bit and plays by different rules, I wonder how AArch64 slows down code when the architectural assumptions change.
deleted 2y ago
[deleted]
orbital-decay 2y ago
Tangential question, perhaps a dumb one: why do most hardware schedulers try to predict the load on their own, instead of letting users explicitly signal their intent? It's everywhere, from CPUs to storage.
- hindsightbias 2y ago
  We could solve a lot of problems if every user had to take EE180.
- 082349872349872 2y ago
  In this case, I'd consider BL (call) a fairly explicit signal of intent to RET?
  - dzaima 2y ago
    Yep. For returns, the more important thing in the article, the "ret"[0] instruction behaves exactly identically to "br x30"[1], just with the hint that it's expected to match a "bl". On x86 things are less pretty as call/ret push/pop the ip from the stack, with no non-matching-hinted versions, but having such would also just not be particularly useful as unpaired call/ret would result in the stack pointer continually drifting without manual fixup (at which point jmp is just clearly better). [0]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/RET https://developer.arm.com/documentation/dui0802/a/A64-Genera... [1]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/BR?lang=en https://developer.arm.com/documentation/dui0802/a/A64-Genera...
    - LegionMammal978 2y ago
      On 32-bit x86, there is the trap of trying to use call/pop to get the absolute instruction pointer. It will work correctly, but it will mess up any call stack prediction and cause great performance penalties. Hence why compiler-generated EIP shims use call/mov/ret instead. (But this is not such a big issue in x86-64 with its RIP-relative addressing.)
- 2y ago
bee_rider 2y ago
> The SIMD code does come with one asterisk, though: because floating-point addition is not associative, and it performs the summation in a different order, it may not get the same result as straight-line code. In retrospect, this is likely why the compiler doesn't generate SIMD instructions to compute the sum! > Does this matter for your use case? Only you can know! Anything is possible of course, and the typical way of writing a loop to sum up an array is literally telling the computer to go element by element and accumulate the values. But it seems pretty unlikely that doing, say, four accumulations in parallel with simd and then summing them up at the end is any more wrong than going element by element. Summing floats should by default be taken to have error bounds, and any answer in those bounds is valid. If you know something special about the floats you are inputting, the language should have some means to explicitly encode that. It shouldn’t be the most basic loop, that’s the default case, so it should give the best performance.
- neonsunset 2y ago
  A lot of code relies on FP operations being deterministic, often within confines of specific ISA. Applying SIMD to loops with FP could have been a default but it breaks a lot of existing code, makes the output frequently straight-up non-deterministic and as a result is something that a programmer has to explicitly choose to use. Moreover, many programmers may not be even aware of these, so when a `float Sum(float[] values)` starts to return something different, they may not have any way to know that it is the vectorization that makes it do so. Which is why, for example, .NET's standard library will use SIMD for `integers.Sum()` but not for `floats.Sum()`.
  - crote 2y ago
    > A lot of code relies on FP operations being deterministic, often within confines of specific ISA How much of this is true in practice? I vaguely recall reading about a hard-to-diagnose bug where a seemingly unrelated code change meant that an intermediate value was no longer stored in the x87 extended-precision register but in memory instead, leading to a different result. Wouldn't you run into stuff like that all the time?
petsounds 2y ago
The title of this article is a reference to "Happy Fun Ball", my favorite SNL skit: https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M
- deleted 2y ago
  [deleted]
quotemstr 2y ago
Yeah. This effect is why, also, using a bare CALL without a RET ends up being a slow way to get the program counter on 32-bit x86, which lacks native PC-relative addressing: it confuses the CPU's tracking of calls and returns. Basically, you always want to balance them. No exceptions.
- gpderetta 2y ago
  Wasn't an article posted a few days ago showing that CPUs special case. CALL+0 not to update the prediction stack as it was commonly used to get IP?
  - rep_lodsb 2y ago
    Yes: https://news.ycombinator.com/item?id=40767676 https://news.ycombinator.com/item?id=40767676
  - quotemstr 2y ago
    Okay, fair enough. It used to be a pessimization before CPUs recognized that pattern. :-)
AshamedCaptain 2y ago
The same thing was covered by Raymond Chen almost 2 decades ago: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36973 https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...
- rkagerer 2y ago
  He did, and that's a fantastic article which is worth the read and provides good context for interpreting this post. One thing this post adds is the simple rectification of replacing ret with another br instruction, so the pairs are again "mirrored", and you get to have your cake and eat it too - slightly faster code without breaking the branch predictor.
- electrodank 2y ago
  As someone who has the old dead tree version of Intel’s x86 and 64 architecture instruction set reference (the fat blue books), and in general as someone who carefully reads the data sheets and documentation and looks for guidance from the engineers and staff who wrote the said data sheets, I always have reservations when I hear that “intuitively you would expect X but Y happens.” There’s nothing intuitive about any of this except, maybe, a reasonable understanding of the semi-conductive nature of the silicon and the various dopants in the process. Unless you’ve seen the die schematic, the traces, and you know the paths, there is little to no reason to have any sort of expectations that Thing A is faster than Thing B unless the engineering staff and data sheets explicitly tell you. There are exceptions, but just my 2c. Especially with ARM.
  - neonsunset 2y ago
    Respectfully, I disagree. CPU architecture optimization is in continuous dance with compiler optimization where the former tries to adapt to the patterns most commonly produced by the latter, and the latter tries to adjust its optimizations according to what performs the faster within the former. Therefore, it is not unreasonable to make assumptions based on the premise of "does this code look like something that could be reasonably produced by GCC/LLVM?". It is true that as cores get simpler and cheaper, they get more edge cases - something really big like Firestorm (A14/M1) can afford to have very consistent and tight latencies for all of its SIMD instructions regardless of the element/lane size and even hide complex dependencies or alignment artifacts wherever possible. But compare that with simpler and cheaper Neoverse N1, and it's a different story entirely, where trivial algorithm changes lead to significant slowdown - ADDV Vn.16B is way slower than Vn.4H, so you have to work around it. This is only exacerbated if you look at much smaller cores. LLVM and GCC deal with this by being able to use relatively precise knowledge of CPU's (-mtune) fetch, reorder, load and store queue/buffer depths, as well as latencies and dependency penalty cost of opcodes of the ISA it implements, and other details like loop alignment requirements, branch predictor limitations. Generally, it's difficult to do better in straight-line code with local data than such compilers assuming that whatever you are doing doesn't make concessions that a compiler is not allowed to make. Nonetheless, the mindset for writing a performant algorithm implementation is going to be the same as long as you are doing so for the same class of CPU cores - loop unrolling, using cmovs, and scheduling operations in advance, or ensuring that should spills happen, the load and store operations have matching arguments - all of that will be profitable on AMD's Zen 4, Intel's Golden Cove, Apple's Firestorm or ARM's Neoverse V3.
allenrb 2y ago
Was summarizing this article for a group of friends who largely met during the Apple II days and wanted to repost a bit of that here: The optimized code at the end takes 94 nanoseconds to sum an array of 1024 32-bit floating point numbers. In 94 nanoseconds, our old friend the 1 MHz 6502, would be just starting to consider signaling the memory chips that maybe they ought to try digging up the first byte of the first instruction in the program. Worth mentioning, that code is entirely dependent on running in cache. Otherwise even the mighty M1 Max in the post would still be stuck waiting on that first memory fetch. DRAM is slow. :-)
- cmrdporcupine 2y ago
  Lucky our total L1 cache sizes are about as big as the entire addressable memory of the 6502. We truly live in amazing times.
  - LoganDark 2y ago
    Truly. And I'm also always amazed by how much slower (in terms of wall time) modern software is than it ought to be. CPUs sure don't feel three to four orders of magnitude faster than they were 50 years ago, because software has gotten four to five orders of magnitude more wasteful to compensate. Argh...
    - jonhohle 2y ago
      I recently moved a project from a Phenom II 945 to an I7 8700. The project took around 1:30 to compile on the Phenom, 15s to compile on the I7. Others working on the project with even more modern systems are compiling in half that time. The major advantage I had was running the same compilers, same interpreters and same tooling, just in better hardware. On the other hand, I always felt KDE 2 and 3 were way more responsive on way less hardware than one of the modern versions or Gnome. Part of it is UI design - giving feedback that an operation is going to take some time immediately instead of blocking until the operation is done before doing anything.
      - 2y ago
samatman 2y ago
Everything I know, or need to know, about branch prediction, I learned from James Mickens. https://scholar.harvard.edu/files/mickens/files/theslowwinter.pdf https://scholar.harvard.edu/files/mickens/files/theslowwinte...
monitron 2y ago
This was a lovely article. I only wish the author wouldn’t have kept switching units (between µs and ns) making it hard to scan the tables for comparison.
- dmccarty 2y ago
  1000ns = 1us :)
  - carl_dr 2y ago
    We know. On a phone at normal reading distance, with the articles styling, it’s really hard to tell the difference between n and u without zooming, and the decimal points get lost - scanning the tables is hard.
- cshimmin 2y ago
  They also switched from C to Rust halfway through the article, which was a bit jarring...
  - packetlost 2y ago
    It looks like that was an addendum that was added later and also benchmarked against the original C version
mrinterweb 2y ago
Classic SNL reference: "Do not taunt happy fun ball" https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M
- rhussmann 2y ago
  If happy fun branch predictor starts to smoke, seek shelter immediately.
- Terr_ 2y ago
  > Happy Fun Ball has been shipped to our troops in Saudi Arabia and is also being dropped by our warplanes in Iraq. "What YEAR is it!?" /robin-williams-in-jumanji
  - throwaway173738 2y ago
    Sometime in the 1990s, judging by how young Mike Meyers is. The Iraq reference makes me think they’re joking about Gulf I not Gulf II, so probably circa 1991.
- chiph 2y ago
  Still legal in sixteen states! https://www.youtube.com/watch?v=2AzAFqrxfeY https://www.youtube.com/watch?v=2AzAFqrxfeY
nayuki 2y ago
> Why do we need a special function return instruction? Functionally, BR LR would do the same job as RET. Using RET tells the processor that this is a function return. I'm not sure this is a good design. Those two opcodes perform the same logic function but have different branch prediction hints. Meanwhile, there are other cases where an existing instruction is reinterpreted with new semantics: * On x86, `XCHG eax, eax` is `NOP`. * On x86, `XOR reg, reg` is `MOV reg, 0` and breaks dependencies for the purposes of register renaming. * On x86, various examples of macro-op fusion and micro-op fusion. * On various RISC architectures, `ADD r1, r0, 1234` is `MOV r1, 1234`. * On some RISC architectures, conditionally branching if r0 == 0 is the only way to express an unconditional branch. I see no reason why `BR LR` can't be the standard function return instruction and involve the branch predictor.
- zerohp 2y ago
  In AArch64, `BR LR` and `RET` do not perform the same logic when FEAT_BTI (Branch Target Identification) is present.
38 2y ago
> const float f = *data++; cursed code. people might say "oh that's normal idiomatic C", I don't care. I am glad Go does not allow code like this
- trealira 2y ago
  The C language seems to really like reading/writing data and then modifying it, or modifying data and then reading/writing it, which can make for some dense one-liners full of side-effects. The pre- and post- increment and decrement operators, and the fact that assignments are expressions, seem to encourage it - especially in combination with the short-circuiting boolean operators. In old C, they would write code like the function below. This is based on a function from The C Programming Language, and it makes the assumption that bufp points to a buffer that's at least one byte long. /* Read a line into a lim-sized buffer at bufp, returning strlen(bufp) */ int getline(char *bufp, int lim) { int c; char *p = bufp; while (--lim > 0 && (c = getchar()) != EOF && (*p++ = c) != '\n') ; *p = '\0'; return p - bufp; } But nowadays, in modern C code, I think most people don't write such terse code. I guess it's because the only people who still code in C are those who have no choice, and so they prefer clarity over compactness.
  - 38 2y ago
    I think the one liner was supposed to show how short and simple programming can be, but I think it ultimately has the opposite effect. It's basically a showcase of terrible programming idioms that you should never use.
    - trealira 2y ago
      To be fair, that's not actually in the book. I said it was based on a function from that book, but below is the version they actually write in the book; I apologize for unintentionally misleading you. I wrote the above function myself (based on this one below) to showcase the type of style I'm talking about. /* getline: read a line into s, return length */ int getline(char s[], int lim) { int c, i; for (i=O; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) s[i] = c; if (c == '\n') { s[i] = c; ++i; } s[i] = '\0'; return i; } They specifically don't use pointer arithmetic or the post-increment operator, because at that point in the book, they haven't introduced those yet. However, that function I wrote isn't far off from the real Unix V7 version of fgets [0], which is a similar function to getline: char * fgets(s, n, iop) char *s; register FILE *iop; { register c; register char *cs; cs = s; while (--n>0 && (c = getc(iop))>=0) { *cs++ = c; if (c=='\n') break; } if (c<0 && cs==s) return(NULL); *cs++ = '\0'; return(s); } Like I said, the creators and first users of C seemed to really like expressions with side-effects, pointer arithmetic, and while-loops with empty bodies (though fgets doesn't have that). It's interesting how Go is different in this regard, considering Ken Thompson was a co-creator of both languages. [0]: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/stdio/fgets.c https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/lib...
tociye9860 2y ago
[dead]
trealira 2y ago
I'm surprised they didn't try something less clever to optimize their code first. The assembly code could be rewritten like this, so the test requires one branch at the bottom of the loop instead of two (one to jump to the top and one to branch conditionally), as well as one instead of two ALU operations per loop for X1 (one subtraction to compare X1 to zero, and one to decrement X1, as opposed to using the result of the latter). stp x29, x30, [sp, #-16]! fmov s0, #0.0 cbnz x1, exit // Skip loop if x1 == 0. loop: ldr s1, [x0], #4 bl foo // Decrement x1. If x1 != 0, repeat the loop. subs x1, x1, #1 b.ne loop // Fall through to exit after the loop finishes. exit: ldp x29, x30, [sp], #16 ret foo: // ... ret Going further, you could just inline foo and omit the RET instruction without doing any trickery with mismatched BL and RET instructions. I haven't benchmarked this, though, so I don't actually know how much this speeds the code up.
- trealira 2y ago
  Typo: that line with "cbnz" should be "cbz". The CBZ instruction branches to a label if a register is zero, and CBNZ branches if the register isn't zero.
croemer 2y ago
Don't miss the 2023! The article really is already a little outdated: since Rust 1.78, the compiler uses some more aggressive loop unrolling (and a little bit of SIMD): https://godbolt.org/z/zhbobW7rr https://godbolt.org/z/zhbobW7rr OP wrote: "Looking at the assembly, it's doing some loop unrolling.", linking to https://godbolt.org/z/Kv77abW6c https://godbolt.org/z/Kv77abW6c, which is using "Rust Nightly", a moving target. By now, there's more loop unrolling. Loop unrolling started with Rust 1.59: https://godbolt.org/z/5PTnWrWf7 https://godbolt.org/z/5PTnWrWf7 Update: The code on Github shows they were using Rust version 1.67.0-nightly, 2022-11-27.
- croemer 2y ago
  Rust 1.67.0, which is likely what OP was looking at, gives: https://godbolt.org/z/4Y61d9seh https://godbolt.org/z/4Y61d9seh I ran the benchmarks locally on the same hardware, using latest nightly Rust 1.81 (aggressive loop unrolling): no difference. Same speed as 1.5 years ago.
- mkeeter 2y ago
  Good catch, I've updated the link to select Rust 1.67 specifically!
Taniwha 2y ago
I was working on an x86 clone back in the 90s (sadly never saw the light of day), one of the things I did early on was to write code to emulate various potential microarchitectural designs by capturing long streams of real world instructions - our real bugbear was one of the C++ compilers (used to compile a popular web browser from memory) that did virtual method dispatch by pushing an address onto the stack and returning to it - broke return predictors every time
- phire 2y ago
  I was confused as to why a compiler might do that. Surely a jump to register would always be faster than writing it out to memory. Then I remembered we are probably talking about 16bit code (for Win16), and that far pointers were a major thing. And turns out there is no "far jump to register" instruction in x86. The far jump instruction requires the 32bit pointer to be in memory. I guess some clever compiler engineer came up with a trick to use two pushes and a far return instruction to avoid needing to allocate a temporary 32bit variable on the stack. But that raises a deeper question: Why is this compiler using this clever "far jump to value in register" trick for virtual method dispatch? The full 32bit far pointer should already be sitting in the vtable, presumably it just loaded it from there? It would be a lot faster to just use the proper far jump instruction directly on the value in the vtable rather than loading it and writing it back out to the stack. I suspect this compiler was deficient, and missing the optimisation that would avoid the need for this "clever trick" most of the time.
  - Taniwha 2y ago
    Main reason is probably just that x86s have so very few registers. Most C++s have a pointer to the current object (bp), virtual objects then contain a pointer to a vtable (to save space) so it's a double indirect load - also I suspect (it was a long time ago) that parameters were already being passed in registers, they would have had to leave a free reg to use as a temp
jcul 2y ago
I'm not super familiar with ARM / ARM64 assembly and was confused as to how x0 was incremented. Was going to ask here, but decided to not be lazy and just look it up. const float f = *data++; ldr s1, [x0], #4 Turns out this instruction loads and increments x0 by 4 at the same time. It looks like you can use negative values too, so could iterate over something in reverse. Kind of cool, I don't think x86_64 has a single instruction that can load and increment in one go.
- sph 2y ago
  lods and stos do load/store + increment of `rsi` or `rdi` respectively. There's also movs to copy between two memory addresses + increment Usually seen in conjunction with rep, which repeats the above instruction `rcx` times. A simple memset of 10 bytes: mov rcx, 10 mov rdi, dest mov rax, 0 rep stosb You can use the w, d or q suffixes to advance by 2, 4 or 8 bytes.
  - jcul 2y ago
    Oh cool, and it looks like it can also decrement by 1/2/4/8. > After the byte, word, or doubleword is transferred from the memory location into the AL, AX, or EAX register, the (E)SI register is incremented or decremented automatically according to the setting of the DF flag in the EFLAGS register. (If the DF flag is 0, the (E)SI register is incremented; if the DF flag is 1, the ESI register is decremented.) The (E)SI register is incremented or decremented by 1 for byte operations, by 2 for word operations, or by 4 for doubleword operations. https://www.felixcloutier.com/x86/lods:lodsb:lodsw:lodsd:lodsq https://www.felixcloutier.com/x86/lods:lodsb:lodsw:lodsd:lod...
michaelcampbell 2y ago
ok, how many people here under 45 years old actually GET the "taunt happy fun" reference?
michaelcampbell 2y ago
<tangent> IIRC, one of the ways the 6502 would allow jumps past its normal boundaries was to PUSH the out of bounds address you wanted to go to onto whatever register then do the asm "return from subroutine" opcode. Perhaps that's old hat and not even allowed any more, but I thought it was pretty clever when I first read about it.

283 points by fanf2 2y ago

(2023) Discussion at the time: https://news.ycombinator.com/item?id=34520498 https://news.ycombinator.com/item?id=34520498

dang 2y ago
Thanks! Macroexpanded: Do not taunt happy fun branch predictor - https://news.ycombinator.com/item?id=34520498 https://news.ycombinator.com/item?id=34520498 - Jan 2023 (171 comments) (Reposts are fine after a year or so; links to past threads are just to satisfy extra-curious readers)

jcranmer 2y ago

> After checking for loop termination, we fall through into the foo function (without a branch!) Literally just reading this line made me go "well, there's your problem." I thought this was going to be something deep about fancy branch predictor heuristics, but it turns out to be a violation of basic heuristics. Folks, don't think you're going to get amazing speedups by using mismatched call/ret instructions. The branch predictor keeping a shadow stack of return addresses is something that's been around for decades.

vlovich123 2y ago
And yet they also showed how they did actually accomplish this and other optimizations. It’s an informative read.
adwn 2y ago
It's great that you're so knowledgeable about branch predictor behavior, but many people aren't and for them this is new, maybe even valuable, information. I guess this article's just not for you then, and that's okay.
- akira2501 2y ago
  I don't think the complaint is that the article exists, it's that it perhaps needs more context. The article does not present the level of skill assumed about the reader or of the author, so comments like these help put that in perspective. The commentary from "old salts" isn't meant to insult or discourage you but to inform your world view with hard earned experience. It all has a value that's greater than the sum of it's parts and there's no good reason to be critical or reactionary about it.
  - patrick451 2y ago
    If you're actually an old salt, it will be immediately obvious when an article is not meant for your level of expertise. Whining that "the article needs more context" is like Michelangelo complaining that a coloring book didn't warn him it was for six year old children.
quotemstr 2y ago
And this will screw up program execution more profoundly (i.e.crash) on systems with architectural shadow call stacks as a security feature.
- astrobe_ 2y ago
  Speaking of "security feature", this insanely complex behavior (for a CPU) is a recipe for disasters like Specter and Meltdown.
chasil 2y ago
On the one hand, a design goal of RISC is to improve the performance of compiled code at the expense of most other things. As such, this sort of hazard should be documented, but the designers should be able to assume that anyone directly writing assembler has read the documentation. On the other hand, Sophie Wilson wrote an implementation of BBC BASIC for the original ARM (but it didn't have a branch predictor). While that is 32-bit and plays by different rules, I wonder how AArch64 slows down code when the architectural assumptions change.

deleted 2y ago

[deleted]

orbital-decay 2y ago

Tangential question, perhaps a dumb one: why do most hardware schedulers try to predict the load on their own, instead of letting users explicitly signal their intent? It's everywhere, from CPUs to storage.

hindsightbias 2y ago
We could solve a lot of problems if every user had to take EE180.
082349872349872 2y ago
In this case, I'd consider BL (call) a fairly explicit signal of intent to RET?
- dzaima 2y ago
  Yep. For returns, the more important thing in the article, the "ret"[0] instruction behaves exactly identically to "br x30"[1], just with the hint that it's expected to match a "bl". On x86 things are less pretty as call/ret push/pop the ip from the stack, with no non-matching-hinted versions, but having such would also just not be particularly useful as unpaired call/ret would result in the stack pointer continually drifting without manual fixup (at which point jmp is just clearly better). [0]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/RET https://developer.arm.com/documentation/dui0802/a/A64-Genera... [1]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/BR?lang=en https://developer.arm.com/documentation/dui0802/a/A64-Genera...
  - LegionMammal978 2y ago
    On 32-bit x86, there is the trap of trying to use call/pop to get the absolute instruction pointer. It will work correctly, but it will mess up any call stack prediction and cause great performance penalties. Hence why compiler-generated EIP shims use call/mov/ret instead. (But this is not such a big issue in x86-64 with its RIP-relative addressing.)
2y ago

bee_rider 2y ago

> The SIMD code does come with one asterisk, though: because floating-point addition is not associative, and it performs the summation in a different order, it may not get the same result as straight-line code. In retrospect, this is likely why the compiler doesn't generate SIMD instructions to compute the sum! > Does this matter for your use case? Only you can know! Anything is possible of course, and the typical way of writing a loop to sum up an array is literally telling the computer to go element by element and accumulate the values. But it seems pretty unlikely that doing, say, four accumulations in parallel with simd and then summing them up at the end is any more wrong than going element by element. Summing floats should by default be taken to have error bounds, and any answer in those bounds is valid. If you know something special about the floats you are inputting, the language should have some means to explicitly encode that. It shouldn’t be the most basic loop, that’s the default case, so it should give the best performance.

neonsunset 2y ago
A lot of code relies on FP operations being deterministic, often within confines of specific ISA. Applying SIMD to loops with FP could have been a default but it breaks a lot of existing code, makes the output frequently straight-up non-deterministic and as a result is something that a programmer has to explicitly choose to use. Moreover, many programmers may not be even aware of these, so when a `float Sum(float[] values)` starts to return something different, they may not have any way to know that it is the vectorization that makes it do so. Which is why, for example, .NET's standard library will use SIMD for `integers.Sum()` but not for `floats.Sum()`.
- crote 2y ago
  > A lot of code relies on FP operations being deterministic, often within confines of specific ISA How much of this is true in practice? I vaguely recall reading about a hard-to-diagnose bug where a seemingly unrelated code change meant that an intermediate value was no longer stored in the x87 extended-precision register but in memory instead, leading to a different result. Wouldn't you run into stuff like that all the time?

petsounds 2y ago

The title of this article is a reference to "Happy Fun Ball", my favorite SNL skit: https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M

deleted 2y ago
[deleted]

quotemstr 2y ago

Yeah. This effect is why, also, using a bare CALL without a RET ends up being a slow way to get the program counter on 32-bit x86, which lacks native PC-relative addressing: it confuses the CPU's tracking of calls and returns. Basically, you always want to balance them. No exceptions.

gpderetta 2y ago
Wasn't an article posted a few days ago showing that CPUs special case. CALL+0 not to update the prediction stack as it was commonly used to get IP?
- rep_lodsb 2y ago
  Yes: https://news.ycombinator.com/item?id=40767676 https://news.ycombinator.com/item?id=40767676
- quotemstr 2y ago
  Okay, fair enough. It used to be a pessimization before CPUs recognized that pattern. :-)

AshamedCaptain 2y ago

The same thing was covered by Raymond Chen almost 2 decades ago: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36973 https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

rkagerer 2y ago
He did, and that's a fantastic article which is worth the read and provides good context for interpreting this post. One thing this post adds is the simple rectification of replacing ret with another br instruction, so the pairs are again "mirrored", and you get to have your cake and eat it too - slightly faster code without breaking the branch predictor.
electrodank 2y ago
As someone who has the old dead tree version of Intel’s x86 and 64 architecture instruction set reference (the fat blue books), and in general as someone who carefully reads the data sheets and documentation and looks for guidance from the engineers and staff who wrote the said data sheets, I always have reservations when I hear that “intuitively you would expect X but Y happens.” There’s nothing intuitive about any of this except, maybe, a reasonable understanding of the semi-conductive nature of the silicon and the various dopants in the process. Unless you’ve seen the die schematic, the traces, and you know the paths, there is little to no reason to have any sort of expectations that Thing A is faster than Thing B unless the engineering staff and data sheets explicitly tell you. There are exceptions, but just my 2c. Especially with ARM.
- neonsunset 2y ago
  Respectfully, I disagree. CPU architecture optimization is in continuous dance with compiler optimization where the former tries to adapt to the patterns most commonly produced by the latter, and the latter tries to adjust its optimizations according to what performs the faster within the former. Therefore, it is not unreasonable to make assumptions based on the premise of "does this code look like something that could be reasonably produced by GCC/LLVM?". It is true that as cores get simpler and cheaper, they get more edge cases - something really big like Firestorm (A14/M1) can afford to have very consistent and tight latencies for all of its SIMD instructions regardless of the element/lane size and even hide complex dependencies or alignment artifacts wherever possible. But compare that with simpler and cheaper Neoverse N1, and it's a different story entirely, where trivial algorithm changes lead to significant slowdown - ADDV Vn.16B is way slower than Vn.4H, so you have to work around it. This is only exacerbated if you look at much smaller cores. LLVM and GCC deal with this by being able to use relatively precise knowledge of CPU's (-mtune) fetch, reorder, load and store queue/buffer depths, as well as latencies and dependency penalty cost of opcodes of the ISA it implements, and other details like loop alignment requirements, branch predictor limitations. Generally, it's difficult to do better in straight-line code with local data than such compilers assuming that whatever you are doing doesn't make concessions that a compiler is not allowed to make. Nonetheless, the mindset for writing a performant algorithm implementation is going to be the same as long as you are doing so for the same class of CPU cores - loop unrolling, using cmovs, and scheduling operations in advance, or ensuring that should spills happen, the load and store operations have matching arguments - all of that will be profitable on AMD's Zen 4, Intel's Golden Cove, Apple's Firestorm or ARM's Neoverse V3.

allenrb 2y ago

Was summarizing this article for a group of friends who largely met during the Apple II days and wanted to repost a bit of that here: The optimized code at the end takes 94 nanoseconds to sum an array of 1024 32-bit floating point numbers. In 94 nanoseconds, our old friend the 1 MHz 6502, would be just starting to consider signaling the memory chips that maybe they ought to try digging up the first byte of the first instruction in the program. Worth mentioning, that code is entirely dependent on running in cache. Otherwise even the mighty M1 Max in the post would still be stuck waiting on that first memory fetch. DRAM is slow. :-)

cmrdporcupine 2y ago
Lucky our total L1 cache sizes are about as big as the entire addressable memory of the 6502. We truly live in amazing times.
- LoganDark 2y ago
  Truly. And I'm also always amazed by how much slower (in terms of wall time) modern software is than it ought to be. CPUs sure don't feel three to four orders of magnitude faster than they were 50 years ago, because software has gotten four to five orders of magnitude more wasteful to compensate. Argh...
  - jonhohle 2y ago
    I recently moved a project from a Phenom II 945 to an I7 8700. The project took around 1:30 to compile on the Phenom, 15s to compile on the I7. Others working on the project with even more modern systems are compiling in half that time. The major advantage I had was running the same compilers, same interpreters and same tooling, just in better hardware. On the other hand, I always felt KDE 2 and 3 were way more responsive on way less hardware than one of the modern versions or Gnome. Part of it is UI design - giving feedback that an operation is going to take some time immediately instead of blocking until the operation is done before doing anything.
    - 2y ago

samatman 2y ago

Everything I know, or need to know, about branch prediction, I learned from James Mickens. https://scholar.harvard.edu/files/mickens/files/theslowwinter.pdf https://scholar.harvard.edu/files/mickens/files/theslowwinte...

monitron 2y ago

This was a lovely article. I only wish the author wouldn’t have kept switching units (between µs and ns) making it hard to scan the tables for comparison.

dmccarty 2y ago
1000ns = 1us :)
- carl_dr 2y ago
  We know. On a phone at normal reading distance, with the articles styling, it’s really hard to tell the difference between n and u without zooming, and the decimal points get lost - scanning the tables is hard.
cshimmin 2y ago
They also switched from C to Rust halfway through the article, which was a bit jarring...
- packetlost 2y ago
  It looks like that was an addendum that was added later and also benchmarked against the original C version

mrinterweb 2y ago

Classic SNL reference: "Do not taunt happy fun ball" https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M

rhussmann 2y ago
If happy fun branch predictor starts to smoke, seek shelter immediately.
Terr_ 2y ago
> Happy Fun Ball has been shipped to our troops in Saudi Arabia and is also being dropped by our warplanes in Iraq. "What YEAR is it!?" /robin-williams-in-jumanji
- throwaway173738 2y ago
  Sometime in the 1990s, judging by how young Mike Meyers is. The Iraq reference makes me think they’re joking about Gulf I not Gulf II, so probably circa 1991.
chiph 2y ago
Still legal in sixteen states! https://www.youtube.com/watch?v=2AzAFqrxfeY https://www.youtube.com/watch?v=2AzAFqrxfeY

nayuki 2y ago

> Why do we need a special function return instruction? Functionally, BR LR would do the same job as RET. Using RET tells the processor that this is a function return. I'm not sure this is a good design. Those two opcodes perform the same logic function but have different branch prediction hints. Meanwhile, there are other cases where an existing instruction is reinterpreted with new semantics: * On x86, `XCHG eax, eax` is `NOP`. * On x86, `XOR reg, reg` is `MOV reg, 0` and breaks dependencies for the purposes of register renaming. * On x86, various examples of macro-op fusion and micro-op fusion. * On various RISC architectures, `ADD r1, r0, 1234` is `MOV r1, 1234`. * On some RISC architectures, conditionally branching if r0 == 0 is the only way to express an unconditional branch. I see no reason why `BR LR` can't be the standard function return instruction and involve the branch predictor.

zerohp 2y ago
In AArch64, `BR LR` and `RET` do not perform the same logic when FEAT_BTI (Branch Target Identification) is present.

38 2y ago

> const float f = *data++; cursed code. people might say "oh that's normal idiomatic C", I don't care. I am glad Go does not allow code like this

trealira 2y ago
The C language seems to really like reading/writing data and then modifying it, or modifying data and then reading/writing it, which can make for some dense one-liners full of side-effects. The pre- and post- increment and decrement operators, and the fact that assignments are expressions, seem to encourage it - especially in combination with the short-circuiting boolean operators. In old C, they would write code like the function below. This is based on a function from The C Programming Language, and it makes the assumption that bufp points to a buffer that's at least one byte long. /* Read a line into a lim-sized buffer at bufp, returning strlen(bufp) */ int getline(char *bufp, int lim) { int c; char *p = bufp; while (--lim > 0 && (c = getchar()) != EOF && (*p++ = c) != '\n') ; *p = '\0'; return p - bufp; } But nowadays, in modern C code, I think most people don't write such terse code. I guess it's because the only people who still code in C are those who have no choice, and so they prefer clarity over compactness.
- 38 2y ago
  I think the one liner was supposed to show how short and simple programming can be, but I think it ultimately has the opposite effect. It's basically a showcase of terrible programming idioms that you should never use.
  - trealira 2y ago
    To be fair, that's not actually in the book. I said it was based on a function from that book, but below is the version they actually write in the book; I apologize for unintentionally misleading you. I wrote the above function myself (based on this one below) to showcase the type of style I'm talking about. /* getline: read a line into s, return length */ int getline(char s[], int lim) { int c, i; for (i=O; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) s[i] = c; if (c == '\n') { s[i] = c; ++i; } s[i] = '\0'; return i; } They specifically don't use pointer arithmetic or the post-increment operator, because at that point in the book, they haven't introduced those yet. However, that function I wrote isn't far off from the real Unix V7 version of fgets [0], which is a similar function to getline: char * fgets(s, n, iop) char *s; register FILE *iop; { register c; register char *cs; cs = s; while (--n>0 && (c = getc(iop))>=0) { *cs++ = c; if (c=='\n') break; } if (c<0 && cs==s) return(NULL); *cs++ = '\0'; return(s); } Like I said, the creators and first users of C seemed to really like expressions with side-effects, pointer arithmetic, and while-loops with empty bodies (though fgets doesn't have that). It's interesting how Go is different in this regard, considering Ken Thompson was a co-creator of both languages. [0]: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/stdio/fgets.c https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/lib...

tociye9860 2y ago

[dead]

trealira 2y ago

I'm surprised they didn't try something less clever to optimize their code first. The assembly code could be rewritten like this, so the test requires one branch at the bottom of the loop instead of two (one to jump to the top and one to branch conditionally), as well as one instead of two ALU operations per loop for X1 (one subtraction to compare X1 to zero, and one to decrement X1, as opposed to using the result of the latter). stp x29, x30, [sp, #-16]! fmov s0, #0.0 cbnz x1, exit // Skip loop if x1 == 0. loop: ldr s1, [x0], #4 bl foo // Decrement x1. If x1 != 0, repeat the loop. subs x1, x1, #1 b.ne loop // Fall through to exit after the loop finishes. exit: ldp x29, x30, [sp], #16 ret foo: // ... ret Going further, you could just inline foo and omit the RET instruction without doing any trickery with mismatched BL and RET instructions. I haven't benchmarked this, though, so I don't actually know how much this speeds the code up.

trealira 2y ago
Typo: that line with "cbnz" should be "cbz". The CBZ instruction branches to a label if a register is zero, and CBNZ branches if the register isn't zero.

croemer 2y ago

Don't miss the 2023! The article really is already a little outdated: since Rust 1.78, the compiler uses some more aggressive loop unrolling (and a little bit of SIMD): https://godbolt.org/z/zhbobW7rr https://godbolt.org/z/zhbobW7rr OP wrote: "Looking at the assembly, it's doing some loop unrolling.", linking to https://godbolt.org/z/Kv77abW6c https://godbolt.org/z/Kv77abW6c, which is using "Rust Nightly", a moving target. By now, there's more loop unrolling. Loop unrolling started with Rust 1.59: https://godbolt.org/z/5PTnWrWf7 https://godbolt.org/z/5PTnWrWf7 Update: The code on Github shows they were using Rust version 1.67.0-nightly, 2022-11-27.

croemer 2y ago
Rust 1.67.0, which is likely what OP was looking at, gives: https://godbolt.org/z/4Y61d9seh https://godbolt.org/z/4Y61d9seh I ran the benchmarks locally on the same hardware, using latest nightly Rust 1.81 (aggressive loop unrolling): no difference. Same speed as 1.5 years ago.
mkeeter 2y ago
Good catch, I've updated the link to select Rust 1.67 specifically!

Taniwha 2y ago

I was working on an x86 clone back in the 90s (sadly never saw the light of day), one of the things I did early on was to write code to emulate various potential microarchitectural designs by capturing long streams of real world instructions - our real bugbear was one of the C++ compilers (used to compile a popular web browser from memory) that did virtual method dispatch by pushing an address onto the stack and returning to it - broke return predictors every time

phire 2y ago
I was confused as to why a compiler might do that. Surely a jump to register would always be faster than writing it out to memory. Then I remembered we are probably talking about 16bit code (for Win16), and that far pointers were a major thing. And turns out there is no "far jump to register" instruction in x86. The far jump instruction requires the 32bit pointer to be in memory. I guess some clever compiler engineer came up with a trick to use two pushes and a far return instruction to avoid needing to allocate a temporary 32bit variable on the stack. But that raises a deeper question: Why is this compiler using this clever "far jump to value in register" trick for virtual method dispatch? The full 32bit far pointer should already be sitting in the vtable, presumably it just loaded it from there? It would be a lot faster to just use the proper far jump instruction directly on the value in the vtable rather than loading it and writing it back out to the stack. I suspect this compiler was deficient, and missing the optimisation that would avoid the need for this "clever trick" most of the time.
- Taniwha 2y ago
  Main reason is probably just that x86s have so very few registers. Most C++s have a pointer to the current object (bp), virtual objects then contain a pointer to a vtable (to save space) so it's a double indirect load - also I suspect (it was a long time ago) that parameters were already being passed in registers, they would have had to leave a free reg to use as a temp

jcul 2y ago

I'm not super familiar with ARM / ARM64 assembly and was confused as to how x0 was incremented. Was going to ask here, but decided to not be lazy and just look it up. const float f = *data++; ldr s1, [x0], #4 Turns out this instruction loads and increments x0 by 4 at the same time. It looks like you can use negative values too, so could iterate over something in reverse. Kind of cool, I don't think x86_64 has a single instruction that can load and increment in one go.

sph 2y ago
lods and stos do load/store + increment of `rsi` or `rdi` respectively. There's also movs to copy between two memory addresses + increment Usually seen in conjunction with rep, which repeats the above instruction `rcx` times. A simple memset of 10 bytes: mov rcx, 10 mov rdi, dest mov rax, 0 rep stosb You can use the w, d or q suffixes to advance by 2, 4 or 8 bytes.
- jcul 2y ago
  Oh cool, and it looks like it can also decrement by 1/2/4/8. > After the byte, word, or doubleword is transferred from the memory location into the AL, AX, or EAX register, the (E)SI register is incremented or decremented automatically according to the setting of the DF flag in the EFLAGS register. (If the DF flag is 0, the (E)SI register is incremented; if the DF flag is 1, the ESI register is decremented.) The (E)SI register is incremented or decremented by 1 for byte operations, by 2 for word operations, or by 4 for doubleword operations. https://www.felixcloutier.com/x86/lods:lodsb:lodsw:lodsd:lodsq https://www.felixcloutier.com/x86/lods:lodsb:lodsw:lodsd:lod...

michaelcampbell 2y ago

ok, how many people here under 45 years old actually GET the "taunt happy fun" reference?

michaelcampbell 2y ago

<tangent> IIRC, one of the ways the 6502 would allow jumps past its normal boundaries was to PUSH the out of bounds address you wanted to go to onto whatever register then do the asm "return from subroutine" opcode. Perhaps that's old hat and not even allowed any more, but I thought it was pretty clever when I first read about it.