Memory Access Optimization: Contiguous vs Non-Contiguous (C++)

Memory Access Optimization

---

Prerequisites

- Compile
- Runtime

---

1. Why Memory Access Matters

Modern CPUs are much faster than memory.

Performance is often limited by:

• Cache hits vs cache misses
• Memory access patterns

Efficient memory access can be orders of magnitude faster than inefficient access.

2. Contiguous Memory Access

Accessing memory in sequential order

int arr[1000];

for (int i = 0; i < 1000; i++) 
{
    arr[i] += 1;
}

Access pattern:

arr[0] → arr[1] → arr[2] → ...

• CPU prefetcher predicts next access
• Cache lines are fully utilized
• Fewer cache misses

Example:

• Cache line ≈ 64 bytes
• int = 4 bytes → 16 elements per cache line

2. Non-Contiguous Memory Access

Accessing memory in irregular / scattered pattern

int arr[1000];

for (int i = 0; i < 1000; i += 16) 
{
    arr[i] += 1;
}

Access pattern:

arr[0] → arr[16] → arr[32] → ...

• Cache lines wasted
• Frequent cache misses
• Poor prefetching

3. Real Performance Difference

👉 Same number of operations, very different speed

// ✅ Fast
for (int i = 0; i < N; i++) {
    sum += arr[i];
}

// ❌ Slow
for (int i = 0; i < N; i++) {
    sum += arr[random_index[i]];
}

4. 2D Array Optimization

C++ uses row-major order

int arr[100][100];

✔ Fast (row-wise)

for (int i = 0; i < 100; i++) 
{
    for (int j = 0; j < 100; j++) 
        arr[i][j] += 1;
}

❌ Slow (column-wise)

for (int j = 0; j < 100; j++) 
{
    for (int i = 0; i < 100; i++) 
        arr[i][j] += 1;
}

Reason:

• Row-wise = contiguous
• Column-wise = strided access

5. Pointer vs Pointer-to-Pointer

✔ Contiguous

int* arr = new int[N];

❌ Non-contiguous

int** arr = new int*[N];

for (int i = 0; i < N; i++) 
    arr[i] = new int[M];

Each row is allocated separately → scattered memory

6. STL Containers

✔ Contiguous

• std::vector
• std::array

❌ Non-contiguous

• std::list
• std::map
• std::unordered_map

Linked structures → pointer chasing → cache miss

• Use std::vector instead of std::list
• Row-major for 2D arrays
• Sequential access is king
• Avoid int** if possible