Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail Call Improvements in .NET Framework 4

extended64.com

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Tail Call Improvements in .NET Framework 4

#11

Post by CWuestefeld »

mikedouglas wrote: post #6
CWuestefeld wrote: post #5

on x64 you should see shorter call stacks in optimized code because the JIT generated more tail calls (don’t worry this optimization is turned off for debug code) I think it used to be that there was little perf difference between DEBUG and RELEASE builds, so for simplicity, with internal apps we always just build to DEBUG. The above quote suggests that these days, they really are doing worthwhile optimizations in RE…

This sounds like a bad idea. TCO is not just a perf difference. Once you add it to a language, you've changed the semantics. The same piece of code will throw a StackOverflowException in DEBUG mode, yet functional perfectly in RELEASE. Scheme's spec requires TCO for this very reason.

I don't think that they're talking about adding this at the language level. Nothing is changing in the C# spec for this, for example. This is just talking about the kinds of code that the optimizer and JITter are allowed to generate on the back end.

Re: Tail Call Improvements in .NET Framework 4

#12

Post by bad_user »

scott_s wrote: post #9
mikedouglas wrote: post #6

Earlier quoted context omitted.

This sounds like a bad idea. TCO is not just a perf difference. Once you add it to a language, you've changed the semantics. The same piece of code will throw a StackOverflowException in DEBUG mode, yet functional perfectly in RELEASE. Scheme's spec requires TCO for this very reason.

You and I have a different definition of "semantics" when it comes to programming languages. Your code still achieves the same result, just in a different way. That requirement - equivalent outcome - is how compilers decide what optimizations it can and can't perform. This is often stated as "optimizations can't change program semantics."

If an optimization means that an algorithm reaches the desired result or not, that's not an optimization anymore.

  def fact(n, r=1):
    if n == 1: return r
    return fact(n-1, r * n)
Regardless of any available stack-space you may have, for the above method (which can be tail-call optimized) try calculating fact(1000000). If that's the requirement, then without TCO this implementation is incorrect.

Re: Tail Call Improvements in .NET Framework 4

#13

Post by trezor »

If I'm reading this correctly this only applies to the .NET 4 runtime and not the old .NET 2.0 runtime (also powering .NET 3.0 and 3.5 solutions).

In that case I guess if you are running tail-recursion heavy algorithms on x64, just recompiling the same old code for the .NET 4 runtime should yield runtime improvements.

Would be interesting if someone had any actual measurements for this.

Re: Tail Call Improvements in .NET Framework 4

#14

Post by Gobiner »

trezor wrote: post #13

If I'm reading this correctly this only applies to the .NET 4 runtime and not the old .NET 2.0 runtime (also powering .NET 3.0 and 3.5 solutions). In that case I guess if you are running tail-recursion heavy algorithms on x64, just recompiling the same old code for the .NET 4 runtime should yield runtime improvements. Would be interesting if someone had any actual measurements for this.

I'm no CLR JIT expert, but I'm not sure you even need to recompile. It sounds to me that you just need to run your existing tail-calling code on the .NET 4 x64 CLR, presuming your current code has ``tail'' opcodes.

Re: Tail Call Improvements in .NET Framework 4

#15

Post by Gobiner »

mikedouglas wrote: post #6
CWuestefeld wrote: post #5

on x64 you should see shorter call stacks in optimized code because the JIT generated more tail calls (don’t worry this optimization is turned off for debug code) I think it used to be that there was little perf difference between DEBUG and RELEASE builds, so for simplicity, with internal apps we always just build to DEBUG. The above quote suggests that these days, they really are doing worthwhile optimizations in RE…

This sounds like a bad idea. TCO is not just a perf difference. Once you add it to a language, you've changed the semantics. The same piece of code will throw a StackOverflowException in DEBUG mode, yet functional perfectly in RELEASE. Scheme's spec requires TCO for this very reason.

If you think a feature that could potentially behave differently in RELEASE and DEBUG modes is problematic, you'll want to avoid floats and doubles in .NET. Runtime optimizations that do calculations in the processor's 80-bit FPU can alter the results of float/double calculations. My personal example: http://stackoverflow.com/questions/2225503/clr-jit-optimizat...

Re: Tail Call Improvements in .NET Framework 4

#16

Post by DougBTX »

Gobiner wrote: post #14
trezor wrote: post #13

If I'm reading this correctly this only applies to the .NET 4 runtime and not the old .NET 2.0 runtime (also powering .NET 3.0 and 3.5 solutions). In that case I guess if you are running tail-recursion heavy algorithms on x64, just recompiling the same old code for the .NET 4 runtime should yield runtime improvements. Would be interesting if someone had any actual measurements for this.

I'm no CLR JIT expert, but I'm not sure you even need to recompile. It sounds to me that you just need to run your existing tail-calling code on the .NET 4 x64 CLR, presuming your current code has ``tail'' opcodes.

Appears to require a small amount of magic: http://stackoverflow.com/questions/896629/how-to-run-clr-2-a...

Re: Tail Call Improvements in .NET Framework 4

#17

Post by eru »

bad_user wrote: post #12
scott_s wrote: post #9

Earlier quoted context omitted.

You and I have a different definition of "semantics" when it comes to programming languages. Your code still achieves the same result, just in a different way. That requirement - equivalent outcome - is how compilers decide what optimizations it can and can't perform. This is often stated as "optimizations can't change program semantics."

If an optimization means that an algorithm reaches the desired result or not, that's not an optimization anymore. def fact(n, r=1): if n == 1: return r return fact(n-1, r * n) Regardless of any available stack-space you may have, for the above method (which can be tail-call optimized) try calculating fact(1000000). If that's the requirement, then without TCO this implementation is incorrect.

Indeed. Though you have to exclude preservation of timing (and memory usage) effects from your definition of semantics to make any optimization possible.

Re: Tail Call Improvements in .NET Framework 4

#18

Post by pcarmichael »

Gobiner wrote: post #15
mikedouglas wrote: post #6

Earlier quoted context omitted.

This sounds like a bad idea. TCO is not just a perf difference. Once you add it to a language, you've changed the semantics. The same piece of code will throw a StackOverflowException in DEBUG mode, yet functional perfectly in RELEASE. Scheme's spec requires TCO for this very reason.

If you think a feature that could potentially behave differently in RELEASE and DEBUG modes is problematic, you'll want to avoid floats and doubles in .NET. Runtime optimizations that do calculations in the processor's 80-bit FPU can alter the results of float/double calculations. My personal example: http://stackoverflow.com/questions/2225503/clr-jit-optimizat...

If you want identical results regardless of optimization level or machine characteristics, you should really be using fixed-point instead.
Post reply on HN