Why did C never implement "stack extension"?

Question

Why did C never implement "stack extension" to allow (dynamically-sized) stack variables of a callee function to be referenced from the caller?

This could work by extending the caller's stack frame to include the "dynamically-returned" variables from the callee's stack frame. (You could, but shouldn't, implement this with alloca from the caller - it may not survive optimisation.)

e.g. If I wanted to return the dynamically-size string "e", the implementation could be:

--+---+-----+
  | a |  b  |
--+---+-----+

callee(d);

--+---+-----+---------+---+
  | a |  b  |  junk   | d |    
--+---+-----+---------+---+

char e[calculated_size];

--+---+-----+---------+---+---------+
  | a |  b  |  junk   | d |    e    |    
--+---+-----+---------+---+---------+

dynamic_return e;

--+---+-----+-------------+---------+
  | a |  b  |    waste    |    e    |
--+---+-----+-------------+---------+

("Junk" contains the return address and other system-specific metadata which is invisible to the program.)

This would waste a little stack space, when used.

The up-side is a simplification of string processing, and any other functions which have to currently malloc ram, return pointers and hope that the caller remembers to free at the right time.

Obviously, there is no point in added such a feature to C at this stage of its life, I'm just interested in why this wasn't a good idea.

That would be inefficient. Everything is a tradeoff - when you are getting some improvement in one side - then check the other side which is going slower. And yes this is note from an implementor. Standard doesn't use the word stack. — user2736738, Jan 16 '18 at 10:41
The reason would be because there is no such thing as a "stack" in the C programming language. — Lundin, Jan 16 '18 at 10:41
@Lundin Are there any important "stackless" C implementations? — fadedbee, Jan 16 '18 at 10:46
Yeah, there are a few. As an example Freescale/NXP RS08 had no stack but was supported by C compilers. Anyway my point here is that it is not the purpose of the C standard to dictate the format of stack frames and calling conventions. That is beyond the scope of a programming language standard. — Lundin, Jan 16 '18 at 10:49
Among all the great things that could've been implemented in C this one is probably rather irrelevant. — user7860670, Jan 16 '18 at 10:49
[Are there stackless or heapless implementation of C++?](https://stackoverflow.com/q/10900885/995714), https://en.wikipedia.org/wiki/Stackless_Python — phuclv, Jan 16 '18 at 12:52

score 3 · Accepted Answer · answered Jan 16 '18 at 13:11

A new object may be returned through many layers of software. So the wasted space may be that from dozens or even hundreds of function calls.

Consider also a routine that performs some iterative task. In each iteration, it gets some newly allocated object from a subroutine, which it inserts into a linked list or other data structure. Such iterative tasks may repeat for hundreds, thousands, or millions of iterations. The stack will overflow with wasted space.

JeremyP · Answer 2 · 2018-01-16T11:24:15.910

2

Some objections to your idea. Some have been mentioned already in comments. Some come from the top of my head.

C doesn't have stacks or stack frames. C simply defines scopes and their life times and it is left to implementations as to how to implement the standard. Stacks and stack frames are really just the most popular way to implement some C semantics.
C doesn't have strings. C doesn't really have arrays as such. Well, it does have arrays, but as soon as you mention an array in an expression (e.g. a return expression), the array decays to a pointer to its first element. Returning a "string" or an array on the stack would involve significant impact on well established areas of the language.
C does have structs. However, you can already return a struct. I can't tell you how its done, because it is an implementation detail.
A problem with your specific implementation is that the caller has to know how big the "waste" is. Don't forget that the waste will include the stack frame of the callee but also the waste from any functions the callee calls either directly or indirectly. The returning convention will have to include information on the size of the waste and a pointer to the return value.
Stacks, as a rule, are quite limited compared to heap memory, particularly in applications that use threading. At some point the caller will need to move the returned array down into its own stack frame. If the array was merely a pointer to storage in the heap, this would be much more efficient, but then you've got the existing model.

edited Jan 16 '18 at 11:24

answered Jan 16 '18 at 11:18

JeremyP

84,577
15
123
161

Some compilers might be able to optimize to the point of removing any stack (for instance, by inlining every function at link-time optimization time). – Basile Starynkevitch Jan 16 '18 at 11:27
@BasileStarynkevitch Yes. I think that is covered in my first point. There isn't necessarily a stack. – JeremyP Jan 16 '18 at 11:33
Probably, but the OP might not have thought about that. – Basile Starynkevitch Jan 16 '18 at 11:35
"C doesn't really have arrays as such": Sorry, but this is completely wrong. C does have arrays, arrays can be allocated statically, automatically, be part of `struct`s, or even elements of arrays. C knows and handles types like `int (*)[n][m]`. The array-pointer-decay is just the mechanic C uses to *access* array elements, to pass arrays around as if by reference, and to create multidimensional arrays as the special case of arrays containing arrays as elements. – cmaster - reinstate monica Jan 16 '18 at 13:31
@cmaster Please read the whole paragraph instead of quote mining the first seven words. There's no "just" about the array-pointer decay mechanic. It is central to the way C models arrays. It is exactly why you can't pass an array as a parameter or (relevant to this question) return one. – JeremyP Jan 16 '18 at 14:04
"C doesn't have strings", what is this non sense, please read the standard, C got string. – Stargateur Jan 16 '18 at 15:34
@Stargateur sorry. C does not have strings. It has pointers to null terminated arrays of characters. These are not strings in any proper sense of the word. – JeremyP Jan 16 '18 at 17:14

cmaster - reinstate monica · Answer 3 · 2018-01-16T14:35:38.810

You have to realize, that the implementation of the stack is strongly dictated by the CPU and the OS kernel. The language does not have much say in this. Limitiations are, for instance:

The ret instruction of the X86 architecture expects the return address at the memory location stored in the stack pointer. Thus, there cannot be anything else on top (semantical top - usually this is the lowest address, as stacks tend to grow down). You could work around this, of course, but that would likely incur additional overheads which C programmers are not going to be willing to pay.
The stack pointer defines what part of the allocated stack memory is actually used. When control flow is changed asynchronously (hardware interrupt), the current CPU's registers are generally immediately stored to memory addresses below the stack pointer by the interrupt handler. This can happen at any time, even throughout most of the kernel code. Any data stored below the place where the stack pointer point to would be clobbered by this. (Well, technically, that's not fully correct, there is generally a "red zone" below the stack pointer to which the interrupt handlers may not write any data. But here we are getting very firmly into architectural design peculiarities.)
Destroying a stack frame is generally a single addition of a constant to the stack pointer. This is the fastest kind of instruction you can get, it will generally not require a single cycle to execute (it will execute in parallel to some memory access). If the stack frame has a dynamic size, the stack frame must be destroyed by loading the stack pointer from memory, and for that a base pointer must have been retained. That's a memory access with a significant latency, and another register that must be saved to be used. Again, this is overhead that's generally unnecessary.

Your proposal would definitely be implementable, but it would require some workarounds. And these workarounds would generally cost performance. Small bits of performance, but definitely measurable amounts. That's not what compiler/kernel developers want, and for good reason.

"the X86 architecture expects the return address at the top of the stack" ... "Any data stored below the stack pointer would be clobbered by this" It is worth pointing out that in x86 and most other modern architectures, the stack grows downwards. The top of the stack is at the lowest in use address of the stack. Data stored below the stack pointer (in memory) is technically not on the stack and in danger of being clobbered because interrupt routines move the stack pointer down through memory to make room for the registers. — JeremyP, Jan 16 '18 at 14:17
@JeremyP Good catch. I have updated my answer now to be more precise on this. Thanks. — cmaster - reinstate monica, Jan 16 '18 at 14:36
I wouldn't describe it as a catch, only a minor clarification of a good answer. — JeremyP, Jan 16 '18 at 17:15

Why did C never implement "stack extension"?

3 Answers3

Linked