Why 8192 Elements Slow Down Your C++ Code: Analysis

Introduction: The Magic Number 8192 and Your Slowing Code

Have you ever noticed that your C++ code, which worked perfectly on 1000 or 10000 elements, suddenly starts slowing down at exactly 8192? No, it's not a compiler bug or a curse from ancient programmers. This is a classic example of how CPU architecture can turn your fast algorithm into a turtle.

This story began with a legendary question on Stack Overflow: "Why is my program slow when looping over exactly 8192 elements?", which gathered thousands of views and became a real meme in the world of High Performance Computing. Today, in 2025, when processors have become even more complex, understanding this problem is not just a fun fact, but a real skill that distinguishes a junior developer from an engineer writing fast code.

In this article, we will break down what's happening under the hood of your processor, why the size 8192 (and its multiples) are a "red zone," and how to write code that will be consistently fast on any data. Let's go!

1. Anatomy of the Problem: Cache Misses and Associativity

To understand the root of the evil, we need to look into the structure of a modern processor. The slowest operation is accessing Random Access Memory (RAM). To speed up access, the processor uses a cache — a small but very fast memory located directly on the chip.

1.1. How the Cache Works (Very Briefly)

\n
• L1 cache: The fastest and smallest (~32 KB per core).
\n
• L2 cache: Slightly slower, but larger (~256-512 KB).
\n
• L3 cache: Shared across all cores, the largest (several MB).
\n

Data is loaded into the cache not byte by byte, but in blocks called cache lines (typically 64 bytes). If the processor requests data that is not in the cache, a cache miss occurs, and it must wait for the data to be loaded from RAM. This can take hundreds of clock cycles.

1.2. The Curse of 8192: Cache Associativity

The cache is not just one big basket. It is organized into sets. Each memory address can only be placed into one of these sets. This is called a set-associative cache.

Imagine a parking lot where spaces are grouped into rows. Your car (memory address) can only be parked in a specific row (set). If all spaces in that row are taken, you must evict one of the cars (evict a cache line) to free up space.

For many modern processors, L1 and L2 caches are 8-way set-associative. This means each set can hold 8 cache lines.

Now for the key point: the cache line size is 64 bytes (512 bits). If you are working with an array of int (4 bytes), one cache line contains 16 elements.

When you traverse an array with a stride that is a power of two, all the elements you access may map to the same cache set. For example, if you take every 16th element, they will all compete for the same 8 slots in the set. When the number of elements exceeds the number of slots (for example, when you traverse an array of 8192 elements that all map to one set), the cache constantly "throws out" old data and loads new data. This is called cache thrashing.

8192 is 2^13. With a certain memory layout, this exact number of elements perfectly "hits" the associativity limits of a typical L1 cache (32 KB / 64 bytes = 512 sets, and 8192 / 16 = 512, which perfectly aligns with each set).

2. Demonstrating the Problem in C++

Let's look at code that reproduces this problem. We will measure the time it takes to traverse a two-dimensional array with different strides.

#include <iostream>\n#include <vector>\n#include <chrono>\n\nconst int SIZE