3 ms·

That can easily lead to excessive branch target buffer invalidation and mess up branch prediction. It might look acceptable in microbenchmarks, with just 1-10%

by vardump 11y ago

That can easily lead to excessive branch target buffer invalidation and mess up branch prediction. It might look acceptable in microbenchmarks, with just 1-10% performance loss and be a total disaster in an actual running system. A mispredicted branch costs about 15 clock cycles. You'll have a lot of those when CPU can't do bookkeeping on all of your range check branches anymore. The range checks themselves might run fast and fine, but those other branches your program has to execute can become pathological. Those, where the default choice for branches not present in CPU branch prediction buffer and branch target buffer is wrong. 15 clock cycles is rather excessive on any modern CPU that's supposed to execute 1-4 instructions per clock cycle! In the worst pathological cases this can mean an order of magnitude (~10x) worse performance. Of course data flow analysis might mitigate need for actual range checks, if the compiler can prove the value can never be out of range (of representable values with a given type). Regardless it is important to understand worst case price can be very high, this type of behavior should not be default in any performance oriented language.

vardump 11y ago
To add, to avoid any misunderstanding: the cost is probably within 1-10% in likely scenarios on most real world code. Pathological case would be code with a lot of taken branches mixed with range/overflow checks. For range checks, any sane compiler would generate code that doesn't branch if the value is in range. If no branch predictor entry is present, branches are assumed [1] to be not taken. These branches can still thrash BTB (kind of cache trashing) and cause taken branches that fell out of BTB to become always mispredicted, thus very expensive. [1]: Some architectures do support branch hints, even x86 did so in the past. Modern x86 CPUs simply ignore these hints.
- pcwalton 11y ago
  Not only that, you lose the ability to pattern match simple arithmetic to LEA and bloat your code size.
giovannibajo1 11y ago
It's very hard for an overflow check to be mis-predicted. On x86, for static branch prediction, it's sufficient to generate code with a forward branch to be predicted as unlikely the first time. From that point, as the branch will never be taken (unless it actually triggers a panic but then who cares), it will keep being predicted as not taken. A correctly-predicted non taken conditional jump on x86 has 0 latency. In the specific case of overflow, you don't even need to generate a cmp instruction. It basically means that's close to a wash, in performance. The actual negative effect that could be measurable is disabling optimizations (like composition of multiple operations, as you need to check each one for overflow).

by vardump 11y ago

vardump 11y ago

To add, to avoid any misunderstanding: the cost is probably within 1-10% in likely scenarios on most real world code. Pathological case would be code with a lot of taken branches mixed with range/overflow checks. For range checks, any sane compiler would generate code that doesn't branch if the value is in range. If no branch predictor entry is present, branches are assumed [1] to be not taken. These branches can still thrash BTB (kind of cache trashing) and cause taken branches that fell out of BTB to become always mispredicted, thus very expensive. [1]: Some architectures do support branch hints, even x86 did so in the past. Modern x86 CPUs simply ignore these hints.

pcwalton 11y ago
Not only that, you lose the ability to pattern match simple arithmetic to LEA and bloat your code size.

giovannibajo1 11y ago

It's very hard for an overflow check to be mis-predicted. On x86, for static branch prediction, it's sufficient to generate code with a forward branch to be predicted as unlikely the first time. From that point, as the branch will never be taken (unless it actually triggers a panic but then who cares), it will keep being predicted as not taken. A correctly-predicted non taken conditional jump on x86 has 0 latency. In the specific case of overflow, you don't even need to generate a cmp instruction. It basically means that's close to a wash, in performance. The actual negative effect that could be measurable is disabling optimizations (like composition of multiple operations, as you need to check each one for overflow).