Why Looping Over 8192 Elements Is Slow in C: Cache Effects, Stride Access, and Memory Layout

This page explains why a C program can suddenly become slower at very specific array sizes, even when the algorithm stays the same. You will learn how 2D arrays are stored in memory, why loop order matters, how cache lines and cache conflicts affect performance, and how a size like 8192 can trigger worst-case memory behavior. You will also see practical ways to rewrite the loops so the program becomes cache-friendly and faster.

In C, a 2D array like float img[SIZE][SIZE] is stored in row-major order. That means each row is laid out contiguously in memory.

For this declaration:

float img[SIZE][SIZE];

an access like:

img[row][col]

means:

• img[row] is one full row
• img[row][col] moves within that row

So the last index changes fastest in memory.

In your code, the loops use img[j][i] and res[j][i], while i is the outer loop and j is the inner loop. That means the code is walking down columns, not across rows. In C, this is usually inefficient because consecutive accesses are far apart in memory.

Why that matters

Modern CPUs are much faster than main memory. To reduce waiting, they use cache: small, fast memory that stores recently used data in chunks called cache lines.

When you access memory in a sequential way, the CPU cache works well:

• one memory fetch brings in several nearby values
• the next few accesses are already available

When you access memory with a large stride, the cache works poorly:

• each access may require loading a different cache line
• many fetched bytes are unused
• cache sets may conflict with each other

Why 8192 is especially bad

Each row has:

8192 floats * 4 bytes = 32768 bytes

That is 32 KB, which is a very important number because it matches or strongly interacts with common L1 cache sizes. When the stride between accesses becomes an exact power-of-two-sized spacing, many addresses can map to the same cache sets. This causes conflict misses: useful data gets evicted too quickly, even though the total amount of data being reused is small.

So the slowdown is not because the algorithm changed. It is because this particular matrix width creates a bad memory access pattern for the cache.

Core idea

The program is slow at 8192 because:

• the array is stored row by row
• the code iterates column by column
• the stride between accesses is very large
• 8192 creates an especially bad power-of-two memory pattern
• that pattern causes many cache misses and cache conflicts

This is a classic example of performance depending on memory layout, not just big-O complexity.

Imagine a library where books on the same shelf are easy to grab one after another.

• Good access pattern: you walk along one shelf from left to right
• Bad access pattern: you take one book from shelf 1, then one from shelf 2, then one from shelf 3, and so on

Now imagine the shelves are arranged so that every jump lands in the same small holding area near the librarian. The holding area keeps getting overwritten, so the librarian has to keep going back to the main storage.

That is what happens here:

• rows are like shelves
• C stores data row by row
• your code jumps between rows in the inner loop
• at 8192, those jumps align in a particularly unlucky way for the cache

So the CPU is not doing more math. It is just spending more time waiting for data.

The main rule for C 2D arrays is:

float a[ROWS][COLS];

Accesses are most cache-friendly when the last index changes in the inner loop.

Cache-friendly traversal

for (int row = 0; row < ROWS; row++) {
    for (int col = 0; col < COLS; col++) {
        use(a[row][col]);
    }
}

This walks through memory in the order it is stored.

Cache-unfriendly traversal

for (int col = 0; col < COLS; col++) {
    for (int row = 0; row < ROWS; row++) {
        use(a[row][col]);
    }
}

This jumps by an entire row each time.

Applying that to your code

Your original version effectively does this:

for (i = 1; i < SIZE - 1; i++)
    for (j = 1; j < SIZE - 1; j++)
        res[j][i] = ... img[j + l][i + k] ...;

A better version swaps the meaning of the loop order so the last index changes fastest:

for (j = 1; j < SIZE - 1; j++) {
    for (i = 1; i < SIZE - 1; i++) {
        res[j][i] = 0.0f;
        for (l = -1; l < 2; l++) {
            for (k = -1; k < 2; k++) {
                res[j][i] += img[j + l][i + k];
            }
        }
        res[j][i] /= 9.0f;
    }
}

This version accesses nearby elements in the same row much more often.

Even clearer initialization fix

