Language feature request: type-specific implementation of generic methods

[Opiumtm]

Background

Implementation of generic methods sometimes require type-specific logic. For example, if generic argument T is struct it may significantly impact implementation details. For example, generic algorithms would be improved by passing large struct around by read-only reference instead of copy. But generic methods implementation don't know if actual type is struct (if no additional constraints specified) and reflection is often required to call type-specific constrained implementation.

Example:

public class A<T> {
    public void ComputeResults(T value)
    {
        // NO WAY to efficiently call "CommonImplementation" or "OptimizedForStructs" 
        // depending of T
        // Slow and inefficient reflection is required
    }

    private void OptimizedForStructs<T1>(T1 value) where T1 : struct
    {
        // logic, optimized for structs
    }

    private void CommonImplementation(T value)
    {
        // common logic for reference types
    }
}

Proposed solution

Type-aware switch and is.

public class A<T> {
    public void ComputeResults(T value)
    {
        // "switch" statement on type argument
        switch (T)
        {
            case struct T1:
                OptimizedForStructs<T1>(value);
                break;
            case string:
                OptimizedForStrings(value);
                break;
            default:
                CommonImplementation(value);
                break;
        }
        
        // improved "is" pattern matching operator

        if (value is struct v) 
        {
            OptimizedForStructs(v);
        } else if (value is string s) // already possible in C# 7
        {
            OptimizedForStrings(s);
        } else
        {
            CommonImplementation(value);
        }
    }

    private void OptimizedForStructs<T1>(T1 value) where T1 : struct
    {
        // logic, optimized for structs
    }

    private void OptimizedForStrings(string value)
    {
        // logic, optimized for strings
    }

    private void CommonImplementation(T value)
    {
        // common logic for reference types
    }
}

[casperOne]

Doesn't the pattern proposal (along with assignments) solve this?

[Joe4evr]

Doesn't the runtime/JIT already optimize the case when there's a check against the type of T by removing the dead branches for structs?

if (T is int i) // branch and other checks will be removed if T is a 'long'
{
    //....
}
else if (T is long l) // branch and other checks will be removed if T is an 'int'
{
    //....
}
else if (T is string s) // branches checking against value types are removed, checks against reference types and 'else' stay
{
    //....
}
else // all other branches get removed if T is any other value type
{
    //....
}

But generic methods implementation don't know if actual type is struct (if no additional constraints specified) and reflection is often required to call type-specific constrained implementation.

The methods don't, but the runtime does know. Your proposal seems based on a false assumption.

The only thing that the language doesn't currently do is checking if T is any struct at all (and assigning it as such). I'm not entirely sure if this is feasible, but I'll let the experts be the judge of that.

[qwertie]

Does it optimize this, though? I decided to speed-test the idea.

Short answer: yes. Long answer: while you can specialize for inputs, it seems impossible to "un-specialize" for outputs; the Add methods in the following example want to return T, but they can't.

public struct Specialized<T>
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static object Add1(T a, T b)
    {
        if (a is byte a8 && b is byte b8) {
            return (byte) a8 + b8;
        } else if (a is sbyte A8 && b is sbyte B8) {
            return (sbyte) A8 + B8;
        } else if (a is ushort a16 && b is ushort b16) {
            return (ushort) a16 + b16;
        } else if (a is short A16 && b is short B16) {
            return (short) A16 + B16;
        } else if (a is uint a32 && b is uint b32) {
            return (uint) a32 + b32;
        } else if (a is int A32 && b is int B32) {
            return (int) A32 + B32;
        } else if (a is float af && b is float bf) {
            return af + bf;
        } else if (a is double ad && b is double bd) {
            return ad + bd;
        }
        throw new NotSupportedException();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static double Add2(T a, T b)
    {
        if (a is byte a8 && b is byte b8) {
            return (byte) a8 + b8;
        } else if (a is sbyte A8 && b is sbyte B8) {
            return (sbyte) A8 + B8;
        } else if (a is ushort a16 && b is ushort b16) {
            return (ushort) a16 + b16;
        } else if (a is short A16 && b is short B16) {
            return (short) A16 + B16;
        } else if (a is uint a32 && b is uint b32) {
            return (uint) a32 + b32;
        } else if (a is int A32 && b is int B32) {
            return (int) A32 + B32;
        } else if (a is float af && b is float bf) {
            return af + bf;
        } else if (a is double ad && b is double bd) {
            return ad + bd;
        }
        throw new NotSupportedException();
    }
}

