Never rely on tail recursion elimination
(No Ratings Yet)
Loading ...Corollary: Never write a recursively method with an unbounded stack depth.
I previously posted a recursive implementation of Factorial, and asked the readers “not to bother saying it’s inefficient because of recursion, since it will probably be optimized away anyway”. Not true.
I don’t really understand why (just posted a question to StackOverflow), but C# does not generally perform tail recursion elimination (at least as my measly test show).
The following method can be easily optimized, both to work faster, consume less space and not to cause a StackOverflowException … but it is not optimized by the compiler (verified by Reflector and the fact a StackOverflowException was indeed thrown).
private static void Foo(int i) { if (i == 1000000) return; if (i % 100 == 0) Console.WriteLine(i); Foo(i+1); } |
So … if for some reason you prefer writing recursive methods over using loops, do it only where performance is not a consideration and you have a good understanding of the maximal stack depth.
Tomer Gabel:
Inconclusive: try NGen’ing the compiled assembly and check the generated native code. CSC performs almost no optimizations; nearly everything is done in the JIT.
2/2/09, 21:38ripper234:
I’ve read somewhere that NGen doesn’t help. Will verify. The JIT obviously didn’t optimize it away because it did throw a StackOverflowException.
3/2/09, 12:11ripper234:
NGen does’t help.
.method private hidebysig static void Foo(int32 i) cil managed { .maxstack 8 L_0000: ldarg.0 L_0001: ldc.i4 0xf4240 L_0006: bne.un.s L_0009 L_0008: ret L_0009: ldarg.0 L_000a: ldc.i4.s 100 L_000c: rem L_000d: brtrue.s L_0015 L_000f: ldarg.0 L_0010: call void [mscorlib]System.Console::WriteLine(int32) L_0015: ldarg.0 L_0016: ldc.i4.1 L_0017: add L_0018: call void StackOverflow.Program::Foo(int32) L_001d: ret }5/2/09, 11:56Tomer Gabel:
That’s not an ngen image – I’m talking native code, here. Try C:\Windows\assembly\NativeImages_v2.0.50727_32, I think that’s where ngen’d assemblies go.
5/2/09, 20:13ripper234:
I went to said location, viewed it with reflector, and this is what it shows.
5/2/09, 20:25I don’t really have the will to open IDA now, but running the example proves my point.
Tomer Gabel:
Can I assume you’ve compiled for RELEASE?
5/2/09, 20:27ripper234:
Yes you can.
6/2/09, 9:46Tomer Gabel:
In that case, I’m (badly) surprised. I’ll try to do some more research on the subject.
6/2/09, 15:52