Does dynamic memory allocation reduce performace? [closed]

Question

I went through the video by Bjarne Stroustrup where he explains why to avoid Linked Lists.

Basically, when memory is dynamically allocated using pointers, there are more number of cache misses which reduces the performance.

But, if the same thing is applied to Non-Linear Data Structures like trees and graphs, does the same thing hold true?

Because, in trees also we have two pointers for each node and again there will be random movements of the pointers leading to cache misses.

But, trees have been proved to perform better than linear data structures. Of course, trees can be implemented using arrays as well but again there is a huge consumption of memory.

My question is: Is dynamic memory allocation good or not?

Answer 1

He was trying to make the point that a lot of indirection between small objects tends to decrease the cache efficiency of the code. You cannot fully avoid linked structures, but in some cases you can prefer a "flat" layout which fits into an entire cache line, for example.

Trees and linked-lists are both linked structures which rely on dynamic memory allocation, but lists are considered "bad" because they are O(n), and almost every chase of the next pointer results in a cache miss. In general, n misses is a lot worse than log(n) misses.

For example, consider the following two structs:

struct point {
    int x, y;
};

struct rect {
    struct point origin;
    struct point size;
};

Even though rect contains two point structs, the entire rect struct is totally "flat" because the inner structs are contained, not referred to via pointers. This flatness is a nice thing because rect can now fit on a cache line, and accessing origin.x, for example, wouldn't incur a cache miss after the initial one for the struct itself.

Further, because the stack is typically "hot" in the cache, it would make sense to allocate the entire rect structure there, and not on the heap. It's not only the overhead of the dynamic allocation itself, it is also that the address returned by the allocator is likely not yet in the cache.