Memory Management in C++ : Non-Primitive Data structures - std::array vs std::vector vs std::list

Memory Management C++

Choosing the right data structure has a direct impact on cache usage and memory efficiency, which can significantly affect the performance of latency-critical applications like trading systems or real-time simulations.

• Introduction

• Memory Allocation: Data Structures

• Performance Impact

Introduction:

Memory management has a direct impact on program performance.

The way is managed impacts performance. The CPU spends a significant amount of time moving data between its registers and the main memory(RAM). To speed up memory access, The CPU uses memory caches (check my post about caches), so programs need to be cache-friendly.

Memory Allocation & Data Structures

If the data is dynamically allocated and used regularly together, it is better to store the elements next to each other. For exemple, using a std::vector is advantageous because it stores elements contiguously in the heap. This way when accessing one element, the neighboring elements are more likely to be loaded into the CPU cache,

improving performance.

These data structures are more complex than they may seem. Behind the scenes, the way data is stored in memory directly affects how efficiently it can be retrieved.

Summary of common C++ data structures:

• std::vector:

  • Stores data contiguously in (heap) memory..

  • Allows efficient access and is cache-friendly.

  • Can grow dynamically but avoids frequent reallocations by managing capacity.

• std::list:

  • Each element contains a pointer to the next (and previous, for std::list) element in the stack.

  • Good for constant-time insertion/deletion in the middle of the sequence.

  • However, elements are scattered in memory, which is not cache-friendly.

• std::array:

  • Fixed-size, contiguous memory allocation.

  • Best suited when the size is known at compile time.

  • No dynamic allocation

    
    

• 
  

  • avoids fragmentation and has predictable memory usage.

Performance Impact

std::array and std::vector are cache-friendly data structures. They store elements contiguously in memory, allowing the CPU to take advantage of cache lines and reducing the number of cache misses. This results in more efficient memory access and overall better performance.

On the other hand, std::list is well-suited for cases where frequent insertions or deletions occur in the middle of the sequence. However, since the elements are scattered in memory and linked via pointers, it is not cache-friendly and may introduce latency due to poor cache utilization.