Feature Proposal: Practical Non-breaking Constant Generics

# Practical Non-breaking Constant Generics

## Background and Use Cases

"Const Generics" enables the use cases where developers need to pass a const value through a type parameter.

Typical use cases are templating for things like shuffle (its basically a guaranteed constant) as well as for buffers, specialization optimizations that can be used in strings, numerics, tensors, matrices and etc.

Today we have inline arrays, which enables the developer to declare their own fixed buffer. But unfortunately different inline array types with the same shape and element type are not interchangeable, making it awkward to be used across the managed ABI.

With const generics, we can have a type `struct ValueArray` to define a type of array of `T` with `N` elements. This can also be useful in variadic parameters. For example, a `params ValueArray` can represent a variadic parameter that receives only 5 int arguments. Besides, we can also leverage the `ValueArray` type to implement `params {ReadOnly}Span`. This supersedes the existing `System.Runtime.CompilerServices.InlineArray##`, which provides a unified way to expose fixed-sized buffer types.

We also have many specializations based on length in `SearchValues`, and let the JIT to optimize unnecessary branch away so that we get specialized lookup code for a specified length of sequence. This works but it can eat up the JIT inline budgets and can have negative impacts on user code. What's worse, this can bloat the BCL because now we need to duplicate types like `SingleStringSearchValuesPackedThreeChars`, `TwoStringSearchValuesPackedThreeChars` etc. for the exact same functionality.

With const generics, it can be simplified to `SearchValues` with `ValueArray` under the hood, allowing a unified abstraction without duplicating code or bloating the BCL.

Similar approaches can also be used in vectors, tensors, matrices, etc. to allow code specialization for hot-path optimizations without duplicating code elsewhere.

It has been a while since I proposed const generics in #89730, which requires massive changes in the runtime type system and unfortunately being hard to take any further action due to the huge impact to the ecosystem.

I have been thinking is there any way without any change or only with minor change to the runtime to accomplish the same functionality, so that it will become much easier to action.

Finally, I managed to build a practical non-breaking const generic system with the existing type system, which requires almost no change to the runtime.

## Design

In this proposal, I'm proposing a practical non-breaking approach to const generics built on top of abstract static interfaces.

### Constant Value Types

We first need constant value types to represent constant values. The primitive building block for constant value types is hexadecimal digits:

```cs
namespace System.Runtime.CompilerServices;

interface IHexDigit
{
abstract static byte Value { get; }
}
```

Then we implement the interface for 0x0 through 0xF:

```cs
namespace System.Runtime.CompilerServices;

struct Hex0 : IHexDigit
{
public static byte Value => 0;
}

struct Hex1 : IHexDigit
{
public static byte Value => 1;
}

...

struct HexF : IHexDigit
{
public static byte Value => 15;
}
```

The hexadecimal digit types will become the fundamental of building constant value types, but before implementing concrete constant value types, we need an interface to do the abstraction work so that it can be passed around to the location where it is requested:

```cs
interface IConstantValue
{
abstract static T Value { get; }
}
```

Then we can implement concrete constant value types.

For example, an `Int16` constant value type:

```cs
namespace System.Runtime.CompilerServices;

struct Int16Constant : IConstantValue
where H3 : IHexDigit
where H2 : IHexDigit
where H1 : IHexDigit
where H0 : IHexDigit
{
public static Int16 Value
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get => Unsafe.BitCast((H3.Value << 12) | (H2.Value << 8) | (H1.Value << 4) | H0.Value);
}
}
```

Same thing applies to all other primitive types, like `bool`, `byte`, `char`, `int`, `long`, `float`, `double` etc. All of those types will need to be implemented in the BCL, maybe under `System.Runtime.CompilerServices`.

If we would like, we can also implement `Value` as an intrinsic that expands it into constant value directly in the importer to minimize the overhead.

### Const Type Parameters

A const type parameter is a type parameter that is constrained by `IConstantValue`, so that:

```cs
// pseudo-code
class Foo { }
```

can be represented as

```cs
class Foo where T : IConstantValue { }
```

To instantiate the `Foo`, we pass the concrete constant value type to the type parameter. For example, `Foo<42>`, which can then be represented as `Foo>`. We can ask Roslyn to lower `42` in a type argument to `Int32Constant` so that we only need to write `Foo<42>` for a better UX.

To use a const type parameter, we write `T.Value`. The C# compiler is free to compile `T` directly to `T.Value` under the hood, allowing developers to write `T` without explicitly accessing `.Value`. This avoids inconsistencies between passing a const type parameter to another const type parameter and passing its value to a normal parameter.

### Reflection

We don't need any change to reflection, and it already supports const generics. But to improve the user experience, I recommend implementing some useful APIs that can be used to retrieve the value of a given constant value type.

```cs
namespace System;

public abstract class Type
{
public virtual bool IsConstantValue { get; }
public virtual object ConstantValue { get; }

public static Type MakeConstantValueType(object value);
}
```

This can make sure we can instantiate a type/method that contains const type parameters without massive `MakeGenericType`, and also get the const value from a constructed type argument easily.

### Value Array

`ValueArray` is a unified type that provides the utility of `InlineArray` in a generic way:

```cs
namespace System.Runtime.CompilerServices;

struct ValueArray where Length : IConstantValue
{
private T _elem;
}
```

The runtime reads the `Length` type parameter to compute the array length and duplicate the field the required number of times.

## Some Useful APIs

Other many APIs can make use of const generics to provide valuable features and abilities for users:

