API runtime support for efficient type switch

[gafter]

I'd like the C# compiler to be able to compile a series of type tests, which typically occur in a pattern-matching switch statement, to something more efficient than a sequence of IL type tests, especially when the number of types being tested for is large (dotnet/roslyn#31515). I originally asked for an IL instruction to do this (https://github.com/dotnet/coreclr/issues/23241), but it was suggested that the library approach could do just as well. Some kind of custom hashtable is probably ideal.

I developed this prototype as a starting point: https://github.com/gafter/TypeSwitch/blob/master/TypeSwitch/TypeSwitchDispatch.cs

It appears to be faster than a series of type tests when there are more than about 10 types being tested in the switch. I think an API something like this should go in System.Runtime.CompilerServices and hopefully live in System.Runtime/corlib.

[2019-04-29: To be clear, I am willing to contribute the code that appears at https://github.com/gafter/TypeSwitch/blob/master/TypeSwitch/TypeSwitchDispatch.cs to the dotnet foundation, who can release it under whatever license they/we see fit. The code was originally developed by me. -@gafter]

[terrajobst]

That sounds reasonable to me. Some questions:

1. What happens if the compiler can't find the type? Presumably it won't fail but simply emit the less efficient code it emits today, correct?
2. Where should this type live? Presumably we'd want this to live at the bottom so that we can use this ourselves. So System.Runtime.dll seems fine to me.

@stephentoub / @jkotas, any objections to this approach?

[jkotas]

I see type-based pattern matching as higher layer C# feature, around the same layer as Linq or dynamic. I do not see a strong need for using it in the lower layer of the stack.

We should extrapolate future pattern matching needs. If the pattern matching is going to need more specialized helpers like this one in future to execute efficiently, it would make sense to have these helpers in C# language runtime support library, like Microsoft.CSharp.

[gafter]

@jkotas There is nothing language-specific about the proposed API. It is simply a multi-way instanceof test. F# would likely use it as well. It was originally proposed as an IL instruction, but now proposed as an API because it isn't clear that an IL instruction could be more efficient.

[gafter]

@terrajobst

1. If the compiler can't find the type, it would fall back to the old less efficient code.
2. Proposed namespace System.Runtime.CompilerServices. Would like it in corlib or System.Runtime.

[jkotas]

Ok, sounds reasonable to me.

[gafter]

Unfortunately, this API is not correct, because the behavior of the isinst instruction is not the same as getting the type of the object and using Type.IsAssignableFrom. The reason is the existence of APIs such as ICastable and COM types. This API would likely have to be implemented in the runtime to be correct. That leads me to prefer a new IL instruction.

[ericstj]

Per @gafter's comment #29002 (comment) closing this. Please reopen if I misunderstood.

[gafter]

I think you misunderstood. All my comment is saying is that it cannot be implemented outside the runtime because of a couple of special cases that only the runtime knows about.

[gafter]

This issue track the same request as #12260. I believe the current consensus is that it can be done as an API in which the set of types to match are passed as generic type arguments (e.g. the elements of a tuple type). See https://github.com/gafter/TypeSwitch/blob/master/TypeSwitch/TypeSwitchDispatch.cs for a prototype that does not address the issue mentioned in #29002 (comment)

[jkotas]

Duplicate of #12260. Let's have just one issue tracking this feature request.