The initialization loop should also follow row-major order:

for (j = 0; j < SIZE; j++) {
    for (i = 0; i < SIZE; i++) {
        img[j][i] = (2 * j + i) % 8196;
    }
}

This avoids the same column-wise traversal problem during setup.

Consider a much smaller example:

#define SIZE 4
float img[SIZE][SIZE];

In memory, C stores it like this:

img[0][0], img[0][1], img[0][2], img[0][3],
img[1][0], img[1][1], img[1][2], img[1][3],
img[2][0], img[2][1], img[2][2], img[2][3],
img[3][0], img[3][1], img[3][2], img[3][3]

Good loop order

for (j = 0; j < SIZE; j++)
    for (i = 0; i < SIZE; i++)
        use(img[j][i]);

Step by step:

1. Read img[0][0]
2. Read img[0][1]
3. Read img[0][2]
4. Read img[0][3]
5. Move to next row
6. Read img[1][0]

These accesses are adjacent in memory, so the cache helps a lot.

Bad loop order

for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
        use(img[j][i]);

Step by step:

1. Read img[0][0]
2. Jump to img[1][0]
3. Jump to img[2][0]
4. Jump to img[3][0]
5. Go back to img[0][1]

Now each access jumps by a whole row. For large arrays, that means thousands of bytes between consecutive accesses.

In your 3×3 filter

For one output cell, you read 9 nearby input values. That part has locality. But because the surrounding loops move in a cache-unfriendly order, the CPU keeps revisiting memory in a pattern that does not fit the cache well.

At SIZE = 8192, the row length becomes exactly 32768 bytes, which can create repeated cache conflicts and make the whole filter much slower.

This concept appears in many real programs, not just image filters.

Image and video processing

Operations like:

• blur filters
• edge detection
• convolution
• resizing

all work over 2D pixel grids. Loop order can dramatically change performance.

Scientific computing

Matrix operations in:

• simulations
• linear algebra
• physics code
• numerical methods

often depend heavily on memory access patterns.

Game development

Tile maps, heat maps, and large simulation grids are often stored in arrays. Traversing them in storage order improves frame-time stability.

Data processing

Large tables and multidimensional buffers in analytics pipelines can become slow if accessed with poor locality.

Machine learning and signal processing

Tensor operations often rely on contiguous memory access for speed. Layout-aware loops are a major optimization technique.

In real C codebases, developers usually combine correct loop ordering with a few common patterns.

1. Match loop order to memory layout

For row-major arrays in C:

• outer loop over rows
• inner loop over columns

for (row = 0; row < rows; row++)
    for (col = 0; col < cols; col++)
        process(a[row][col]);

2. Use local accumulators

Instead of repeatedly writing to memory, compute in a local variable and write once:

for (j = 1; j < SIZE - 1; j++) {
    for (i = 1; i < SIZE - 1; i++) {
        float sum = 0.0f;
        for (l = -1; l <= 1; l++)
            for (k = -1; k <= 1; k++)
                sum += img[j + l][i + k];
        res[j][i] = sum / 9.0f;
    }
}

This reduces unnecessary stores to res[j][i] inside the inner loops.

3. Keep reused rows hot in cache

Stencil operations like 3×3 filters often reuse neighboring rows. Sequential traversal helps the cache retain those rows.

4. Compiler-friendly code

Clear indexing and contiguous access make it easier for compilers to:

• vectorize loops
• unroll loops
• optimize address calculations

5. Tiling for very large data

In high-performance code, developers may process arrays in smaller blocks so working data fits better in cache. This is called blocking or tiling.

6. Alignment and allocation choices

Dynamic allocation with aligned memory can help in some optimized code, but it does not fix a bad traversal pattern by itself. The biggest win here comes from changing access order.

1. Assuming all loop orders are equivalent

They are logically equivalent, but not performance-equivalent.

Broken-for-performance example:

for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
        img[j][i] = 1.0f;

Better:

for (j = 0; j < SIZE; j++)
    for (i = 0; i < SIZE; i++)
        img[j][i] = 1.0f;

