16
$\begingroup$

While programming, I often wonder what prevents languages from allowing arbitrary sized stack returns, like this:

/*special syntax, not valid C, N tells the language that the return type is dynamically sized */    
int[N] returnArbitrary(void) {
 // calculate the size
 int size = /*some complex calculation*/;
 int n[size];
 // do something with the data
 return n; // I know that this is not valid C,
}
// invocation
int test[size] = returnArbitrary(); // this would also set size to a correct value, thus internally returning two values, the size and the data
assert(size == 100);

What are the reasons for not allowing dynamically sized returns? Are there languages exposing stack allocation that do allow dynamically sized returns?

$\endgroup$
4
  • 3
    $\begingroup$ In your example as currently written, arbitrary-sized or constant-sized doesn't matter. In C, you shouldn't return a pointer to stack-allocated data, because that memory will be overwritten by later function calls. $\endgroup$ Dec 17, 2023 at 11:56
  • $\begingroup$ Thank you. Clarified it. $\endgroup$
    – user3394
    Dec 17, 2023 at 14:48
  • 1
    $\begingroup$ Maybe because copying arbitrary large objects is inherently inefficient (especially for nested function calls), despite of the fact that not every CPU architecture (not to talk about OS configurations) allows arbitrary large stack sizes. $\endgroup$
    – U. Windl
    Dec 17, 2023 at 22:05
  • 3
    $\begingroup$ The stack is also technically an implementation detail for a lot of languages. Some compilers, if they can figure out the static size of a dynamic allocation and if it is small, will allocate these structures on the stack. Also some languages do explicitly allow dynamic stack allocations -- see 'stackalloc' in C#. $\endgroup$
    – Chuu
    Dec 18, 2023 at 18:29

11 Answers 11

15
$\begingroup$

This would in principle be possible. It would require that the function communicates back both the data, and its size. It wouldn't quite work with the standard calling conventions, but we could easily come up with one that allows it.

The actual problem is that this would massively complicate everything that happens further down at the call site. For example, consider

int mainEasy() {
  int foo = 37;
  int testC = normalFunctionCall();
  int bar = foo + 1;
  return 0;
}

int mainHard() {
  int foo = 37;
  int testA[size] = returnArbitary();
  int bar = foo + 1;
  return 0;
}

Recall that machine code doesn't really have variables. All it has is addresses, and in case of local variables these have to be relative to the top of the stack. Well, that's ok for mainEasy, because the offset can be precomputed at compile time, thus you would find something like this in the executable for the bar = foo + 1 line: (x86-ish assembly)

...
mov eax, [esp + 8]  % load `foo` into register
add eax, 1          % `foo + 1`
push eax            % store as new variable `bar`
...

The + 8 has been hard-coded because the compiler knows there is only the one constant-size integer testC between the top of the stack and the location where foo was originally stored. (Could also be a constant-size array or whatever.) The CPU has an addressing mode built in for accessing a variable at a constant offset from some address in a register (in this case the stack pointer), so there's no real overhead here.

Not so with mainHard! In this case, the compiler doesn't know beforehand how much extra stuff the returnArbitrary call would put on the stack, so the machine code for foo + 1 would be way more complicated, like

...
mov ebx, [esp + 4]  % load `size` of `testA`
mov ecx, esp        % load stack pointer for doing address-arithmetic
mul ebx, 4          % calculate `size` in bytes
add ecx, ebx        % offset of the location before `testA`
mov eax, [ecx + 4]  % load `foo` into register
add eax, 1          % `foo + 1`
push eax            % store as new variable `bar`
...

Ok, for this example it's not too bad, and probably could be further simplified if you know your addressing modes. But the point stands that you would need to do these offset computations for every variable, and it gets more complicated the more variable-size variables you have. In other words, your executable size and runtime would scale quadratically with the number of variables in each function.

Could it be done? Yes. Would it be a good idea? Doubtful, though I wager modern compilers would be able to make it work pretty ok in practice, by cleverly adding "stepping stone" pointer variables or other tricks.

