Do not taunt happy fun branch predictor (2023)

Lucky our total L1 cache sizes are about as big as the entire addressable memory of the 6502.

We truly live in amazing times.

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.

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.

This seems no longer to be true for recent x86 processors: https://news.ycombinator.com/item?id=40767676

Raymond Chen is a treasure. I'm so glad that Microsoft gives him the leeway to write that blog, I have learned a ton from it.

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()`.

Sorting the floats reduces the error. I think using multiple accumulators reduces the accuracy then. And sorted data is not uncommon.

I think there is always a correct answer and the compiler shouldn’t make changes at least by default that are wrong.

But ways for the programmer to express his intent more clearly are always welcome.

> 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.

This is a lot of "should" for something that basically doesn't happen. The only information you give is the order of arithmetic in the original expression.

It is a total nightmare if arithmetic is not stable between builds. Rebuilding the software and running it on the same input should not produce different results.

(Long ago I encountered the special Intel version of this: because the FPU used 80-bit registers internally but 64-bit in memory, changing when a register fill/spill happened would change when your answer got rounded, and thereby change the results. You can set a global FPU flag at the start of the program to force rounding on every operation.)

It turns into a serious problem if the floats are of different magnitude. Consider [1e50, -1e50, 1e3, 1e3]. Evaluating it as (((1e50 + -1e50) + 1e3) + 1e3) gives 2e3, evaluating it as ((1e50 + 1e3) + (-1e50 + 1e3)) gives 0.

You get similar issues if you're trying to add a large number of small-magnitude numbers to a single larger-magnitude number. (((1e3 + 1e3) + 1e3) ... + 1e50) is substantially different from (((1e50 + 1e3) + 1e3) ... + 1e3).

> this is likely why the compiler doesn't generate SIMD instructions to compute the sum!

Isn't this the type of thing ffast-math is supposed to enable?

Surprisingly there are different algorithms for doing something as simple as summing up a list of numbers.

The naïve way of adding numbers one-by-one in a loop is an obvious way, but there are more sophisticated methods that give better bounds of the total accumulated error; Kahan summation[1] being one of the better-known ones.

Like most things, it can get complicated depending on the specific context. For streaming data, adding numbers one at a time may be the only option. But what if one could use a fixed-size buffer of N numbers? When a new number arrives what should be done? Take a partial sum of some subset of the N numbers in the buffer and add that to a cumulative total? If a subset if chosen, how? Are there provable (improved) error bounds for the subset selection method?

Fun stuff.

[1] https://en.wikipedia.org/wiki/Kahan_summation_algorithm

And yet they also showed how they did actually accomplish this and other optimizations. It’s an informative read.

And this will screw up program execution more profoundly (i.e.crash) on systems with architectural shadow call stacks as a security feature.

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.

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.

If happy fun branch predictor starts to smoke, seek shelter immediately.

> 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

Still legal in sixteen states!

https://www.youtube.com/watch?v=2AzAFqrxfeY

Rust 1.67.0, which is likely what OP was looking at, gives: 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.

Good catch, I've updated the link to select Rust 1.67 specifically!

Thanks! Macroexpanded:

Do not taunt happy fun branch predictor - 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)

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.

1000ns = 1us :)

They also switched from C to Rust halfway through the article, which was a bit jarring...

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.

In this case, I'd consider BL (call) a fairly explicit signal of intent to RET?

1. "Explicitly signaling your intent" takes space and time. Decoding isn't free, and even if there were no other downsides you'd want to be careful with that change.

2. It's a bit historical. Early CPUs didn't have a RAM/CPU discrepancy and didn't need pipelining. Code wasn't written to account for pipelining. As CPUs got a little faster relative to RAM, you added a few prediction mechanisms so that most consumers and workloads could actually use your brand new 2x faster gigaterrawatthournewton CPUs without having to rewrite all their code. Iterate 10-20 generations, where most software has never been written to care about branch prediction and where modern languages don't even expose the concept, and you have the current status quo.

It's supported by some CPUs: the linux kernel has likely/unlikely macros to indicate whether a branch is expected to be taken or not in the common case (which uses GCC attributes which allow this to be propagated through to codegen). It's just that it's generally less effective: firstly because not all branches get annotated, some that are annotated are annotated incorrectly, and in a lot of cases the branching behaviour is data-dependent enough that you can't make an optimal static prediction at all.

The user doesn't know the capabilities of the system. In particular, anything compiled in is set in stone: you don't know the capabilities of systems yet unbuilt. New systems don't sell well unless they make existing code run faster, and sell badly if they require you to rebuild everything and make it non-backwards-compatible.

The peak example of "let the user do the scheduling" was Itanium, which had a VLIW system which scheduled three instructions at once. It was a huge commercial failure, and allowed AMD to instead define the instruction set people wanted: X64 is IA32 but wider and with more registers, but not substantially different and certainly not as weird as Itanium.

Often, but not always, optimal scheduling is data dependent so it can't be statically computed at compile time.

They want to be able to guess long, long, before actually executing the instructions.

We could solve a lot of problems if every user had to take EE180.

You should look into the history of Itanium, it was designed around the idea that the compiler would do pretty much exactly that. It looked great on paper, but in practice nobody figured out how to actually write a compiler capable of doing it without constantly running into weird edge cases.

X86 does have "prefetch" instructions, which tell the CPU that you want to use some data in the near future. There are also "branch hint" instructions which tell the CPU if a branch is usually taken or not. The problem is that they tend to make your code slower: the CPU is already more than capable of predicting it by itself, and the extra instructions slow down the overall execution because they take up cache space and have to be decoded too.

GCC has the _builtin_expect macro to give hint for branch prediction. C++ has added something similar recently .

Because it can't actually see that return instruction until way too late.

Apple M1 CPU here loads and decodes 8 instructions per cycle, and the instruction cache access, plus the decoding takes multiple cycles. I don't know exactly how many cycles (more cycles allow for bigger instruction caches, and Apple gave the M1 a massive 192KB instruction cache), but the absolute minimum is 3 cycles.

And until the instruction is decoded, it has no idea that there is even a return instruction there.

3 cycles at 8 instructions per cycle is a full 24 instructions, so the M1 CPU will be a full 24 instructions past the return before it even knows the return exists. The loop body in this article is only 7 instructions long, so overrunning by an extra 24 instructions on every iteration of the loop would be a massive performance hit.

What actually happens is that the branch predictor remembers the fact that there is a return at that address, and on the very next cycle after starting the icache fetch of the return instruction, it pops the return address of it's return address prediction stack and starts fetching code from there.

For short functions, the branch predictor might need to follow the call on one cycle, and the return on the next cycle. The call instruction hasn't even finished decoding yet, but the branch predictor has already executed both the call and the return.

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.

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

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?

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.