Zig: @expect() hint to optimzer

[PavelVozenilek]

Accepted Proposal

---

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 [e-mail]:

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