All About Recursion and Tail Calls in JavaScript | Hacker News Reader

All About Recursion and Tail Calls in JavaScript

lucasfcosta.com

67 pointsblacksmythe21 comments

What I don't understand with STCs is, how would I, as a developer, decide when to use them and when not?

As program correctness is concerned, tail calls and recursive calls should behave exactly the same (except stack use), so going by correctness alone, either the choice doesn't matter at all or tail calls are preferable. So the logical thing to do would be to always use tail calls.

The post goes on to list a number of disadvantages, but those seem to be either debugging concerns or platform-specific implementation concerns.

The former doesn't seem to be something that should be solved in the code - the document itself lists a number of solutions. The latter is not something that I as developer could judge as I likely don't have knowledge about the specific implementation of the platform the code is running on (if I know the platform in advance at all)

So it seems to me, STC shifts the problem of deciding to the developer even though the developer has no good tools to actually solve it.

I think that TCO (and similar optimisations) are a bane to most junior developers. I vividly remember pulling my hair out when trying to single step through optimised C++ code early in my career. But in my experience, all good developers come to this point where they realise -- Hey, I don't need to single step through this code. I can read it and understand what it is supposed to do. These days, with the popularity of techniques like unit testing, debuggers are not really necessary. I've spent the last 4 1/2 years writing ruby and JS code and I don't even know how to use the various debuggers -- never needed to.

So I'm with you. Just give me TCO every single time -- or give it to me never. Optimising it by hand is not that hard, and it's what most non-functional programmers do most of the time anyway. You'll see loops where recursion would be clearer, but then when you look at it hard you'll realise that it's just the TCO optimised version of the same code.

You absolutely should have knowledge of your target platform and whether it does TCO (and whether it kicks in for your code).

Otherwise, you may decide to just use recursion everywhere and then your stack overflows when your N is bigger than expected.

When in doubt, don't use recursion and don't expect that you get TCO.

> You absolutely should have knowledge of your target platform and whether it does TCO

If I write web apps, as far as I'm concerned, my platform is V8, Whatevermonkey, Trident and every other hypothetical javascript engine out there, any of which might or might not support TCO under different circumstances.

> When in doubt, don't use recursion and don't expect that you get TCO.

I think relying on TCO is always a bad idea, exactly because you can't be sure your platform supports it. But STC doesn't change that. You can't expect the platform to support tail calls because you did some magic incantations.

On the other hand, it doesn't make sense to me to forbid tail calls either. If you know your recursive code will work without TCO, it will work with TCO, too.

Until ES6 which introduces Tail Call Optimization, you can use trampolines.

Small summary code: http://paste.ubuntu.com/24568118/

Trampoline would make a nice addition to Ramda. Unless I'm missing it under an unexpected name?

http://ramdajs.com/

What's the best way to benchmark perf optimizations in JavaScript. I see lot of articles like this with no time and memory usage stats. I would like to hear an answer from someone who has experience using gdb or visual studio while studying performance. Whenever I use the chrome debugger to time anything involving async calls and recursion I have this uncomfortable feeling I am not getting it right. With gdb or visual studio C/C# I always feel like I know what is going on.

Having worked on this pretty extensively, my preferred method is: (1) make two implementations of the function I'm trying to speed up, (2) add a wrapper so half of that function's calls get sent to each version, and then (3) profile in Chrome and compare the results (particularly the time spent in the two alternate implementations, but overall as well).

I know that's not the gdb-like experience you're looking for, but as far as I've found it's the best approach. The issue is that modern JS engines achieve their speed by tracking what happens at runtime and dynamically re-optimizing hot functions - so microbenchmarks are largely meaningless, and the performance of a given function can hugely affected by code that's far away.

