Proposal: Generic Specialization

[benaadams]

From: dotnet/roslyn#15822
Related: "Adding a 'static if' construct to support generic specialization" dotnet/roslyn#8871

Currently generics create a duplicate code path for structs and share one for classes

This can be used to specialize the generic type for individual structs using typeof which are then removed at jit time to make branchless paths; System.Numeric.Vectors is probably the most extreme example of this.

However even this advantage for structs can lead to oddities (as well as very large functions); such as casting values through object to convert T to valuetype

public unsafe Vector(T value) : this()
{
    if (Vector.IsHardwareAccelerated)
    {
        if (typeof(T) == typeof(Byte))
        {
            fixed (Byte* basePtr = &this.register.byte_0)
            {
                for (int g = 0; g < Count; g++)
                {
                    // Cast via object
                    *(basePtr + g) = (Byte)(object)value;
                }
            }
        }
        else if (typeof(T) == typeof(SByte))
        {
            fixed (SByte* basePtr = &this.register.sbyte_0)
            {
                for (int g = 0; g < Count; g++)
                {
                    // Cast via object
                    *(basePtr + g) = (SByte)(object)value;
                }
            }
        }

Proposal

Allow specialist implementations of a Generic type to be pre-defined; including for class types

public struct GenericType<T> : IEquatable<GenericType<T>>, IFormattable {}
public struct GenericType<byte> : IEquatable<GenericType<byte>>, IFormattable {}
public struct GenericType<string> : IEquatable<GenericType<string>>, IFormattable {}

If a specific generic type is specified this will take precedence over the T version; otherwise will work as now.

Bonus Round

Allow templating "specialization" where the overload is automatically generated

public struct GenericType<TList> 
    : where TList : IList<int>
    : specialize List<int>, int[]

Where the specializations will automatically be generated for those class types to take advantage of inlining etc

Questions

• Can the specialist type be partial or inherited in some way so it can choose the methods it overrides?
• Specialisation of generic functions? e.g.

public static EqualityComparer<T> Default { get; }
public static EqualityComparer<string> Default { get; }
public static EqualityComparer<byte> Default { get; }

[CyrusNajmabadi]

Sorry, not quite getting the proposal. Can you explain what this generates:

public struct GenericType<TList> 
    : where TList : IList<int>
    : specialize List<int>, int[]

Basically, what would the C# compiler do with this?

Thanks!

[mgravell]

Is this a compiler feature? or compiler+runtime feature? i.e. what does:

var type = typeof(GenericType<T>).MakeGenericType(typeof(string));

result in? and is there a distinction in the type depending on whether the type was known at compile-time?

How do dependency chains work? if 6 levels sit between GenericType<T> and T, and T turns out to be string, 2 assembly references away: does it still work?

[benaadams]

what would the C# compiler do with this?

It would duplicate the struct creating

public struct GenericType<TList> : where TList : IList<int>
public struct GenericType<List<int>> 
public struct GenericType<int[]>

The TList calls in the methods of GenericType<TList> can't be inlined for class types as its shared generic code so will be from different types.

However, the List<int> and int[] calls can be inlined and use strongly typed enumerators for

public struct GenericType<List<int>> 
public struct GenericType<int[]>

As is non-shared code.

The current way around this is to create a struct wrapper; and then call with that, but its a bit ugly

new GenericType<ListIntWrapper>(new ListIntWrapper(list));
new GenericType<ArrayIntWrapper>(new ArrayIntWrapper(array));

struct ListIntWrapper : IList<int>
{
    List<int> _list;

    public ListIntWrapper(List<int> list) => _list = list;
    public int this[int index] { get => _list[index]; set => _list[index] = value; }
    public int Count => _list.Count;
    public bool IsReadOnly => ((IList<int>)_list).IsReadOnly;
    public void Add(int item) => _list.Add(item);
    public void Clear() => _list.Clear();
    public bool Contains(int item) => _list.Contains(item);
    public void CopyTo(int[] array, int arrayIndex) => _list.CopyTo(array, arrayIndex);
    public List<int>.Enumerator GetEnumerator() => _list.GetEnumerator();
    public int IndexOf(int item) => _list.IndexOf(item);
    public void Insert(int index, int item) => _list.Insert(index, item);
    public bool Remove(int item) => _list.Remove(item);
    public void RemoveAt(int index) => _list.RemoveAt(index);
    IEnumerator IEnumerable.GetEnumerator() => _list.GetEnumerator();
}

struct ArrayIntWrapper : IList<int>
{
    int[] _array;

    public ArrayIntWrapper(int[] array) => _array = array;
    public int this[int index] { get => _array[index]; set => _array[index] = value; }
    public int Count => _array.Length;
    public bool IsReadOnly => ((IList<int>)_array).IsReadOnly;
    public void Add(int item) => ((IList<int>)_array).Add(item);
    public void Clear() => Array.Clear(_array, 0, _array.Length);
    public bool Contains(int item) => _array.Contains(item);
    public void CopyTo(int[] array, int arrayIndex) => _array.CopyTo(array, arrayIndex);
    public int IndexOf(int item) => Array.IndexOf(_array, item);
    public IEnumerator GetEnumerator() => _array.GetEnumerator();
    public void Insert(int index, int item) => ((IList<int>)_array).Insert(index, item);
    public bool Remove(int item) => ((IList<int>)_array).Remove(item);
    public void RemoveAt(int index) => ((IList<int>)_array).RemoveAt(index);
    IEnumerator IEnumerable.GetEnumerator() => _array.GetEnumerator();
    IEnumerator<int> IEnumerable<int>.GetEnumerator() => ((IList<int>)_array).GetEnumerator();
}

[benaadams]

Is this a compiler feature? or compiler+runtime feature? i.e. what does: result in?

Likely you'd call the shared version; you've started paying cost with reflection, behaving same performance wise as before is probably valid? (Maybe the Jit would fix you up?)

[CyrusNajmabadi]

I'm not sure what this is:

public struct GenericType<TList> : where TList : IList<int>
public struct GenericType<List<int>> 
public struct GenericType<int[]>

That's not legal C# code. What does it mean to have a generic type who's type parameter is a type argument? Thanks!

[CyrusNajmabadi]

This feels very similar to Shapes (#164) to me. Especially when you talk about the wrappers. It seems like you'd define a shape describing the capabilities you needed. Then you'd provide types that wrapped another type with that shape (preferably happening implicitly), and then your calls would always be optimized fully since shapes are done with structs, so the runtime always gives you a type specific implementation for each instantiation of hte shape.

[benaadams]

That's not legal C# code. What does it mean to have a generic type who's type parameter is a type argument? Thanks!

That's why its the proposal: 😄

Proposal

Allow specialist implementations of a Generic type to be pre-defined; including for class types

public struct GenericType<T> : IEquatable<GenericType<T>>, IFormattable {}
public struct GenericType<byte> : IEquatable<GenericType<byte>>, IFormattable {}
public struct GenericType<string> : IEquatable<GenericType<string>>, IFormattable {}

If a specific generic type is specified this will take precedence over the T version; otherwise will work as now.

[Neme12]

@benaadams What if you have a Container<T> and inside that you have a field of type GenericType<T>? The compiler can't know that T will be a byte.

[benaadams]

A parallel would be extensions where you can override a generic argument by using a more concrete one

static class GenericTypeExtensions
{
    public static void DoThing<TList>(this GenericType<TList> list)  where TList : IList<int> {}
    public static void DoThing(this GenericType<List<int>> list) { }
    public static void DoThing(this GenericType<int[]> list) { }
}

However you can't do with with instance methods; which is what the proposal is about

[CyrusNajmabadi]

Yeah, shapes seems much better for this. With shapes you'd just do:

public shape SList<T> { /*list members*/ }
public extension ListExt<T> of IList<T> : SList<T>;

public struct GenericType<TList> : where TList : SList<int>
{
     // Your members
}

Now, you'd just do:

new GenericType<int[]>() and you'd get all the specialization you want. That's because it would translate into "new GenericType<ListExt<int[]>>()" and inside GenericType, default(ListExt<int[]>) would be used to dispatch all your calls. The would see all of these as struct and would be able to avoid any sort of virtualization for all your code.

[Neme12]

@benaadams But if you're working inside a generic type, the compiler can't know what overload to pick. This only works with templates unfortunately.

If you have a specialized Vector<byte> and then have a VectorList<T> and call a "specialized generic" method on Vector<T> it can't statically know to use the 'byte specialization' unless the compiler basically mimics templates and starts making these 'specializations' and duplicate classes all the way up.

[benaadams]

@CyrusNajmabadi as far as I can tell Shapes seems to fix every issue I raise... I want these magical beasts

[CyrusNajmabadi]

That would juts be:

public static int DoThing<TList>(TList list)  where TList : SList<int> {
    var sum = 0;
    for (var i = 0; i < list.Length; i++) {  sum  += list[i]; }
    return sum;
}

You can then just call this as DoThing(someIntArray). That will get translated to:

DoThing<int[], SyntheticCompilerGeneratedIntArray_SlistImpl>(someIntArray);

And DoThing will actually be compiled by the compiler into something like:

int DoThing<T, TImpl>(T list) where Tmpl : struct, SList<T> {
    var impl = default(TImpl);
    var sum = 0;
    for (var i = 0; i < impl .get_Length(list); i++) {  sum  += impl .get_Item(list, i); }
    return sum;
}

[CyrusNajmabadi]

Basically, you can call these shape/extensions methods and as long as you show how your type abides by the shape, you effectively always get the specialized version. Stuff like impl .get_Length(list) looks weird, but the runtime will effectively see through all of that. Because default(TImpl) is just an empty struct, it costs nothing. And because .get_length is just going to be a trivial method like:

int get_Length(int[] array) => array.Length;

everything should inline. Basically it's like a double dispatch system, except where everything is known at codegen time, so all the actual bouncing around can be totally elided.

[CyrusNajmabadi]

I want these magical beasts

#preach

[Neme12]

@CyrusNajmabadi what does SList get compiled to? I'm just wondering how you can call those methods on TImpl without being virtual?

[CyrusNajmabadi]

I'm just wondering how you can call those methods on TImpl without being virtual?

The runtime is smart. This is a "constrained call" on a type-parameter value with some constraints. It knows that when you do a constrained call on a struct that it doesn't have to do virtual dispatch as structs can't be overridden. i.e. ignore shapes for a second. Say i just have:

interface IList<T> { /* normal members */ }
struct StructList<T> : IList<T> { /* impl */ }

void Foo<T, TList>(TList list) where TList : struct, IList<T> {
    // I can call IList members on 'list' because of the contraint.
}

Foo<int, StructList<int>>(someStructListOfInts);

Here, because Foo is instantiated with value types, it gets a unique jit compilation. The jit sees the constrained calls to IList members in the body of Foo. But, because it knows the final result type and sees that it is a struct, it can avoid virtual dispatch entirely and just call the actual concrete, non-virtual method that implements the IList member.

--

In essence, this is what shapes compile down to. From the linked to proposal:

See how the extra Impl type parameter carries the knowledge of how to do + and Zero into the method. The benefit of doing this with a struct type parameter, rather than, say, extra delegate parameters, is that the runtime does a really good job of optimizing it: it will specialize the generic method code for each different struct it gets called with, so that the method body can inline and optimize the specific + and Zero implementations. Measurements on the linked type classes proposal show incredibly good performance, with near-zero cost to the abstraction.

The runtime already does this trick. And, if shapes were to come to pass, i bet they could even take "near-zero cost" down to zero, with the only overhead being the jit compilation step, but the final runtime code being exactly what you would want it to be.

[dsaf]

@CyrusNajmabadi could you please create an FAQ section describing what cannot be achieved by using shapes, source generators and extension-everything?

[benaadams]

@CyrusNajmabadi if I understand correctly don't think it will work; as it needs to be a concrete rather than generic struct.

So this will cause the optimization

struct ListIntWrapper : IList<int>
{
    List<int> _list;
}

but this won't

struct IListWrapper<TList> where TList : IList<int>
{
    TList _list;
}

As the generic code portion will still use shared code for the object path; I believe

[CyrusNajmabadi]

as it needs to be a concrete rather than generic struct.

In Shapes, it's always a concrete struct at the end of the day i believe. (but i could be wrong). Best to ask on the shape discussion and seek clarification.

[CyrusNajmabadi]

@benaadams It would be helpful to have a concrete example of what your'e trying to do. i.e. don't just write "i want public struct GenericType<TList>", but instead state what real world problem you're trying to solve (maybe the Vector one). Then we can explore how you might write it with Shapes.

[alrz]

I think type classes should cover this case (warning: the example is severely similar to Rust's)

 // TSelf is an implicit type parameter available to all traits
trait Eq</* TSelf, */ Rhs = TSelf> {
 static bool operator ==(TSelf self, Rhs other);
 static bool operator !=(TSelf self, Rhs other) => !(self == other);
}

// specialized implementations
implement Eq for C<byte> { // TSelf = C<byte>, Rhs = TSelf = C<byte>
  static bool operator ==(C<byte> self, C<byte> other) { ... }
}

implement Eq for C<string> { // TSelf = C<string>, Rhs = TSelf = C<string>
  static bool operator ==(C<string> self, C<string> other) { ... }
}

// fallback/generic implementation
implement<T> Eq for C<T> where T : Eq { // TSelf = C<T>, Rhs = TSelf = C<T>
  static bool operator ==(C<T> self, C<T> other) { ... }
}

After that, overload resolution determines the precise member to be invoked.

[Happypig375]

@dsaf Shapes/Extensions and Source Generators would not be appropriate for Higher Kinded Polymorphism (#339).

[voltcode]

I wanted to have generic specialization (full and partial!) ever since I came back to .NET from C++ around 8 years ago, but there was no repo to report that problem anywhere back then :)

Two suggestions for consideration:

Partial specialization

My first suggestion is to explicitly define whether partial specialization (in C++ sense) is supposed to be possible or not, because the examples don't show it. I believe that partial specialization is great for further improving development of high performance code on value types.

With partial specialization you can do things like:

MyMethod<T1, T2>(T1 o1, T2 o2) 
{
...
}

MyMethod<int, T2>(int o1, T2 o2) 
{
...
}

Generic type specialization scope inside typeof(T) comparison blocks

Another suggestion is related to the typeof(T) == typeof(value_type) comparison.
Within such scope the type of T is certain. Here's an example:

MethodWorkingOnInts(int something)
{ 
}
...
MyMethod<T1>(T1 o1) 
{
   if (typeof(T) == typeof(int))
   {
       MethodWorkingOnInts(o1); // ERROR, even though type of o1 is definitely an int here!      
   }
}

My suggestion is to make the compiler aware of such comparisons in that they create compile-time type materialization. JIT alread recognizes such constness, and removes the statement away when its true, but you still need to box and unbox to get it to compile.

Perhaps implementing such awareness is much easier in the compiler than rolling out full generics specialization and/or Shapes.

I agree it is less readable than specialization, but in contrast to specialization it's not requiring new syntax.

[Joe4evr]

My first suggestion is to explicitly define whether partial specialization (in C++ sense) is supposed to be possible or not

It isn't. C# generics are not at all like C++ templates.

Think of it like this: The IL for a generic type is not usable immediately, it's merely a blueprint. When constructing, the runtime creates a copy of that blueprint to make the actual type instance from. This copy then remains cached for re-use (only a single copy when all type arguments are reference types, and a separate copy for each permutation of value types used).

C++ compiles down to platform-specific code (most of the time), meaning their compilers (and probably even language spec) can make decisions based on knowledge from the entire program, which I think is what makes its specialization possible in the first place. (On the other hand, C++ has no way to constrain type parameters, last I heard.)

If anything, support for specialization à la C++ should first be surfaced in the CLR, since that's the only thing that even knows the whole program. After that, it can be discussed how it'll get supported in the language.

but you still need to box and unbox to get it to compile.

Having to write (int)(object)o1 certainly looks ugly as all get out, but the JIT could possibly be improved to remove the box/unbox routine. But don't expect any syntax improvements because...

Perhaps implementing such awareness is much easier in the compiler than rolling out full generics specialization and/or Shapes.

I doubt that, because there are still other .NET runtimes and the compiler has to emit IL that should work on any of those. So let's say Microsoft's CLR can elide the boxing, that still means every other runtime can't. If you then had the ability to write only (int)o1 in that particular context, that would hide the fact that it could still allocate depending on the runtime.

[ruilvo]

(On the other hand, C++ has no way to constrain type parameters, last I heard.)

Absolutely not true. Many techniques, of which SFINAE is the most common one are used very often to constrain types on templates. There's even std::enable_if. C++20 introduced "concepts" to make the whole thing nicer.

[voltcode]

It isn't. C# generics are not at all like C++ templates.

Of course they aren't at this point of time, but this this original issue is a proposal to extend their expressiveness. I'm merely suggesting additional points for consideration.

I know the C++ templates vs C# generics bullet points, however there are valid use cases for more powerful parametrized types, especially when performance is a concern.

If anything, support for specialization à la C++ should first be surfaced in the CLR, since that's the only thing that even knows the whole program. After that, it can be discussed how it'll get supported in the language.

My second proposal should not require knowledge of the entire program, it's similar to how constraints work in restricting the types for a block (a method or a class). Moreover, you can nest constraints and combine them in some ways. The typeof specialization is conceptually similar to adding a generic constraint on a block, albeit allowing for concrete types. It would not break existing code, but add a way to simplify it + get performance boost without relying on the JIT. Old, expensive, box + unbox would still be valid.

If you are aware of a related JIT proposal change for optimizing away the box + unbox, please add a link to it. If this is the only way to get it soon, I'm happy to live with ugly syntax if the performance is right.

[zpodlovics]

Related research project: Claudio Russo, Matt Windsor: Type Classes for the Masses

https://github.com/MattWindsor91/roslyn/blob/master/concepts/docs/csconcepts.md#performance
https://github.com/MattWindsor91/visualfsharp/blob/hackathon-vs/examples/fsconcepts.md#performance

[ruilvo]

I'd want this so much. This relates in an interesting way to this discussion:
dotnet/runtime#80665
How cool would it be to have Complex<float> and Complex<double>?

For example, if I'm writing DSP code and I want an FFT for floats and an FFT for doubles, I might want to do an API like MyFft<float> and MyFft<double> with different implementations for optimization.

[HaloFour]

there is no good way to make this API neatly an performant,

The runtime explicitly looks for that typeof(T) == typeof(float) pattern today and specializes the code in JIT/AOT, so it should be as performant.

[ruilvo]

That's nice and good for things like I mentioned above... For a complicated thing like an Fft, where you may want to write the whole implementation in separate classes, what can you do? I sketched this (non-working) piece of code, for you to see what I mean:

using System.Numerics;

namespace ClassLibrary1
{
    interface IFftImpl<T>
    {
        void Execute(Span<T> input, Span<T> output);
    }

    class FftImplFloat : IFftImpl<float>
    {
        public void Execute(Span<float> input, Span<float> output)
        {
            // do something specific to float
        }
    }

    class FftImplDouble : IFftImpl<double>
    {
        public void Execute(Span<double> input, Span<double> output)
        {
            // do something specific to double
        }
    }

    public class FftGeneric<T>
    {
        int _size;
        IFftImpl<T> _impl;

        public FftGeneric(int size)
        {
            if (typeof(T) == typeof(float))
                _impl = new FftImplFloat() as IFftImpl<T> ?? throw new Exception("This should never throw...");
            else if (typeof(T) == typeof(double))
                _impl = new FftImplDouble() as IFftImpl<T> ?? throw new Exception("This should never throw...");
            else
                throw new Exception("Unsupported type");
            _size = size;
        }

        public void Execute(Span<T> input, Span<T> output)
        {
            _impl.Execute(input, output); // Wonder if the compiler is smart enough to inline this?
        }
    }
}

Maybe there's a pattern to achieve this that I don't know about?

[CyrusNajmabadi]

This all seems like a runtime feature to me. Without support on their end, we'd have nothing to properly compile down to.

[ruilvo]

Maybe some shenanigans with the actual name of the types, like C++ name mangling? And just present concrete types for the IL for the specialized generics whenever they are found? Maybe it would be a problem with some fringe runtime type deduction, hum...

[msedi]

@HaloFour. We had a discussion about this a long time ago, but I cannot find it anymore.