RyuJIT: optimize comparisons for const strings

[EgorBo]

Let's say I have a code:

public bool Test()
{
    return Validate("FAILED");
}

bool Validate(string name)
{
    return name != "FAILED";
}

Validate is inlined into Test like this:

public bool Test(string name)
{
    return !string.Equals("FAILED", "FAILED");
}

And it's not optimized into just false constant.
There are 3 solutions to fix it:

1. Intrinsify string.Equals, working prototype: EgorBo@06eca1c
2. Make string.Equals always inlineable via [MethodImpl(MethodImplOptions.AggressiveInlining)] and it will work! However, it will significantly regress non-constant cases - definitely not an option.
3. Tweak the inliner a bit, because it almost passes the threshold due to constant args + conditions, a simple repro:

public bool Test()
{
    // should be inlined but currently is not.
    return !String_Equals("hello", "hello");
}

public static bool String_Equals(string a, string b) // Code size: 36
{
    if (object.ReferenceEquals(a, b))
    {
        return true;
    }
    // `a is null` and `b is null` increase the multiplier (constant args into constant tests), good
    if (a is null || b is null || a.Length != b.Length) // jit doesn't know `a.Length` and `b.Length
                                                        // will be optimized into constants (see https://github.com/dotnet/runtime/pull/1378)
    {
        return false;
    }

    return EqualsHelper(a, b);
}

[MethodImpl(MethodImplOptions.NoInlining)]
private static bool EqualsHelper(string a, string b) => false;

Inline candidate looks like a wrapper method.  Multiplier increased to 1.
Inline candidate has an arg that feeds a constant test.  Multiplier increased to 2.
Inline candidate has const arg that feeds a conditional.  Multiplier increased to 5.
Inline candidate callsite is boring.  Multiplier increased to 6.3.
calleeNativeSizeEstimate=521
callsiteNativeSizeEstimate=115
benefit multiplier=6.3
threshold=724
Native estimate for function size is within threshold for inlining 52.1 <= 72.4 (multiplier = 6.3)
// but doesn't pass max amount of BB check :-( 

E.g. if I remove object.ReferenceEquals(a, b) it will be inlined!

category:cq
theme:inlining
skill-level:intermediate
cost:medium

[stephentoub]

Can you share some examples where this occurs in production code?

[benaadams]

Can you share some examples where this occurs in production code?

Would this be triggered by Attribute annotations? e.g. string in attribute then used by switch or if when interpreting that attribute.

[stephentoub]

Would this be triggered by Attribute annotations? e.g. string in attribute then used by switch or if when interpreting that attribute.

The consuming code using reflection to access the attribute wouldn't see it as a const, right? And even if it did, we're talking about reflection; the extra optimizations matter in such cases?

[EgorBo]

Can you share some examples where this occurs in production code?

I'll try to find production cases but I am more interested in feedback regarding the jit inliner as I think it should allow to inline more calls when args are const strings (with arg.Length conditions inside) -- String.Equals is more like an example of a profitable inline. Jit is already smart enough to take const args + conditions into account, e.g. see sharplab (and here). But it doesn't work for strings yet (however it knows about Array.Length).

Also in theory we can optimize things like Environment.GetEnvironmentVariable("myvar") == "value" (in JIT mode only), Environment.MachineName == "testmachine" etc.. (if we make these methods/props intrinsic)

[jkotas]

I think teaching JIT to inline SpanHelpers.SequenceEqual for small constant sizes may make sense. The C/C++ compilers do this sort of optimization for memcmp.

we can optimize things like Environment.GetEnvironmentVariable("myvar") == "value" (in JIT mode only), Environment.MachineName == "testmachine" etc.

Both of these can change during process lifetime. And both of these are expensive operations by design that are not meant to be called on hot paths. Not worth doing anything for these in the JIT.

[EgorBo]

I have a demo! Inliner now takes string.Length into account for const args and increases the benefit multiplier. E.g.

