Understanding Cache Lines

Understanding cache lines is the cornerstone of high-performance programming (e.g., database kernels). If you ignore them, even an algorithmically optimal program can suffer a 10x or even 100x performance degradation due to frequent cache misses.

Why Cache Lines Exist

The CPU accesses main memory far more slowly than it accesses its caches. To bridge this gap, the CPU does not read a single byte at a time from memory — instead it reads a whole contiguous block of data into the cache in one go. The smallest unit of this batch read is called a cache line, typically 64 bytes in size.

You can check the cache line size with:

postgres@slpc:~$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

Or programmatically:

#include<unistd.h>

long cache_line_size = sysconf(_SC_LEVEL1_DCACHE_LINESIZE);

When you access a 4-byte integer at memory address 0x1000, the CPU loads the entire 64-byte block from 0x1000 to 0x103F into the L1 cache. Subsequent accesses to 0x1004, 0x1008, etc. are cache hits — extremely fast. This is the hardware implementation of spatial locality.

If L1 misses, the CPU must wait for the entire 64-byte cache line to be loaded from the next level of cache (L2/L3) or from main memory (DRAM).

Checking CPU Cache Sizes

Use lscpu:

postgres@slpc:~$ lscpu | grep -i cache
L1d cache:                               384 KiB (8 instances)  # L1 data cache
L1i cache:                               256 KiB (8 instances)  # L1 instruction cache
L2 cache:                                10 MiB (8 instances)   # L2 cache
L3 cache:                                36 MiB (2 instances)   # L3 cache

# Check CPU0's L1 cache size
postgres@slpc:~$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
48K

The Cost of Cache Misses

Here we benchmark array traversal versus linked list traversal. Both have the same O(N) algorithmic complexity, but the array’s higher cache hit rate yields significantly better performance.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>

#define ARRAY_SIZE 1000000
#define CACHE_LINE_SIZE 64

// Array structure
typedef struct {
    int* data;
    size_t size;
} Array;

Array* create_array(size_t size) {
    Array* arr = (Array*)malloc(sizeof(Array));
    arr->size = size;
    arr->data = (int*)malloc(size * sizeof(int));
    
    for (size_t i = 0; i < size; i++) {
        arr->data[i] = i % 1000;
    }
    
    return arr;
}

void free_array(Array* arr) {
    free(arr->data);
    free(arr);
}

long long traverse_array(Array* arr) {
    long long sum = 0;
    for (size_t i = 0; i < arr->size; i++) {
        sum += arr->data[i];
    }
    return sum;
}

// Linked list node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_linked_list(size_t size) {
    if (size == 0) return NULL;
    
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    
    Node* current = head;
    for (size_t i = 1; i < size; i++) {
        current->next = (Node*)malloc(sizeof(Node));
        current = current->next;
        current->data = i % 1000;
        current->next = NULL;
    }
    
    return head;
}

void free_linked_list(Node* head) {
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
}

long long traverse_linked_list(Node* head) {
    long long sum = 0;
    Node* current = head;
    while (current != NULL) {
        sum += current->data;
        current = current->next;
    }
    return sum;
}

typedef long long (*TraverseFunc)(void*);

void benchmark(const char* name, TraverseFunc func, void* data, int iterations) {
    clock_t start = clock();
    long long result = 0;
    
    for (int i = 0; i < iterations; i++) {
        result += func(data);
    }
    
    clock_t end = clock();
    double time_ms = (double)(end - start) / CLOCKS_PER_SEC * 1000;
    
    printf("%-30s: %8.3f ms (sum=%lld)\n", name, time_ms, result);
}

int main() {
    printf("╔════════════════════════════════════════════════════════╗\n");
    printf("║     Array vs List: Cache Performance Benchmark        ║\n");
    printf("╚════════════════════════════════════════════════════════╝\n\n");
    
    srand(time(NULL));
    
    printf("Test size: %d elements\n\n", ARRAY_SIZE);
    
    printf("Creating data structures...\n");
    Array* array = create_array(ARRAY_SIZE);
    Node* linked_list = create_linked_list(ARRAY_SIZE);
    printf("✓ Data structures created\n\n");
    
    int iterations = 100;
    
    printf("=== Sequential Traversal Benchmark ===\n");
    benchmark("Array (contiguous memory)",  (TraverseFunc)traverse_array, array, iterations);
    benchmark("List  (scattered allocation)", (TraverseFunc)traverse_linked_list, linked_list, iterations);    
    printf("\n");

    printf("Cleaning up...\n");
    free_array(array);
    free_linked_list(linked_list);
    printf("✓ Cleanup complete\n\n");
    
    return 0;
}

