Cost of static memory allocation vs dynamic memory allocation in C

Question

I am very interested to know what is the preferred method of memory allocation static vs dynamic is good for performance (e.g., running time) when you know the exact number of objects/items in C on Linux. Cost for a small number of objects (small amount of memory) and as well as for a large number of objects (huge amount of memory).

e.g., type A[N] vs type *A = malloc(sizeof(type) * N)

Please let me know. Thank you.

Note: We can benchmark this and probably know the answer. But I would like to know the concepts that explain the performance differences between these two allocation methods.

Answer 1

Static allocation will be much faster. Static allocation can happen at global scope, and on the stack.

In global scope statically allocated memory is built into the binary image. That is the total size of the memory required, and where it is to be located in the running binary is computed at compile time. Then when the program loads the operating system loader will allocate enough memory for all the global static arrays. I'm pretty sure it happens in constant time for all the allocations. ( e.g. more allocations don't cost more time )

In local scope, static allocations are allocated on the stack. This involves simply reserving a fixed number of bytes on the stack, and happens in constant time per allocation. Stack space is very limited.

Dynamic memory must be allocated from a heap, and even in the best case most allocations will take time that scales more than linear with each allocation, like n log n time or something.

Also practically speaking the dynamic allocation will be many times slower than static allocation.

@update: As has been pointed out in comments below: stack allocations are not technically static allocations ( but they are allocations with the syntactic form used in OP's question ).

Also when speaking about "allocation time", I'm considering total time to manage the memory ( alloc and free ).

In some dynamic allocators allocation time is faster than freeing time.

It is also true that some fast allocators trade memory efficiency for allocation speed. In these cases static is still "better" in that static and stack allocs are no time and constant time respectively while allocating exact sized blocks.

Dynamic allocators to be fast trade off significant memory efficiency ( e.g. buddy allocators round up to the next power of two sized block, like 33k alloc will use 64k )

Answer 2

True static allocations (globals, and local variables marked static) are glued into sections and loaded along with the rest of the section at load time (execve) using mmap. They're essentially free, already covered by the cost of loading the program.

Automatic arrays with statically known sizes can be glued together with other local variables and allocated by adjusting the stack pointer. That's essentially one integer subtraction (the stack grows downwards) or something close to 1 ns on modern processors.

Variable length arrays can't be glued to other variables so they should cost about 1 ns each.

I tried measuring mallocs with different sizes in a single threaded process and I got this, which would imply that malloc+free pairs cost about 50-100 times as much as stack variables for allocations <16MiB. After that, it spikes upwards (32MiB and 64MiB both cost about a hundred times as much as allocations <=16MiB do):

These are just the costs of obtaining the pointer though. Actual access may cause page faults and thereby further increase the cost of the memory block. The page faults should be extremely rare with stack allocations, but likely with first-time accesses to dynamically allocated memory.

Additionally, many small dynamic allocations will put quite a strain on caches as your memory will be fragmented. (You can reduce this fragmentation by using memory pools, either your own or the obstack functionality available as part of glibc.)