Timeline for Is recursive code slower than non-recursive code?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 11:33 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| May 6, 2014 at 19:20 | comment | added | user7043 |
@Giorgio Tail recursion elimination is easy enough, and indeed implemented. TCO for arbitrary callees would require full trampolining everywhere, which kills Java interop (extremely important for both) and is very slow. You can't pull local tricks like jumping to the target code without setting up another stack frame because the JVM won't allow it. There's no cross-method jump, only the invoke* opcodes which always set up the call frame for you.
|
|
| May 6, 2014 at 19:01 | comment | added | Giorgio | @delnan: I still have to understand why a JVM limitation should prevent a Scala or Clojure compiler from generating code that does TCO. This is really beyond my understanding. Maybe there is no direct translation, but I cannot see why it is so difficult to generate code that does TCO. | |
| May 6, 2014 at 0:57 | comment | added | John R. Strohm | See also stackoverflow.com/questions/34125/… | |
| May 5, 2014 at 18:33 | comment | added | user7043 | @JohnR.Strohm You can discuss how easy and desirable TCO is with the maintainers of the various language implementations mentioned before. As of right now, a large number of very popular languages have no implementation that does TCO, and another set has no reliable TCO. (And to be honest, I'd be surprised if your evangelism changed anything about that.) | |
| May 5, 2014 at 18:30 | comment | added | John R. Strohm | @delnan, Steele's paper explains TCO and shows that TCO is not particularly difficult to implement: it is a very straightforward code generator optimization IF the code generator sees stacking the return address and jumping to the subroutine as two separate operations, and then allows the optimizer to decide whether it actually NEEDS to stack the return address, or any intermediate data. If the optimizer decides it does need to do this, it generates a CALL. If the optimizer decides otherwise, it generates a plain jump. | |
| May 5, 2014 at 6:17 | comment | added | user7043 | @JohnR.Strohm What claim exactly do you want to support with that reference? I did not say TCO can't happen or can't be very effective. I supported m3th0dman's claim that many imperative languages don't have TCO by given numerous examples. Regardless of how effective TCO is, or how easy it might be to implement, if it isn't actually implemented users of those languages don't benefit from TCO. I see nothing in the Steele paper arguing against that. | |
| May 5, 2014 at 6:02 | comment | added | John R. Strohm | @delnan: Read Guy Lewis Steele, Jr.. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977. repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf | |
| May 5, 2014 at 5:34 | comment | added | user7043 |
@JohnR.Strohm There are many languages without optimizing compilers (mostly those commonly called "interpreted"). The JVM doesn't do TCO -- Scala and Clojure have to implement their own tail recursion elimination and don't have TCO. The CLR does support tail calls, but it must be opted into and at least C# (and probably other imperative CLR languages) doesn't do that. Finally, even in imperative language compilers that support TCO in principle, it's optional and very restricted/fragile (just check the restrictions on LLVM's tailcall).
|
|
| May 5, 2014 at 2:51 | comment | added | John R. Strohm | @m3th0dman, in this, the second decade of the 21st century, pretty much ALL production-quality compilers support tail-call optimization. There was a StackOverflow question about strange 8051 code generation (may have been PIC), that turned out to be tail-call optimization. Read the various "Lambda: The Ultimate ..." papers from the MIT AI Lab, from decades ago. Tail-call optimization is in fact a very straightforward code generator optimization. | |
| May 4, 2014 at 15:08 | comment | added | Random42 | @Giorgio The only thing is that most imperative languages does not have support tail-call optimization. And in functional languages there is no discussion since you only have recursion. | |
| May 4, 2014 at 15:06 | history | edited | Random42 | CC BY-SA 3.0 |
added 150 characters in body
|
| May 4, 2014 at 14:40 | comment | added | Giorgio | As far as I know, a clever implementation of tail-call optimization will run as fast as a while loop using local variables. The difference is that using recursion you have to specify inputs and outputs to each iteration explicitly, which makes it easier to write correct code. Also, while the underlying implementation can still use side-effects for efficiency, at the level of your programming language semantics you can write purely functional (side-effect free) code. | |
| May 4, 2014 at 14:14 | comment | added | Overly Excessive | Yes, I've ran into a couple of stack overflows because of using recursion "carelessly" .. | |
| May 4, 2014 at 14:08 | history | answered | Random42 | CC BY-SA 3.0 |