public struct Ungeneric
{
    public static int NormalAdd(int a, int b) => a + b;
    public static double DoubleAdd(int a, int b) => a + b;
    public static object BoxedAdd(int a, int b) => a + b;
}

public class GenericSpecializationSpeedTest
{
    const int Iterations = 100_000_000;

    [Test]
    public void WasteTimeFast()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += Ungeneric.NormalAdd(i, i + 1);
    }

    [Test]
    public void WasteTimeBoxed()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += (int)Ungeneric.BoxedAdd(i, i + 1);
    }

    [Test]
    public void WasteTimeDouble()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += (int)Ungeneric.DoubleAdd(i, i + 1);
    }

    [Test]
    public void WasteTimeGeneric1()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += (int)Specialized<int>.Add1(i, i + 1);
    }

    [Test]
    public void WasteTimeGeneric2()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += (int)Specialized<int>.Add2(i, i + 1);
    }
}

Typical results:

• WasteTimeBoxed: 532ms
• WasteTimeDouble: 66ms
• WasteTimeFast: 40ms
• WasteTimeGeneric1: 527ms
• WasteTimeGeneric2: 66ms

[qwertie]

Ahh, I figured it out! You can "unspecialize" in a just slightly more complicated way than you specialize:

public struct Specialized<T> where T: struct
{
    ....
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static T Add3(T a, T b)
    {
        if (a is byte a8 && b is byte b8) {
            return ((byte)a8 + b8) is T r ? r : default;
        } else if (a is sbyte A8 && b is sbyte B8) {
            return ((sbyte)A8 + B8) is T r ? r : default;
        } else if (a is ushort a16 && b is ushort b16) {
            return ((ushort)a16 + b16) is T r ? r : default;
        } else if (a is short A16 && b is short B16) {
            return ((short)A16 + B16) is T r ? r : default;
        } else if (a is uint a32 && b is uint b32) {
            return ((uint)a32 + b32) is T r ? r : default;
        } else if (a is int A32 && b is int B32) {
            return ((int)A32 + B32) is T r ? r : default;
        } else if (a is float af && b is float bf) {
            return (af + bf) is T r ? r : default;
        } else if (a is double ad && b is double bd) {
            return (ad + bd) is T r ? r : default;
        }
        throw new NotSupportedException();
    }
}
...
public class GenericSpecializationSpeedTest
{
    ...
    [Test]
    public void WasteTimeGeneric3()
    {
        long sum = 0;
        for (int i = 0; i < Iterations; i++)
            sum += (int)Specialized<int>.Add3(i, i + 1);
    }
}

