Lightweight interfaces solely for type constraining purposes of generic parameters allowing inlining of member functions

[ghost]

Dear all,
Currently an interface in C# encapsulates 2 purposes, 2 concepts. The first is to describe functionality and properties. The 2nd is that it can be used as constraint for C# generics. What I am suggesting is new generic interfaces that serve only the role to be used as constraints for generics.

Interface based implementation of linear algebra expressions such as:

Vector x = 2*x1-0.5*x2+y*(x1+x2)*10.0

aiming to avoid temporary arrays such as temp1=x1+x2, temp2=temp1*10.0, temp3=y*temp2 and the performance and memory overhead associated with them, introduces another penalty associated to indirect local access of Expression member functions. This penalty translates to almost 8-10x slower code when the size of array is large compared to a hand-coded loop, see #6893.

C++ complains if a template parameter does not implement a requested member function. However, it does not use constraints for templates, and thus it can inline functions efficiently resulting in much faster code and syntax extremely easy to follow. C# uses Interfaces as generic constraints but then when a class or struct or record inherit from an interface, calling its member functions is not as efficient because it is done from something like a C++ vtable, which prevents inlining and the performance associated with inlining.

To this end, it seems beneficial to allow Lightweight interfaces maybe not even called interfaces but TypeDeclarations or something similar currying just the signature of the methods and to be used solely as generic constraints for the only purpose of enforcing the compiler to ask the exact interface member functions signature for each Generic parameter. In other words just for compiling reasons and not for runtime reasons.

This way, we keep the best of both worlds, and the implementation will not involve inheritance of the interface member functions as it is done now resulting in the performance penalty I described above, but these lightweight interfaces will help the compiler enforce constraints at the classes to be used as Generic parameters only. Example

public generic interface IVector
{
   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   public double Value(int i);
   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   public double this[int i] {get; set;}
}

public class Vector : IVector
{
   public double[] data;
   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   public double Value(int i) {return data[i]; };
   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   public double this[int i] 
   {
      get { return data[i]; } 
      set { data[i] = value; } 
   }
}

These member functions cannot be inlined if the standard interface is used.
As a result, the member functions of Expressions like Add<Vector, Vector> or Mul<Vector, Vector> etc, will be inlined without trouble allowing for much faster execution.

What do you think? Can you think of applications that would benefit from something like that other than Fortran like syntax of array/matrix operations described #6893?

[HaloFour]

I don't see why this proposed construct would be any different from an interface. I don't think the optimizations you suggest would be realized because you'd still require a form of indirection for the runtime to call through in order to call the actual method. The C# compiler doesn't get involved in optimizations such as inlining. And generics aren't expanded by the compiler like they are in C++.

Have you tried making Vector a struct? The runtime, as a general rule, does not specialize generic methods for reference types. But it does for value types.

[ghost]

Believe me I have. Nothing changed. Same runtimes.

I don't think the optimizations you suggest would be realized because you'd still require a form of indirection for the runtime to call through in order to call the actual method.

From your statement above it seems that you have no experience with how C++ templates work and how they promote inlining. It is simple. As I explained the generic interface is lightweight. It means that it is not used in the classical interface sense. It is used as a compilation constraint and not as a runtime constraint. It just informs the compiler what he should expect from generic arguments. In this sense no inheritance takes place at all as it is the case with standard interfaces. If you have experience with C++ you will see that the code sample I have described below to user @ufcpp using C++ templates achieves the exact same performance with the hand coded version of the loop I described to @ufcpp. This is around 10 times faster. Just by allowing inline to take place. Nothing more, and nothing else. Another way to achieve the same speedup would be if C# was providing native support for array [] or [,] operations (+,-,*,/). For this discussion see 6893.

The C# compiler doesn't get involved in optimizations such as inlining.

Then what does [MethodImpl(MethodImplOptions.AggressiveInlining)] stand for?

[siegfriedpammer]

The C# compiler doesn't get involved in optimizations such as inlining.

Then what does [MethodImpl(MethodImplOptions.AggressiveInlining)] stand for?

The C# compiler simply emits a flag in the method metadata that serves as a hint to tell the runtime it should try to inline the method. However there are no guarantees that it actually will inline the method if it is too large or contains try catch blocks.

[HaloFour]

More importantly, the C# compiler has no special knowledge of what that custom attribute does. It is emitted into the metadata of the assembly as any other custom attribute. It's the runtime that understands and interprets that attribute and uses it as a hint when it comes to optimization.

[siegfriedpammer]

Sorry for the nitpicking, but the method implementation attributes are NOT custom attributes, they are stored as flags in a column in the method table (and in IL there is a keyword for them). There are some (advanced) "built-in" attributes that are represented in C# using custom attribute syntax. Other than that you are right of course.