$\endgroup$
7
  • $\begingroup$ That would just be an alloca, though. $\endgroup$ Dec 18, 2023 at 7:20
  • 1
    $\begingroup$ @SimonRichter well, yes but I wouldn't say "just". alloca is not part of the C standard. Even if you're writing e.g. GCC-specific code, alloca makes it quite obvious that this is a nontrivial thing and you wouldn't use it without carefully considering that it's the right thing. On the other hand, as soon as something like "returning variable-size arrays" is supported by the language, programmers will tend to forget caution and use it everywhere. $\endgroup$ Dec 18, 2023 at 9:18
  • $\begingroup$ Couldn't the compiler allocate all variables whose size is statically known above all variables with runtime size? The program would still have to do the more complex address calculation for the dynamically sized data but static data is not affected by dynamically sized variables. $\endgroup$
    – chrysante
    Dec 18, 2023 at 10:02
  • 1
    $\begingroup$ In most C ABIs you have a constraint that the stack pointer register also serves as the stack allocation mark, so all valid objects must be at positive offsets from the stack pointer, and dynamic allocations must be made by subtracting from the stack pointer. As soon as you have dynamic allocations, this means that the statically allocated variables are at varying offsets from the stack pointer, so you need an additional register as the frame pointer. $\endgroup$ Dec 18, 2023 at 10:09
  • 1
    $\begingroup$ All of those are trivially bypassed though. The compiler can simply make each stack allocation a pointer, and then have the alloca and similar allocate after all stack variables. As long as it keeps track of where the "end" is, it doesn't even add much complexity to calling methods. $\endgroup$ Dec 19, 2023 at 22:26
8
$\begingroup$

You obviously can't return an object on the stack that's larger than the stack can get.

It is pretty easy to support returning objects of arbitrary size as long as you aren't too tightly bound to a traditional notion of what it means to "return it on the stack".

For example, C++ supports something called copy elision. In terms of the language itself, "copy elision" (aka return value optimization/named return value optimization) was originally a one-sentence permission from the standard saying an implementation is allowed to omit the copying the return value (under the right circumstances)--even if (as you can do in C++) the copying would normally have visible side effects (e.g., an overloaded copy ctor that prints something out when a copy happens). As of C++17, this was changed from permission to a requirement.

The implementation is pretty simple. Since you're (eventually) going to copy the data (e.g., array) from the callee back to the caller, the caller will normally have a place to put the result, so you just pass the callee a hidden pointer to the caller's object. The callee then writes directly to that location. In other words, bigObject foo() is effectively turned into void foo(bigObject *) (while maintaining return value syntax, so you calling code can still do things like while (x = foo()) ...). In the (presumably unusual) case that the caller doesn't actually try to store the returned object, you normally just allocate an object in the caller anyway, and pass a pointer to that hidden object.

$\endgroup$
3
  • $\begingroup$ But how would this work if the size of bigObject is dynamic, like the VLA in the question? The caller can't provide a space for the callee to put the result. $\endgroup$
    – Barmar
    Dec 17, 2023 at 22:18
  • $\begingroup$ If you need the callee to define the size of the object, then you would probably need to have the caller pass the return value as some kind of reference/pointer indirection, with the callee aware of how to reallocate its internal storage in a valid way. Such behaviour is unusual for "return values" in the traditional sense, though not illegal as long as the calling conventions agree on it. $\endgroup$
    – Miral
    Dec 18, 2023 at 5:14
  • 1
    $\begingroup$ Yup, this could be solved with a different calling convention, but stack size is still a concern -- there is an implicit assumption that objects on the stack are small, and that is pervasive through the operating system, for example Linux allocates stack pages on demand, but only as long as they are in reasonable distance from the last page allocated. $\endgroup$ Dec 18, 2023 at 7:36
5
$\begingroup$

Conceptually, this code is equivalent and compiles in C, even though it does invoke undefined behavior:

int* returnArbitary(void) {
 int size = /*some complex calculation*/;
 int *n = alloca(sizeof(int) * size);
 // do something with the data
 return n;
}

What would happen is that the space allocated by alloca() on stack may get overwritten if another function gets called. So you could design a language to allow this, but the returned data would only be accessible until the next function call, which is not very useful.

To extend the usefulness, you could make the compiler aware of any stack-allocated storage that is still in scope, and adjust the stack pointer accordingly. It would permit longer lifetime for stack allocated storage, but at the cost that all space between the current stack frame and the deepest stack allocation is kept reserved also.

Anything more fine-grained than that, and the stack allocation starts to look a lot like a heap manager, which is already available through malloc().

$\endgroup$
1
  • 10
    $\begingroup$ Returning an alloca pointer is generally unsafe, because the kernel can (and on Windows, actually does) clobber the unallocated portion of the stack (beyond the red zone) at any time with no warning. If you return an object larger than the red zone, or if the compiler optimizes stack manipulation in such a way that the returned variable is not within the red zone (or if your architecture has no red zone), then your data can be changed behind your back. $\endgroup$
    – Kevin
    Dec 17, 2023 at 19:20
3
$\begingroup$

Traditional C stack.

There are multiple issues with a traditional C stack.

