.net JIT compiler quadratic on large methods

Question

I would like to generate a large switch statement in IL, then JIT-compile it, and run it . It seems that the JIT compiler takes time somewhat worse than quadratic in the size of the code. Doubling the input size multiplies the compilation time by a factor of between 4 and 6. The individual cases are under 10 instructions each.

Could someone please tell me if there is a way of asking the JIT compiler to take O(n^(1+epsilon)) time (E.g. linear, n log n, or something else substantially sub-quadratic)? I am not fussed about degraded quality of results.

The reason for generating an enormous switch is not important here. I can work around the issue by nesting switches. I cannot just put the keys into a dictionary because it would need to map to functions, and lots of little functions are bad for scalability too (possibly not as bad as massive switches, but it's still a pan/fire sort of a situation where blindly changing one for the other probably will not buy a huge amount of headroom).

Answer 1

I would guess the JITter is trying to find common sub-expressions, etc. I think it is worth attempting to convert it to a Dictionary(Of <lookupType>, Func(Of <ParameterTypes>, <ReturnType>)) as that would also mean the JITter only compiles the cases actually used. Of course, if your individual delegates end up being based upon large closures, that probably explains part of your original performance issue.

Alternatively, and to partially confirm what the JITter is doing, don't change the switch code, but in each case call a delegate that evaluates the result for that case. This will force the JITter to not inline the call and thus not attempt many optimisations. In fact, you can probably avoid the delegate call and just supply each case in a subroutine with the System.Runtime.CompilerServices.MethodImpl(MethodImplOptions.NoInlining) attribute.