[Animats]

"It seems like at least for this kind of large-scale, complex application, the cost of pervasive runtime bounds checking is negligible."

Right. The myth that bounds checking is expensive may have come from some terrible compilers in the early days. Berkeley Pascal was a notable example. Each bounds check was a subroutine call.

The common cases for bounds checks are:

- It's in an inner loop iterating over arrays. That's the case where the highest percentage of the time goes into the bounds check. It's also the case likely to be optimized out. This is the case people worry about.

- It's in code that doesn't do a lot of subscript operations. So it doesn't matter.

- It's in non-optimizable code that does a lot of subscript operations. That's unusual, but it does come up. An modern case might be Unreal Engine's Nanite meshes, which have lots of small offsets within the data stream. On the other hand, if you don't check that stuff, it's a great attack vector.

[moloch-hai]

Each check burns a branch prediction slot, even if it always goes the same way. That may eject a branch predictor whose prediction matters.

[imtringued]

Then it sounds like our branch predictors are shit if they can't deal with simple things like this.

[saagarjha]

This is exactly what they are designed to do and they do their job well, but they can't do it for free.

[KMag]

If even our performance-critical code moves to languages that always bounds-check, perhaps that will put pressure on ISA designers to add instructions for never-taken branches that just don't participate in any of the branch prediction logic. You'll always get a mispredict on failed bounds checks or final loop condition checks, but you'll avoid causing mispredictions elsewhere.

Yes, some architectures (including x86) have instructions that hint to the branch predictor, but I think they still end up influencing branch predictor state.

[moloch-hai]

This is the sort of thing shamefully absent from RISC-V. Shameful because its designers were in a position to know better.

There are four versions of a conditional branch: to be predicted, almost always taken, almost never taken, and too random to waste a predictor on. Compilers nowadays have "likely" and "unlikely" intrinsics, but offer, yet, none for the last. I think x86 now ignores its "likelihood" branch prefix because back when introduced it was too often wrong; and now compilers don't emit it because it they know it is ignored.

The "too random to predict" would be good for sorting, where it could provide a 2x speedup. To get the effect today you need to use conditional-move instructions, which have become unfashionable. Getting your compiler to emit a cmov is tricky.

Intel added a special instruction (maybe in skylake?) to use for spinning on an atomic flag update, that just halts until the cache line being watched gets clobbered by a message from some other cache. Compilers don't emit it, unfortunately, even when spinning on what they know is an atomic flag.

There are zillions of such instructions that were good ideas but were never taken up by programmers who they were meant for.

[saagarjha]

How would this work? The branch isn’t “never” taken, it gets triggered when the bounds check fails. So someone needs to keep track of it…

[moloch-hai]

If the instruction is tagged to keep it from claiming a branch prediction slot, it does not thereby evict some other branch from its prediction slot.

A prediction slot is where statistics on past behavior of a branch at a particular address accumulate. If no past behavior is needed to predict whether the branch will be taken, the predictor needs no statistics to decide, and statistics on some other branch instruction may accumulate in that slot instead.

[dllthomas]

"Don't keep track of this branch for prediction stuff, instead always behave as if that prediction stuff says it won't be taken."