First of all, its size is generally limited, and it cannot necessarily be extended:

  • Extension in-place may be blocked by a latter block of memory -- such as the stack of another thread.
  • Reallocating the stack would invalidate existing pointers.
  • Appending another stack segment -- creating a segmenting stack -- leads to performance issue around segment boundaries.

With typical stack sizes in the MB range (1MB on FreeBSD for example), it's very easy to run out of stack space while trying to use alloca.

There are, however, further difficulties with regard to performance:

  • As per @leftaroundabout's answer, the presence of a dynamic allocation worsens the access performance to "sibling" stack variables.
  • There are also difficulties in returning through multiple stack frames. Copying each time will cost an arm and a leg, not copying will create holes in the stack, etc...

Trade-offs must be made, and none are great.

What about another stack?

As mentioned by @fadedbee's Forth answer, Forth implementations may use two stacks.

Now, Forth is a bit exotic, but what about SafeStack? SafeStack is an implementation technique in Clang which uses two stacks to run a C or C++ program:

  • A safe stack: for bookkeeping and vetted values.
  • An unsafe stack: for non-vetted values.

The measured wall-clock performance overhead of SafeStack is < 1%, so performance impact is minimal.

This makes it clear that having two stacks is definitely possible, and therefore it's definitely possible to have:

  • A stack for statically sized variables.
  • A stack for dynamically sized variables.

But the multiple return juggling issue remain, even then. If two dynamically sized variables are created, and the second is returned, do you leave a hole? Or do you move it?

You can invent a "clever" strategy which only moves when the hole is at least as big as the variable -- to avoid copying a lot to save peanuts -- but it does mean you need to track where the holes are, and when they are extended, and then if your variable moves you better not have any pointer to it stored somewhere, ...

So, even with two stacks, things get a wee bit complicated, and it's not clear there's an optimal & transparent solution.

$\endgroup$
2
  • $\begingroup$ Thank you for your comment. I will further research those FORTH stacks and the possibility of completmenting the traditional C stack with a dynamic stack, a idea wich also has recently occured to me. $\endgroup$
    – user3394
    Dec 19, 2023 at 18:57
  • $\begingroup$ pointers to dynamically sized variables can be stored as a pointer to pointer, where the first one does not change, while the pointed one is the point into the movable object in your dynamic stack. the first one is returned to user code, while the changeable one is only known to compiler generated code of dynamic stack re-ordering mechanism. $\endgroup$
    – dEmigOd
    Dec 20, 2023 at 14:31
3
$\begingroup$

What prevents languages from having arbitrary sized return data on the stack?

The question implies that all languages disallow arbitrary sized return data on the stack.

This is not the case for Forth. It is normal for Forth "words" (similar to functions) to leave their return value on the stack from which they take their arguments.

e.g. the "+" word pops two arguments from the stack and pushes their sum onto the stack.

(Forth uses two stacks. A data stack, often referred to as "the stack" and a "return stack" which holds return addresses and is also used for temporary values.)

In Forth, you could push N unicode wide characters onto the data stack, followed by the count of characters. The caller could then pop the character count and the next N values. This is not the normal way of working in Forth, but you can return a runtime-sized number of words.


But is Forth's stack the stack (the one pointed to by esp/rsp), or just a stack? – Pablo H

sectorforth uses the hardware stack as the stack for arguments and return values.

https://github.com/cesarblum/sectorforth/blob/master/sectorforth.asm

Addition and NAND from Sector Forth:

    defword "+",PLUS
    pop bx
    pop ax
    add ax,bx
    push ax
    NEXT

    defword "nand",NAND
    pop bx
    pop ax
    and ax,bx
    not ax
    push ax
    NEXT

sectorforth also uses the x86 hardware stack for the return stack, by swapping sp before manipulating the return stack and restoring sp afterwards. e.g.

    defword "exit",EXIT
    xchg sp,bp              ; swap SP and BP, SP controls return stack
    pop si                  ; pop address to next word
    xchg sp,bp              ; restore SP and BP
    NEXT

@PabloH: Tying the notion of a stack to two specific x86 registers seems strange to me. I am running an OS written in C on an ARM CPU. Does that mean, my C doesn't have a stack? – Jörg W Mittag

Most CPU architectures have one hardware stack, which is implicitly used by push and pop instructions.