(of course, if you're on .NET 7+, in many cases you can use generic numerics instead.)

Typical results in Release build (in Debug builds I'm seeing a 1500+ ms, for all 3 generic versions, which is a 4-5x speed penalty over and above the usual penalty for debug builds):

• WasteTimeGeneric1: 554 ms
• WasteTimeGeneric2: 60 ms
• WasteTimeGeneric3: 50 ms
• WasteTimeFast: 50 ms

[MichalPetryka]

Worth noting that this is not guaranteed and the only case it happens is with value types on CoreCLR; reference types or running on Mono don't give you such specialization.

[siegfriedpammer]

Then the Mono runtime needs to be optimized or even better: dumped entirely. I doubt that MS will spend time to implement a C# language feature to circumvent short-comings of an alternative and inferior CLI implementation.

Also, if you are really concerned about performance, you should not touch Mono anyway, because the Mono C# compiler produces very bad IL code compared to Roslyn or even the legacy C# compiler. My experience is based on ILSpy decompiler development, where we have to test and support multiple versions and variants of the compilers. No offense, but mcs code gen makes my eyes bleed sometimes. Sorry.

[Opiumtm]

@casperOne @Joe4evr

Doesn't the pattern proposal (along with assignments) solve this?

Doesn't the runtime/JIT already optimize the case when there's a check against the type of T by removing the dead branches for structs?

Whole idea of this proposal is to introduce additional generic type constraints in method code for some region of method code. If actual substituted type of T does not satisfy additional type constraints over T, this region of code is ignored for this exact substituted type of T.

if (T is int i) // branch and other checks will be removed if T is a 'long'
{
    //....
}

This wouldn't help as you cannot branch code for any struct nor add additional type constraints for generic type argument T without going to exact types.
There can be literally thousands of struct types and you can't use if for each possible struct type in the world.

[Joe4evr]

Yes, so the problem is checking if T is any kind of struct. I just fiddled a bit and found that any struct instance is apparently assignable to System.ValueType, but it boxes the value and therefor can't be used as T when T : struct.

So the concrete proposal is: Allow checking if a type parameter is any kind of struct and have it be assignable as such without boxing.

[HaloFour]

I'm curious about this "generic-yet-optimized-for-structs" method implementation. I'd think that such a beast would be relatively rare and not worth a language feature specifically to support. The normal case, as mentioned, would be to switch or branch directly off of the type of the value which the JIT is optimized to handle.

[Opiumtm]

@Joe4evr

So the concrete proposal is: Allow checking if a type parameter is any kind of struct and have it be assignable as such without boxing.

I propose more broad approach. Ability to add any type constraints to existing and efficiently call appropriate "more constrained" generic methods. Part of the example:

        // "switch" statement on type argument
        switch (T)
        {
            case struct T1:
                OptimizedForStructs<T1>(value);
                break;
            // ...
        }        

this part of code introduce "new" generic type argument T1 (based on "parent" generic type T, but "more constrained" - in this case constrained with struct type constraint, but it can be any) inside method code block.

Developer apparently can write additional private methods with more constrained (so, more specific) type arguments, but developer can't invoke those methods without slow and inefficient reflection.
As for now, to invoke such "more specific" version developer should extract generic method info and invoke specific method via reflection. It's obviously slow, error prone runtime approach.
But "more specific" type constraints are well-known at compile time if developer use "switch on type argument" statement.

[Opiumtm]

@HaloFour
It depends on the nature of code you develop. Major headache with current implementation of generics in C# is fundamental inability to invoke generic methods with more constrained generic argument from a method with less constrained type argument. It's not needed if you're using only classes and can cast object to interface or base class. But for structs you should box value to cast structure to interface and you can't specialize on constraints such "new()". So you can't implement own optimizations for compile-time known cases. Generics typically provide good speed improvements and reduce runtime errors. But inability to specialize generic type argument inside method code (and so, requirement to use reflection at runtime) reduce ability to write high performance code. It especially important for .NET Native as if static compiler don't know about generic type constraints it emit fallback "common generic" code.

And I must note that such kind of optimizations is common for fundamental libraries such as serialization frameworks, generic collection libs, RPC network libs, object-relation-mappers and so on. Performance in such kind of libs is absolutely important and developer of such lib don't know exact types to be used with such fundamental lib. It maybe not so wide "developer base" for such libs, but it would be apparently wide "user base", so performance improvements in fundamental lib should be important for its user base.

[Joe4evr]

this part of code introduce "new" generic type argument T1 (based on "parent" generic type T, but "more constrained" - in this case constrained with struct type constraint, but it can be any)

Ah, I think I understand what you're getting at now. Outside of the T1 : struct issue, there's another major friction point for having methods with tighter constraints. For example, the following compiles just fine:

public class C<T>
{
    void Do(T value)
    {
    	if (value is IAdditional a)
        {
            M(a);
        }
    }
    
    void M<T1>(T1 value) where T1 : IAdditional
    {
    }
}

public interface IAdditional
{
}

But it would only work as long as there's a single constraint. If M<T1>() had T1 : T, IAdditional , the method declaration itself is fine, but the type system only sees a as an IAdditional which has no implicit conversion to T.

At this point I'm inclined to say we've hit a "Gödel limit", so to speak. Which is to say, with the double constraint on M<T1>(), we know that M(a) should work (i.e. it's a true statement) but it cannot be proven by the axioms of the type system at this juncture. Even if you have an IBase, make IAdditional : IBase and constrain T : IBase the type system still can't prove that M(a) should be valid.

[Opiumtm]

@Joe4evr

Yes, you understand it. It's what I'm talking about.

[Joe4evr]

Then you realize that what you're asking for is roughly equivalent to solving the Halting Problem?

Don't take it personal, I really hate to have rained on your parade, but having learned about Gödel earlier this week, I couldn't help but point out the similarity.

[Opiumtm]

@Joe4evr

Then you realize that what you're asking for is roughly equivalent to solving the Halting Problem?

Of course, I'm not asking for it. Let developer explicitly declare what he knows for sure.
There is no need to calculate all possible variants of additional constraints. Developer explicitly list specific cases he care of. Runtime knows what specific type is substituted for generic argument. Runtime can check additional constraints without the burden of many "security" and "type safety" checks of the reflection (anyway JIT prepares specific versions of constrained generic classes and methods). Static .NET Native compiler can prepare all branch cases explicitly declared by developer. In worse case it's not worse than fallback reflection approach. There is no extraordinary things I ask for. It's just extension of the existing things. Today language and runtime can constrain whole generic types and methods. Why not extend it to blocks of code inside methods? And well, such "additional generic arguments constraints" are known at compile time or at least at JIT time. So JIT could calculate type safety checks once. There are fast runtime approaches to overcome reflection requirements for such situations when you need additional type argument constraints or invocation of generic method from the non-generic code. Those approaches are well known. But they're apparently low-level such as IL emit at runtime. Why emit IL at runtime when all possible specific cases are well-known and explicitly declared at compile time? And runtime IL generation approach obviously wouldn't work for static .NET Native, but declared in code (and so known at compile time) additional type specification would emit those IL (same as emitted by fast runtime solutions) statically and so available to static .NET Native optimizations.

Let me repeat. It is not so different from runtime IL emit approach to invoke generic methods from non-generic or less constrained code. IL emit approach is extremely faster than reflection, so CLR already can handle this "generic invoke issue" without additional effort. Just let make it static instead of runtime. If developer can declare use cases statically (in "switch on type argument" statement), so there is no need to emit IL opcodes at runtime. It should be done by C# compiler.

[Opiumtm]

One another major performance consideration about ability to specialize generic code.

Let's see

void Invoke(ISomeInterface arg)  // invoke by interface
{
   // ...
}

void Invoke<T>(T arg) where T : ISomeInterface // invoke generic with constraint
{
   // ...
}

Second invoke (generic parameter with interface constraint) is much faster than first invoke (interface-typed parameter), especially when interface is implemented by struct.

JIT and .NET Native static compiler are completely ignore interface type and use direct class/structure method invokes instead of virtual invokes on interface methods because it's well known that generic type have specific and exact methods, so invokes are optimized. This optimization especially important for structs as invokes on interface method require boxing, but invokes on interface-constrained struct generic type does not require boxing at all! At RavenDB repository there is special "Fast dictionary" class which exploit this constrained generics behavior.

Article about constrained generics performance

Citation:

The actual dictionary impl is very close to the standard one, but that isn’t what make it fast. Note the generic argument? If we pass a struct implementing IEqualityComparer generic argument, then in most cases, the compiler and the JIT are going to generate code that is able to eliminate all virtual calls. And if there is a trivial equality comparison, that means that you can eliminate all calls and inline the whole thing inside that generic dictionary implementation.
In other words, we eliminate a minimum of two virtual calls per key lookup, and in some cases, we can eliminate even the method calls themselves, and that turn out to be quite important when the number of key lookups is in the billions.

You can figure how important language improvements of generics for high-performance apps and libs.

[alrz]

Shapes could allow some kind of "specialization" , e.g.

shape Operation { void Do(); }
implement<T> Operation for T where T : struct { public void Do() { ... } }
implement<T> Operation for T where T : class { public void Do() { ... } }

You could simulate that via extension methods but it causes ambiguity error (addressed by #98)

static class X { public static void Do<T>(this T self) where T : class { ... } }
static class Y { public static void Do<T>(this T self) where T : struct { ... } }

[mburbea]

@alrz, that approach doesn't work inside a generic method. (Which method would a uncontrained generic open type call?)

The current technique that the BCL uses is a bit hokey for specialization.

internal class Doer<T>
 {
     public virtual void DoIt(T member) => Console.WriteLine($"Normal route for {member}");
 
     public static Doer<T> Instance { get; } = Specialize();

     public static Doer<T> Specialize() => typeof(T).IsValueType ? Activator.CreateInstance(typeof(StructDoer<>).MakeGenericType(typeof(T))) as Doer<T> : new Doer<T>();
 }
 internal class StructDoer<T> : Doer<T> where T : struct
 {
     public override void DoIt(T member) => Console.WriteLine($"Struct route for {member}");
 }
/*...*/
void MyGenericMethod<T>() =>  Doer<int>.Instance.DoIt(5);

The CoreClr team uses it for things like specializing EqualityComparer<T>.

Updated it for a version that actually compiles. I didn't add the next level which is for nullable structs, so they fall into the non-specialized route.