Ways to avoid using malloc? [closed]

Question

With all recent noise C gets, I read that there are some ways to minimize usage of malloc in C, and that it is a very good practice. I how ever have no idea when or how or what such practices are good. So my question would be, maybe some experienced C programmers could give some examples where one could (or should) write something without malloc, but what would be really non-obvious way for newbie C programmer (and thus said newbie would simply use malloc)? Maybe you have some experiences from factoring out malloc into something else.

P.S. some posts I read were referencing Quake 3 source code and how it avoids use of malloc, so if someone has knowledge of this it would be interesting to know what is done there, since at least for know I would like to avoid digging into quakes code aimlessly. (since well if they avoid using malloc searching for malloc will not give much results I suppose, also code base is most likely not as simple as individual examples could be)

Answer 1

I don't know about totally avoiding malloc, but you can certainly reduce it.

The basic concept is a memory pool. That is a large buffer which you have allocated that you can use for many objects instead of requesting lots of small allocations.

You might use this in a real-world situation where you are sending events into a queue to be processed by another thread. The event objects might be smallish structures and you really need to avoid making thousands of calls to malloc every second.

The answer of course is to draw these event objects from a pool. If you need to, you can even use parts of your pool buffer to form a list so that you can quickly index memory that has been returned to the pool. These are generally known as free-lists.

You do have to be careful about memory alignment, as you can severely impact performance by having misaligned data. But you can handle all that with a little maths.

---

Don't freak out about these concepts. A pool doesn't actually have to be that sophisticated. Consider this:

int ** matrix = malloc( rows * sizeof(int*) );
for( int i = 0; i < rows; i++ ) {
    matrix[i] = malloc( cols * sizeof(int) );
}

I see this all the time, and it's a pet peeve of mine. Why would you do that, when you can do this:

int ** matrix = malloc( rows * sizeof(int*) );
matrix[0] = malloc( rows * cols * sizeof(int) );
for( int i = 1; i < rows; i++ ) {
    matrix[i] = matrix[i-1] + cols;
}

And of course, that reduces to this (beware of potential alignment issues in your first row though - I've ignored it here for the sake of clarity)

int ** matrix = malloc( rows * sizeof(int*) + rows * cols * sizeof(int) );
matrix[0] = (int*)matrix + rows;
for( int i = 1; i < rows; i++ ) {
    matrix[i] = matrix[i-1] + cols;
}

The cool thing about that last example is how easy it is to delete your matrix =)

free( matrix );

Oh, and zeroing the matrix is just as easy...

memset( matrix[0], 0, rows * cols * sizeof(int) );

Answer 2

In the scenario where you need small, dynamic sized arrays in local scope, there is alloca() which allocates from the stack and doesn't need you to explicitly free the memory (it gets freed when the function returns), and there are variable length arrays (VLA):

void meh(int s) {
    float *foo = alloca(s * sizeof(float));
    float frob[s];
} // note: foo and frob are freed upon returning

Answer 3

If you know all the sizes of arrays, lists, stacks, trees, whatever data structures your program needs beforehand, you can allocate the required memory statically by defining arrays of constant number of elements. Pros: no memory management, no memory fragmentation, fast. Cons: limited use, wasted memory.

You can implement a custom memory allocator on top of malloc() or whatever your OS provides, allocate a big chunk of memory once and then carve it up without calling standard malloc() functions. Pros: fast. Cons: not quite trivial to implement right.

Another (and a rather perverse) way of avoiding malloc() would be to store most of your data in files instead of memory. Pros: virtually none.

You may also use local variables and deep function calls (or explicit recursion) to allocate space for data on the go if you're certain that the program's stack is going to be big enough. Pros: no memory management, easy, fast. Cons: limited use.

As an example of a working midsize project that avoids malloc() I can offer my pet project, Smaller C compiler. It statically allocates a number of arrays and it also allocates small local variables inside recursive functions. Beware, the code hasn't been beautified yet and it's not something small or easy to understand if you're fairly new to programming, C or compilers.

Answer 4

The primary reason for not using malloc in some particular cases is probably the fact that it employs a generic, one-size-fits-all approach to memory allocation.

Other approaches, such as memory pools and slab allocation may offer benefits in the case of having well-known allocation needs.

For example, it is much more advantageous for an allocator to assume that the allocated objects will be of a fixed size, or assume that their lifetime will be relatively short. A generic allocator cannot make such assumptions and cannot therefore perform optimally in such scenarios.

The potential benefits can include a decreased memory footprint due to the specialized allocator having a more condensed bookkeeping. A generic allocator most probably holds a larger amount of metadata for each allocated object, whereas an allocator that "knows" in advance what the object's size will be can probably omit it from the metadata.

It can also make a difference in allocation speed - a custom allocator will probably be able to find an empty slot faster.

This is all talking in relatives here, but the questions you should ask before choosing a custom allocation scheme are:

• Do you need to allocate and deallocate a large number of objects having the same size? (Slab allocation)

• Can these objects be disposed at once without the overhead of individual calls? (Memory pools)

• Is there a logical grouping of the individually allocated objects? (Cache aware allocation)

The bottom line is, you have to inspect the allocation needs and patterns of your program carefully, and then decide whether a custom allocation scheme can be beneficial.