Enable Compile-Time Folding of Deterministic Outputs

[TonyValenti]

This is a feature request to enable the compiler to do Compile-Time folding of deterministic variables and method outputs.

This will provide the following enhancements to C#:

• More errors can be discovered at compile time.
• "Gotchas" related to "That's not a constant" errors will be related.
• Trade compile time Performance for run time performance.

First, a few definitions:
Constants are deterministic.
Literals are deterministic.
A variable is said to be deterministic at a specific point in time if, at that point in time, it has only been assigned to or constructed from other deterministic values.
A method is said to be deterministic if, given a set of input, it always returns the exact same output. (It does not reference any external sources. Files, sockets, Time, globals, etc)
A function invokation is said to be deterministic if the function being called is deterministic and every input to the function is deterministic at the call site.
A value is said to be "Literalized" when the compiler can create construction information that can be stored to recreate a lossless copy of the value at runtime.

When the compiler encounters a variable or function invokation that is deterministic, the compiler should attempt to execute the method and then replace the variable or function invokation with the literalized output from the function.

[DavidArno]

When the compiler encounters a variable or function invokation that is deterministic, the compiler should attempt to execute the method and then replace the variable or function invokation with the literalized output from the function.

I like the idea here. However, I'm concerned over the increase to execution time that this could put on the compiler:

static void Main() => Console.WriteLine(DeterministicallyCalculatePiToOneMillionDigits());

Whilst amusing that the compiler would convert this to:

static void Main() => Console.WriteLine("3.1415...");

I'm not sure I'd want to wait for it to compile each time...

[bbarry]

@DavidArno why not?

So long as you could interrupt and cancel compilation and get a reasonable message about what was going on (perhaps a deterministic compilation profile of some sort?) I don't see why potentially long compilation times should be a stopper.

That said I don't think this folding optimization should be written into the C# language. I think it would be much better as an IL rewrite tool.

I'm imagining being able to fold across assembly boundaries for example.

[DavidArno]

@bbarry,

Because I like to work using TDD, so want a very fast save/build/test loop whilst writing the code. I really like your the idea of a post-build deterministic IL run/rewrite process though. That could take its time as it would be something I'd run occasionally.

[svick]

Are you basically asking for adding support for C++ constexpr to C#?

[TonyValenti]

Yes.

…

On Wed, Apr 26, 2017 at 12:18 PM, Petr Onderka ***@***.***> wrote: Are you basically asking for adding support for C++ constexpr to C#? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://github.com/dotnet/csharplang/issues/504#issuecomment-297481041>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AM-qVsasDepn6bv5RyMzCs1LvxW8pD1wks5rz3xggaJpZM4NIrug> .

-- Tony Valenti

[jnm2]

See dotnet/roslyn#15079 for background.

[lachbaer]

I'm not sure I'd want to wait for it to compile each time...

Actually the evaluation could be given a short period of e.g. 10ms otherwise the whole expression or function is considered non-deterministic.

Also the deterministic optimizations should be allowed within the same assembly only.

[FredyFerrari]

@lachbaer Better not compile time based, otherwise when compiled on different machines we may get completely different IL.

[lachbaer]

@FredyFerrari True, maybe it could be done with something like "evaluation cycles", e.g. sub-expression counts.

[gafter]

Is there a language specification change requested here? Or merely a change in the code produced by compilers?

[tannergooding]

@gafter, from my point of view, the language spec should be updated to have an explicit keyword (à la constexpr) and it would explicitly document what is/isn't allowed (for reference, this started very minimally in C++11 and was expanded in C++14 and further expanded in C++17: http://en.cppreference.com/w/cpp/language/constexpr).

The compiler would additionally perform constant folding on an constexpr that are used (dropping calls in favor of just emitting the result returned by the expression).

[mattwar]

@DavidArno This could make compilation really slow, but think about the speed up at runtime! Performance benchmark tests would be blown away! Imagine graphics tests where the series of completed bitmaps are compiled in! 😏

[tannergooding]

