Feature request: maybe-break

[mikmoore]

break is a useful construct. One of its uses is to "short circuit" operations, exiting evaluation early if the outcome becomes known early. For example, any and all make use of it.

However, there is a cost. A loop with a break condition is not SIMD-able and doesn't unroll as well. This is because execution is required to terminate immediately upon reaching break. This makes them poorly suited for checking exceptional cases that usually don't break early. A common example of this is a check for any(isnan, x) that branches to some alternative code. The performance implications can be considerable. Consider the following semantically-equivalent operations:

## version 1.8.0

julia> x = fill(1.0, 1000);

julia> @btime all(>=(0), $x)
  454.315 ns (0 allocations: 0 bytes)
true

julia> @btime count(>=(0), $x) == length($x)
  59.003 ns (0 allocations: 0 bytes)
true

For simple predicates like this one, in the case that the whole input must be evaluated, the cost of eager break is considerable: almost an 8x slowdown. Since all uses short-circuiting, it can be expected to exit almost instantly if a false is found. Despite this, unless a false appears in the first ~1/8 of the input, all will be strictly slower than the count-based version that exhaustively checks every element.

I propose a "maybe-break" construct that gives execution the option to exit the block but does not require it. This would permit execution to only check the exit condition periodically, enabling SIMD and easier unrolling, while still allowing an early exit. For example, this would permit the operation to evaluate a chunk of inputs and then decide whether to break. If the predicate were expensive, such that it was not useful to SIMD or unroll, it would break immediately.

Maybe-break provides a best-of-both-worlds opportunity: operations that don't terminate quickly can benefit from SIMD/unrolling while operations that do terminate quickly only run a small number of excess evaluations. Operations that are expensive can continue to exit immediately upon a decisive result. It might be necessary to manually opt in to (or out of, but that would be more likely to be breaking) maybe-break in functions like any/all in case one really does require strict short-circuit semantics.

This feature would require communicating this maybe-break desire to LLVM. I don't know whether LLVM supports such a construct at this point or how difficult it might be to add.

[oscardssmith]

one thing that would be a little unfortunate about a maybebreak is that it would almost certainly taint consistency.

[MasonProtter]

There could just be a compiler heuristic that determines when the break occurs right? It can be stable and statically knowable for a specific function how it's breaking behaviour will work without it being set globally, or guaranteed to be the same between versions

[gbaraldi]

maybebreak wouldn't necessarily break consistency if the result is the same and if the loop body doesn't have sideeffects.

[oscardssmith]

The problem is that if the compiler had figured out that the break didn't change the semantics, it could have done the optimization itself without maybebreak.

[gbaraldi]

I was going to say that this might be a hard optimization to do, but maybe we need to fix some part of our codegen because it seems to be supported upstream in LLVM https://github.com/preames/public-notes/blob/master/multiple-exit-vectorization.rst

[vtjnash]

It is listed as one of the future topics for research: https://github.com/preames/public-notes/blob/master/multiple-exit-vectorization.rst#data-dependent-exits

[mikmoore]

If the compiler could figure out this transformation automatically in some common cases, that would obviously be even better. A maybebreak syntax could be a real footgun for careless use (and might be difficult to use responsibly, e.g. in all with a user-passed predicate).