C efficient way to manage function temporary dynamic memory

Question

I'm making an Nondeterministic Finite Automata (NFA). An NFA has a set of states, I need four array with the same size(number of states in the NFA) to record temporary information about states during the simulation of the NFA.

However, different NFAs has different number of states, thus the size of arrays varies with different NFAs.

Using C I have come up with three ways to deal with the memory allocation:

Use a very big fix-sized array.
malloc memroy dynamically every time the function is called, and before the function finishes, free the allocated memory
Use malloc but not allocate memory on every function call, use four static pointer variables, and one static int arraySize to record allocated array size, for the first time when the function is called, allocate arrays of size NFA->numStates and assign to each of the static pointers, assign NFA->numStates to static int arraySize; for the second time, if NFA->numStates is less than or equal to arraySize, no memory allocation; if NFA->numStates is greater than arraySize, free previous memory and realloc arrays of size NFA->numStates.

Method 1 uses fix-sized array, which means when the input NFA->numStates is greater than the hard-coded array size, the function will not work.

Method 2 is adaptable, but need to allocate memory every time the function is called, not so efficient ?

Method 3 is adaptable too, but is complicated, and is not thread safe ?

Suggestions or other alternatives ?

Use a VLA? [15 chars] – Filipe Gonçalves Apr 03 '14 at 12:20 — Filipe Gonçalves, Apr 03 '14 at 12:20

score 0 · Accepted Answer · answered Apr 03 '14 at 12:20

0

How about option 2 but with alloca(), i.e. allocate on the stack? It's much (much) faster than malloc(), and automatically de-allocates when you leave the scope which sounds like what you want.

Of course, it's not standard or portable, so it might not be applicable for you.

Failing that, a big fixed-size array seems easy enough and doesn't use more memory.

answered Apr 03 '14 at 12:20

unwind

391,730
64
469
606

`alloca` is supported by most environnments and therefore it's IMHO mostly portable. Actually I'm not aware of any environnment that doesn't support it. Unwind: please correct me if I'm wrong. – Jabberwocky Apr 03 '14 at 12:34
@MichaelWalz You're almost right. As Richard W. Stevens said in "Advanced Programming in UNIX Environment 2d Edition", "The disadvantage is that some systems can't support alloca, if it's impossible to increase the size of the stack frame after the function has been called". – mesmerizingr Apr 03 '14 at 13:00
sounds nice, but [http://stackoverflow.com/questions/1018853/why-is-alloca-not-considered-good-practice]("If the allocation causes stack overflow, program behaviour is undefined") – Linlix Apr 03 '14 at 14:13

score 0 · Answer 2 · answered Apr 03 '14 at 12:25

0

Variable-Length Arrays (VLAs) have been available since C99. I'd be impressed if you are still working with an implementation that does not support such a thing. VLAs work like regular arrays, except that the size you use to declare them is determined at runtime. That seems to be what you're looking for.

answered Apr 03 '14 at 12:25

Filipe Gonçalves

20,783
6
53
70

It sounds simple and nice. But what if the caller give a invalid n, e.g. -1, or too big that cause stack overflow ? – Linlix Apr 03 '14 at 14:08
@Linlix Well, it's your job to validate the size given by the caller. You can perform checks before declaring the array to make sure that the size is positive. As for the stack overflow issue: you will always be bounded by some limit (`malloc()` can also hit memory exhaustion). Do you really think you will have that much states in your NFA? It shouldn't be of much importance if you don't plan to allocate a huge array (e.g. something with 1000000 elements). There is always a limit, it's just a matter of thinking whether you will possibly hit it - I personally don't think you will – Filipe Gonçalves Apr 03 '14 at 14:57
you're right, I don't need that much states, but I am considering other similar cases. Now I decide to use fixed array, if the size is not enough I use malloc – Linlix Apr 06 '14 at 04:30

mesmerizingr · Answer 3 · 2014-04-03T12:50:26.247

As you are dealing with arrays of arbitrary size I suggest you to implement simple linked list structure that at initialization will hold an array of predefined size and can be extended to hold additional chunks of memory. This will be an abstraction over contiguous memory space. You just need to store the current size of this structure in parent container.

#include <stddef.h>

struct contmem
{
        size_t size;
        struct memchunk
        {
                void *data;
                struct memchunk *next, *prev;
        } head;
}

So, you can extend this structure when you have to and store information by iterating over elements of linked list. This is similar to what happens inside lists from standard C++ library and differs from straight memory reallocation.

C efficient way to manage function temporary dynamic memory

3 Answers3