(I'm not an ARM expert, so please correct me.) In ARM architecture, you are free to use whichever registers you like as a stack pointer, but there are PUSH and POP aliases for storing to and loading from the address in the sp register, while adjusting sp in the correct sequence:

PUSH {r2}
POP {r2}

are aliases for:

str r2, [sp, #-4]!
ldr r2, [sp], #4
$\endgroup$
10
  • 2
    $\begingroup$ But is Forth's stack the stack (the one pointed to by esp/rsp), or just a stack? $\endgroup$
    – Pablo H
    Dec 18, 2023 at 16:48
  • 1
    $\begingroup$ Implementers of Forth are free to do what they like, but using the hardware stack often makes sense. (See my update on sectorforth, above.) $\endgroup$
    – fadedbee
    Dec 18, 2023 at 21:55
  • 2
    $\begingroup$ @PabloH: Tying the notion of a stack to two specific x86 registers seems strange to me. I am running an OS written in C on an ARM CPU. Does that mean, my C doesn't have a stack? $\endgroup$ Dec 18, 2023 at 21:59
  • 1
    $\begingroup$ It's worth emphasizing Forth's unusual characteristic of having separate data stack and return stack, which is what decouples stack-passing/returning from program flow and intrinsicaly allows an arbitrary (and potentially runtime-variable) number of arguments and return values to be passed. $\endgroup$
    – Matthijs
    Dec 19, 2023 at 0:20
  • 2
    $\begingroup$ @Matthijs What you’re describing is a case the answer could make, but it doesn’t. As written, it doesn’t address the question. In fact, it only ever even refers to a return value singular, gives as the only example a fixed-arity function that consumes two arguments and returns one result, and doesn’t ever approach the idea of dynamically-sized values; it simply is not an answer to this question, although it certainly could make for a sort of frame challenge about the limited conception of stack the question assumes. Currently it’s just an introduction to stack-based language evaluation. $\endgroup$
    – Michael Homer
    Dec 19, 2023 at 6:13
1
$\begingroup$

As others have pointed out, storage for function return values is usually provided by the caller, as it simplifies calling sequences. If the size of the return value is determined dynamically by the callee, this method can't be used.

Given existing calling sequences, you'd probably have to implement it something like:

struct returnArray {
    size_t size;
    void *data;
}

returnArray foo() {
    returnArray retval;
    ...
    // int a[n]; return a;
    retval.size = n * sizeof *a;
    retval.data = malloc(retval.size);
    memcpy(retval.data, a, retval.size);
    return retval;
}

// test = foo();
returnArray ra = foo();
int test[ra.size/sizeof *test];
memcpy(test, ra.data, ra.size);
free(ra.data);

So it requires a dynamic allocation and copying into and out of that memory block. Since it's easy enough to just return dynamically-allocated memory and hand off responsibility, this overhead seems prohibitive.

And in object-oriented languages you can just return a reference to an object that contains a pointer to variable-length data, so this issue doesn't come up.

$\endgroup$
1
$\begingroup$

I believe this is roughly equivalent: instead of returning the arbitrary-sized value, the function takes a reference to it and writes it, then the caller allocates the value on the stack within its own frame. The only caveat is that the value's size, though dynamic, needs to be computed separately and gets exposed to the caller.

size_t calculateArbitrarySize(void) {
    return ...
}

void returnArbitrary(size_t arbitrarySize, int* arbitraryData) {
    arbitraryData[0] = ...
    ...
}

// Usage
int main(void) {
    size_t size = calculateArbitrarySize();
    int* data = alloca(size);
    returnArbitrary(data);
    ...
}

This version is also more flexible, because by simply changing alloca to malloc, you can run the exact same computations but allocate the arbitrary data on the heap instead. Or you can reserve some fixed amount of global memory, assert that arbitrarySize is less than whatever you reserved, and store the data there.

$\endgroup$
1
  • 2
    $\begingroup$ Yes. It's not suitable for all use cases though: the calculation of the size and content of the array may well be intertwined, and running them separately could be impossible or at least wasteful. $\endgroup$ Dec 18, 2023 at 9:20
0
$\begingroup$

There are multiple issues with your example.

First of all, the result type should be either int[size] or struct { int N, int[N] }. Based on your choice you should look into either the dependent types direction or the structural subtyping direction.

Second, your invocation, the way you do it, declares two different local variables and uses an assignment to do it. If we would follow that idea literally, it would mean that returnArbitrary creates the result and it is then copied on return. Such copy is, generally speaking, a lot more expensive than passing pointers to heap-managed resources. Especially if you have a larger codebase and a lot of function decomposition on your operations.

Third, languages that would be candidates for allowing these features usually do not have the required constness for the example to result in correct code in practice. Languages with such semantics usually box everything and consider not boxing everything as optimization.

Fourth, you need a stack management protocol that allows you to manage such types. If you think about it, the variable declaration int n[size] should be at the position of your result. Unless you have an invocation on that very n in do something. If it is conditional, it is no longer clear how to do stack layout. If you start to copy things around, you are again inferior to heap-managed. If you pass the variable declaration from outside, you cannot have zero-allocation semantics, which might not be a drawback.

If you really want a list of languages allowing some of these interpretations you should ask separate questions with clarified semantics based on this one.

Note: after the recent change of the question, only third and fourth points seem still to be valid. This answer should be cleaned up after the question has stabilized.

$\endgroup$
2
  • $\begingroup$ Thank you for your input. I added some clarification. $\endgroup$
    – user3394
    Dec 17, 2023 at 14:51
  • 1
    $\begingroup$ @thejack Your change partially invalidated my answer. I think you should revert it and ask a different question instead. $\endgroup$
    – feldentm
    Dec 17, 2023 at 16:54
0
$\begingroup$

Nothing at all prevents languages from returning arbitrary-sized data on the stack, to the extent the operating system allows.

If you are asking whether the size must be known at compile time instead of being determined only at run time (something that C is demanding), I suppose that such compilers are easier to build.

$\endgroup$
0
$\begingroup$

In order for the ability to have a function allocate a variable-sized chunk of storage on the stack to be useful (whether the storage is "returned" or not), two conditions must both apply:

  1. There must be enough stack space to handle whatever sizes of allocations will occur on each function call.

  2. There must not be enough stack space to handle maximum-size allocations on each function call.

Although some tasks might benefit from having a function that work with small objects even when stack space is scarce, but also handle very large objects when stack space was plentiful, in most cases having a common function which receives a pointer to the storage where it should place results, along with a wrapper which stack-allocates a small fixed-sized buffer and passes it to that function, and another which stack-allocated a bigger fixed-sized buffer, would be cheaper than trying to have a function return a variable-sized buffer.

$\endgroup$
5
  • $\begingroup$ Whether it's cheaper depends a lot on the use case. Sure, if your goal is to fill a global struct, passing in a pointer to the function saves you a copy. But if you simply want to use the created value, for example in nested expressions, constructing the value directly in the "returned" stack memory is hard to beat and much simpler. Modern features like move semantics and copy elision invalidate some classic paradigms. As a bonus, pure functions lend themselves better to parallelization. $\endgroup$ Dec 20, 2023 at 14:57
  • $\begingroup$ @Peter-ReinstateMonica: Returns of a fixed-sized object is often best handled by having the recipient create space and pass a pointer to it. If all return statements in a function use the same object ret and its address doesn't leak through language semantics, the compiler can replace references to ret with (*passedPointer), and process ret = functionReturningFoo by passing through the address. Such techniques don't work with objects whose size isn't known in advance to the caller. $\endgroup$
    – supercat
    Dec 20, 2023 at 18:52
  • $\begingroup$ @Peter-ReinstateMonica: In a language like Java (or JVM bytecode) which lacks a reference-to-storage-of-possibly-automatic-duration type, allowing a function to specify that it returns more than one primitive object or reference might be an easier way of supporting multi-value returns than adding support for the aformentioned kind of reference, but even there the benefits of allowing a function to return an amount of information that isn't known in advance would seem limited. $\endgroup$
    – supercat
    Dec 20, 2023 at 18:57
  • $\begingroup$ @Peter-ReinstateMonica: Incidentally, I would think it would be useful for an ABI to functions that return objects by value export two endpoints, one of which could be used for foo = func(); only in cases where ret's address has never been leaked to the outside world, but which would be allowed to use the storage at arbitrary times during function execution, and one of which could be used even if the passed address has leaked because the called function wouldn't use the address except as the destination for a concluding copy operation. A compiler generating code for a function that... $\endgroup$
    – supercat
    Dec 20, 2023 at 19:03
  • $\begingroup$ ...would benefit from being able to modify the return-value object during execution could make the second entry point identify a wrapper that would create space for the return value, invoke the first version using that as the return-value address, copy that space to the outer function's buffer, and return. This would result in temporary storage for a "working copy" of the reutrn value being created only when doing so would be useful. $\endgroup$
    – supercat
    Dec 20, 2023 at 19:05
-1
$\begingroup$

What prevents languages from having arbitrary sized return data on the stack?

Nothing in particular, other than design choices, and dominating (or domineering) platform ABI. It's easy to implement.

$\endgroup$
1
  • $\begingroup$ Welcome to the site. This question already has a lot of answers - how is yours different from this one? $\endgroup$
    – kaya3
    Feb 7 at 19:57

You must log in to answer this question.