Timeline for How do function inlining and Tail Call Optimization affect call stack?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2023 at 16:59 | comment | added | gnasher729 | Now if Bs and Cs stack frame are not identical then the compiler might know that C can happily live with a stack frame that is too large, or B might be able to make its stack frame larger quite easily. If B and C are not the same function then this saves a few nanoseconds. If they are the same function then it’s called tail recursion. In that case since B knows it’s own code some optimisations might be possible. | |
| Sep 30, 2023 at 16:53 | comment | added | gnasher729 | @b3rry Assume C has been compiled like any ordinary function: Build stack frame, do your job, remove stack frame, return. The same for B. Except the very last thing B does is to call C, wait for it to return, remove B’s stack frame, return. At that point B has built its own stack frame. So instead of calling C, B jumps into C after The point where C builds its stack frame. So C reuses B’s stack frame without knowing, and at the end removed Bs stack frame and returns straight to Bs caller. | |
| Sep 29, 2023 at 0:11 | comment | added | Erik Eidt | If we know that B is calling B (the recursive case), then we know that the outer B creates a stack frame that is of exactly the right size for even the inner (recursive, next) B. So, no adjustment necessarily need be made when B calls B, and some overhead can then be bypassed. | |
| Sep 29, 2023 at 0:07 | comment | added | Erik Eidt | Depends on the calling convention and the function, but modern processors have 16-32 registers, and their entire execution context may fit therein, including parameters. | |
| Sep 28, 2023 at 23:35 | comment | added | b3rry | " if B/C needs a stack frame, then it might skip setting up the frame and tearing it down, transferring control not to the beginning of B/C but just past setup of a frame, since part of that has already been done by the outer invocation" - can't understand that :( could you please elaborate? Or share an article or a video about this mechanism so I can learn more about how this works? | |
| Sep 28, 2023 at 23:31 | comment | added | b3rry | "With TCO, it is possible that B didn't even need a stack frame in the first place" - but what about execution context of function B? Where are function arguments (for example) stored if no stack frame (SF) is created for B? I've never heard about skipping creation of a SF. I thought there were 2 technics of reducing the amount of SFs: 1) when the next function reuses the SF of the previous function 2) removing the previous SF before creating a new SF for the next function, so call stack always has the same amount of SFs, i.e. AB->AC->AD->AE where B, C, D and E are recursive functions | |
| Sep 27, 2023 at 17:53 | vote | accept | b3rry | ||
| Sep 27, 2023 at 11:36 | comment | added | Erik Eidt | Wikipedia is a good resource, for example, en.wikipedia.org/wiki/Tail_call. In some cases, what one needs to do is learn terminology to more effectively search for articles and videos on Wikipedia and beyond. At the very end of that Wikipedia page, there is a box labeled "Categories:" , which allows navigation to other similar content. For example, the first item is en.wikipedia.org/wiki/… | |
| Sep 27, 2023 at 11:30 | comment | added | Erik Eidt | In the case of recursion, B and C are the same function. Further optimizations may be possible knowing that, for example, if B/C needs a stack frame, then it might skip setting up the frame and tearing it down, transferring control not to the beginning of B/C but just past setup of a frame, since part of that has already been done by the outer invocation. | |
| Sep 27, 2023 at 11:28 | comment | added | Erik Eidt | The principle of TCO is that, when A calls B, and B calls C, which returns to B, which returns to A, that B erases itself and transfers to C — instead of calling C. C then returns directly to A instead, since B has been effectively erased. With TCO, it is possible that B didn't even need a stack frame in the first place (but it would have needed one without TCO). | |
| Sep 27, 2023 at 10:16 | comment | added | b3rry | 3) Where can I get more information about all those things you mentioned in your answer? Books, courses, youtube videos? I'm really interested in what happens under the hood when I run my program. And I want to learn more about such things. Low-level concepts are not often discussed so I discover them only when I acidentally come across them on the internet (like the post about function inlining I mentioned in my question). Maybe I should take a look at some low-level programming languages? And is the Dragon Book a good source? | |
| Sep 27, 2023 at 10:08 | comment | added | b3rry | wow! Thanks for such a detailed answer! But I have a few more questions. 1) In case of recursion every recursively called function needs a stack frame of the same size. But you mentioned that recursion is not required for TCO. But there's a very small chance that a function called at the very end of a caller would need a stack frame of a size the caller needed. How does re-using the same stack frame works in this case? 2) With TCO, if (for some reason) a recursive function does not have a base case it doesn't necessarily mean that a stack overflow would occur, right? | |
| Sep 27, 2023 at 9:52 | vote | accept | b3rry | ||
| Sep 27, 2023 at 9:52 | |||||
| Sep 27, 2023 at 0:12 | history | answered | Erik Eidt | CC BY-SA 4.0 |