ActivePatterns: Compilation issues (memory and speed)

[Thorium]

I'm trying to compile a little simple F# file I made, using the latest released stable .NET. Zip attached

ClassLibrary1.zip

Expected behaviour

Either compile or fail in a meaningful manner. F# should be fast to compile a single file, right?

Actual behaviour

I have no idea what is going on.

Related information

Provide any related information (optional):

• Operating system: Windows 11
• .NET Runtime kind (.NET Core, .NET Framework, Mono): Net 9.0,.201
• Editing Tools (e.g. Visual Studio Version, Visual Studio): Dotnet.exe or VS 2022 Professional 17.13.5.

[Thorium]

This is somehow related to active-pattern usage:

match
| A
| B
| C
| D
...
| Y
| Z when (something) -> ... // out of memory

But if the when-conditions break the match often, (even with identical "something") then it works:

match
| A when (something) -> ...
| B when (something) -> ...
| C when (something) -> ...
| D when (something) -> ...
| E when (something) -> ...
| F when (something) -> ...
...
| Z when (something) -> ...

[T-Gro]

Bisecting tells me the issue (I assume it is an infinite loop, but could also be something too slow and I was not patient enough to see it finish) is within

// A = "x" && A = "x" ->  A = "x"
    let ``remove duplicate condition`` (e:Expression) =

function's body. The code above it, despite also having big patterns (e.g. ~150 clauses for distribute_complement) compile fine.

[Thorium]

Yes. Although if you remove that code totally, and then remove the other duplicate intermediate "when"s, then it will fail as well:

The annoying thing here is that you'd expect the code to be more efficient when removing the "unnecessary" whens.

[T-Gro]

The presence of a when can disable certain optimizations due to having the possibility of a side effect.

This --times:files.csv output indeed tells that there is something in optimizations for this file. Worth mentioning that even the typechecking and TAST->IL transformations (=IlxGen) are super slow considering a single-file project here.

(note that I have disabled all optional optimizations just to get the compilation done, there likely are other bottlenecks if the full optimizations would be running)

[Thorium]

Something like this maybe? https://sharplab.io/#v2:DYLgZgzgNALiCGEC2AfAsAKGAUxgAnwF48AlbCASwC9sBBAJ3vgE8AeAewCMArAPgAoAlJkw587AHbYAkhIAqAC2wBRCQBMheYpjy68SeDADGCgngDuFGAp16UeEAH48AZWYQY2JADoAwu2AcIxgKSQhvAHFsKXoKI28AGQoPVgB9Xl1bXXsnV3dPH39A7GDQiXComLjE5Jg0jLwsvBznNw8vPwCgkLDI6OxY+KSU9MyMPWaHVvyOou6yiv7BmpGGppa89sKukp7yvqqh2vqxiY22gs7i0t7KgerhutHG8bspzcu53YWD+6PV05vXIXWY7G77O7LR4nF5nd4g7bXPaLQ4rJ5rV7ZeEzRHzW5LB7HZ7rbFbK54iEE/7owFY4E48nffGo6HEzGTelkr7glF/NEwkmcz5g5G/KFEjFwoWgpE/SGEgGIAgAFgsSgkKs6AFcJEQ8AAGPAAWgyMGVJNSxoyEi1gREWFweEkyngJn86isZU02nZBmMpnwlmsgumXJFcqp/NGSrNauimv8Or1hpNKpDHxlFN54sVEBVcY1Zu1uq0BqtafZ5wZ3NF8upJxjqvM6oT7CTpZTpvNldJwtlzL5rIyjYLrfbxE7Falob7WbFCppI+b8aLiZLE/LZvTCMZPPn9ejedjy8LyuLyc33enGdxTMpLIleCXLdXbfXZdTW570tve7rUeHI8mxfM81wvT8ryBGdMzvbMFwbIDR1fccPy7bdq3DAcc0XRCTzHd9Jy/a8dxrCMH1zfM8OQgjL3QsN+3vQdH2fFdQLfcC0O/aDf1rSMhyfXCQPPDtaK4m9d148icMooSwJEiC6NnWD9wAgSZNY4SNwUntLVTG07QwURHWdAA3AZmAAMQoMz3TUT1JG9WE9D9EwzCDGwxJIzDGOwgVPIwhi4IPSUoPE0isPgtliICud/34py6W4iSyKYijj1k9j5M46L6NivjHwSjkkvCnzIpCxKwu8oLVMKqtcuUuKCsUmC/3ytLgI0uStOy0KvMClT4uaniUt8qLepihq2ppWrexayTUumobkoi4K1PSzrMu6qc3l061bWAe0gA===