(The above is for everyday. For extreme deep-diving, one can use JS engine tools to see what kind of internal representation your code has been compiled into after it got optimized. In chrome this is done with IRHydra - http://mrale.ph/irhydra/2/ .)

Thanks for link. Didn't know this was possible. Also will try your wrapper approach.

Google has a lot of content, for example "Chrome DevTools => Analyze Runtime Performance => Get Started With Analyzing Runtime Performance" [0].

But an important piece of advice is at the bottom of one of their pages [1]: "Avoid micro-optimizing your JavaScript". Apart from their argument there, keep in mind you are programming for a number of very different runtime environments. An optimization that gives you a big boost in one implementation may slow you down on another one. That is true not just between various vendors but also among runtime versions from the same vendor.

[0] https://developers.google.com/web/tools/chrome-devtools/eval...

[1] https://developers.google.com/web/fundamentals/performance/r...

Ya but that's like a get out jail free card. I have been through their stuff. It's very superficial. JavaScript has all kinds of implementation dependent mechanics when it comes to promises/async calls/recursion. And when they are happening together, all I want are two numbers at the end of the process. How long did this take and how much memory did this take.

But then you are looking at the wrong thing: You are no logger profiling/debugging Javascript but the Javascript runtime. Those tools do tell you the Javascript part, why do you say "superficial"?

Example (memory profiling with heap snapshots): https://developers.google.com/web/tools/chrome-devtools/memo...

Profiling functions (V8, Chrome, using the CPU Profiler): https://developers.google.com/web/tools/chrome-devtools/rend...

What is missing there, I can see how long each function took, even more so when I combine it with the flame chart?

I assume you are still talking about the Javascript part. What the C++ based subsystem does can be examined using tools for that language on the respective platform.

Why exactly was my reply downvote-worthy guys?

Yes I know asking for an explanation causes a lot more nasty voting. This is ridiculous, the site is getting more and more like reddit, and I blame the site's maintainers: There are soooo many things that could be done for a more civilized discussion culture. Like making votes public, meta-voting, requiring explanations for downvotes, a very small downvote pool (e.g. no more than three downvotes per day), etc.

How about somebody would tell me what exactly is missing from those tools I linked to, or what is supposed to be wrong that I wrote? It's not like I insulted anyone. The guy I responded to had a lot less substance in his (short) comments. "It's very superficial" - what is superficial? What is missing? Also, "all I want are two numbers at the end of the process. How long did this take and how much memory did this take." -- well, he gets those number with the DevTools! So what exactly is the complaint? For someone with a question he doesn't seem to try very hard to get an answer. Then someone downvotes posts that try to get more out of him.

Superficial as in all I want is the two numbers to be printed out at the end. Why do I have to go look at flame charts and timelines? Boggles the mind.

If you look at the documentation of what I am actually interested it is time-timeEnd or profile-profileEnd. With profile end I just don't get output on console and have to jump back and forth between these views looking at a ton of crap I am not interested in. With timeEnd I get the number I want but would like to see a "safe" approved way of where to place the timeend while dealing with async/promises/recursion separately and together.

I am used to testing different approaches within a function. Running the approaches overnight and just getting the 2 numbers printed out for each. Only if these deviate from expectations does the timeline and flamechart etc become useful. But Google debugging implementation seems to assume perf optimization is done in the opposite direction.

> With timeEnd I get the number I want but would like to see a "safe" approved way of where to place the timeend while dealing with async/promises/recursion separately and together.

Measuring asynchronous code? You are not measuring your code. Your code is only the synchronous parts, the time spent in asynchronous parts are "environmental factors". Your code doesn't run during those times, it sits in the event loop waiting for an event so that it can continue.

when doing micro benchmarks in JS you are likely to make the wrong conclutions because of JS engine optimizations for example removing code where the result is not used. the proper way to optimize is to identify bottlenecks and look at cpu and memory profile when running in production. then optimize the the code that would bring the most "bang for the bucks" likely to be found at the top of a flame graph. when doing the actual code optimizations remove unnecesary abstractions by inlining functions, use native objects, avoid memory, and preallocate/fixed buffers to get rid of GC stops by not creating new objects.

For benchmarking I use nanobench:

https://github.com/mafintosh/nanobench

For debugging llnode is super good:

https://github.com/nodejs/llnode

JavaScript TCO can't be feature detected so how do you know when tail calls are safe to use in front end or library code that can run on a variety of clients?

You don't. Assume you don't get it. Right now, chances are you don't get it anyway.

Which js implementations currently support TCO?

Javascriptcore (so all the webkits :) )

Reply on news.ycombinator.com