RyuJIT: Allow developers to provide Branch Prediction Information

The __builtin_expect function provided by GCC comes to my mind here. While I would root for a great profile based collection system, this could be very helpful as an stopgap into that direction.

http://stackoverflow.com/questions/7346929/why-do-we-use-builtin-expect-when-a-straightforward-way-is-to-use-if-else

category:cq
theme:profile-feedback
skill-level:expert
cost:large

@lemmaa

@lemmaa @seanshpark @parjong @chunseoklee We might need to consider this option (something like "likely" and "unlikely" macros in Linux kernel) for ARM optimisation.

@myungjoo

@myungjoo afaik the Linux kernel "likely" and "unlikely" is actually __builtin_expect( !!(x), 1) and __builtin_expect( !!(x), 0) respectively.

The idea that I had in mind is providing something like this:

public static class Unsafe
{
   [JitIntrinsec]
   [MethodImpl(MethodImplOptions.AggresiveOptimization)]
   public bool Expect ( bool value, bool branchTaken )
   {
       return value;
   }
}

In that way, if the JIT version do understand it, it can (after inlining) reorder the blocks and put the unlikely branch at the end of the method (very away from the critical path). If it is not understood, the inlining process will eliminate the call altogether.

Surely it is not an optimization for everybody, but there are cases where it would make sense.

Related issue: #4966

cc @dotnet/jit-contrib

I like the idea, and using Expect aligns with existing practice, but to me it messes with the readability of the code. Instead of writing if (Expect(cond, true) it would be nicer IMO to write if (ExpectTrue(cond)) or even if (PredictTrue(cond)), since (to me) that makes it clearer that a prediction is what's desired. Of course, one would then have the ExpectFalse or PredictFalse.

@CarolEidt

@CarolEidt I was using the existing practice to show the idea. Another alternative is if (Likely(cond)) and if (Unlikely(cond)) that has the plus of denoting how likely and unlikely that condition is bound to happen.

I think the biggest problem with this construct is its ability to become stale rapidly. There are certainly less problematic use cases, like error handling functions, whose likelihood is easy to validate via code inspection and can be abstracted behind wrapper methods, but other cases become very sensitive to level of programmer discipline to properly maintain accurate information, lest seemingly innocent refactoring leads to big local performance losses that accumulate because they are difficult to detect individually (bitrot).

I'm no fan of telling people they can't have a sometimes-useful feature just because other people might shoot themselves in the foot with it, but I do think we should consider not adding this until we have rich tooling/infrastructure available to validate the annotations and possibly even automatically update them based on profile data. The big problem with that argument is that such infrastructure would probably share a lot of features with a proper profile feedback system, so one might argue you should just wait for the whole thing.

That said, this is being proposed as a stopgap. Perhaps it's acceptable to live with the potential for misuse until a proper profile feedback system comes online, at which time we commit to the annotation validation infrastructure.

@RussKeldorph

@RussKeldorph wholeheartly agree with you, this is choosing between giving the developer the power to get higher quality code; which is easy to build (and probably can be done in a few weeks by one of your guys) and could have a huge impact, even if some devs occasionally forget they have a loaded gun and shoot themselves in the foot. On the other hand, we have a very hard problem which can takes months to build and probably a year or two to get right (which would be very useful to have available today, even in rudimentary state).

I am a lazy programmer, I would prefer the JIT to do the proper job every time, but I also know that is impossible for every single case... for most, if the JIT can handle the 99% its great, but IMHO we shouldnt punish the 1% either, because those are the framework, library and/or high performance developer that later make the great business cases. The work that was done at Kestrel on the performance front is such an achievement. A single morpher (https://github.com/dotnet/coreclr/issues/1619) improved most managed implementations of hashing functions (both at the framework and at our end) by a wide margin, couldnt have been done without providing the tools to do so.

The JIT could use likelihood information to type-specialize by cloning code for different cases. Here, it could specialize the code for arrays and other IList's:

IList<T> list = F();

Expect(list is T[]);

foreach (var item in list) ...

Turning into:

if (list is T[]) foreach (var item in (T[])list) //specialized for arrays
else foreach (var item in list)

Multiple cases could be supported e.g. Expect(list is T[] || list is List<T>).

Somewhat related to the Expect is the Unpredictable which could be useful for knowing when to apply cmov based conditionals branches optimizations proposed at https://github.com/dotnet/coreclr/issues/7447

Just to provide some context of the kind of speed up (and business value) this kind of optimization can achieve and the complexity of the code we have to write to work-around the lack of control.

This is the code we have to write:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public byte* GetTailPointer(int offset, bool isWritable = false)
{
    if (_lastTailPointer.PageNumber == Header.Ptr->TailPageNumber)
        return _lastTailPointer.Value.DataPointer + offset;

    // This is an unlikely case which doesnt make any sense to inline.
    // A method call is smaller than all the code that has to be executed. 
    return UnlikelyGetTailPointer(offset, isWritable);
}

private byte* UnlikelyGetTailPointer(int offset, bool isWritable)
{
    var page = _pageLocator.GetReadOnlyPage(Header.Ptr->TailPageNumber);
    _lastTailPointer = new PageHandlePtr(page, isWritable);
    return page.DataPointer + offset;
}

and we have many such routines, it is not an isolated case.

For a detailed analysis on how much we are able to gain using this workaround see: https://ayende.com/blog/175841/multiple-optimizations-passes-with-case-insensitive-routing

For reference purposes...

This is pre-optimization:

We shaved 6%+ (or 250ms) with this simple change (which could have been automatically done by the JIT knowing the second part of the branch is Unlikely):

And given these results, we are sure that using unlikely hints at the codegen level could generate far bigger improvements...

Hope this helps to upgrade the priority of this optimization ;)
For us it means that we can serve a lot more requests, which is good for business. Noone has ever called to request we give them their slowness back. ;)

