Why does allowing for recursion make C slower/inefficient on 8-bit CPUs

user_1730895 0
Viewed 86

Answers to this question about compiler efficiency for 8-bit CPUs seem to imply that allowing for recursion makes the C language inefficient on these architectures. I don't understand how recursive function calling (of the same function) is different from just repeated function calling of various functions.

I would like to understand why this is so (or why seemingly learned people think it is). I could guess that maybe these architectures just don't have the stack-space, or perhaps the push/pop is inefficient - but these are just guesses.

8-bit recursion c
1 Answers

Because to efficiently implement the C stack, you need the ability to efficiently load and store to arbitrary offsets within the current frame. For example, the 8086 processor provided the indexed and based address modes, that allowed loading a stack variable within a single instruction. With the 6502, you can only do this with the X or Y register, and since those are the only general purpose registers, reserving one for a data stack pointer is extremely costly. The Z80 can do this with its IX or IY registers, but not the stack pointer register. However, indexed load instructions on the Z80 take a long time to execute, so it is still costly, along with the fact you either reserve a second register for the stack pointer, or have to load the stack pointer from the SP register any time you want to access variables.

By comparison, if recursive calls are not supported, then a second instance of the function can not start inside a call whilst an existing is still in progress. This means only a single set of variables is needed at a time and you can just allocate each function its own static piece of memory to use for variables. Since the memory has a fixed location, you can then use fixed address loads. Some implementations of fortran used this approach.

user_19371980
Related