@expect() hint to optimizer

[PavelVozenilek]

This is proposal for a small feature, local and isolated. Could improve code readability.

---

Linux kernel uses macros likely and unlikely :

if (likely(x > 0)) { ... }
...
if (unlikely(y == NULL)) { ... }

These macros may improve performance a little bit and they serve as handy documentation.

Language Nim supports this functionality too, through its standard library ( https://nim-lang.org/docs/system.html#likely.t,bool ).

---

My proposal:

Add if+ and if- into the language. if+ would signal that the path is rather likely, if- will suggest the flow will not go this way.

if+ (x < 0) { 
  ...  // likely goes here
}
if- (err) { 
  ... // unlikely
}

What is this good for:

1. It gives hint to source code reader, hint which will be almost never found in the documentation. This hint is very short, intuitive, and doesn't require extra pair of parenthesis.
2. It may slightly improve the performance, by rearranging instructions so that the likely path goes w/o jump, or by inserting hint for branch selector.

How it could be implemented:

1. By doing nothing, just using it as documentation only feature.
2. By using IR opcode llvm.expect. This is how clang implements __builtin_expect, which is called by likely/unlikelymacros. (GCC also provides __builtin_expect, MSVC has nothing similar.)

---

Performance effects of __builtin_expect are hotly disputed on the internet. Many people claim programmers are invariably bad in such prediction and profile guided optimization will do much, much better. However, they never support their claim by benchmarks.

Even if performance is unaffected the documentation value remains. When one is stepping the code through debugger and the flow goes against the hint, one may be get more cautious a catch a bug.

[raulgrell]

I do think that something to guide branch prediction can be pretty neat, but might be clearer with a builtin like @expect(expression, value) or @likely(condition).

This would be less surprising to someone who's familiar with llvm.expect and gcc __builtin_expect. A builtin might also be better suited as it communicates a hint to the compiler as opposed to actual program logic.

if (@expect(x < 0, false)) {
    //
}

[PavelVozenilek]

I use likely/unlikely in my code and the additional parenthesis make have impact on readability. Alternative syntax could be something as

if (x > 0) {
  @likely
   ...
} else {
  ...
}

but this wastes one precious line.

[raulgrell]

Sure, it wastes a line, but it makes it abundantly clear that the first branch is the likely one. It is important to note that if you choose the wrong branch, performance will be worse and it is actually good for the hint to be easily found. More information on performance: http://blog.man7.org/2012/10/how-much-do-builtinexpect-likely-and.html

More explicitly/consistent with the language, perhaps:

if (x > 0) {
  @expectedBranch(this);
   ...
} else {
  ...
}

[andrewrk]

It's going to be @expect as described by @raulgrell. This avoids adding new syntax and closely matches the LLVM intrinsic.

[lanior]

Compare

if (@expect(x < 0, false))

with

#define likely(x)   (__builtin_expect(!!(x), 1))
#define unlikely(x) (__builtin_expect(!!(x), 0))

if unlikely(x < 0)
   ...

The former is too chatty. If you are going to leave two sets of parenthesis, please consider adding @likely and @unlikely because people are used to it. Almost nobody uses two argument intrinsic directly.

[thejoshwolfe]

How would I expect no error from something?

if (errorable()) |payload| {
    // this should be likely
} else |err| {
    // this should be unlikely
}

The proposed @expect(expression, value) builtin looks like it needs to be able to effectively do == comparison, which doesn't very well cover the spectrum of possible control flow in zig.

Would there be any way to expect or not expect certain branches of a switch? How about the else of a while? How about the error path in a try, catch, or errdefer?

Glancing at the LLVM docs, it looks like we're pretty limited in what we can do. Looks like @expect() is the best we can do for now. I think a more generally useful feature is the ability to annotate an IR basic block to be likely or unlikely, then have zig builtins that you state at the beginning of a block, like @expectedBranch(this); that @raulgrell proposed.

The former is too chatty.

I think it's ok to be a little verbose with this feature, since it's a bit advanced and not recommended unless you understand the drawbacks. My concern is lack of generality.

[andrewrk]

Zig would always expect no error. That's #84

[0joshuaolson1]

Would this make sense on other conditional Zig operators?

[shawnl]

Would this make sense on other conditional Zig operators?

Yes, and for that reason likely/unlikely is prob. Better.

[PavelVozenilek]

@0joshuaolson1: it probably doesn't make sense to expand the feature. It has to be used often to have an impact. if+/if- has low typing overhead and is also acts as intuitive self-documentation (the main advantage, I would say). Trying to shoehorn it elsewhere would require clumsy syntax.

Language Nim has support for fine tuned switch, using linearScanEnd pragma ( https://nim-lang.org/docs/manual.html#pragmas-linearscanend-pragma ), but I think this is overkill

[BarabasGitHub]

Why does it have to be used often to have an impact? I'd say you'll only have to use it in hot loops and stuff like that. It really doesn't matter most of the time.

[PavelVozenilek]

@BarabasGitHub: the hint allows to reorder instructions so that the likely flow goes without jumping (and this cleaning the pipeline). This can save few cycles. To have measurable impact, it should be applied a lot.

I value it more as the documentation. VC++ does not support implementation of likely/unlikelylike GCC does, but I use it anyway, as empty macro.

[BarabasGitHub]

I know how it works. I also know most of the code you write isn't in the hot path and thus has a neglectable impact on performance.

Plus you have the branch predictor which mostly negates these kinds of optimizations in most cases.

Not saying you shouldn't use it, because it can definitely help. However I don't think it should be used all over the place because you think it improves performance.

Op wo 8 aug. 2018 01:02 schreef PavelVozenilek notifications@github.com:

@BarabasGitHub https://github.com/BarabasGitHub: the hint allows to reorder instructions so that the likely flow goes without jumping (and this cleaning the pipeline). This can save few cycles. To have measurable impact, it should be applied a lot.

I value it more as the documentation. VC++ does not support implementation of likely/unlikelylike GCC does, but I use it anyway, as empty macro.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ziglang/zig/issues/489#issuecomment-411229866, or mute the thread https://github.com/notifications/unsubscribe-auth/AL-sGu-hosG2iwAJ5U3hy47C3TfBqDjhks5uOhxogaJpZM4PaIPQ .

[PavelVozenilek]

In theory, with a very advanced benchmarking tool (could be based on #1010#issuecomment-389227431), validity of these hints could be checked and clear violation reported. This may help the programmer to discover wrong assumptions about runtime behaviour.

If the major reason for if+/if- is self-documentation, then it makes sense to use it often.

[andrewrk]

In theory, with a very advanced benchmarking tool validity of these hints could be checked and clear violation reported.

That sounds like #237

[andrewrk]

This is still accepted but there are some problems to solve before implementing it:

• how to expect a certain switch prong
• how to expect a certain branch for if-optionals
• how to override the default and expect a certain branch for if-error-unions
• how to expect a certain branch for while-bool, while-optional, while-error-union

The underlying llvm intrinsic that we have is to expect an integer to be a certain value. That also means booleans. One way to solve this problem for switch statements and optionals would be specialized builtins:

@expect(actual_value: var, expected_value: comptime @typeOf(actual_value)) @typeOf(actual_value)

This would work for any type and always return the actual_value, as if actual_value were referenced directly. For if-bool and while-bool it's obvious how to lower to the LLVM instrinsic.

For if-optional and while-optional, one could do this for expecting null: if (@expect(value, null)) |_| {}. When expecting non-null: if (@expect(value, T(undefined))) |_| {} Where T is the payload type of the optional. The expected payload is undefined which means unknown, but it's known to be non-null.

Same deal for if-error-union and while-error-union:

• if (@expect(value, ErrorSet(undefined))) |_| {}
• if (@expect(value, T(undefined))) |_| {} (this will be the default after #84)

The same technique can be used for switch:

switch (@expect(value, Union{.Tag = undefined})) {}

I think that solves all the problems.

[andrewrk]

Related question, should it be called @asExpected instead?

For a long time I've hated the convention of defining likely() and unlikely() macros for __builtin_expect, because they read so wrong in English ("if this condition is likely...") So a while back I was thinking about how to replace them in a way that reads naturally: as_expected() and unexpectedly(). "If, as expected, ..." and "If, unexpectedly, ..."

https://twitter.com/RichFelker/status/1146906341417594887

[andrewrk]

Counter proposal: #5177

[daurnimator]

The builtin should probably more closely resemble the LLVM ‘llvm.expect.with.probability’ Intrinsic in that it also takes a probability of how likely the value is.

[andrewrk]

Both @cold (#5177) and this are accepted.

@expect(value, comptime expected_value: @TypeOf(value), comptime probability: f32) @TypeOf(value)

Returns value. value may be any type. probability is a value between 0 and 1.0, inclusive.

how to expect a certain switch prong how to expect a certain branch for if-optionals how to override the default and expect a certain branch for if-error-unions how to expect a certain branch for while-bool, while-optional, while-error-union

These are all solved with #5177 which is also accepted.

[johan-bolmsjo]

I want to add that apart from the mentioned benefits, readability and static hints for branch prediction it also reduce the pressure on the L1 instruction cache by typically moving cold instructions last in functions. I believe this to be the greatest benefit of using a likely/unlikely construct. For the longest time I was not a believer but I've seen the performance benefits of using this in a real product that was optimized a lot over its life time. Eventually we resorted to pepper the hot code paths with likely and unlikely. Ugly, but it can be effective.

[Snektron]

how to expect a certain switch prong

switch (@expect(123, x, 1)) {
  123 => { 
    // likely
  },
  124, else => {
    // unlikely
  },
}

Here its still impossible to order branches in likelyness. This could be handled with an if/else chain I guess.

[mlugg]

Here it's still impossible to order branches in likeliness.

@expect(123, @expect(124, x, 0.3), 0.7) perhaps? That said, the arg order makes this a bit weird. Perhaps it'd be better if it were @expect(123, 0.7, @expect(124, 0.3, x)). Or maybe even if @expect took a whole map of probabilities in some form, but maybe that's more complicated of a form than we want in a builtin.

Also, regarding the natural language point made earlier in this isue: perhaps @withExpectation would be a better name? "expect" is definitely better than "likely", but still reads a little weird.

[jacobly0]

I realize that this accepted definition of @expect matches an llvm intrinsic, but I do not believe that this is the most helpful tool for the programmer, for self-hosted backends, or for automated addition of profiling annotations to the source code.

As a programmer, I care less about the expected value and more about the expected branch, I want go to the part of the source code that contains the code path that I think is important and annotate that. Also, raw probabilities are problematic for keeping them consistent while editing code, what I really want are weights for each branch with a default of 1 for unannotated branches. Note that this doesn't prevent using weights that add up to some number like 100 and that translate directly to probabilities.

For self-hosted backends, assuming no higher level optimizations, the best you can do for an if branch is make the machine code likely branch (with the x86_64 branch predictor, not taken for conditional forward branches and taken for conditional backwards branches) match a source code annotation. This is certainly possible with the accepted @expect definition, but requires either Sema to shuffle around the information to be more useful (basically an optimization pass at that point) or the backend to go through unnecessarily convoluted value tracking.

One optimization that can be done for switches on x86_64 is make the most likely prong a fake "fallthrough" from the indirect branch (which the x86_64 branch predictor assumes as the likely target). This is also compatible with the accepted definition of @expect. Additionally, we should not be take llvm's codegen as gospel and the best we can hope to accomplish. For example, we already expect to have to generate custom jump tables to codegen labeled continue. So there's no reason to expect that a self-hosted backend wouldn't use the same or similar logic. However, for switches that are not amenable to jump tables due to non-contiguity of prong items or due to overly large prong item ranges, we are in the realm of deciding how to order the value comparisons, for which we need more information for each prong to be able to make informed decisions. This requires something closer to what was more helpful for the programmer above.

For automated tooling, a profiler is going to have branch counts for each branch, and so it would be trivial to just edit the source code with an annotation for the branch count of each branch, which is just a weight as described above.

For a syntax proposal, in the interest of avoiding extra grammar complexity, I think there can just be a @branchWeight builtin or similar that applies a weight to the enclosing scope, just like many other builtins (@setEvalBranchQuota, @setFloatMode, @setRuntimeSafety). This would look like:

switch (x) {
    1 => { // likely
        @branchWeight(100);
    },
    2 => {}, // unlikely, default weight of 1
    // it seems like this branch should have a lower weight than the default
    // maybe a weight of 0, or floats weights < 1 could mean "cold" or "never optimize for this branch being taken"
    // in the future, branches that always trigger safety, panic, or error could be detected and treated like that
    else => unreachable,
}
while (true) {
    if (normal_term_cond) {
        @branchWeight(10); // slightly unlikely termination condition
        break;
    } else {
        @branchWeight(1_000); // very likely to keep looping
    }
    if (special_case) {
        @branchWeight(1); // very unlikely termination condition
        break;
    } else {
        @branchWeight(1_000); // very likely to keep looping
    }
}

[silversquirl]

Adding to jacobly's points, I also wonder whether @setCold could be merged with this somehow, as they fill similar purposes (at least from the perspective of the programmer). Perhaps a negative or zero @branchWeight at the top level of a function could replace it.

[andrewrk]

Unaccepted to consider #20642 as an alternative.