2
$\begingroup$

I was wondering, given the usual stack memory functioning, whether it is possible for an array like primitive type allowed to grow in size to exist.
The functioning of such primitive type is as follows.

  • Any one function is allowed to have only one such primitive variable.
  • Appending to such primitive variable is allowed only within the function that it was initialized in.
  • If the function that such primitive variable was initialize in is not the last in the stack, such primitive variable is not allowed to grow in size.

enter image description here

I was wondering whether:

  • Such primitive type is theoretically possible.
  • Whether it is something that is already in use.
$\endgroup$
4
$\begingroup$

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication.

First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your existing array elements down to the new array position every time you enlarge the array.

After that, it is really a linguistic question. In assembler you can obviously do it, because you can do anything in assembler. Whenever you want your array to be n bytes bigger, just subtract n from the stack pointer.

In C there is often a function - disapproved of by all respectable computer scientists and therefore very useful when it is useful - called alloca or _alloca - which allocates n bytes of data on the stack and returns a pointer to the new allocation. I would be very surprised if two consecutive alloca calls did not just allocate contiguous stack space, so although there isn't a realloca function, you could effectively simulate its behaviour.

Where life gets interesting is when the compiler decides to use the stack for its own purposes: for instance, it might precompute the arguments for several function calls and push them all onto the stack before calling any of the functions. Usually such compilers notice a call to alloca and disable optimisations in the function that uses it - this is one of the reasons for disapproving of alloca.

The main difficulty you would run into would be that, if you wanted your array indices to be "the right way up" - a[0], a[1], a[2] and so on - then every reallocation would require data to be moved, which is a bore. And you can't write your own function in C to do this (that is, both the extra stack allocation and the data movement) because when you call a function, you usually push a return address onto the stack, so the stack-based array is (as you showed in your pictures) blocked by that extra piece of data and can't be enlarged. You would have to write a special realloca function in assembler which pops the return address and keeps it safe; subtracts an appropriate amount from the stack pointer; pushes the return address again; and then does the necessary memory movement. It would actually be quite fun to implement, though not at all portable because different systems will use the stack in different ways in a function call.


Is it used? Yes, I have used alloca for things I know to be small, because I love not having to rampage all over the heap and I love not having to deallocate. But your more elaborate scheme - I haven't heard of anyone who has done it.

Except in assembler - where one can do a beautiful merge sort by using the stack to store data.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very interesting! I did not know of the existence of the function alloca. Researching a bit more, I did not find types where there is a dynamic growth in the allocated memory. However, I found that stack allocated dynamic size array are implemented also in Rust, with the feature unsized-locals. $\endgroup$ – Andrea Nardi Jul 19 '19 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.