1

Most languages does support variable length arrays on the heap but I've heard that those can be stored on the stack too. I'm curios what languages support this construct, some examples and how are they implemented?

I would prefer examples from modern languages as I don't want to code in legacy (like 'C', etc.).

4
  • What do you mean by legacy? – Giorgio Apr 19 '15 at 11:03
  • I mean that I want to use newer languages. – Cplusminus_is_coming Apr 19 '15 at 11:04
  • 4
    Newer is a bit fuzzy. Most mainstream languages are at least 10 to 20 years old. – Giorgio Apr 19 '15 at 11:10
  • 4
    Why do you care where your arrays are allocated? – Telastyn Apr 19 '15 at 12:49
12

The term "variable-length array" is actually specific to C, but it sounds like you're mostly interested in dynamic stack allocation. To review, VLAs are a feature added in C99 (then made optional in C11) which allow an array to be declared with a size not known until runtime. This means that the language must allocate space at runtime once it knows what the size is. It is not specified whether this runtime allocation is done on the heap or the stack. GCC happens to use the stack, but that's not required.

So from a language-lawyer point of view, the correct answer is probably "no language does" because I'm not aware of any standard feature in any language that must be implemented via stack allocation. From a practical point of view, I'm under the impression this is a very C-specific feature (many people see this as a standard replacement for the alloca() function), and dynamic stack allocation isn't generally viewed as a very appealing or desirable feature for other languages, partly because it's very easy to blow out the stack with it, it adds yet another complication to memory management, and there's not much of a need to have it in the first place.

If you're primarily interested in "modern" languages, a lot of those are garbage collected nowadays, so whether heap/stack/static/cloud/aether allocation is being used is an implementation detail you should (almost) never have to think about. I don't believe any of Rust, Go or Swift have explicit stack allocation either (even the ones that allow an array's size to be unknown until runtime also seem to treat that array more like a std::vector than a "raw" array).

4

On top of lxrec's nice answer, there's no such thing as a variable-length stack contiguous array of the kind I think you're talking about since they'd be too impractical. There are VLAs in C which can allocate the sufficient amount of space on the stack based on a size determined at runtime, but they're not resizable, variable-sized containers of the kind I imagine you have in mind.

It's not really practical to have resizable contiguous data structures using the stack, since that would render it no longer a stack. If you allocated a big array on the stack and then tried to realloc and shrink it to a smaller size, what's the stack going to do with that if there's data being stored at the end of the array (say from stack spills)? And how is it going to make room if the array grows?

All of these questions lead towards something a lot more complicated than a stack and ultimately defeat the purpose of the stack which has the appeal of just pushing data and popping it off in a symmetrical fashion. A stack based linked structure, like a free list using a limited amount of maximum space (maybe using the heap after it runs out), might be more feasible than one which aims to be resizable and perfectly contiguous.

You could probably get really fancy and design metal-scraping languages around that idea, but the structure would not be a perfectly contiguous one living on the stack if it can grow beyond a certain size. At the very least it would have to become split into two blocks (one on stack, one on heap) or move entirely to the heap after that point.

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.