Legitimate Use of Variable Length Arrays | Hacker News Reader

Legitimate Use of Variable Length Arrays

nullprogram.com

41 pointsweinzierl24 comments

I ran into a great alloca bug back in the early days, think 2001 of OS X.

Used alloca to allocate a string on the stack. Depending on the size of the string the colours on the dialog would either look normal or have a rainbow like colour.

Turns out that alloca allocated the data on a non aligned memory address on occasion this caused the quartz compositor, which depended on aligned memory, to draw text with goofy colours.

Moral of the story, I don't use alloca anymore and if I do, I ensure that its aligned properly.

>If there’s any risk that nmemb is too large, it must be guarded. [...] However, if median is expected to safely accommodate COPY_MAX elements, it may as well always allocate an array of this size. If it can’t, then that’s not a safe maximum.

Et voilà, a library function that could have been portable between the smallest microcontroller and the largest workstation becomes restricted to a single application.

Um, no? That COPY_MAX would still need a different value between small MCU and full-blown PC.

Not to mention that using stack allocation on low-memory device is extremely dangerous... at least with malloc you get a nice diagnostic, while alloca will just do random program damage.

It does not do random damage, you get a segmentation fault in most systems.

In really small embedded you should not be allocating anything meaningful in the stack anyway.

In small embedded things are either statically allocated or allocated on the stack. There is no heap.

Isn't that like choosing your poison? If you have a low memory device, you need to statically guarantee safety and reject oversized inputs. Crashing your embedded device may work if your are a server with a client that knows to retry another backend, but isn't an elegant solution if it disables your car's brakes.

"What’s the behavior in the VLA version when n is so large that sizeof(*identity) doesn’t fit in a size_t?"

Isn't size_t supposed to be as large as to fit the cardinality of the largest type you can create?

In C++, at least, you are right.

> The type size_t is an implementation-defined unsigned integer type that is large enough to contain the size in bytes of any object.

§21.2.24(3)

They're trying to allocate an n·n element array. If int and size_t are 32b (typical 32-bit architectures), and n == INT_MAX, then n·n·sizeof(float) can't be represented by a size_t.

(Used · for multiplication, because HN turns stars into emphasis.)

That may be true but an array of n x n chars where n is 2^32 won't fit (well obviously) in RAM and size_t should be at least 64 bit to match (2^32 x 2^32 = 2^64).

Regardless, even without these unobtainium big machines, the cardinality of the largest array for a platform (by any number of dimensions) must be representable in size_t. A too large of an array would not fit in RAM and you should get a compile/link/out of memory error.

> A too large of an array would not fit in RAM and you should get a compile/link/out of memory error.

Except we're talking about variable sized arrays, where the wanted size is not known until runtime (e.g. from user input). We can't check this at compile time.

This also isn't the same problem as an out of memory error; we need to check that nn didn't overflow the size of size_t, as well as that the memory allocation is successful. Something like:

    int n = /* run-time value */
    size_t sz = (size_t)n;
    // Check n fits in size_t.
    if ((int)sz != n) <error>
    sz *= sz * sizeof(float);
    // Check against overflow.
    if (((sz / (size_t)n) / sizeof(float)) != (size_t)n) <error>
    float *matrix = malloc(sz);
    // Check allocation succeeded.
    if (matrix == NULL) <error>

One is still confined by the limitations of the target machine. Ignoring them is at one's own peril.

This doesn't seem to be a new thing generally. Variable length arrays (if you like) are just what you have in Fortran. If you support scientific processing, you'll often have seen mysterious SEGVs due to people insisting on using Intel ifort, which allocates arrays on the stack by default (or used to?), and doesn't fare well with typical default stack limits. This is the equivalent of Gfortran's -fstack-arrays, which is only turned on by -Ofast. (Recursive procedures use the stack anyway.)

> Stack allocations are trivial and fast by comparison: Allocation is a matter of bumping the stack pointer, and no synchronization is needed.
And this is why runtimes with moving garbage collectors can be faster than malloc - allocation with such a GC is always this cheap even when it's to the heap. (The costs move elsewhere, of course, but ideally to another thread, and are temporally and spatially grouped so that the work uses cache better.)

Allocation is always cheap, also with manual memory management. It's reclaiming/freeing memory which is the tricky part ;)
Best approach is still to minimize dynamic allocation as much as possible. One can often get surprisingly far with an entirely static memory layout that's defined upfront at application start.

In support of flohofwoe's point: good implementations of malloc will, on the common path, just bump a pointer without synchronization. The allocation path of good manual allocator implementations and garbage collectors will probably look similar.

> In support of flohofwoe's point: good implementations of malloc will, on the common path, just bump a pointer without synchronization.
How does this work when the heap address space becomes fragmented, with randomly distributed available space and objects that are still live? You can't just bump when the next piece of memory may still be in use, and when you're not able to move memory.

That's the uncommon path.

Yes, exactly. And! It exists in garbage collectors, too.

Why would you ever encounter a fragmented Eden in a garbage collector?

I wasn't thinking of that case in particular, but that there are other instance in a garbage collector where you will not just be able to bump a pointer: you need to request more memory from the OS, or you need to start a collection phase before satisfying a memory request.

Very good GCs can be faster compared to common system allocators while minimizing the STW moment, but you cannot beat using a proper allocator for your needs.

> but you cannot beat using a proper allocator for your needs
How do you know this to be true?
And why isn't a GC a 'proper' allocator?

"Legitimate Use of Variable Length Arrays"
There isn't any.*
The author shows what's at best a minor convenience, which is in no way worth all the downsides of which the author lists. For any actual use he'd have to wrap it in a function, if merely to have an assertion to check the array ranges. Oh, and have a version for compilers which don't support VLAs at all. At which point he might as well do the right thing always instead of VLA.
There author must be aware this isn't worth it. I guess the actual intent of the post was to show the author's knowledge, and indeed the author knows C and taught me some things I didn't know (VLAs are even worse than I thought them to be).
* Note that I'm talking about VLA, not stack allocation. There are better ways to do that when that's useful.

Reply on news.ycombinator.com