Runtime: Allow CLR to get/invoke direct pointer to a virtual method (interface method)

[dmitriyse]

Current CLR implementation have two OpCodes that works with virtual methods:
ldvirtftn -> "vtable offset"
"vtable offset" -> callvirt

In this feature request new OpCode is introduced: "ldvirtftnptr".
This opcode should resolve direct pointer to the virtual/interface method.
ldvirtftnptr -> "pointer to method"
"pointer to method" -> call (with load "this" object as a first argument)

With this CLR improvement, compilers will be able to eliminate performance penalty of virtual method call.

For example:

public class A
{
    public virtual int GetValue()
    {
         return 1;
    }
}

public class B: A
{
    public override int GetValue()
    {
         return base.GetValue() * 2;
    }
}

// Client code that is sensitive to a virtual method call performance.
A b = new B();
int sum = 0;

// resolve direct pointer to machine code of b.GetValue() implementation and store it in the stack
// IL:   ldvirtftnptr  b.GetValue() 
for (int i = 0; i < 100; i++)
{
     // IL:  load "b" as the first argument to subsequent call
     // IL:   call (0x28 opcode)  with the direct pointer to machine code of b.GetValue() implementation
     sum += b.GetValue();
}

It's a kind of devirtualization.
The same idea is described here http://blog.llvm.org/2017/03/devirtualization-in-llvm-and-clang.html and implemented in LLVM since version 4.0.
It's referenced here as "Devirtualization of function calls inside loops"

LINQ to objects will receive huge performance improvement from this feature.

[benaadams]

The Jit in .NET Core will now does this optimization sharplab.io

using System;
public class C 
{
    public int M() 
    {
        A b = new B();
        int sum = 0;

        for (int i = 0; i < 100; i++)
        {
            sum += b.GetValue();
        }

        return sum;
    }
}

public class B: A
{
    public override int GetValue()
    {
         return base.GetValue() * 2;
    }
}

public class A
{
    public virtual int GetValue()
    {
         return 1;
    }
}

C..ctor()
    L0000: ret

C.M()                              ; No virtual calls
    L0000: sub rsp, 0x28
    L0004: xor eax, eax
    L0006: xor edx, edx
    L0008: add eax, 0x2
    L000b: inc edx
    L000d: cmp edx, 0x64
    L0010: jl L0008
    L0012: add rsp, 0x28
    L0016: ret

B..ctor()
    L0000: ret

B.GetValue()
    L0000: mov eax, 0x2
    L0005: ret

A..ctor()
    L0000: ret

A.GetValue()
    L0000: mov eax, 0x1
    L0005: ret

[dmitriyse]

The same idea is described here http://blog.llvm.org/2017/03/devirtualization-in-llvm-and-clang.html and implemented in LLVM since version 4.0.
It's referenced here as "Devirtualization of function calls inside loops"

[Suchiman]

@benaadams but sharplab shows the desktop JIT, not coreclr.

[dmitriyse]

@benaadams please point me the version of CLR where this optimization has introduced ?

[dmitriyse]

@benaadams, no, this optimization is not implemented in CLR
https://sharplab.io/#v2:EYLgHgbALANALiAhgZwLYB8ACBmABJgJlwGFcBYAKAG9Lc788BLAOzlwFkAKAQV2AEpa9GhXpjcLNsgCuqXAF5cABgDclIeNwAzAPYAnXJ0kSFylSYA8uAIxLVEgNQPBozbhFvxMuQ8XAAdADiAKZwAGqIADbSwZz8aq6aAL7qieKYAOy43gliKRT5lDj4RABCILjclB70xToAbsF6eowAJsESrLgh4VExcRrug+lZwCjBQaER0bH8uABUuAS59PmFFMWEldWDxfWMenDSUZ1sPdP9LmI1bpk2K3RrqZRAA=

public class C 
{
    public int M(A b)
    {
        int sum = 0;

        for (int i = 0; i < 100; i++)
        {
            sum += b.GetValue();
        }

        return sum;
    }
}