2. Forgetting that C uses row-major order

Many beginners expect img[x][y] to behave like a mathematical (x, y) coordinate system. In memory, C cares about array layout, not geometry.

3. Writing to memory too often inside inner loops

Less efficient:

res[j][i] = 0.0f;
for (l = -1; l <= 1; l++)
    for (k = -1; k <= 1; k++)
        res[j][i] += img[j + l][i + k];
res[j][i] /= 9.0f;

Better:

float sum = 0.0f;
for (l = -1; l <= 1; l++)
    for (k = -1; k <= 1; k++)
        sum += img[j + l][i + k];
res[j][i] = sum / 9.0f;

4. Blaming only memory size

The problem is often not “too much memory” but “bad access pattern”. A program can fit in RAM and still run slowly because the CPU cache is used poorly.

5. Ignoring power-of-two effects

Sizes like 1024, 2048, 4096, and 8192 sometimes trigger worst-case cache behavior because of address mapping patterns.

6. Expecting malloc alone to fix it

Dynamic allocation changes where memory lives, but it usually does not solve a fundamentally poor stride pattern. Access order matters more here.

Loop order comparison

Static vs dynamic allocation

Quick rules for C 2D arrays

• C stores a[rows][cols] in row-major order
• The last index is contiguous in memory
• Put the last index in the inner loop for better cache use

Best traversal pattern

for (row = 0; row < rows; row++)
    for (col = 0; col < cols; col++)
        use(a[row][col]);

Avoid this when possible

for (col = 0; col < cols; col++)
    for (row = 0; row < rows; row++)
        use(a[row][col]);

Why 8192 can be slow

• 8192 * 4 = 32768 bytes per row
• power-of-two strides can cause cache conflicts
• exact sizes may be much slower than nearby sizes

Better 3×3 filter pattern

for (j = 1; j < SIZE - 1; j++) {
    for (i = 1; i < SIZE - 1; i++) {
        float sum = 0.0f;
        for (l = -1; l <= 1; l++)
            for (k = -1; k <= 1; k++)
                sum += img[j + l][i + k];
        res[j][i] = sum / 9.0f;
    }
}

Key terms

• Cache line: small chunk of nearby memory loaded together
• Stride: distance between consecutive memory accesses
• Locality: how close your accesses are in memory/time
• Conflict miss: cache eviction caused by address mapping collisions

Why is 8192 slower than 8191 or 8193?

Because 8192 creates a power-of-two row size that can interact badly with CPU cache mapping, causing many conflict misses.

Is this a bug in GCC?

Usually no. The main issue is the memory access pattern in the code, not the compiler.

Does malloc fix cache problems?

Not by itself. Dynamic allocation changes where memory is allocated, but poor loop order can still cause the same slowdown.

Why does swapping loop order help so much?

Because it makes memory accesses follow the actual layout of the array in C, allowing the CPU cache to reuse nearby data efficiently.

Is this only about large arrays?

The effect becomes more noticeable with large arrays because cache misses are much more expensive when the working set no longer fits comfortably in cache.

What is a stride in memory access?

A stride is the byte distance between one access and the next. Large strides usually reduce cache efficiency.

Would a 1D array behave differently?

A 1D array has the same underlying memory rules, but indexing is more explicit. You still need to access it in contiguous order for best performance.

Can compilers automatically fix poor memory layout usage?

Sometimes they can improve small details, but they usually cannot completely undo a cache-unfriendly traversal pattern.

• Arrays in C — Understanding how array elements are stored is the foundation for this topic.
• Row-major order — Explains why the last index should usually change fastest in C.
• CPU cache — Helps explain why memory access patterns affect speed so much.
• Cache locality — Shows why nearby accesses are faster than scattered ones.
• Loop optimization — Covers practical ways to rewrite loops for better performance.
• Matrix traversal — Directly related to iterating through 2D data structures efficiently.
• Convolution and stencil operations — Common patterns in image and numerical code that depend on cache behavior.
• Blocking and tiling — Advanced but very relevant techniques for improving cache usage on large arrays.