dotnet
[Proposal]: Practical existential types for interfaces
Practical existential types for interfaces
- [x] Proposed
- [ ] Prototype: Not Started
- [ ] Implementation: Not Started
- [ ] Specification: Not Started
Terminology note: What's called "existential types" in this proposal is more correctly called "associated types" in other languages. The previous proposal, referenced below, did not have the same restrictions and thus implemented something much closer to a pure existential type without type erasure. This proposal is more restrictive and doesn't support using interfaces with associated types in all locations. You can think of every mention of "existential type" in this proposal as meaning "associated type."
Intro
Previously I proposed adding some form of existential types to C#. In that proposal, I describe existential types at a high level and describe how some features could be added to C#. However, I didn't propose any particular implementation strategy and left many questions open, including the mechanism for enforcing type safety.
In this proposal I will describe a full implementation and type safety mechanism, as well as a metadata representation.
To start, the syntactic presentation. I propose that existential types be represented as abstract type members of interfaces. For example,
interface Iface
{
// Existential type
type Ext;
public Ext P { get; }
}
The existential type is substituted when the interface is implemented, e.g.
class C : Iface
{
type Iface.Ext = int;
public int P => 0;
}
This syntax is similar to other languages with existential types and provides a clear separation from existing type parameters on types.
This syntax also emphasizes the differences described in the earlier proposal: unlike regular type parameters, which are provided by the creator of a type, existential types are provided by the implementer of the interface and are invisible at type creation.
Note: Some alternate syntaxes include
interface IFace<protected Ext>(this was the syntax I used in my first proposalinterface IFace<abstract Ext>interface IFace<implicit Ext>interface IFace|<Ext>
This does raise the question left open in the previous proposal: how to define type equality. Since each interface implementation may have a unique subsitution for the existential type, type equality depends on the exact type of the implementation. Notably, the interface itself is not an implementation, so the following would not type check:
void M(Iface left, Iface right)
{
var x = left.P;
x = right.P; // error, left.P and right.P may not be the same type
}
Worse, the type of x is difficult to express in the language, as-is. It is in some sense a type parameter, but there isn't a named type parameter in scope to use to refer to it. Inside the interface we call it Iface.Ext, but this is not actually a type, it is a type parameter. The actual type is whatever was substituted by the implementation. In the case of our example C above, the type is int.
However, we can improve the power of the feature using a different feature: existing C# generics. If we avoid using the type parameter as a type, and instead use it as a constraint, things get simpler:
void M<T>(T left, T right)
where T : Iface
{
var x = left.P; // `var` could be type `T.Ext`
x = right.P; // type checks
}
With this usage, we can be confident that the implementations will produce "compatible" types. This leads to the following proposal: interfaces with type members should only be usable as generic constraints. With this restriction, we can treat type members as relatively standard C# types, usable in the places where type parameters would be permitted. That this is type safe may not be obvious, but the proposed reduction to existing .NET metadata will verify that the resulting code is type safe.
Motivating example
The examples above demonstrate simple usages, but don't give an example of practical advantages. One opportunity is improved optimizations. Consider LINQ. As Jared Parsons described in a blog post, two of the biggest weaknesses of IEnumerable<T> are the repeated interface dispatches, and the abstraction of the enumerator type. As he describes, we could improve the pattern using generics:
public interface IFastEnum<TElement, TEnumerator>
{
TEnumerator Start { get; }
bool TryGetNext(ref TEnumerator enumerator, out TElement value);
}
One big problem with this pattern is it makes the enumerator into either an additional type parameter which needs to be manually propagated, or public surface area. This is a job much better left to the compiler. This is how it could be written with existential types:
public interface IFastEnum<TElement>
{
type TEnumerator;
TEnumerator Start { get; }
bool TryGetNext(ref TEnumerator enumerator, out TElement value);
}
The enumerator type is now appropriately elided for everyone except the implementor. A user might write
void M<TEnum>(TEnum e) where TEnum : IFastEnum<string>
{
foreach (var elem in e)
{
Console.WriteLine(elem);
}
}
This is more verbose than not using generics, but that is a more general concern about verbosity of generics.
And on the implementor side, it would look like this:
class List<T> : IFastEnum<TElement>
{
type IFastEnum.TEnumerator = int;
int Start => 0;
public bool TryGetNext(ref int enumerator, out TElement value)
{
if (enumerator >= Count) {
value = default(TElement);
return false;
}
value = _array[enumerator++];
return true;
}
}
This is much the same code that Jared wrote, and should provide the same performance benefits.
Compilation
In the previous proposal, I described a lowering strategy based on logic theorems around existential and universal type equivalence. This technique is powerful and flexible, but much more complicated and difficult to implement. The above design has substantial limitations on how existential types can be used, therefore the implementation can be much simpler. If these limitations prove too onerous in the future, some restrictions may be loosened with a more complex compilation strategy.
The proposed compilation strategy is broadly quite simple: turn existential types into hidden generic parameters. This may seem extreme, but note that the language rule for type members requires the interface which contains them to only be used as constraints. This means that compilation may add generic parameters, but it will never make a method generic which wasn't before, and the type parameters will not spread past the introduction of the constraint.
Here's a simple example of the code before and after.
Before:
interface Iface
{
type Ext : IDisposable;
Ext P { get; }
}
class A : Iface
{
type Ext = MemoryStream;
MemoryStream P => new MemoryStream();
}
void Dispose<T>(T t)
where T : Iface
{
t.P.Dispose();
}
Dispose(new A());
After:
interface Iface<Ext>
where Ext : IDisposable
{
Ext P { get; }
}
class A : Iface<MemoryStream>
{
MemoryStream P => new MemoryStream();
}
void Dispose<T, Ext>(T t)
where T : Iface<Ext>
{
t.P.Dispose();
}
Dispose<A, MemoryStream>(new A());
The important transformations are:
- Type members become additonal type parameters on the interface.
- Constraints on type members become constrains on the interface.
- Type member assignments in the implementation become type substitutions in the interface implementation.
- In all places where type parameters are declared with constraints to interfaces with type members, all type members must be added to the parameter list.
- At all callsites with synthesized type parameters, the correct type arguments must be inferred.
Most of the transformations are simple, but the synthesizing and inferring of type parameters may be worth some elaboration.
First, we need to establish what is necessary for inference. To do so, we need to determine which synthesized type parameters "belong" to which type parameter. This should be doable using synthesized attributes or modreqs to point to the "owning" parameter's index.
Once we know the owning parameters and the synthesized parameters, we can temporarily remove the synthesized parameters and perform type inference as currently specified in C#, or use the manual substitutions. Once the substitution is identified, we can identify the substitutions for the synthesized parameters. First, identify the needed interface by walking the constraint list in order. Next, determine the substitutions in the interface implementation. As currently proposed, the syntax only allows for a single implementation of a given interface for a given type. By searching types from most to least derived for the first implementation of the target interface, we can identify the substitutions on the argument. By matching the substitutions of the argument with the synthesized type parameters, synthesized type arguments can be generated.
The process above can be repeated for all type definitions and substitutions.
- [ ] Open question
Consider also banning re-implementation of the same interface across inheritance. It's not a type safety violation (and therefore shouldn't need a runtime check), but it could lead to confusing behavior on which implementation is chosen, especially since it is always fully inferred.
Conclusion
Advantages
- Relatively simple to implement and explain
- Provides full performance benefits
- Compact metadata representation
Drawbacks
- More complexity in generics in C#
- Generics are different in metadata vs. source
- Other languages have to implement encoding/decoding separately
Design Meetings
https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-02-16.md#practical-existential-types-for-interfaces
I can see the utility but I really don't like how this causes the source declarations and the metadata to differ so much in what I think would be non-obvious ways. IIRC this was a serious sticking point in the earlier discussions on shapes, that the witness type had to be a generic type parameter, and that the team overall would have preferred that the runtime offer a solution that did not require something like that.
Could "optional type parameters" solve this? A bit borrowed from C++ templates, not sure how this would be represented in metadata though.
interface Iface<Ext = MemoryStream> where Ext : IDisposable
{
Ext P { get; }
}
class A : Iface // implicitly: Iface<MemoryStream>
{
MemoryStream P => new MemoryStream();
}
void Dispose<T>(T t)
where T : Iface
{
t.P.Dispose();
}
Dispose(new A());
Or for the fast enumerable case:
public interface IFastEnum<TElement, TEnumerator = int>
{
TEnumerator Start { get; }
bool TryGetNext(ref TEnumerator enumerator, out TElement value);
}
class List<TElement> : IFastEnum<TElement> // implicitly: IFastEnum<TElement, int>
{
int Start => 0;
public bool TryGetNext(ref int enumerator, out TElement value)
{
if (index >= Count) {
value = default(T);
return false;
}
value = _array[index++];
return true;
}
}
// implicit: any IFastEnum<string, int>
void M<TEnum>(TEnum e) where TEnum : IFastEnum<string>
{
foreach (var elem in e)
{
Console.WriteLine(elem);
}
}
// explicit? it does allow overriding the value, while "type Foo" would not
// would only be called when the implemetation is specialized and Fancy(TM)
// question about overload resolution though.
// and how TEnumerator could be hoisted up to be a type parameter of M.
void M<TEnum>(TEnum e) where TEnum : IFastEnum<string, FancyEnumerator<string>>
{
foreach (var elem in e)
{
Console.WriteLine(elem);
}
}
@BhaaLseN This seems wrong to me Iface<Ext = MemoryStream> where Ext : IDisposable because existential types needs to be declared first so if anything it should be something like this Iface<Ext = MemoryStream> where Ext : type, IDisposable otherwise it's just a regular generic type parameter and to be honest it looks weird to me.
I think that "optional type parameters" is a separated feature that doesn't really solve the problem here but enhances generics that the proposed solution take advantage of and might benefit from the enhancement as well should it ever added to the language.
I'm confused by the FastEnum example. First of all, the index should be enumerator and TElement should be T. But those typos aside, how is that better than just creating a new:
interface IFastEnumerator<T>
{
bool TryMoveNext(out T item);
}
interface IFastEnumerable<T>
{
IFastEnumerator<T> GetFastEnumerator();
}
class List<T> : IFastEnumerable<T>
{
class FastEnumerator : IFastEnumerator<T>
{
public FastEnumerator(List<T> list) => this._list = list;
int _index;
List<T> _list;
// or
T[] _array; int _size; // to get rid of the indirection
public bool TryMoveNext(out T item)
{
// ...
}
}
public IFastEnumerator<T> GetFastEnumerator() => new FastEnumerator(this);
}
foreach(var x in list) { ... }
C# is expanded to look for GetFastEnumerator and use it accordingly. The only downside of this approach is one initial allocation of a class, which has the list reference (8 bytes) and the counter (4 bytes) = 12 bytes. Are we sure it's worth it to introduce a whole new concept of "sort of generics" to save allocating 12 bytes once per loop? And doesn't the performance cost of extra generic arguments (in terms of runtime) negate the benefit of saving that allocation?
Also, with the example in the OP, it has to repetitively put the ref index on the stack - on top of invoking an instance method using v-table. With my example, the instance invocation is still there, but the ref index push isn't. Maybe I'm wrong but it seems my example is faster.
What about abstract classes? And hope it eventually will be a runtime feature... Compiler "tricks" like that always remind me of java's type erasure...
At all callsites with synthesized type parameters, the correct type arguments must be inferred.
I wonder if there's space here to do somethign akin to how VB works with extension methods and type parameters. Where tehre can be the 'original def' with some number, and the 'reduced' version with less. Except that here it woudl be somewhat the reverse. I'm just speaking at the Language level how we might represent this, while the emitted level could def look different.
Improved version of my code sample:
interface IFastEnumerator<T>
{
bool TryMoveNext(out T item);
}
interface IFastEnumerable<T>
{
Type GetFastEnumeratorType(); // return type which has a ctor accepting one parameter, the collection; and has TryMoveNext method
}
class List<T> : IFastEnumerable<T>
{
struct FastEnumerator : IFastEnumerator<T>
{
public FastEnumerator(List<T> list) => this._list = list;
int _index;
List<T> _list;
// or
T[] _array; int _size; // to get rid of the indirection
public bool TryMoveNext(out T item)
{
// ...
}
}
public Type GetFastEnumeratorType() => typeof(FastEnumerator);
}
foreach(var x in list) { ... }
// becomes
var enumerator = new List<T>.FastEnumerator(list); // look for ctor which takes the list as a parameter
// the enumerator now lives on the stack
while(enumerator.TryGetNext(out readonly x)) // this call can be inlined, virtually removing any overhead
{
}
And the best part, all this is possible today, with minor changes to the C# compiler (recognize new types/method names/etc.)
Improved version of my code sample:
interface IFastEnumerator<T> { bool TryMoveNext(out T item); } interface IFastEnumerable<T> { Type GetFastEnumeratorType(); // return type which has a ctor accepting one parameter, the collection; and has TryMoveNext method } class List<T> : IFastEnumerable<T> { struct FastEnumerator : IFastEnumerator<T> { public FastEnumerator(List<T> list) => this._list = list; int _index; List<T> _list; // or T[] _array; int _size; // to get rid of the indirection public bool TryMoveNext(out T item) { // ... } } public Type GetFastEnumeratorType() => typeof(FastEnumerator); } foreach(var x in list) { ... } // becomes var enumerator = new List<T>.FastEnumerator(list); // look for ctor which takes the list as a parameter // the enumerator now lives on the stack while(enumerator.TryGetNext(out readonly x)) // this call can be inlined, virtually removing any overhead { }And the best part, all this is possible today, with minor changes to the C# compiler (recognize new types/method names/etc.)
That Enumerator type is not something that the compiler can determine at compile time, meaning it would have to be reflection. Associated types is how you achieve your interface proposal with actual compile time knowledge.
How about:
interface IFastEnumerator<T>
{
bool TryMoveNext(out T item);
}
interface IFastEnumerable<T>
{
IFastEnumerator<T> GetFastEnumerator(); // this is for regular usage
}
class List<T> : IFastEnumerable<T>
{
public struct FastEnumerator : IFastEnumerator<T> // this can be public - who cares
{
public FastEnumerator(List<T> list) => this._list = list;
int _index;
List<T> _list;
// or
T[] _array; int _size; // to get rid of the indirection
public bool TryMoveNext(out T item)
{
// ...
}
}
public IFastEnumerator<T> GetFastEnumerator() => new FastEnumerator(this); // this is for regular usage
public FastEnumerator GetFastEnumeratorDirect() => new FastEnumerator(this); // this is for highest performance
}
foreach(var x in list) { ... }
// becomes
var enumerator = list.GetFastEnumeratorDirect(); // C# looks for a method named GetFastEnumeratorDirect
// the enumerator now lives on the stack
while(enumerator.TryGetNext(out readonly x)) // this call can be inlined, virtually removing any overhead
{
}
How about:
interface IFastEnumerator<T> { bool TryMoveNext(out T item); } interface IFastEnumerable<T> { IFastEnumerator<T> GetFastEnumerator(); // this is for regular usage } class List<T> : IFastEnumerable<T> { public struct FastEnumerator : IFastEnumerator<T> // this can be public - who cares { public FastEnumerator(List<T> list) => this._list = list; int _index; List<T> _list; // or T[] _array; int _size; // to get rid of the indirection public bool TryMoveNext(out T item) { // ... } } public IFastEnumerator<T> GetFastEnumerator() => new FastEnumerator(this); // this is for regular usage public FastEnumerator GetFastEnumeratorDirect() => new FastEnumerator(this); // this is for highest performance } foreach(var x in list) { ... } // becomes var enumerator = list.GetFastEnumeratorDirect(); // C# looks for a method named GetFastEnumeratorDirect // the enumerator now lives on the stack while(enumerator.TryGetNext(out readonly x)) // this call can be inlined, virtually removing any overhead { }
That's pretty much what we have today, with the same performance issues in fully generic code.
That's pretty much what we have today, with the same performance issues in fully generic code.
Oh yea, I didn't even realize it's there. Given that's already there, what are the performance issues? How can that be improved any further? (Other than getting rid of the MoveNext/Current and replacing it with TryGetNext) What's the drive for "existential types"?
the problem is when you are workign with IFastEnumerable. The compiler doesn't know about GetFastEnumeratorDirect to do this quickly. With existential types, it could.
the problem is when you are workign with IFastEnumerable. The compiler doesn't know about GetFastEnumeratorDirect to do this quickly. With existential types, it could.
I'm completely confused now. The compiler already looks for GetEnumerator which returns the public struct enumerator, not the interface (per @333fred and List<T> definition).
I'm completely confused now. The compiler already looks for GetEnumerator which returns the public struct enumerator
It can do that when workign with the concrete type. But if you're workign with the interface it has no idea. That's what existential types aims to solve. You can both be working with the interface, but pass along enough information that the compielr/jit can statically know all the information necessary to generate more optimal code (namely code that doesn't need to call through virtual-dispatch or allocate on the heap).
Using Andy's example, you could pass around an IFastEnum, but get the same perf as if you passed around a concrete impl of that interface.
I'm completely confused now. The compiler already looks for GetEnumerator which returns the public struct enumerator
It can do that when workign with the concrete type. But if you're workign with the interface it has no idea. That's what existential types aims to solve. You can both be working with the interface, but pass along enough information that the compielr/jit can statically know all the information necessary to generate more optimal code (namely code that doesn't need to call through virtual-dispatch or allocate on the heap).
Oh I see what you mean. Still, is it really that important to get rid of one allocation per entire loop? My first example - basically adding TryGetNext and leaving everything else as is - works just as fast per iteration. Or am I missing something else?
Still, is it really that important to get rid of one allocation per entire loop?
Yes.
My first example - basically adding TryGetNext and leaving everything else as is - works just as fast per iteration.
Again, this is what we have today :)
However, you only get the benefits if you know the concrete types. But that's highly problematic. In many domains you do not. And now there are tons of allocations happening as you have to work over abstract interfaces with no additional information present to help the runtime/jit/etc. avoid them.
@CyrusNajmabadi @333fred OK I just ran performance testing, enumerating 1,000,000 items, 100 times to get an average, and the results are: (.NET 5)
- OP example with
ref int state: 00:00:00.0057360 - My example with interface and
TryGetNextinstead ofMoveNext/Current: 00:00:00.0055274 - Concrete type - struct returned, and
TryGetNext: 00:00:00.0047260
.NET FW 4.8:
- OP example with
ref int state: 00:00:00.0139251 - My example with interface and
TryGetNextinstead ofMoveNext/Current: 00:00:00.0128952 - Concrete type - struct returned, and
TryGetNext: 00:00:00.0117484
In .NET 5, the first 2 approaches (ref int and interface) sometimes switch places; to be completely fair, I think they perform equally. In .NET FW 4.8, the 2nd (interface) approach is always faster.
Code: https://pastebin.com/UA1N1KCG
@TahirAhmadov please show a BenchmarkDotnet result, including memory allocations. FUrthermore, this only shows TryGetNext appraoch which is not extendible to all the cases where existential types may be used.
This proposal is also about the ergonomics of generic types, not performance. Those scenarios where performance benefits can be achieved but currently necessitate painful generic signatures are just a bonus.
My BDN results:
| Method | Mean | Error | StdDev | Ratio | Allocated |
|----------------- |-----------:|--------:|--------:|------:|----------:|
| IFastEnumerable | 1,647.0 ns | 4.52 ns | 4.23 ns | 1.00 | - |
| | | | | | |
| IFastEnumerable2 | 2,269.2 ns | 6.86 ns | 6.41 ns | 1.00 | 32 B |
| | | | | | |
| FastEnumerator2 | 347.1 ns | 0.71 ns | 0.66 ns | 1.00 | - |
Gist: https://gist.github.com/CyrusNajmabadi/9a1acd7f5c2f2b63c194870533e6af62
So anywhere from 5-7x faster (not even counting things like allocations).
@TahirAhmadov please show a BenchmarkDotnet result, including memory allocations. FUrthermore, this only shows TryGetNext appraoch which is not extendible to all the cases where existential types may be used.
The code is self explanatory, I don't have the time now to make a new project with that BenchmarkDotnet. I do agree that the allocation will add some memory consumption, but again, we're talking about something like 20 bytes; this only becomes a problem if the loop is executed many times - which is usually a code smell for a whole bunch of reasons, not only allocating the enumerator object. In short, I think there may be a miniscule performance benefit to squeeze out of this improvement; but the cost of creating a whole new syntax constructs plus necessary runtime changes just doesn't seem to be worth it right now. Again - I'm going off of what's in the OP. They show the motivational example and that's what I can work with. I can't sit here and invent other ways to use a feature which I'm not the one proposing.
The code is self explanatory
The code is not acceptable as it does hand written measurements without any of the efforts or smarts that BDN puts into reliable, repeatable, and statistically significant measurements.
but again, we're talking about something like 20 bytes; this only becomes a problem if the loop is executed many times
No it's not. That's the common case. Components are producing enumerables and other parts of hte system are consuming it.
I think there may be a miniscule performance benefit to squeeze out of this improvement;
You are incorrect. Even in the basic examples you showed it's 5-7x, and no allocs.
My BDN results:
| Method | Mean | Error | StdDev | Ratio | |----------------- |-----------:|--------:|--------:|------:|- | IFastEnumerable | 1,647.0 ns | 4.52 ns | 4.23 ns | 1.00 | | | | | | | | IFastEnumerable2 | 2,269.2 ns | 6.86 ns | 6.41 ns | 1.00 | | | | | | | | FastEnumerator2 | 347.1 ns | 0.71 ns | 0.66 ns | 1.00 |Gist: https://gist.github.com/CyrusNajmabadi/9a1acd7f5c2f2b63c194870533e6af62
So anywhere from 5-7x faster (not even counting things like allocations).
The FastEnumerator2 is the concrete type struct approach - I just included it for comparison sake. However your results are interesting. The existential type approach does seem to be about 27% faster. I'll look into it further later.
The existential type approach does seem to be about 27% faster. I'll look into it further later.
No. The existential type approach would allow for the speed of FastEnumerator2 as there will be no virtual dispatch. The jit will literally know that 'start' is an int, and that there is a not-virt call to:
public bool TryGetNext(ref int enumerator, out TElement value)
{
if (index >= Count) {
value = default(T);
return false;
}
value = _array[index++];
return true;
}
which will likely get entire inlined and optimized.
The existential type approach does seem to be about 27% faster. I'll look into it further later.
No. The existential type approach would allow for the speed of FastEnumerator2 as there will be no virtual dispatch.
How is that? You said yourself the purpose is to allow passing an interface. How are you going to avoid a virtual dispatch with an interface?
The jit will literally know that 'start' is an int, and that there is a not-virt call to:
public bool TryGetNext(ref int enumerator, out TElement value) { if (index >= Count) { value = default(T); return false; } value = _array[index++]; return true; }which will likely get entire inlined and optimized.
Isn't the same true for the FastEnumerator2 interface method? It can also be inlined and optimized.
How is that? You said yourself the purpose is to allow passing an interface. How are you going to avoid a virtual dispatch with an interface?
That's literally what existential types allow. :)
This is the point of hte proposal. Please see the translation provided in the OP and how it allows generics to make this work.
Isn't the same true for the FastEnumerator2 interface method? It can also be inlined and optimized.
No :) Which is why you see the performance in the BDN of the interface dispatch approach being a problem. THe only existing approach we have that is fast on the current system is to return the FastEnumerator2 struct, which requires both teh production and consumption code to know about this concrete type.
Again, that's the point here. There's no way to accomplish that today ergonomically with interfaces. THere are unergonomic ways (with extra type parameters). Existential types is trying to get the best of both worlds. The perf and runtime wins that we get with extra type parameters today, but with the convenience and ease of a more ergonomic solution that doesn't require passing around all that information in all signatures.