1. `Matrix`: fixed-sized matrix to supersede `Matrix3x3`, `Matrix4x4` and etc.
2. `Vector`: fixed-sized vector to supersede `Vector2`, `Vector3` and etc.
3. `Tensor`: tensor types with a fixed rank
4. `Span`: ND-span that can support multiple dimension arrays
5. ... and more

## Further Thoughts

There're some areas that I haven't thought about but can be expanded in the future. For example:

- Value constraints: constraining a constant value type parameter to fulfill specific constraints. For example, `Span` should require `Dim >= 1`, and `ValueArray` should require `Length >= 0`. This situation is unchanged from #89730; the same approach applies.
- Arithmetic operations: allowing arithmetic operations on constant value type parameters, so that `A + 1`, `A + B` can be used to produce a new constant value type. The situation doesn't improve nor regress from #89730, the same approach can be taken without issue. Well, this is quite complicated, but I think it would be better to postpone the support as this can be covered by associated types if we need it in the future.
- Constant strings: constant strings can be represented by linked-list-like types. For example, `"hello"` can be expressed by `StringNode<'h', StringNode<'e', StringNode<'l', StringNode<'l', StringNode<'o', StringNull>>>>>`, where `'h'` is `Char /* h = 0x68 */` and the like, and its value can be cached in a `static readonly` for code access at the runtime without runtime parsing. This is an improvement from #89730 because we don't have the metadata-level encoding limitation and complexness here.

## Benchmarks

I built two apps following this approach to validate performance.

### TypedSql

TypedSql is a small experimental SQL-like query engine. Each query turns into a closed generic type built from Where / Select / Stop nodes and runs entirely through static methods, and constant values in the SQL are all lowered to constant value types to allow constant folding. See https://github.com/hez2010/TypedSql.

I then benchmarked it to compare a query against equivalent LINQ and handwritten loops over the same in-memory data. For example, filtering out rows in the People table and returning the matching `Id` values, produced numbers like these:

| Method | Mean | Error | StdDev | Gen0 | Code Size | Allocated |
|--------- |----------:|----------:|----------:|-------:|----------:|----------:|
| TypedSql | 10.953 ns | 0.0250 ns | 0.0195 ns | 0.0051 | 111 B | 80 B |
| Linq | 27.030 ns | 0.1277 ns | 0.1067 ns | 0.0148 | 3,943 B | 232 B |
| Foreach | 9.429 ns | 0.0417 ns | 0.0326 ns | 0.0046 | 407 B | 72 B |

As a result, TypedSql and the handwritten `foreach` loop end up with very similar throughput and allocation, while the LINQ query is noticeably slower and allocates more. TypedSql even has a smaller code size due to reduced code cloning. From the generated code, I observed that the specialized constant value was used directly in the core comparison loop, eliminating all query overhead.

### Brainfly

A Brainf**k JIT and AOT compiler built on top of this approach that turns constant values into types. See https://github.com/hez2010/Brainfly.

I then benchmarked it with various interpreter and compiler implementations:

| Name | Time (ms) | Rank | Ratio | Binary size | Description |
| --- | --- | --- | --- | --- | --- |
| Interpreter in C | 4,874.6587 | 5 | 5.59 | N/A | A Brainfuck interpreter written in C |
| GCC | 901.0225 | 3 | 1.03 | **52 KB** | Compile BF code to C, then build with `gcc -O3 -march=native` |
| Clang | 881.7177 | 2 | 1.01 | 56 KB | Compile BF code C, then build with `clang -O3 -march=native` |
| .NET JIT | 925.1596 | 4 | 1.06 | N/A | Use JIT to build the type on-the-fly for running |
| .NET AOT | **872.2287** | 1 | 1.00 | 1732 KB | Use .NET NativeAOT to build the exe that runs the compiled type directly |

This approach achieves the best performance among all tested implementations, including those written in C.

Similar result can be observed at https://github.com/kostya/benchmarks, where `C# (Staged)/.NET Core` follows the same approach, which dominates the top of all bf benchmarks by a wide margin.

## Conclusions

This brings .NET the ability of constant generic types without any breaking change and gives us the ability to do value specialization with low cost. Compared to the previous design, this brings us 90% of the benefit for 10% of the cost.

In general, there're several advantages with this approach:

- The runtime doesn't need any change to support const generics
- No metadata changes or breaking changes at all, so that existing tools continue to work
- Generic instantiation is **NOT recursive**, which means that it's fairly cheap for the runtime to evaluate its value when necessary (eg. `ValueArray`)
- The JIT requires no special handling for constant folding
- It's fairly easy for the C# compiler to implement, and can be used even without the compiler support (with reduced UX)
- Provides unified interfaces for data interchange across the managed ABI

One tradeoff of this approach is that it can increase pressure on the generic type system, since each distinct constant value produces a distinct generic instantiation at runtime. This naturally results in more constructed types than traditional generics. However, the primary purpose of const generics is to enable hot‑path specialization while preserving abstraction and code reuse, particularly across managed ABIs. In practice, const‑generic types are expected to appear only in performance‑critical paths where specialization is intentional and beneficial. They are unlikely to be used heavily in startup‑sensitive code, and once a constant value type is instantiated, it remains available for the entire lifetime of the process. These instantiations can also be preinitialized via ReadyToRun when desirable. As a result, the additional generic instantiations should not meaningfully impact startup performance or overall application footprint. Additionally, if we want to reduce the number of type parameters in an instantiation, we can replace the hexadecimal digit types with base‑256 digit types so that `Int32Constant` becomes `Int32Constant`.

Finally, a partial reference implementation can be found here: https://github.com/hez2010/TypedSql/blob/3e61a99e26ef27bf573b0f7dfc38dffcc18d226c/Runtime/TypeLiterals.cs

/cc: @AaronRobinsonMSFT