public static void Test()
{
    Validate("hello");
}

public static void Validate(string a)
{
    if (a.Length > 10)
        throw new Exception();
}

Currently Validate won't be inlined into Test:

Native estimate for function size exceeds threshold for inlining 64.3 > 45 (multiplier = 5.3)

So the current codegen for Test is:

; Method Program:Test()
G_M24707_IG01:
       4883EC28             sub      rsp, 40
G_M24707_IG02:
       48B9E0310C235C020000 mov      rcx, 0x25C230C31E0
       488B09               mov      rcx, gword ptr [rcx]
       E81AA3FEFF           call     Program:Validate(System.String)
       90                   nop      
G_M24707_IG03:
       4883C428             add      rsp, 40
       C3                   ret      
; Total bytes of code: 28

With my inliner fix, the codegen for Test is now:

; Method Program:Test()
G_M24707_IG01:
G_M24707_IG02:
       C3                   ret      
; Total bytes of code: 1

Here is the fix (it's based on existing CALLEE_ARG_FEEDS_RANGE_CHECK and CALLSITE_CONSTANT_ARG_FEEDS_TEST): EgorBo@3810c21

cc @AndyAyersMS 🙂

Inline candidate has const arg that feeds string.Length + const test.  Multiplier increased to 7.
Inline candidate callsite is boring.  Multiplier increased to 8.3.
calleeNativeSizeEstimate=643
callsiteNativeSizeEstimate=85
benefit multiplier=8.3
threshold=705
Native estimate for function size is within threshold for inlining 64.3 <= 70.5 (multiplier = 8.3)

[AndyAyersMS]

@EgorBo it probably costs too much jit time to resolve every callvirt token.

Noticing the when caller passes or callee pushes constant strings and that those values are then used in comparisons or as the "this arg" in calls is probably the sort of analysis we can afford here.

I can work up a code sketch, but it may take me a day or two.

[sfiruch]

@AndyAyersMS Is it too expensive even for tiered JIT?

[AndyAyersMS]

Is it too expensive even for tiered JIT?

@deiruch probably so. At some point down the road we'll be able to consider more aggressive optimizations in higher tiers, but we're not there yet.

[EgorBo]

Probably not so important for R2R? and then R2R can give hints to Tier1 where it's profitable to inline.
I guess there are other things we could resolve, e.g. IntPtr.Size == 8, BitConverter.IsLittleEndian, Sse.IsSupported etc

[YairHalberstadt]

As a motivating example, consider a source generator that generates a method which acts differently depending on where it's called form. To do so it switches on CallerLineNumber, and CallerFilePath.

For example, a source generator might provide a method to print the expression passed into it as an argument (see it on sharplab):

using System;
using System.Runtime.CompilerServices;

public static class Program
{
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    public static void Main()
    {
        Console.WriteLine(Helpers.PrintExpression(1 + 3 + 7));
        Console.WriteLine(Helpers.PrintExpression(new object()));
        Console.WriteLine(Helpers.PrintExpression(5 == 7));
    }
}


public static partial class Helpers
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static string PrintExpression(object expression, [CallerFilePath] string filePath = default, [CallerLineNumber] int lineNumber = default)
    {
        return lineNumber switch {
                10 => filePath switch { "main.cs" =>  "1 + 3 + 7", _ => ""},
                11 => filePath switch { "main.cs" =>  "new object()", _ => ""},
                12 => filePath switch { "main.cs" =>  "5 == 7", _ => ""},
                _ => ""
        };    
    }
}

By inlining you can get rid of the first switch, on CallerLineNumber, but not the inner switch, on the file path.
If the inner switch is large enough to use a hash switch, the jit will also need to be smart enough to recognize this pattern, and optimize it away. That should be reasonably doable, as the use of <PrivateImplementationDetails>.ComputeStringHash is a dead giveaway.