@mattwar, I think the compilation slowdown entirely depends on what limitations the compiler imposed.

Some of the limitations would exist simply because C# doesn't support them today. For example, you likely wouldn't be able to use constexpr with user defined types (System.Numerics.Vector4, for example) since the compiler doesn't allow those to be constant today.

If/when C# does get support for other constant types, this could be greatly expanded and start taking longer :) (constant support for blittable types might not even need runtime changes, since they already support constant byte[]).

[gulshan]

👍 for const support for blittable types.

[Joe4evr]

@gulshan That is #688, which is filed separately because it would be done differently under the hood.

[paulomorgado]

@DavidArno

Because I like to work using TDD, so want a very fast save/build/test loop whilst writing the code. I really like your the idea of a post-build deterministic IL run/rewrite process though. That could take its time as it would be something I'd run occasionally.

That wouldn't be the only optimization turned of in the Debug configuration.

[scalablecory]

This could open up some really fun stuff, like a generalized hash-based switch() that uses constexpr methods to get hashes for cases.

[ArtGangsta]

This is a feature request to enable the compiler to do Compile-Time folding of deterministic variables and method outputs.

This will provide the following enhancements to C#:

• More errors can be discovered at compile time.
• "Gotchas" related to "That's not a constant" errors will be related.
• Trade compile time Performance for run time performance.

First, a few definitions:
Constants are deterministic.
Literals are deterministic.
A variable is said to be deterministic at a specific point in time if, at that point in time, it has only been assigned to or constructed from other deterministic values.
A method is said to be deterministic if, given a set of input, it always returns the exact same output. (It does not reference any external sources. Files, sockets, Time, globals, etc)
A function invokation is said to be deterministic if the function being called is deterministic and every input to the function is deterministic at the call site.
A value is said to be "Literalized" when the compiler can create construction information that can be stored to recreate a lossless copy of the value at runtime.

When the compiler encounters a variable or function invokation that is deterministic, the compiler should attempt to execute the method and then replace the variable or function invokation with the literalized output from the function.

Sir, no issue with your proposal. I like it. I do have a question for you with regard to your take on "literalization". Let's say today with C# upon startup, a list of words (strings) are added to an array. The array doesn't change, and in fact, it is the same list of words every time. You can assume the list comes from a file, or perhaps they appear as part of an array initialization in a static constructor.

The problem with C# is that the only type of string is a .NET string. What if I have 100 strings, each no longer than 64 characters in length. I'd like to allocate memory that's 100 * 64 * sizeof(char), and put those strings there, padding with spaces as necessary. Then I'd calculate the start of each of those strings and place the address in a 100 * IntPtr size array. All of this to be done at compile time such that at runtime I can make a method call, given an index, it would return to me directly one of the strings, based on the index, in the form of a ReadOnlySpan.

I imagine the only part of this that unknown until runtime is which index the program wants. Even the construction of the ReadOnlySpan could be done at compile time, theoretically.

I don't know how much of this would require a change to the CLR. These things are possible in C++/CLI, so there must be some way to do this.

Thoughts?

[yaakov-h]

also unknown is the endian-ness for multibyte characters. IIRC this is why a ROS initialiser can be rolled into a data block but ROS cannot.

[koenbeuk]

Just to add: this can already be done today using Source Generators (e.g. as demoed here: https://github.com/hermanussen/CompileTimeMethodExecutionGenerator)

A source generator could at compile time evaluate properties and methods marked with an Attribute and generate a companion method/property with the predetermined result. Then during Linking, the source implementation could properly be removed from the final output.

[TonyValenti]

Can this be expanded so that it does the replacement at the call site? A deterministic method can still be deterministic if all its inputs are deterministic. This seems to be limited to only functions that accept no parameters.

[koenbeuk]

As long as the arguments are deterministic, I would see why not. The linked project is just a proof of concept but it should be able to be expanded upon to accept input arguments. A replacement at the call site would then just be a method call with some deterministic arguments that then get inlined.