Results:

╔════════════════════════════════════════════════════════╗
║     Array vs List: Cache Performance Benchmark        ║
╚════════════════════════════════════════════════════════╝

Test size: 1000000 elements

Creating data structures...
✓ Data structures created

=== Sequential Traversal Benchmark ===
Array (contiguous memory)  :   28.274 ms (sum=49950000000)
List  (scattered allocation):  340.064 ms (sum=49950000000)
Cleaning up...
✓ Cleanup complete

Over 10x difference — the root cause is that pointer chasing in the linked list leads to massive cache misses, while the array’s contiguous layout yields a much higher cache hit rate.

You can use perf to measure cache references and misses:

# Count cache references and misses during program execution
perf stat -e cache-references,cache-misses ./your_program

If a VM lacks access to physical hardware performance counters, use valgrind’s cachegrind tool to simulate cache behavior:

root@slpc:~# valgrind --tool=cachegrind --cache-sim=yes ./array
# ...
==10443== D refs:        101,055,817  (100,040,083 rd   + 1,015,734 wr)
==10443== D1  misses:      6,314,563  (  6,251,637 rd   +    62,926 wr)
==10443== D1  miss rate:         6.2%

root@slpc:~# valgrind --tool=cachegrind --cache-sim=yes ./list
# ...
==11420== D refs:        306,061,821  (270,043,788 rd   + 36,018,033 wr)
==11420== D1  misses:     51,016,462  ( 50,515,889 rd   +    500,573 wr)
==11420== D1  miss rate:        16.7%

Comparing the two:

==10443== D1  miss rate:         6.2%   # array D1 miss rate
==11420== D1  miss rate:        16.7%   # linked list D1 miss rate

The MESI Protocol

MESI is the core mechanism for maintaining cache coherence in modern multi-core CPUs. Each core has its own private L1/L2 caches, while L3 is shared. This creates a coherence problem, solved by MESI, which tags each cache line with one of four states:

StateNameMeaning (plain-language)Coherence
MModified”Dirty data, I own it.” Data has been modified and differs from main memory. Only this core has it.Out of sync
EExclusive”Clean data, I own it.” Matches main memory, and only this core holds it. Can be modified freely.In sync
SShared”Clean data, we all have it.” Matches main memory, and other cores may also have cached it. Must invalidate others before writing.In sync
IInvalid”Garbage.” Data is stale (someone else modified it). Cannot be used — must re-read.Invalid

MESI relies on bus snooping. Think of the system bus as a broadcast channel:

  • Action: When core A wants to read or write memory, it signals on the bus.
  • Snoop: Cores B, C, D all “listen” on this channel.
  • Response: If core B sees core A about to modify data that B also holds (in S state), B marks its copy as I (Invalid).

Example: variable x = 10 in memory, cores A and B both operate on it.

Phase 1: Initial Read (E state)

  • Action: Core A reads x.
  • Result: The bus detects no other core has cached x.
  • State: Core A’s cache line → E (Exclusive).
  • Meaning: A has the latest data, uniquely, and it is clean.

Phase 2: Shared Read (S state)

  • Action: Core B also reads x.
  • Process: Core B issues a read request. Core A snoops this and says “I have that data too.” Core A tells the bus: “I’ve got it, here’s a copy.”
  • State: Both core A and core B’s cache lines → S (Shared).
  • Meaning: Everyone has the data; no one may modify it arbitrarily.

Phase 3: Write (S → M state)

  • Action: Core A wants to execute x = 20.
  • Process: Core A broadcasts an invalidation request: “I’m modifying x — invalidate your copies!” Core B snoops this and immediately marks its x as I (Invalid). Core A, on confirmation, modifies its cached data.
  • State: Core A → M (Modified), Core B → I (Invalid).
  • Meaning: Core A now has the latest data (20), but main memory still holds the old value (10). The write-back to memory happens only when core A evicts this cache line.

False Sharing

False sharing is a performance killer in multi-core programming, caused by the MESI protocol.

The scenario:

  • Variables a and b are completely independent.
  • But they happen to be close enough to land in the same cache line (typically 64 bytes).
  • Core 1 frequently modifies a; core 2 frequently modifies b.

From MESI’s perspective:

  • The cache coherence protocol operates at cache line granularity — it doesn’t know a and b are independent.
  • Core 1 modifies a → entire cache line is invalidated → core 2’s line becomes I.
  • Core 2 modifies b → entire cache line is invalidated → core 1’s line becomes I.

The consequence:

  • The two cores, despite operating on entirely different variables, are furiously “kicking” each other’s cache lines.
  • The cache line bounces between cores (the ping-pong effect), tanking performance.

Solution: Cache line padding — insert unused bytes between variables to force them into separate cache lines.

    // ❌ Wrong: false sharing
    struct Counter {
        long long val1; // written by thread 1
        long long val2; // written by thread 2
        // adjacent val1 and val2 likely share the same 64-byte line
    };

    // ✅ Correct: isolate with padding
    struct Counter {
        long long val1;
        char pad[64 - sizeof(long long)]; // pad to push val2 into the next line
        long long val2;
    };
    
    // C++ standard approach (alignas)
    struct AlignedCounter {
        alignas(64) long long val1;
        alignas(64) long long val2;
    };

Cache Line Alignment

If a data structure (e.g., a lock or a hot counter) straddles two cache lines, accessing it may require loading two lines or trigger extra coherence traffic.

Best practice: align frequently accessed small objects (spinlocks, atomic counters) to 64-byte boundaries.

    struct SpinLock {
        std::atomic<int> flag;
        // ensure the entire struct fills one line and is aligned to avoid sharing
    } __attribute__((aligned(64)));

Observing Cache Behavior

We cannot directly read the contents of L1/L2/L3 caches, but tools can provide indirect insight into cache hits and misses.

Modern CPUs have dedicated hardware counters that track cache behavior:

# Count cache references and misses during program execution
perf stat -e cache-references,cache-misses ./your_program

Cache Line Optimizations in PostgreSQL

In foundational software like databases, where performance demands are extreme, cache line optimization is a mandatory consideration in kernel design.

PostgreSQL sets its cache line size to 128 rather than 64. This accommodates diverse hardware platforms — while x86 uses 64-byte lines, some ARM architectures (e.g., Kunpeng 920 with 128-byte cache lines) already use 128, and the conservative choice future-proofs against hardware evolution.

/*
 * Assumed cache line size. This doesn't affect correctness, but can be used
 * for low-level optimizations. Currently, this is used to pad some data
 * structures in xlog.c, to ensure that highly-contended fields are on
 * different cache lines. Too small a value can hurt performance due to false
 * sharing, while the only downside of too large a value is a few bytes of
 * wasted memory. The default is 128, which should be large enough for all
 * supported platforms.
 */
#define PG_CACHE_LINE_SIZE		128

Locks heavily impact performance, and PG optimizes for this. Taking the lightweight lock LWLock as an example — it protects shared memory variables. Since PostgreSQL uses a multi-process architecture, LWLocks are accessed extremely frequently and their implementation is critical. In C, a union’s size is determined by its largest member. Defining LWLockPadded as a union ensures that no matter how compact LWLock is internally, once placed inside LWLockPadded it is padded to 128 bytes.

typedef struct LWLock
{
	uint16		tranche;		/* tranche ID */
	pg_atomic_uint32 state;		/* state of the exclusive/nonexclusive lockers */
	proclist_head waiters;		/* list of waiting PGPROCs */
} LWLock;

/*
 * It is generally desirable to align each tranche of LWLocks on cache line
 * boundaries and make the array stride a power of 2.
 *
 * This saves a few cycles in indexing, but more importantly ensures that
 * individual LWLocks don't cross cache line boundaries. This reduces cache
 * contention problems, especially on AMD Opterons.
 *
 * In some cases it's also useful to add more padding so that each LWLock
 * takes up an entire cache line; this is useful, for example, in the main
 * LWLock array when the overall number of locks is small but some are very
 * heavily contended.
 */
#define LWLOCK_PADDED_SIZE	PG_CACHE_LINE_SIZE

/* LWLock, padded to a full cache line size */
typedef union LWLockPadded
{
	LWLock		lock;
	char		pad[LWLOCK_PADDED_SIZE];
} LWLockPadded;

WAL insert locks are also cache-line-aligned to prevent false sharing:

typedef struct
{
	LWLock		lock;
	XLogRecPtr	insertingAt;
	XLogRecPtr	lastImportantAt;
} WALInsertLock;

typedef union WALInsertLockPadded
{
	WALInsertLock l;
	char		pad[PG_CACHE_LINE_SIZE];
} WALInsertLockPadded;