[HaloFour]

Ah, I did not realize that MethodImplAttribute was a pseudo-attribute.

[En3Tho]

I'm not even sure where to answer because you've opened so many discussions all covering different topics but using this totally unconcrete example (which resembles C# but it's not one) as

Vector x = 2*x1-0.5*x2+y*(x1+x2)*10.0

The main problem I see is that you fail to provide a clean C# example. Maybe open your repo, provide some code there first in C# then in "ideal" syntax. I mean first try to solve the problem using means C# already has so people can actually see where the problem lies. It seems to me that people do not really get what you really want to achieve.

You've already did some tests/benchmarks so it would be cool to add some proper Benchmark.Net tests there (in that repo) too.

At least this will give people (and hopefully you too) more problem context and clear numbers to try work around.

[ufcpp]

Virtual methods in struct and sealed class can be inlined by JIT optimization, but is that not enough?

[ghost]

The runtime is capable of specializing generic methods and avoiding the virtual call through the interface. The easiest way to enable this would be to define the generic type argument as a struct and not a class, and the runtime tends to not specialize the latter due to the amount of potential bloat that will cause at runtime. Such specialization is still a runtime optimization detail and not a language one.

Theoretically. In practice it does not. As I said check #80970 to see that even without generics the function call with IArray arguments is 4 times slower or more. Try the code given there yourself to have a first hand experience that all these claims about interface method inlining are just claims and nothing more.

[HaloFour]

Theoretically. In practice it does not.

As I said, the runtime tends not to specialize with reference types, which you are using. Try declaring the type as a struct, not as a class or record.

[ghost]

As I explained this is already done and nothing changes at all. Same runtimes. The problem is not there. Why don't you try it yourself to be convinced?

[CyrusNajmabadi]

If generic specialization isn't happening with structs, then that's a runtime issue. Please supply them with a full repro case they can look at at dotnet/runtime. This is the repro for the c# language. We can't directly help with that issue.

[ghost]

I already have as you suggested here 80970

Thank you for your inputs. If you also have any suggestions for the 80970# you are welcome. Sample code is provided and the problems of .NET7.0 vs .NET6.0 related to QuickJitForLoops env variable are discussed but not fully resolved. You will see there the performance impact of calling the function from the interface pointer IArray. My hope is that once the experts are aware of this problem something will be done to speed things up.

[svick]

If you want to rely on generic constraints, you have to use them all the way, you can't just use them locally, and then box the result as the interface.

That could look for example something like this (full benchmark code):

public interface IArray<T> where T : IArray<T>
{
    double this[int i] { get; }
}

static class Extensions
{
    public static Plus<TL, TR> Plus<TL, TR>(this TL left, TR right) where TL : IArray<TL> where TR : IArray<TR>
        => new Plus<TL, TR>(left, right);
}

public struct Vector : IArray<Vector>
{       
    double[] data;
    public double this[int i] => data[i];
    public Vector(int n)
    { data = new double[n]; }
}

public struct Plus<Left, Right> : IArray<Plus<Left, Right>>
    where Left  : IArray<Left>
    where Right : IArray<Right>
{
    public readonly Left  L;
    public readonly Right R;

    public Plus(Left left, Right right)
    {
        L  = left;
        R = right;
    }
    public  double this[int i] =>  L[i] + R[i];
}

public class Benchmark
{
    [Benchmark]
    public double Modified()
    {
        Vector a = new Vector(n);
        Vector b = new Vector(n);
        Vector c = new Vector(n);
        return ModifiedImpl(a, b, c);
    }

    public double ModifiedImpl<T>(T a, T b, T c) where T : IArray<T>
    {
        var x = a.Plus(b).Plus(c).Plus(c);
        double sum = 0.0;
        for (int i = 0; i < n; i++)            
            sum += x[i];
        return sum;
    }
}

Using this code, the performance was close to the hand-coded version:

Method	Mean	Error	StdDev	Median	Gen0	Gen1	Gen2	Allocated
Original	4.193 s	0.0080 s	0.0165 s	4.1958 s	1000.0000	1000.0000	1000.0000	2.24 GB
Modified	1.166 s	0.0108 s	0.0101 s	1.1674 s	1000.0000	1000.0000	1000.0000	2.24 GB
HandCoded	1.025 s	0.0657 s	0.1719 s	0.9492 s	2000.0000	2000.0000	2000.0000	2.98 GB

Note that I had to use a.Plus(b).Plus(c).Plus(c) instead of the nicer syntax a + b + c + c, because C# does not have generic operators (see #813). But I don't see how this proposal would solve that, especially since it's not clear to me how the proposed generic interface would achieve the desired performance gains.

[CyrusNajmabadi]

But the header could be generated by the compiler and later used wherever the compiler needs it.

I don't know what you mean by 'header' here. Such a thing does not exist currently for c#/.net. It would have to be entirely designed. Hence why I said "we would need a portable source representation."

This is non trivial and itself would be a ton of work. And it's just a single piece (of many) that need designs and solutions. For example, even if we had this, we would still need a satisfactory solution to the versioning problem. Specifically, in .net it likely would not be acceptable for library A to change and not have that change be picked up unless all downstream libraries also recompiled. But that's how templates work today (unlike generics). So that would likely also need huge amounts of design and impl work.

My entire point though is that none of this is "simple". It's likely multiple teams of people working for several years just on these problems/issues. And it looks like alternate solutions (like shapes/roles), are much cheaper and subsume the use cases you want in this discussion.

[ghost]

I don't know what you mean by 'header' here

I mean the header file the .h or the .hpp file of the associated .cpp file of C++. For example a C++ developer could write only the .cpplus file (similarly to a C# developer writes the .cs file) and the compiler even before compilation he should preprocess the .cpplus file to generate the .cpp file and the .hpp file so that the developer does not need to write both since the .hpp can be generated from the .cpplus (assuming classes have to be declared in the .cpplus in this case) or something like that. But this is another topic.

My entire point though is that none of this is "simple". It's likely multiple teams of people working for several years just on these problems/issues. And it looks like alternate solutions (like shapes/roles), are much cheaper and subsume the use cases you want in this discussion.

OK I see your point. In that case, since I do not even know if shapes/roles are currently supported, would you please provide an example showing how to use the shapes or the roles or both for writing vector math for expressions like the ones discussed above? Thanks in advance!

[CyrusNajmabadi]

I mean the header file the .h or the .hpp file of the associated .cpp file of C++.

I know what a header is in c++. I'm saying I have no idea what you mean when your use that term in the context here. We have no such thing in .net. So we'd have to build it. And we'd have to do so in a way that works for .net. For example having a template be written in a way that it could be consumed by vb or f#, or any other language. I haven't seen even a sketch of how that would work.

Indeed, maybe you should start there. Show what someone could write, what it would compile down to, and how it could be used by any .net language. I'm talking specifically about your idea about templates for .net.

[ghost]

Sorry Cyrus it was not clear what you meant.

I know what a header is in c++. I'm saying I have no idea what you mean when your use that term in the context here. We have no such thing in .net.

OK. I see. Clearly all I can offer is ideas and you will be the judge. I am wondering, what would be the problem if current C# interfaces did were not directly linked with inheritance mechanisms. Why that would be a problem for you to do what you are doing? And again excuse my ignorance but I am not an expert in language internal implementations. Is there anything at the moment that requires this direct link of a C# interface to some inheritance concepts in order for it to function as a generic constraint?

Indeed, maybe you should start there. Show what someone could write, what it would compile down to, and how it could be used by any .net language. I'm talking specifically about your idea about templates for .net.

I was under the impression that you suggested role/shape for implementing mathematical expressions such as:

Vector x = alpha*y - beta*z + gamma*(x-y)

I'm talking specifically about your idea about templates for .net.

From your answer above it seems you recommended role/shape for implementing templates for net. Is this the case?

[CyrusNajmabadi]

Clearly all I can offer is ideas and you will be the judge

I'm asking you to actually flesh out the idea. Write me, saying something (paraphrased) like "do this like C++ does it" isn't helpful. The systems are hugely different. If you want something like C++, you'll need to actually do legwork and dive deeper into what that would actually look like and how it's would actually work. You're proposing it as there solution, so it's incumbent on you to show that it would be.

Wrt roles/extensions. It would be similar to the wrapper struct approach, just without the need to write the wrapper struct. Instead, you could just add those operators to your arrays without wrapping them.

That said, as I mentioned before, I think this would be a bad idea. You should be wrapping as not all arrays are things you want all these operators for. Instead, you should have strongly typed struct wrappers to make sure you're working with your data correctly and your avoiding mistakes.

[En3Tho]

@Dhmosthenis
Seriously what?. You're are speaking to language users as yourself and we are trying to help you overcome your problem with what we have now. I even checked it in F# and provided you with gist demonstrating behaviour you're seeking. It's not about what we want now, it's about what we have. And we clearly do not have generic operators (now) or macros (possibly never) in C#.

There is no problem using F# - it is a .Net language perfectly interoperable with C# it does even have units of measure to simplify those computations you're talking about. (And it has many more cool features).
The problem of having operators on array(-like) types itself is solvable but obviously not through special casing "+" on array in complier. As you can see in F# example, generic operators can solve this. And note that generic operators are much broader feature that allows much more than just array computations.

There is also a feature that might solve this: shapes. Or type classes if you wish. It's aim is to allow to extend arbitrary types with interfaces or members. So this might even allow extending arrays with operators directly too.

I don't see a problem designing a generator which will generate whatever code you want from a given expression either.

[SomeAttributeForYouGenerator]
private void SomeComputationTemplate()
{
    ... write down your program using marker types
}

public partial void SomeComputation
{
    ... generate optimized code using arrays or matrices or whatever
}

And even if we assume language team is very interested in your idea then they obviously will design a very versatile math syntax/features that will be applicable to different problems within math scope. This might take years to research and design properly. I don't know if you are just seeking approval or something but people here are seriously trying to help you solve your problem right here and now. Goodnight.

[CyrusNajmabadi]

So basically, this is Ab, where A is a diagonal matrix.

The point is that you shouldn't use an array for that as the type you interact with. Use that as the storage. But wrap it with an struct that then exposes the correct semantics (including operators) that this type supports.

Now you have the syntactic niceties, and you have type safety that you're only doing things correctly

[333fred]

@Dhmosthenis I lightly edited your post to fix the italics formatting issues from having * not inside ` blocks.

Is this really possible?

Yup.

Take a look at this BiCGStab

I'm not sure what I'm supposed to learn from this link.

Do you have any idea (example) how these could be used for my purposes?

You have given syntactic examples already, such as the example shown in the original post. These are techniques I'm suggesting that will enable that syntax.

[ghost]

@333fred,

I'm not sure what I'm supposed to learn from this link.

Thanks for the editing. Just to look how many vector and matrix times vector operations are needed to implement this and similar to this methods. There are others much more complicated than this one. Do you see now how much easier it would be to implement this using syntax as close to mathematics as possible? Imagine to implement this with for loops. Nightmare.

[CyrusNajmabadi]

Do you see now how much easier it would be to implement this using syntax as close to mathematics as possible?

Operator overloading is already present in the language. What's not clear is why the existing facilities cannot be used to support these cases.

[ghost]

Do you see now how much easier it would be to implement this using syntax as close to mathematics as possible?

Operator overloading is already present in the language. What's not clear is why the existing facilities cannot be used to support these cases.

You can Cyrus, of course you can, but I do not remember if I explained it in this post, when you use simple operator overloading as ADA does for its Real_Arrays library, then x := x1+x2+x3+x4 creates a temp1 = x3+x4 and then temp2=x2+temp1 and then temp3 = x1+temp3. For large arrays you waste GB for these temporaries apart from the slow down.

[CyrusNajmabadi]

@Dhmosthenis I want to avoid the impression that you're getting piled on here. First, thank you for bringing these areas of interest to be discussed here, and for suggesting ideas on how you think things could be better in the language for your needs.

That said, please recognize that this is a repo that does extensive design and discussion. It's a huge process to go from idea to acceptance to implementation. That's normal.

The bigger the idea, the more extensive this will be. Do not take the comments you are getting to mean that your ideas are not welcome. Rather, it's the exact opposite. People are considering your ideas, but rightfully and appropriately bringing up very important feedback that is all part of yours process.

Just keep that in mind as you engage here. People can even want what you want. But it's still going to be a huge discussion and process to get there.

[CyrusNajmabadi]

Perhaps, to agree with all the members, and design it for every possible case taking several possible ideas into account yeah,

Yes. None of this is trivial. It would take a significant amount of design and impl work. Furthermore, I'm not at all convinced this is a good idea, or if we'd go this route at all to solve this problem.

Remember that as part of the design we have to figure out how this affects the future of the language. It impacts everything so far and all the things we want to do in the future. Even basic questions (like what Fred brought up) could be months to years to resolve.

[CyrusNajmabadi]

I had to give the same answer many times

I didn't see the answers. Indeed, what I saw was a claim that this stuff was trivial, without literally anything backing it up beyond that c++ has a templates feature. That doesn't answer any question about how we would bring that beast to .net. Nor does it address it actual experiences working with the c++ team here (and on the c++ compiler itself) that tells us just how hugely complex this.

[ghost]

@CyrusNajmabadi,
guys, you are the designers, you know better what needs to be done and how long it would require. I am not an expert in Language implementations, all I can provide is ideas for better and more consistent/readable syntax.

[CyrusNajmabadi]

In/out/ref are not part of the type. Pointers are. That says, I would highly highly highly recommend not muddying the conversation here with that idea. Just open a new discussion.

[ghost]

I do not agree, but it is removed.