Transcript from the "Optimization: Tail Calls" Lesson
>> 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: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: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: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:08:52] They're dramatically different ways of approaching those fine level memory optimizations and things.