Repository navigation
Performance Improvement: Value Range Test #61664
Description
Description
JIT cannot at this time perform conditional move or set operations. For example with ternary operators. I'd like to bring up different ideas to reduce branching and am asking if such morphing can be achieved now with the current JIT.
I'm also trying to get more familiar with the JIT optimizer, so I maybe can integrate such ideas myself. I have everything I need to do so, I just have to give myself patience and time.
Most often, there is code to check for a range of values... for example
bool Condition1 = 'A' <= chr && chr <= 'Z';
bool Condition2 = chr is >= 'A' and <= 'Z'; This can be morphed into:
bool Condition1 = ((unint) chr - 'A') <= (unint)('Z' - 'A');Both must be constants, the comparison needs to be unsigned. Benefit is the reduction of 2x branching into 1x branching.
Question: Is such morphing possible now? Without major code rewrite?
Morphing would be:
bool Condition1a = C1 <= val && val <= C2;
bool Condition1b = C1-C1 <= val-C1 && val-C1 <= C2-C1;
bool Condition1c = 0 <= (nuint)(val-C1) && (nuint)(val-C1) <= (nuint)(C2-C1);
bool Condition1d = true && val-C1 <= C2-C1;
bool Condition1e = val-C1 <= C2-C1;- it will work both signed/unsigned when C1 <= C2 and at stage 1c both values are cast to unint. (native int to have val-C1 overflow)
- it will also work for "<" comparison when C1/C2 is adjusted (shifted by 1)
Analysis
I wrote some helper functions that will achieve this morphing. And it works. It will be faster, but I cannot add any useful benchmark, as the CPU branch predictor will counter any benefit. Maybe by unrolling a large loop and feeding it with data that will always mispredict the branch...
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static bool CondA(int value, int low, int high) => low <= value && value <= high;
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static bool CondB(int value, int low, int high) => (nuint)(value - low) <= (nuint)(high - low);
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static int TestA(int value) => CondA(value, 'A', 'Z') ? 1 : 2;
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static int TestB(int value) => CondB(value, 'A', 'Z') ? 1 : 2;TestA disassembly:
G_M52463_IG01:
;; bbWeight=1 PerfScore 0.00
G_M52463_IG02:
cmp ecx, 65
jl SHORT G_M52463_IG05
;; bbWeight=1 PerfScore 1.25
G_M52463_IG03:
cmp ecx, 90
jg SHORT G_M52463_IG05
mov eax, 1
;; bbWeight=0.50 PerfScore 0.75
G_M52463_IG04:
ret
;; bbWeight=0.50 PerfScore 0.50
G_M52463_IG05:
mov eax, 2
;; bbWeight=0.50 PerfScore 0.12
G_M52463_IG06:
ret
;; bbWeight=0.50 PerfScore 0.50
; Total bytes of code 22, prolog size 0, PerfScore 5.33, instruction count 8, allocated bytes for code 22 (MethodHash=bdf53310) for method SharperDisasm.RegisterExtensions:TestA(int):int
; ============================================================TestB disassembly:
G_M7244_IG01:
;; bbWeight=1 PerfScore 0.00
G_M7244_IG02:
add ecx, -65
movsxd rax, ecx
cmp rax, 25
jbe SHORT G_M7244_IG05
;; bbWeight=1 PerfScore 1.75
G_M7244_IG03:
mov eax, 2
;; bbWeight=0.50 PerfScore 0.12
G_M7244_IG04:
ret
;; bbWeight=0.50 PerfScore 0.50
G_M7244_IG05:
mov eax, 1
;; bbWeight=0.50 PerfScore 0.12
G_M7244_IG06:
ret
;; bbWeight=0.50 PerfScore 0.50
; Total bytes of code 24, prolog size 0, PerfScore 5.40, instruction count 8, allocated bytes for code 24 (MethodHash=e215e3b3) for method SharperDisasm.RegisterExtensions:TestB(int):int
; ============================================================
Activity
EgorBo commentedon Nov 16, 2021
Duplicates #8418
Btw:
is slower than:
for cases where
chris smaller thanA. (but we can handle it via PGO data).hopperpl commentedon Nov 16, 2021
Yes. Casting to
nuintis also not needed here,uintwould be sufficient. Forchar/ushorteven a cast toushort, if the comparison is handled in a 16-bit register. Similar withbyte. But this is a decision only the JIT optimizer can make.The benchmark issue is range of values, order of comparison and input value predictability. And order of condition.
I have a critical code block that needs to be run 25 million times per second with unpredictable input. This gives me 40 ns per run and so far I reduced it from 95 ns down to 35 ns by just rearranging branches and conditions. Or removing conditions altogether. Exploiting the static branch predictor to adjust unlikely code flows. Very excited about PGO support in JIT which will do that for me.
Small modification to a helper function that gets fully inlined:
for chases where
chris smaller thanAor greater thenZ, the branch is not mispredicted. PGO can rearrage flow, but if I'm not mistaken, it still is left with 2 comparisons.The would be a beautiful scenario for a
cmovbeinstruction, but I'm aware of the challenge.On a side note what I find interesting is, that if I use
charinstead ofintfor parameters, the JIT adds amovsxinstruction, okay all math only on 32-bit, but it spillsrdxas additional register instead of usingrcxlike for this case.JulieLeeMSFT commentedon Nov 18, 2021
@hopperpl l I am closing this ticket becaues it is duplicate. Please continue discussion in #8418.