Introduce detection of generic cycles #1681
Conversation
| if (previousAlgorithmTimeoutWatch.ElapsedMilliseconds > s_previousAlgorithmTimeout) | ||
| { | ||
| abortedDueToTimeout = true; | ||
| break; | ||
| } |
There was a problem hiding this comment.
We might not want this for determinism. I've not seen things go anywhere near the timeout. Even in unoptimized debug builds most assemblies are analyzed within 2 seconds.
There was a problem hiding this comment.
So delete it for now and see whether it is going to show up as actual problem?
There was a problem hiding this comment.
We may want to just print a message to verbose logger, so that it is easy to tell that the compilation is struck in this recursion detector.
There was a problem hiding this comment.
I looked at this a bit more and the "previous algorithm" this is referring to is the original algorithm .NET Native used. .NET Native originally had a naive implementation of this that would take a really long time. Then David changed it to use Tarjan's algorithm. He kept the original algorithm and in DEBUG builds we run both and compare the results. So all of the timeouts are under #if DEBUG. It's probably fine to just keep this or delete it all. I don't have a strong opinion either way. It's probably easier to see why the cycle formed in the naive algorithm.
MichalStrehovsky
force-pushed
the
lazygenerics
branch
from
e20ec47 to
a4e5c58
Compare
|
With the latest commit, the impact on compiler throughput is within noise range. The largest assembly in WebApi gets analyzed in 88 ms. Most assemblies are in single-digit ms range, a lot even at 0. We do pretty much all of this work in the multithreaded phase. |
MichalStrehovsky
force-pushed
the
lazygenerics
branch
from
ff42a68 to
1ec14c5
Compare
| { | ||
| if (referentType != null) | ||
| { | ||
| // TODO: better exception string ID? |
There was a problem hiding this comment.
This is more part of the compiler, not part of the core type system. I think we can just use regular logger to communicate the problem here, and also log the types and method involved in the cycle here.
There was a problem hiding this comment.
This exception will still be rethown at runtime when the cutoff code is actually reached, so we need a string ID because we might end up generating throwing code out of this. Throwing a type system exception makes all of this fall out of it nicely because we have all the infrastructure to do that.
I'll revisit this when I work on a nicer experience around this.
|
Cc @yowl - the change in CorInfoImpl.RyuJit.cs (or the equivalent change in ILImporter.Scanner.cs) is relevant to WASM as well - without the extra call to check if we're forming a cycle, the new tests in Generics.cs will run out of memory at compile time trying to compile an endless generic recursion. |
|
With above changes there're still some tests failing, see #776 for test cases.
|
|
Are you running the tests in reflection disabled mode? The tests do use reflection and reflection disabled mode didn't bother overriding non-abstract methods on System.Type, so that would explain NotSupported_SubclassOverride. The NullReferenceException is expected because "If we cutoff the generic recursion within a generic dictionary, the failure mode at runtime is a NullRef shortly after a dictionary lookup (because the cut off slot will be null). It’s not great. I think we can update the lookup helpers to check for null while restricting the check to only the helpers where we’ve seen a damaged slot. We also need to make sure such lookups never get inlined by RyuJIT and always go through our helpers. I think it’s doable and not hard. I just don’t want to put more in this pull request than what’s strictly necessary."). |
Yes. I forgot to enable reflection while testing :D |
Alternatively I suppose if the methods in questions were compiled with the new RyuJit process they would get the benefit of your changes in |
Yup, that should just fall out there! |
4 participants
Motivated by npgsql/npgsql#4057. The generic recursion that was in Npgsql made its way back into Npgsql. We've seen these show up too often. Not because it's common to write recursions in C#, but because popular NuGets end up having these and then people hit it too often.
This brings over the generic cycle detection from .NET Native and hooks it up in a rudimentary way. The pull request is split into logical commits for better reviewability.
We detect generic recursion at two spots:
If we detect a recursion, we unceremoniously cut it off after a couple levels of nesting. The cutoff point is fairly low because in the cases I’ve seen, the recursion also causes an expansion in breadth, not just depth, and allowing that to go unchecked was resulting in sadness. If the code goes beyond the cutoff point at runtime, it will not work.
The recursion detector is essentially a prepass – it goes over everything in the assembly, trying to look for recursions and generating a list of types/generic method involved in a cycle. I’m fairly convinced it cannot be done in other ways than with a prepass.
Looking at the .NET Native code, we had quite a few limitations where generic recursion would not be detected. Given a failure to detect a cycle results in a compiler failure, and we’ve not heard of this failure over the years, the .NET Native approach is likely sufficient.
What’s missing
If we cutoff the generic recursion within a generic dictionary, the failure mode at runtime is a NullRef shortly after a dictionary lookup (because the cut off slot will be null). It’s not great. I think we can update the lookup helpers to check for null while restricting the check to only the helpers where we’ve seen a damaged slot. We also need to make sure such lookups never get inlined by RyuJIT and always go through our helpers. I think it’s doable and not hard. I just don’t want to put more in this pull request than what’s strictly necessary.
Lazy generics. If the recursion happens over reference types, we could potentially generate fully working code by failing back to lazy generics. The cases I was looking at were not over reference types.
We might want to allow specifying the cutoff point at compile time (also allow disabling all of this).
Perf
I've seen a 2% regression in compilation throughput for WebApi template. We can make this more efficient by e.g. not hydrating type system objects for everything when we're scanning for cycles and staying with S.R.Metadata for longer.