PS: For the other ugly hacks, aka optimization oportunities, you can take a look to that and other blog series where we show the workarounds we use.

This looks like partial inlining, not branch prediction stuff. Granted, partial inlining would need to know if the branch is likely taken or not but ultimately partial inlining is a feature in its own right and not a trivial one.

Branch predicción and aggresive inlining will behave in the same way as partial inlining. I the JIT knows that first part of the code is expected or the second is rare, then it will be marked cold. the rare block of code is going to be written at the end of the method. With the added benefit of skipping the method call altogether. Partial inlining in its own right is very difficult but you can still get a restricted one with branch prediction information.

aggresive inlining

This doesn't apply to TryGetValue because it contains exception handling. So we're back at square one, you want branch prediction hints but in reality you need inlining to work in the presence of EH.

the rare block of code is going to be written at the end of the method

It doesn't really matter where that block of code is going to be written. What marking a block as rarely run may do is improve register allocation and in turn that may make the surrounding code more efficient. Or not, it depends on the code.

You got 6% improvement by eliminating a call from a hot path. There's no evidence anywhere that lifting the EH inlining restriction and inlining the original TryGetValue would have resulted in a significant performance penalty due the absence of branch prediction hints.

Not really that is just a single example, our most common example is the code I posted (as code).

Agree that the blog example which would require EH but we can still workaround it (as we did it) in those cases. Most of the time we are just dealing with our code, therefore we are (among other things) abusing goto's to control the emitted code and generate cold sections by hand (which could be solved by the JIT if the hint is provided). The improvement is rarely less than 6% on tight code-paths (which we have many).

If you are interested into measuring the difference on a real business critical example just try out the different alternatives of our PageLocator (which is at the core of the ACID storage). The most advanced one includes tricks like unrolling, disabling the bound-checks, jump tables, fingerprinting and cold sections (all forced by hand): https://github.com/Corvalius/ravendb/blob/v4.0/bench/Micro.Benchmark/PageLocatorImpl/PageLocatorV7.cs
It's ugly but fast!!! For comparisons check the original one and the V7 tables that were posted at https://github.com/dotnet/coreclr/issues/7572 .. At the 8 items level we are talking about 22ns to 16ns which is like a 50% improvement total on very tight code. At the 32 items we are talking about 100ns to 23ns, which is 430+% (give or take) improvement.

The one that probably is most interesting for this issue purposes is:
https://github.com/Corvalius/ravendb/blob/v4.0/bench/Micro.Benchmark/PageLocatorImpl/PageLocatorV5.cs

I think several things that RyuJIT currently doesn't do have been said here. Namely:

Profile Feedback
Partial Inlining
Inlining in presence of EH
Induction variable promotion

Does anyone like to see them made into GH issues (if not already) for tracking purposes?

Is this something that can/should be baked into IL as prefixes for branching instructions? Ultimately I'd like to see something like this:

void DoSomething(int x)
{
    if unlikely(x < 0) throw new ArgumentOutOfRangeException(nameof(x), "can't be below 0.");
    if unlikely(x > 100) throw new ArgumentOutOfRangeException(nameof(x), "can't be above 100.");
    // important code.
}

I'd like this to drive code generation to pack the hot path as close together as possible for cache optimization. So this would create:

cmp x, 0
jb throw_below
cmp x, 100
ja throw_above
; important code
ret
throw_below:
...
throw_above:
...

This could also enable PGO prior to distribution without needing AOT.

@scalablecory

@scalablecory For blocks that clearly always throw, shouldn't that be done automatically? I think unlikely is not necessary for that case.

@svick

@svick you're right, I totally forgot about that rule. So -- not the best example. There are plenty more blocks I could use this for, though.

The problem is that for a lot of code this doesn't matter, but when it does matter it can have a significant benefit... which means perf-sensitive code (often not the simplest to read already) becomes even more loopy, like with @redknightlois's example.

I have plans sketched out for how the JIT should eventually tackle this sort of thing (as part of a much larger effort), but haven't ever polished them to the point where they'd make sense to a wider audience. Let me try and give an overview here:

Enhance ability of the the jit to represent layout-influencing information from a variety of sources: user annotations, internal heuristics (like the throw case above, and more generally some kind of static profile synthesis), and actual profile feedback (either out of band like current IBC, or in process). Represent all "weights" as normalized execution frequencies.
Introduce profile maintenance and repair techniques so that as code is transformed by the jit, this information is kept reasonably self-consistent and approximately correct and can be relied on by downstream phases. General principle here is that local invariants (exit probabilities, say) are easy to incrementally maintain; global invariants (count consistency / Kirchoff's law) are hard to maintain but can be restored when it's valuable to do so (say before layout or register allocation).
Update inliner to take this information into account. This is the largest beneficiary.
Implement a code layout algorithm. This is the second largest beneficiary. Ideally equip layout with a notion of idealized benefit (layout score). I have had good results in other compilers by starting with a greedy reverse-post-order layout (which is fairly cheap to determine) and then if time permits, improve things from there via local search (using TSP techniques like "3-opt").
Also feed this information into other key phases (LICM, loop cloner, allocator, finally cloning) that need to make cost/benefit assessments.
Generalize hot/cold method splitting so it can be used while jitting.
Develop capabilities and heuristics for tail/head merge, number of returns, and other flow-related transformations.
Look into relaxing some of the current runtime-imposed layout constraints (eg must keep try regions contiguous) by changing how EH clause information is conveyed to the VM.

I was hoping to get some of the groundwork for this in place during 3.0 but it didn't happen. As we start to think about post-3.0 work, I'll try and polish my notes and put forth specific proposals for some of the above.

Also it'd be nice to have an api for switch expressions like what case to expect:

switch(Expect(x, 10)) {
    case 0:

With any luck we may actually get around to this in the 8.0 release.

Cost on its own is not large, but it's a follow-on on efforts that are large, so leaving the costing as is for now.

Navigation Menu

Repository navigation

RyuJIT: Allow developers to provide Branch Prediction Information #6225

5 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

RyuJIT: Allow developers to provide Branch Prediction Information #6225

Description

Activity

myungjoo commented on Jun 28, 2016

redknightlois commented on Jun 28, 2016

mikedn commented on Jun 28, 2016

pgavlin commented on Jun 28, 2016

CarolEidt commented on Jun 29, 2016

redknightlois commented on Jun 29, 2016

RussKeldorph commented on Jun 29, 2016

redknightlois commented on Jun 30, 2016

GSPP commented on Aug 6, 2016

redknightlois commented on Oct 4, 2016

redknightlois commented on Oct 28, 2016

mikedn commented on Oct 29, 2016

redknightlois commented on Oct 29, 2016

mikedn commented on Oct 29, 2016

redknightlois commented on Oct 29, 2016

5 remaining items

choikwa commented on Nov 18, 2016

scalablecory commented on Apr 1, 2019

svick commented on Apr 1, 2019

scalablecory commented on Apr 1, 2019

AndyAyersMS commented on Apr 1, 2019

EgorBo commented on Oct 9, 2019

AndyAyersMS commented on Oct 21, 2022

AndyAyersMS commented on Oct 21, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions