-
-
Notifications
You must be signed in to change notification settings - Fork 2.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
introduce @branchWeight
builtin with numerical branch weights
#20642
Comments
The only issue I see here is that this doesn't work so well with #8220, because |
@mlugg If I understand your comment correctly, the actual distinction here would be to mark the branches = code paths rather than the target block they lead to. Current syntax might make this more verbose than would be ideal, but here's some examples anyway:
if (iterator.hasNext()) {
@branchWeight(2); //unlikely to enter
while(true) {
const next = iterator.next().?;
// actual logic - no @branchWeight directly here
if (!iterator.hasNext()) {
@branchWeight(1); //very unlikely to exit
break;
}
@branchWeight(20); //very likely to continue looping
}
}
switch(nextToken()) {
.end => {},
else => |tok| {
switch (tok) {
.a => @branchWeight(1), //unlikely to be .a initially
}
inner: switch(tok) {
.a => {
// actual logic - no @branchWeight directly here
const next_token = nextToken();
switch(next_token) {
.a => @branchWeight(20), //very likely to be .a as a followup
// other cases...
}
continue :inner next_token; //or alternatively inline this continue into the switch above with `@branchWeight` to make it easier for the optimizer to understand this?
},
// other cases...
}
}
} |
The idea of a builtin on the block instead of the condition makes sense to support cases where the condition isn't visible (or would be annoying to make visible) in the source code like captures ( One thing that still feels fuzzy is the idea of having arbitrary weight values. The original mentions that probability values are problematic when keeping consistent across code edits. But more concretely, there's the argument for switch cases and profiling: Switch cases in reality have little control on how they're dispatched: If a case is marked as "likely/unlikely" but a jump table would be ideal, what should codegen do here? If cases are sparse (jump table unavailable), what is the codegen for two equally "likely/unlikely" cases? Branch hints primarily affect which path falls through a conditional and which is jumped to. Default Switch statements don't execute comparisons in order (you can have Profiling (Profile Guided Optimization) tracks which branches are taken to form a probability model, but how this affects codegen is another story: PGO can either 1) reorganize branching to make most/least probable ones fall-through/jumped-to or 2) eliminate the (conditional) branch entirely. The latter is aggressive and only correct when the optimized program will only run again with similar inputs to when profiled. The former is still a decision that's binary, not probability/weighted. Note It's also unclear how PGO could take advantage of "source code annotations" here since it bases optimizations on what's executed not speculated. Maybe it could report if an unlikely-marked branch was profiled to be more likely? Either ways, no codegen changes that this builtin wouldn't already do. I propose the builtin be renamed to something like
|
I’m not a fan of “weight” values with undefined semantics (in general), because it leads to paranoid developers doing things like (It may be too early, but) it would be nice if this had a documentation that;
These are just the concerns that pop into my head, I don’t know how it would actually be implemented. |
This seems a little bit arbitrary. Why not use floats and specify 1.0 as the default weight? |
LLVM's branch weight metadata encodes probability. To those who suggest to toss out this data, can you explain why LLVM devs have decided to include this information, and why they have made a mistake by doing so? |
LLVM optimizes branches using weights to be compatible with PGO:
The weights are also influenced by variables like what's inside the branch. LLVM internally warns against using arbitrary weights given the clash with implementation thresholds. We should take their advice and prefer the binary |
Is there any kind of control flow that would want information about the source of a branch other than replicated dispatch switch loops? In a replicated dispatch switch loop you probably would want to have more control than simply saying which is the mostly likely target anyway, so I don't think sw_loop: switch (instructions[i].tag) {
.add => {
i += 1;
continue :sw_loop @branchWeight(.{ .add 4 }, .{ .mul, 2 }, .{ .div, 1 }) intructions[i].tag;
},
.mul => {
i += 1;
continue :sw_loop @branchWeight(.{ .add, 2 }, .{ .mul, 3 },}) intructions[i].tag;
},
.div => {
i += 1;
continue :sw_loop intructions[i].tag;
},
} That looks a bit unweildy, but maybe it could take an anonymous struct instead allowing the weight map to be specified elsewhere and leaving
This could be modelled with either if (condition) {
@branchWeight(1);
while (true) {
@branchWeight(2);
// loop code
if (!condition) {
@branchWeight(1);
break;
}
}
} else {
@branchWeight(2); // shouldn't be needed given default weight of 10
} It may be sensible to just make the above the interpretation of an 'unexpected' loop body so it could be simply written as while (condition) {
@branchWeight(1);
// loop code
} else {
@branchWeight(2); //shouldn't be needed given default weight of 10
} as I'm not sure it makes sense (and as far as I know it's not possible) to have a loop continually predicted to exit.
I would expect the branch weightings to just be additional input to assist codegen heuristics - there doesn't have to be a order-preserving map between the weightings and the branch's preference in the generated code, rather I would expect them to be used to try and optimise something like branch-weight-weighted average performance. If a jump table would be ideal just ignore them and generate a jump table. For sparse cases there could be a whole rabbit hole of techniques here, but the weights provide the information needed to make decisions. It should be relatively straightforward to map branch weights to a binary decision tree that optimises fall-through/jump behaviour relative to the provided weights; while any specific branch in that tree is binary the best way to arrange the whole tree requires the per-branch weighting information precisely because there is no comparison order information in a switch statement.
Even if we use the binary API, we can still use something like |
An efficient dispatch switch should have dense comparison targets so that it generates a jump-table. If the cases are sparse, then dispatch is no longer efficient and hints wont help: It then requires at most log(N) comparisons and choosing which to fall-through into with a
A weight can dictate the level in the comparison tree that a conditional appears (and maybe the order in that level), but not which side or the depth of the tree. So in these tree-based sparse comparisons, one still can't accurately control branching codegen. As a practical example, something like this could be written using a switch statement. But unsure how weights at each case could achieve the desired codegen compared to its explicit use of likely
I think so too. A while loop at codegen is two conditionals: 1) condition to enter the loop and 2) condition to keep going. For a loop to jump back up, 2) must conditionally branch so its fundamentally unlikely. The branch hint would then apply to 1) for whether it falls-through to loop body or jumps-away to it. |
Technically unrolling the loop is a mechanism to model 2) as the likely branch via inlining, although the resulting code size limits the scalability of this. |
I agree that the programmer is not going to have precise control over the branching and I don't think they ever will with a sparse switch; what I'm getting at is that I would expect a 'sparse switch optimizer' to be minimizing some (potentially target specific) objective function of branch weights.
I think I agree with you, though I might have to think about that last sentence a bit more (not 100% sure at the moment what you mean with the cancelling out). I wasn't really trying to suggest the branch weights in switch continue loops is going to be very useful because, as you say, when you care you'll make jump tables. I was just saying that I think if someone did end up wanting source and target branch information for some kind of optimization pass here I think a special form of |
@jacobly0 I would value your input here if you have the energy to spare. Otherwise I'll go ahead and make an executive decision. |
I was mostly just exploring ideas that hadn't been discussed yet, so I don't have much more to say than I already did, since it seems to have accomplished the goal of creating more discussion. I can reiterate the points that I personally give extra weight to, which are that "expected value"-based builtins are, in my experience, difficult to use as a programmer, especially during refactors, and potentially impossible to make use of by a self-hosted backend. There needs to be a direct way of associating the annotation with the (air) instructions that it is supposed to affect.
This would also allow adding things like .unpredictable to encourage an optimizer to perform branchless speculation of both prongs, something which isn't representable with probabilities/weights.
Just want to explicitly mention that one of the extra implications of cold over unlikely is that cold code can be loaded to different pages of memory than other code. This allows each page fault to load more hot code with the expectation that a cold code path is allowed to be very expensive the first time it is executed, and locality with nearby code is not desirable. This means that it is possible for an unlikely annotation to be beneficial where a cold annotation would be harmful. |
@jacobly0, regarding coldness allowing code to live in different memory pages, perhaps this could be another enum variant, e.g.: const BranchWeight = enum {
/// This branch of control flow is more likely to be reached than its peers.
/// The optimizer should optimize for reaching it.
likely,
/// This branch of control flow is less likely to be reached than its peers.
/// The optimizer should optimize for not reaching it.
unlikely,
/// It is difficult to predict whether this branch of control flow will be reached.
/// The optimizer should avoid branching behavior with expensive mispredictions.
unpredictable,
/// This branch of control flow is unlikely to *ever* be reached.
/// The optimizer may place it in a different page of memory to optimize other branches.
cold,
}; |
If possible, I think multiple calls of this builtin in the same branch should be a compile error. I can't think of a reason to have multiple calls in the same branch other than to add confusion |
Discussion continues at #21058 |
@branchWeight
builtin@branchWeight
builtin with numerical branch weights
Rejected in favor of #21148. |
Originally specified at #489 (comment).
This proposal supplants:
@setCold
with@cold
#5177Summary:
@branchWeight
builtin.u32
This generalizes better to
switch
expressions.This allows source code to be annotated with PGO data.
The text was updated successfully, but these errors were encountered: