Why Does Cache Hit Rate Make Programs Sometimes Fast and Sometimes Slow?

1. Cache Hit Rate Definition

Cache hit rate = hits / total accesses
Hit Rate = Hits / (Hits + Misses)

Higher hit rate yields better performance; lower hit rate forces more memory accesses and slows execution.

Typical Hit‑Rate Levels

L1: 90‑95 %

L2: 95‑99 %

L3: 99 %+

If a miss occurs, the next cache level must be accessed, causing a sharp latency increase.

2. Factors Influencing Cache Hit Rate

2.1 Data Locality

// Good locality – sequential access
for (int i = 0; i < N; i++) {
    sum += arr[i]; // high hit rate
}

// Poor locality – strided access
for (int i = 0; i < N; i++) {
    sum += arr[i * stride]; // low hit rate
}

2.2 Working‑Set Size

The working set is the total amount of data a program uses at a given time.

If working set < cache capacity → most accesses hit → good performance.

If working set > cache capacity → frequent evictions → poor performance.

2.3 Cache Associativity

Associativity is the number of blocks per set.

Direct‑mapped: 1‑way (many conflicts).

N‑way set‑associative: N blocks per set (more flexible).

Fully associative: any block can occupy any line (most flexible).

Higher associativity reduces conflict misses but adds lookup latency.

3. Types of Cache Misses

3.1 Compulsory (Cold) Miss

First access to a datum when the cache is empty. Mitigations include prefetching and increasing cache‑line size.

3.2 Capacity Miss

Occurs when the working set exceeds cache capacity, causing useful data to be evicted. Solutions: increase cache size or redesign data access patterns.

3.3 Conflict Miss

Arises in direct‑mapped or low‑associativity caches when multiple addresses map to the same line, even if free space exists elsewhere. Solutions: increase associativity or adjust data layout.

4. Techniques to Improve Cache Hit Rate

4.1 Data Alignment

// Cache line size = 64 bytes

// Properly aligned struct (good)
struct Data {
    int a;          // 4 bytes
    char b;         // 1 byte
    char pad[3];    // padding to 8‑byte boundary
    long c;         // 8 bytes
};

// Misaligned struct (bad) – may span two cache lines
struct Data {
    int a;          // 4 bytes
    char b;         // 1 byte
    // missing padding
    long c;         // 8 bytes, potentially crossing a line
};

4.2 Array Traversal Optimization

// 2‑D array matrix[M][N]
int matrix[1000][1000];

// Row‑major (good) – contiguous rows
for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        sum += matrix[i][j];
    }
}

// Column‑major (bad) – strided column access
for (int j = 0; j < N; j++) {
    for (int i = 0; i < M; i++) {
        sum += matrix[i][j];
    }
}

4.3 Data Packing

// 10 000 000 bools = 10 MB
bool flags[10000000];

// Pack into bits → 1.25 MB
uint32_t flags[10000000 / 32];

// Process 32 flags per load, improving cache utilization

4.4 Prefetching

// Manual prefetch hint (GCC/Clang)
for (int i = 0; i < N; i++) {
    if (i + 16 < N) {
        __builtin_prefetch(&arr[i + 16], 0, 3);
    }
    sum += arr[i];
}

5. Performance Monitoring Tools

5.1 Linux – perf

# Measure cache references and misses
perf stat -e cache-references,cache-misses ./program

# Sample output
# 1,234,567 cache-references
#   56,789 cache-misses
#   4.60% cache-miss rate

5.2 Windows – Task Manager / CPU‑Z

Task Manager → Performance → CPU shows L1/L2/L3 cache sizes and utilization.

5.3 Intel VTune

# Collect memory‑access data
vtune -collect memory-access ./program

# Provides cache‑miss distribution, memory‑bandwidth usage, and hot‑spot analysis.

6. Practical Case Studies

6.1 Matrix Multiplication Optimization

// Original, cache‑unfriendly implementation
void matrix_mul(float* C, float* A, float* B, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i*n+j] += A[i*n+k] * B[k*n+j]; // B accessed non‑contiguously
            }
        }
    }
}

// Optimized with cache blocking (BLOCK = 32)
#define BLOCK 32
for (int ii = 0; ii < n; ii += BLOCK) {
    for (int jj = 0; jj < n; jj += BLOCK) {
        for (int kk = 0; kk < n; kk += BLOCK) {
            for (int i = ii; i < min(ii+BLOCK, n); i++) {
                for (int j = jj; j < min(jj+BLOCK, n); j++) {
                    for (int k = kk; k < min(kk+BLOCK, n); k++) {
                        C[i*n+j] += A[i*n+k] * B[k*n+j];
                    }
                }
            }
        }
    }
}
// Reported speed‑up: 3‑10×

6.2 Linked List vs. Array Traversal

// Linked list traversal (cache‑unfriendly)
struct Node {
    int value;
    struct Node* next;
};
// Nodes may be scattered; each next pointer can cause a miss.

// Array traversal (cache‑friendly)
int arr[10000];
for (int i = 0; i < 10000; i++) {
    sum += arr[i]; // sequential access, hardware prefetch works
}

7. Typical Cache‑Hit Numbers by Workload

Scientific computing – L1 > 95 %, L2 > 99 %, L3 > 99.9 %.

Gaming – L1 ≈ 90‑95 %, L2 ≈ 95‑98 %, L3 ≈ 98‑99 %.

Databases – L1 ≈ 85‑90 %, L2 ≈ 90‑95 %, L3 ≈ 95‑98 %.

Web services – L1 > 95 %, L2 > 99 %, L3 > 99.5 %.

8. Consequences of Cache Misses

L1 miss  : +5‑10 cycles  (~5‑10 ns)
L2 miss  : +30‑50 cycles (~30‑50 ns)
L3 miss  : +100‑200 cycles (~100‑200 ns)
Memory miss: >200 cycles (>200 ns)
Worst case – multiple misses per instruction can push latency to several hundred nanoseconds, degrading performance by >100×.

9. Summary of Effective Practices

Exploit data locality – prefer sequential over strided access.

Keep the working set within cache capacity – load only needed data and process large data in blocks.

Align structures and use cache‑friendly layouts (padding, row‑major arrays).

Leverage hardware or manual prefetching to hide memory latency.

Choose cache‑friendly data structures – arrays generally outperform linked lists for traversal.