Optimization: Tail Calls

[00:00:00]
>> Kyle Simpson: And the way to address it that they invented back then, it has been this time on an approach ever since, is an optimization called tail calls. To understand what a tale call is and how until call works we need to understand when we make this recursive call here, the call on line four, we need to understand why the stack frame that is currently executing needs to be cupped.

[00:00:25]
What is it about that stack frame that still needs to be cupped around? And in particular the reason why that stack frame needs to be cupped is because we are doing that first addition, the addition of the return result, after the function completes. So it's essentially that part of the program that's requiring our current stack frame to be around.

[00:00:48]
But if there was no more work to do, if we literally just said return count vowels, and there was nothing before or after that, it just called the function and it was done. Then we could think at least in theory that it seems like the current stack frame isn't needed anymore.

[00:01:06]
We've done all of our work in our current stack frame and we're gonna dispatch to another function call. And so why don't we just maybe throw away the current stack frame or just reuse the existing stack frame for the next function call, you follow me? That's the idea here, behind tail calls.

[00:01:24]
If a function call happens in a position which is referred to as a tail call, meaning it's at the tail of the execution logic, it's at the very end of that function's logic. Then we don't need the existing stack frame anymore and we can essentially dispatch to another function call and not take up any extra net memory, which means that function A can call B, can call C, can call D.

[00:01:51]
If all of those calls happen in a tail position, then we've only ever needed one stack frame in memory, at any given time. We don't have this run away of O of N memory usage where every function call has taken up a new section of memory. And it's an implementation detail, whether we create a new one and throw the old one away, or whether we reuse.

[00:02:13]
It's different under different situations, but the general idea is at any given time, you should basically only need one stack frame. That only holds for function calls that have happened in a tail position. Now, this is an optimization in the bigger sense of optimization. It's not actually a performance optimization, it's not actually faster.

[00:02:36]
In some cases, it might actually be slower to do what we're talking about. So when people say optimization, they usually jump to thinking, well this is a performance, it's gonna go faster. It's not necessarily gonna go faster, and in some particular cases, might actually go slower. But it's an optimization in the bigger sense, because we're optimizing memory usage.

[00:02:56]
We're saying, let's not have runaway memory usage unnecessarily. Let's not keep all those stack frames that aren't needed anyway. Let's run in essentially fixed memory space, 0 of 1 memory usage instead of 0 of n, okay. And it's important to understand that tail calls are an additional feature that the system, your language, your compiler, your runtime, has to support.

[00:03:20]
You don't get it for free. So you would wonder then, well, what about JavaScript? Does JavaScript have this? And for literally decades people have been calling for JavaScript to have this tail call support, this memory optimization so that recursion doesn't need to throw this error that says range error out of memory.

[00:03:42]
And by the way, a little side note on the range error issue, that range error Stack Overflow exceeded or whatever that error is there not because you ran out of memory. A lot of people think that's what's happening. It's not an out of memory error. If you've ever had an out of memory condition in a web app, I guarantee you that what you saw was, at a minimum, the browser crashed.

[00:04:04]
And if it wasn't the browser that crashed, the whole device crashed. Anybody ever have your mobile phone just like shut itself off and restart? How's that even possible to just be clicking around on Facebook and all of a sudden my phone restarts itself? Congratulations, that was an out of memory error.

[00:04:18]
Almost certainly, that's what happens when the system completely runs out of memory. It just throws its hands in the air and says start over, right? Just restart the device, cuz I am completely out of memory. And JavaScript knows that that's a really terrible idea to allow JavaScript programs to run the device out of memory.

[00:04:35]
Because it's a very clear sort of denial of service attack vector for somebody to run some infinite loop on a page and kill people's devices, okay? So because we know that's a terrible idea, JavaScript, essentially from the beginning, has had a check in place that has said, let's not run so far that we are going to definitely eventually run out of memory.

[00:04:57]
And that heuristic that decision metric for how does it know if it's going to run out of memory is more complex than you might have expected. It used to be really, really simple. So this is actually true, back in IE6, there was a fixed limit for the number of function calls that could happen and that limit would in succession.

[00:05:18]
This doesn't mean total functions ever executed, it means in a chain or one it's called the other. The total stack depth was limited to 13. I don't have any idea where they came up with that number but if you ever had a situation where you call to that 14th call and a chain of function calls, you would get the range error in IE6.

[00:05:37]
Somehow, someway, they thought 13, maybe they had a heuristic that said nobody ever goes over 13 and if they do, it's almost always recursive, I don't know. But, anyway, it was limited to 13, which is ridiculous, right? That's ridiculously low because that's probably less than 100 K of memory, way probably less than 100 k of memory.

[00:05:56]
So how many function calls should it allow? This is a weird prediction because it's essentially the engine needing to say this looks like you're probably gonna run them out of memory. You can't actually know if the recursion is just about to finish. There's no way for the system to predict that.

[00:06:14]
So it's gotta run basically a heuristic and say, I think this looks like you're running a lot of memory and you're probably gonna run the system out of memory so I'm just going to stop you. That's the heuristic, and it's more complex than you might realize. Luckily, today, in modern browsers, it is much more sophisticated, the way they decide this stuff.

[00:06:33]
I don't know exactly how they work. I don't know if it's monitoring the amount of available RAM at any given point or something. But in my general testing, I've seen somewhere around 20,000 in the VA JavaScript engine on my Chrome instance. I don't know if it's different for VAD on different devices or whatever.

[00:06:50]
But I've basically been able to get up to about 20,000 stacked up before I generally see that Ranger, sometimes 21,000 it's somewhere in that range. So your mileage literally may vary there, you may have different results when you run it. But it's pretty easy to set up a test, just write a recursive function that it just prints out an eye and then increments and see how many I's print out, that sort of thing.

[00:07:12]
So the good news is that actually well on the topic of writing yourself a test, just putting in a try catch so that you can see how how big I was whenever the exception was strong. But anyway the point is there is some sort of limit and it's going to be different based upon the environment that you are running in.

[00:07:29]
Based upon the device, based upon the browser all of those things, those are not things that you can predict or control. So that is what ups this ante for saying we need to have JavaScript support in this idea of telcalls. And it has never done that, it has never gone to that level, and one of the reasons historically for not having that is because the idea of requiring tail calls was almost antithetical to the way the JavaScript specification was written.

[00:07:58]
I don't really mean antithetical, but the specification is really deliberately designed to be as agnostic about implementation details as possible. It says, this is the final outcome that should happen, and it does specify algorithms for how you should, you know, go about accomplishing things. But if the end goal of any operation is preserved, the JavaScript engines, and there are many, There are fewer and fewer each day, but there are many out there.

[00:08:26]
The JavaScript engines are allowed to decide, we're gonna cut this corner and have this effect. As long as we're spec compliant We have a lot of leeway to do different sorts of optimizations, to address things. So the shocker a JavaScript engine for Microsoft back when they were running that did things dramatically differently for the Windows operating system than say the chrome V8 was was doing on the Mako OS architecture, right?

[00:08:52]
They're dramatically different ways of approaching those fine level memory optimizations and things.