public class B: A
{
    public override int GetValue()
    {
         return base.GetValue() * 2;
    }
}

public class A
{
    public virtual int GetValue()
    {
         return 1;
    }
}

; Desktop CLR v4.7.3163.00 (clr.dll) on amd64.

C..ctor()
    L0000: ret

C.M(A)
    L0000: push rdi
    L0001: push rsi
    L0002: push rbx
    L0003: sub rsp, 0x20
    L0007: mov rsi, rdx
    L000a: xor edi, edi
    L000c: xor ebx, ebx
    L000e: mov rcx, rsi
    L0011: mov rax, [rsi]
    L0014: mov rax, [rax+0x40]
    L0018: call qword [rax+0x20]
    L001b: add edi, eax
    L001d: inc ebx
    L001f: cmp ebx, 0x64
    L0022: jl L000e
    L0024: mov eax, edi
    L0026: add rsp, 0x20
    L002a: pop rbx
    L002b: pop rsi
    L002c: pop rdi
    L002d: ret

B..ctor()
    L0000: ret

B.GetValue()
    L0000: mov eax, 0x2
    L0005: ret

A..ctor()
    L0000: ret

A.GetValue()
    L0000: mov eax, 0x1
    L0005: ret

[benaadams]

Ah you mean hoist the resolution of the virtual call outside the loop; then use the resolved call in the loop?

Could maybe even do this with IEnumerable+IEnumerator

public class C 
{
    public int M() 
    {
        var sum = 0;
        foreach (var i in GetEnumerator())
        // Type of IEnumerator is fixed in the loop, could be resolved prior
        // rather than interface call per iteration
        {
            sum += i;
        }

        return sum;
    }

    IEnumerable<int> GetEnumerator()
    {
        return new List<int>() { 1, 2, 3 };
    }
}

/cc @AndyAyersMS

[dmitriyse]

In this example, the optiimzation has performed on a JIT level. But JIT is not smart enough to handle all cases. New OpCodes for "virtual call resolution" will allow to do optimizations on a compiler level.

See LLVM approach, they introduced new special hints for that kind of optimization.

[svick]

But JIT is not smart enough to handle all cases.

Just because the JIT is not smart enough right now doesn't mean that will always be the case.

New OpCodes for "virtual call resolution" will allow to do optimizations on a compiler level.

I think adding new opcodes has an incredibly high cost. Pretty much every piece of code that does something with opcodes would have to be updated.

That doesn't mean it should never be done, but it has to be something that has very high benefit and no reasonable alternatives. I think this proposal does not fit that: the benefit is not that high and the alternative of doing this purely in the JIT should be possible.

See LLVM approach, they introduced new special hints for that kind of optimization.

As I understand it, the LLVM IR is intentionally an unstable API that keeps changing with every version. On the other hand, I think CIL didn't change since .Net Framework 2.0, which makes the threshold for changes quite different.

[dmitriyse]

But JIT is not smart enough to handle all cases.

Just because the JIT is not smart enough right now doesn't mean that will always be the case.

Jit will never be smarter than IL producers. So whenever you want to optimize something "put it behind the JIT" is a wrong approach in general. For example I have created another issue that practically will never implemented by JIT (https://github.com/dotnet/coreclr/issues/17272). So JIT is already incredibly complex.

New OpCodes for "virtual call resolution" will allow to do optimizations on a compiler level.

I think adding new opcodes has an incredibly high cost. Pretty much every piece of code that does something with opcodes would have to be updated.

True, this is the problem. But look to CPU world, they are adding instructions and world still survives.
This feature can increase general C# code performance up to 20%, please compare cost of other efforts that gives the same result.

LLVM is just an example. GCC, CLANG also have that kind of optimization. So that's why C++ have benefits over C#. Here 10% there 5% another place with 15%, trick, trick and finally C++ faster in two or more times in general.

Remember what's MS evangelists say: "Performance is a feature"!

[dmitriyse]

CPU producers will more likely add some additinal instruction that can help C++ to optimize performance rather than implement some tricks to improve performance of GCC produced assembly code. The same thing with JIT, it's should become an "Oracle" to perform some oprimization that are easly can be performed on upper levels. So finally on the road with "put everithing behind the JIT" we will receive AI with huge Trained Model that easily understand what was in mind of a developer who wrote this particular IL instruction.

[dmitriyse]

In this repo there always will be tons of unresolved issues like this, until some push from reality. For example push from this benchmarks https://www.techempower.com/benchmarks/#section=data-r17&hw=ph&test=query
You can check what place takes in this benchmark ASP.Net 4 framework.

CLR 2.0 Level instructions sets is not always a thing to proud of.

Compare how many efforts takes "Spans" feature. It's also brokes some of IL related tools and futhermore near to all C# related tools.
Spans was pushed to the lanugage by ASP.Net Core team, because there were dramatic language bottlenecks for the Kestrel (it's my suggestion).

For example another next push is C# to LLVM backend with some new runtime like CoreRT. That will allow to execute C# code in 1.5 times faster. In this case CoreCLR+RyuJIT will requre to provide performance improvements to all .Net ecosystem.

[mikedn]

Ah you mean hoist the resolution of the virtual call outside the loop; then use the resolved call in the loop?

I suggested that years ago on Connect. That got "imported" to GitHub in dotnet/runtime#6558

Jit will never be smarter than IL producers

I'm not sure how you reached that conclusion. Are you writing your own IL producer? Because well known IL producers such as Roslyn certainly do not qualify as being smarter than the JIT, they're simple source code -> IL translators.

[AndyAyersMS]

This optimization is possible in the jit today and would not require any IL level changes.

Currently this aspect of virtual calls gets expanded after we run optimizations, but things could be revised so that this gets expanded earlier. With early expansion and a proper understanding of vtable invariance, vtable fetches would be hoistable just like any other computation (and would be subject to the same limitations -- so the jit would have to honor exception ordering constraints, and could only do this hosting if it already knew the object was not null).

And given the two-level vtable structure we use today, there would be nice wins in cases like the example above where the loop does little other work and the callee is trivial.

For interfaces things are a bit more complicated. But a conceptually similar mechanism could be built where the jit invokes a the runtime helper to resolve the interface call target; this resolution result would be invariant and could be cached in jitted code and reused in a loop.

So basically: instead of expressing this idea early on in IL, it can be entirely encapsulated within the jit and the jit's interaction with the runtime.

dotnet/runtime#6558 tracks this pretty well.

cc @dotnet/jit-contrib

[jkotas]

proper understanding of vtable invariance

The vtable slots have never been invariant and we are taking more dependencies on patching them in dotnet/coreclr#21292.

[AndyAyersMS]

Yes -- so with the current 3 load sequence for a virtual call (fetch method table, fetch method chunk, fetch target address) we would only consider hoisting the first two loads.

[dmitriyse]

It's very good to know that I was wrong and JIT is powerfull enough to hoist the resolution of the virtual call outside the loop.

But with the new opcodes I also keep in mind another use case:
128 Bit ValueTyped delegate.
First part is an object/null second part is direct pointer to the machine code.

From the current discussion I found:
1) It's never possible to have invariant pointer to a machine code of method
2) It's not safe to rely on JIT internal implementation of method call

So I need to create another issue (feature request):
New type of delegate with fastest possible invocation. (object reference + most fetched/patched pointer to machine code)

[benaadams]

So I need to create another issue (feature request): New type of delegate with fastest possible invocation.

"Proposal: Struct Lambdas" https://github.com/dotnet/csharplang/issues/1060 ?

[dmitriyse]

Thank you for pointing for this issue, but I read this too late and created another issue https://github.com/dotnet/coreclr/issues/21385

[BruceForstall]

It looks to me like the proposal here is already practically covered by the JIT optimization issue dotnet/runtime#6558 and other referenced issues, so I'm closing this.