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

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:

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]);

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

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:

Loop order comparison

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;
         (l = ; l <= ; l++)
             (k = ; k <= ; k++)
                sum += img[j + l][i + k];
        res[j][i] = sum / ;
    }
}

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.