[T-Gro]

There is definitely a missing reduction step to put those shared conditions together, which is also what might be slowing down the compilation's optimization phase.

It correctly unifies the type check / type cast as far as I can see, but it still multiplities the when clause contents instead of unifying it. Strange.

[Thorium]

Any news on this? Can I somehow help. or is this requiring way too much internal domain knowledge for a random dev to be useful?

[T-Gro]

I would love to be able to tell more, but I am also not deeply familiar. I would start with looking at PatterMatchCompilation, this section might be relevant: https://github.com/dotnet/fsharp/blob/main/src/Compiler/Checking/PatternMatchCompilation.fs#L1689 .

One option could also be to add your sample as a test into the ComponentTests suite and set up breakpoints at the beginning of pattern match compilation - but due to the big sizes of both input and output, the debugging session might be tricky to navigate :((

[T-Gro]

This comment admits something you spotted when trying different placement of the when clause:

https://github.com/dotnet/fsharp/blob/0dd8a0a3d562996ab5ad3854cd27eabab5fb7ae4/src/Compiler/Checking/PatternMatchCompilation.fs#L1673

[majocha]

Trying to build it in current VS, memory use is not super excessive but it fails after few minutes:

Build started at 12:47 PM... 1>------ Build started: Project: ClassLibrary1, Configuration: Debug Any CPU ------ 1>error FS0193 : internal error : Specified argument was out of the range of valid values.Parameter name: index 1>Done building project "ClassLibrary1.fsproj" -- FAILED. ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== ========== Build completed at 12:51 PM and took 03:05.894 minutes ==========

[Thorium]

Regardless of the optimization-step-fix (which would be nice, yes):

The clear answer here is that patterns that crash the compiler should be considered as problematic.

As far as I understand, a "problematic pattern" causes the compiler optimzation to be skipped and just generate a lot of (possibly duplicate) IL-code, so it has a runtime-execution performace hit.

What are the limits, how much is expected that the compiler can do? That's hard to say, because on hard-line approach "code recommended cyclomatic complexity is 10", would hit many of users who use active patterns just for the exact reason that they make complex code easier to handle.

It's better to code to compile than crash, but existing users shouldn't see runtime-performace-hit.

I asked Claude Sonnet for it's recommendation (which should always be considered with doubt) considering the full picture, and it recommended this kind of code to solve the issue (the threshold "200" is just a magic figure because it didn't analyse the capability of compiler, but rather existing match-clauses from this codebase): https://github.com/Thorium/visualfsharp/commit/4bc05654890abfc4d83301a74b11b265290a501e

[T-Gro]

It's difficult to assess if the complexity is inherent to the problem space, or just accidental and possible to avoid via different coding style.

I have a feeling a "warning: Complexity over 200" is not that helpful to programmers unless we would be able to advice them better.

In your experimentation, did you find any matches in a codebase, e.g. this one, where this triggered? It would be interesting for me to have a look at the reported cases in code - and see if there is "an obviously better" way to code them or not.

[Thorium]

What do you thing should we take the unit-test from that commit?

[T-Gro]

The test has value for sure, as it shows a currently problematic area 👍 .