CPU cache

lastmod 2025-11-12created 2016-11-2324 edits

A CPU cache is built into the CPU architecture to be used as memory. A CPU cache is a small but fast memory that holds the data of the most frequently used locations in main memory. Because most memory accesses tend to occur frequently near particular locations, copying data into a small but fast cache memory can save average memory access time.

When the processor wants to read or write main memory, it first checks whether the data for that address exists in the cache. If the data for that address is in the cache, it reads the data directly from the cache; otherwise, it accesses main memory directly. At this point, most processors copy the data transferred from the direct main memory access into the cache, so that the next time the processor accesses the same address, it can read and write directly from the cache.

Locality of reference (data locality)

What if the cache simply sat there as an intermediate-speed medium without any particular algorithm? Then, with or without such a cache memory, the speed at which the CPU reads or writes data would just be the same as reading and writing main memory. In other words, having cache memory would be no different from not having it.

Cache memory does its job because it exploits data locality (localty). Data locality is divided into the following three types.

Spatial locality (spartial locality)
Temporal locality (temporal locality)
Sequential locality (sequential locality)

How caches work

Cache lines and tags (a chunk of data and a small piece of data describing its contents)
- Data is transferred between memory and cache in units of cache lines.
Cache data storage structure
- Full Associative
- Set Associative
- Direct Map

Performance Tuning

Understanding the characteristics of L1/L2/L3 caches and cache lines
The false sharing problem and cache coherency protocols
Reducing Korean: 컨텍스트 스위칭 costs with CPU affinity settings

aligned_malloc

See C++:alignas.

Thrashing

Performance degradation caused by contention for cache lines is called thrashing.

Optimization

With the Direct Map scheme, if the cache has 256 lines of 64-byte data chunks, the same cache line is used every 16Kb (8byte * 2048). ¹

Suppose we have the following code.

double a[2048], b[2048];
for (i=0; i<N; i++) { a[i] = b[i]; }

The code above uses the same cache line, causing frequent replacements due to line contention. This thrashing can be fixed as below so that a different cache line is referenced.

double a[2048], dummy[8], b[2048];
for (i=0; i<N; i++) { a[i] = b[i]; }

Cache performance factors

Based on the rough overview above, a good cache memory should always hold the data the CPU wants and be able to supply it to the CPU quickly whenever needed.

When the CPU wants data and that data exists in cache memory, we call it a cache hit. The rate of such hits is called the hit rate.

On the other hand, when the data does not exist in the cache, the CPU has to accept high latency and read the data from main memory to find what it wants. A case where the desired data does not exist in cache memory is called a miss, and this failure rate is called the miss rate.

Cache line

Computer systems: cache memory ²

Get cache line

Stackoverflow - Programmatically get the cache line size?

#ifndef GET_CACHE_LINE_SIZE_H_INCLUDED
#define GET_CACHE_LINE_SIZE_H_INCLUDED

// Author: Nick Strupat
// Date: October 29, 2010
// Returns the cache line size (in bytes) of the processor, or 0 on failure

#include <stddef.h>
size_t cache_line_size();

#if defined(__APPLE__)

#include <sys/sysctl.h>
size_t cache_line_size() {
    size_t line_size = 0;
    size_t sizeof_line_size = sizeof(line_size);
    sysctlbyname("hw.cachelinesize", &line_size, &sizeof_line_size, 0, 0);
    return line_size;
}

#elif defined(_WIN32)

#include <stdlib.h>
#include <windows.h>
size_t cache_line_size() {
    size_t line_size = 0;
    DWORD buffer_size = 0;
    DWORD i = 0;
    SYSTEM_LOGICAL_PROCESSOR_INFORMATION * buffer = 0;

    GetLogicalProcessorInformation(0, &buffer_size);
    buffer = (SYSTEM_LOGICAL_PROCESSOR_INFORMATION *)malloc(buffer_size);
    GetLogicalProcessorInformation(&buffer[0], &buffer_size);

    for (i = 0; i != buffer_size / sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION); ++i) {
        if (buffer[i].Relationship == RelationCache && buffer[i].Cache.Level == 1) {
            line_size = buffer[i].Cache.LineSize;
            break;
        }
    }

    free(buffer);
    return line_size;
}

#elif defined(linux)

#include <stdio.h>
size_t cache_line_size() {
    FILE * p = 0;
    p = fopen("/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size", "r");
    unsigned int i = 0;
    if (p) {
        fscanf(p, "%d", &i);
        fclose(p);
    }
    return i;
}

#else
#error Unrecognized platform
#endif

#endif

AMAT

In most cases, AMAT (Average Memory Access Time) is used to express cache performance.

For cache memory, AMAT is given by the following formula.

AMAT = Hit Rate x Hit Time + (1 - Hit Rate) x Miss Penalty

Documentation

Windows Architecture and Principles - Chapter 12. Cache management within the processor: Windows_Architecture_and_Principles_-_Chapter_12._Cache_management_within_the_processor.pdf

Favorite site

References

(See page 123 of "Technology Supporting Processors - ISBN 6788994506241") ↩
Computer_system_-_cache_memory.pdf ↩
Leojesus_-_what_is_cache_01.pdf ↩
Leojesus_-_what_is_cache_02.pdf ↩
Library_of_Ezbeat_-_Principles_of_CPU_Cache.pdf ↩
ARM9_cache.pdf ↩
For_effective_multi-threaded_programming.pdf ↩

author Zer0 sitemap