LRU and FIFO Cache Simulator in C, Tested on Real Memory Traces

Sum a 256 × 256 matrix of int by rows and a 32 KiB, 8-way cache hits on 93.75% of the reads. Sum the same matrix by columns and it hits on none of them. The cache is not too small; the column’s blocks all land in 4 of its 64 sets. A cache simulator makes effects like that visible, provided its own numbers can be trusted.

This guide builds a set-associative cache simulator in C with LRU and FIFO replacement, feeds it memory traces of a real program recorded with Valgrind, and checks its miss counts against Valgrind’s own cache simulator. Along the way it explains that column-order result, and why a bigger FIFO cache can miss more often than a smaller one. Every program was compiled for this article on Ubuntu 24.04 with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, with -Wall -Wextra -pedantic -Werror and no warnings, and the simulator runs clean under AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind. Traces were recorded with Valgrind 3.22 on x86-64; the Windows build was not run on the test machine. Every output block is captured verbatim, and the code is in a GitHub repository whose workflow repeats these checks, plus an MSVC build, on every commit.

Which “LRU Cache” This Page Is About

“LRU cache” means two different things. This page is about a hardware cache simulator: it models a CPU cache with sets, ways and blocks, and counts hits and misses for a stream of memory addresses. The other meaning is a software LRU cache, a key-value store with a size limit, usually built from a hash table and a doubly linked list in C so lookups and evictions take constant time. Both evict the least recently used entry; the hardware version does it within one small set at a time, which is why it needs no list at all.

What Is a Cache Replacement Policy?

A cache replacement policy decides which block to evict when a new block must be loaded into a full cache set. LRU (least recently used) evicts the block that was accessed longest ago. FIFO (first in, first out) evicts the block that was loaded earliest, no matter how often it has been used since.

The difference shows with two lines and the accesses A, B, A, C. When C arrives, both lines are full. LRU evicts B, because A was used more recently. FIFO evicts A, because A was loaded first; using it again did not reset its place in the queue. LRU usually misses less on real programs, which tend to reuse what they used recently, but it has to record every hit, while FIFO only records loads. Many CPUs use cheaper approximations of LRU, such as tree pseudo-LRU, for the same reason.

How a Set-Associative Cache Finds a Block

A cache with 64-byte blocks splits each address into three fields:

A direct-mapped cache has one line per set, so two blocks with the same set index evict each other. A fully associative cache has one set holding every line, so a block can go anywhere. An N-way set-associative cache is in between: each set holds N blocks, and the replacement policy chooses among those N. The number of sets must be a power of two so the set index is a plain group of bits, but the number of ways need not be; a 48 KiB, 12-way cache with 64-byte blocks also has 64 sets.

This simulator is write-through with write-allocate: every write is passed on to memory, and a write that misses loads the block first, just as a read miss does.

The Source Code

cache.h

/* cache.h - a set-associative cache simulator with LRU and FIFO replacement.
 * Write-through with write-allocate: every write also goes to memory, and a
 * miss on a write loads the block, the same as a miss on a read. */
#ifndef CACHE_H
#define CACHE_H

#include <stdbool.h>
#include <stdint.h>

typedef enum { CACHE_LRU, CACHE_FIFO } cache_policy;

typedef struct {
    uint64_t size;          /* total capacity in bytes                     */
    uint64_t block;         /* block (line) size in bytes, a power of two  */
    uint64_t ways;          /* lines per set; 1 = direct-mapped            */
    /* size must equal block * ways * sets, with sets a power of two.
     * So 48 KiB, 64-byte blocks, 12 ways (64 sets) is fine. */
    cache_policy policy;
} cache_config;

typedef struct {
    uint64_t reads, writes;           /* accesses by the program        */
    uint64_t hits, misses;            /* per block looked up            */
    uint64_t mem_reads, mem_writes;   /* traffic to the next level      */
    uint64_t evictions;               /* valid blocks replaced          */
} cache_stats;

typedef struct cache cache;

/* Returns NULL if the configuration is usable, else a message saying why not. */
const char *cache_config_error(const cache_config *cfg);

/* Returns NULL if the configuration is invalid or memory runs out. */
cache *cache_create(const cache_config *cfg);
void cache_destroy(cache *c);

/* Simulates one access of `size` bytes (at least 1) at `addr`. An access that
 * spans two blocks touches both. Returns true if every block touched hit. */
bool cache_access(cache *c, uint64_t addr, uint64_t size, bool is_write);

const cache_stats *cache_get_stats(const cache *c);
uint64_t cache_sets(const cache *c);

#endif

cache.c

/* cache.c - set-associative cache with LRU or FIFO replacement. */
#include "cache.h"

#include <stdlib.h>

typedef struct {
    uint64_t block;     /* full block number: address >> offset bits       */
    uint64_t stamp;     /* LRU: last use; FIFO: time the block was loaded  */
    bool valid;
} line;

struct cache {
    cache_config cfg;
    uint64_t sets;
    unsigned offset_bits;
    uint64_t clock;     /* increments on every stamp, so stamps are unique */
    cache_stats stats;
    line *lines;        /* sets * ways lines; set s starts at s * ways      */
};

static bool is_power_of_two(uint64_t x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

static unsigned log2_exact(uint64_t x)  /* x is a power of two */
{
    unsigned n = 0;
    while (x > 1) {
        x >>= 1;
        n++;
    }
    return n;
}

const char *cache_config_error(const cache_config *cfg)
{
    if (!is_power_of_two(cfg->block))
        return "block size must be a power of two";
    if (cfg->ways == 0)
        return "associativity must be at least 1";
    if (cfg->size == 0 || cfg->size % cfg->block != 0)
        return "cache size must be a whole number of blocks";
    if ((cfg->size / cfg->block) % cfg->ways != 0)
        return "the number of blocks must be a multiple of the associativity";
    if (!is_power_of_two(cfg->size / cfg->block / cfg->ways))
        return "the number of sets (size / block / ways) must be a power of two";
    if (cfg->policy != CACHE_LRU && cfg->policy != CACHE_FIFO)
        return "unknown replacement policy";
    return NULL;
}

cache *cache_create(const cache_config *cfg)
{
    if (cache_config_error(cfg) != NULL)
        return NULL;
    cache *c = calloc(1, sizeof *c);
    if (c == NULL)
        return NULL;
    c->cfg = *cfg;
    c->sets = cfg->size / cfg->block / cfg->ways;
    c->offset_bits = log2_exact(cfg->block);
    /* calloc: every line starts invalid. */
    c->lines = calloc((size_t)(c->sets * cfg->ways), sizeof *c->lines);
    if (c->lines == NULL) {
        free(c);
        return NULL;
    }
    return c;
}

void cache_destroy(cache *c)
{
    if (c != NULL) {
        free(c->lines);
        free(c);
    }
}

/* Looks up one block; loads it on a miss. Returns true on a hit. */
static bool access_block(cache *c, uint64_t block)
{
    line *set = c->lines + (size_t)((block & (c->sets - 1)) * c->cfg.ways);
    line *victim = NULL;

    for (uint64_t i = 0; i < c->cfg.ways; i++) {
        line *l = &set[i];
        if (l->valid && l->block == block) {
            if (c->cfg.policy == CACHE_LRU)
                l->stamp = ++c->clock;            /* FIFO ignores hits */
            c->stats.hits++;
            return true;
        }
        /* Prefer an empty line; otherwise the oldest stamp. */
        if (victim == NULL || (victim->valid &&
                               (!l->valid || l->stamp < victim->stamp)))
            victim = l;
    }

    c->stats.misses++;
    c->stats.mem_reads++;                         /* load the block */
    if (victim->valid)
        c->stats.evictions++;
    victim->valid = true;
    victim->block = block;
    victim->stamp = ++c->clock;
    return false;
}

bool cache_access(cache *c, uint64_t addr, uint64_t size, bool is_write)
{
    if (size == 0)
        size = 1;
    if (is_write) {
        c->stats.writes++;
        c->stats.mem_writes++;                    /* write-through */
    } else {
        c->stats.reads++;
    }
    const uint64_t first = addr >> c->offset_bits;
    const uint64_t end = addr + (size - 1) < addr ? UINT64_MAX : addr + (size - 1);
    const uint64_t last = end >> c->offset_bits;
    bool hit = true;
    for (uint64_t b = first;; b++) {
        if (!access_block(c, b))
            hit = false;
        if (b == last)
            break;
    }
    return hit;
}

const cache_stats *cache_get_stats(const cache *c)
{
    return &c->stats;
}

uint64_t cache_sets(const cache *c)
{
    return c->sets;
}

Each line stores its full block number rather than only the tag bits, which gives the same comparisons with less arithmetic. The lines live in one array allocated with calloc, so every line starts invalid; using malloc here instead is the first of the mistakes in “Three Mistakes That Break a Cache Simulator” below. The guide to malloc and calloc in C covers the two in detail.

LRU and FIFO differ by one line. Both evict the line with the smallest stamp; LRU updates the stamp on every hit, FIFO only when the block is loaded.

The Trace Reader and the Command-Line Program

trace.c reads two formats, described in its header: simple R/W lines, and the output of Valgrind’s Lackey tool, which records every load, store and modify a real program makes. It reads one line at a time into a fixed buffer and rejects lines that are too long or malformed, with the line number.

/* trace.h - reads memory traces, one access per call.
 *
 * Two line formats are accepted:
 *   R 0x7ffd5a2c        a read or write of one byte; an optional first
 *   W 0x7ffd5a30        field ending in ':' (a program counter) is ignored
 *    L 1ffefffd40,8     Valgrind Lackey: L load, S store, M modify (a load
 *    S 1ffefffd48,8     then a store); I (instruction fetch) lines are
 *    M 0401d1f0,4       skipped
 * Blank lines, lines starting with '#' or '=', and a final "#eof" are skipped. */
#ifndef TRACE_H
#define TRACE_H

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

typedef struct {
    uint64_t addr;
    uint64_t size;
    bool is_write;
} trace_access;

typedef struct {
    FILE *in;
    unsigned long line;     /* number of the line last read */
    bool pending_store;     /* second half of a Lackey M line */
    trace_access pending;
} trace_reader;

void trace_init(trace_reader *r, FILE *in);

/* Returns 1 with *out filled, 0 at end of input, or -1 on a malformed or
 * over-long line (r->line says which). */
int trace_next(trace_reader *r, trace_access *out);

#endif

cachesim.c takes five arguments: cache size, associativity, policy, block size and trace file, with - for standard input. Every number is checked, and a bad argument or a bad trace line stops it with a message and a non-zero exit status.

/* cachesim.c - runs a memory trace through a simulated cache.
 * Usage: cachesim <cache bytes> <direct|assoc|assoc:N> <lru|fifo> <block bytes> <trace file|->
 * Example: cachesim 32768 assoc:8 lru 64 trace.txt */
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "cache.h"
#include "trace.h"

static void usage(void)
{
    fprintf(stderr, "usage: cachesim <cache bytes> <direct|assoc|assoc:N> <lru|fifo> "
                    "<block bytes> <trace file|->\n");
}

/* Parses a whole decimal argument; rejects signs, spaces, junk and overflow. */
static int parse_count(const char *s, uint64_t *out)
{
    if (*s < '0' || *s > '9')
        return 0;
    char *end;
    errno = 0;
    const unsigned long long v = strtoull(s, &end, 10);
    if (errno == ERANGE || *end != '\0')
        return 0;
    *out = (uint64_t)v;
    return 1;
}

int main(int argc, char **argv)
{
    if (argc != 6) {
        usage();
        return 2;
    }
    cache_config cfg = {0};
    if (!parse_count(argv[1], &cfg.size) || !parse_count(argv[4], &cfg.block)) {
        usage();
        return 2;
    }
    if (strcmp(argv[3], "lru") == 0)
        cfg.policy = CACHE_LRU;
    else if (strcmp(argv[3], "fifo") == 0)
        cfg.policy = CACHE_FIFO;
    else {
        usage();
        return 2;
    }
    if (strcmp(argv[2], "direct") == 0)
        cfg.ways = 1;
    else if (strcmp(argv[2], "assoc") == 0)
        cfg.ways = cfg.block != 0 ? cfg.size / cfg.block : 0;     /* fully associative */
    else if (strncmp(argv[2], "assoc:", 6) != 0 || !parse_count(argv[2] + 6, &cfg.ways)) {
        usage();
        return 2;
    }
    const char *problem = cache_config_error(&cfg);
    if (problem != NULL) {
        fprintf(stderr, "cachesim: %s\n", problem);
        return 2;
    }

    FILE *in = strcmp(argv[5], "-") == 0 ? stdin : fopen(argv[5], "r");
    if (in == NULL) {
        fprintf(stderr, "cachesim: cannot open %s: %s\n", argv[5], strerror(errno));
        return 1;
    }
    cache *c = cache_create(&cfg);
    if (c == NULL) {
        fprintf(stderr, "cachesim: out of memory\n");
        return 1;
    }

    trace_reader r;
    trace_init(&r, in);
    trace_access a;
    int status;
    while ((status = trace_next(&r, &a)) == 1)
        cache_access(c, a.addr, a.size, a.is_write);
    if (in != stdin)
        fclose(in);
    if (status < 0) {
        fprintf(stderr, "cachesim: %s: line %lu is not a trace line\n", argv[5], r.line);
        cache_destroy(c);
        return 1;
    }

    const cache_stats *s = cache_get_stats(c);
    const uint64_t lookups = s->hits + s->misses;
    printf("Cache: %llu bytes, %llu-byte blocks, %llu-way, %llu set%s, %s\n",
           (unsigned long long)cfg.size, (unsigned long long)cfg.block,
           (unsigned long long)cfg.ways, (unsigned long long)cache_sets(c),
           cache_sets(c) == 1 ? "" : "s", cfg.policy == CACHE_LRU ? "LRU" : "FIFO");
    printf("Memory reads: %llu\n", (unsigned long long)s->mem_reads);
    printf("Memory writes: %llu\n", (unsigned long long)s->mem_writes);
    printf("Cache hits: %llu\n", (unsigned long long)s->hits);
    printf("Cache misses: %llu\n", (unsigned long long)s->misses);
    printf("Hit rate: %.2f%%\n", lookups ? 100.0 * (double)s->hits / (double)lookups : 0.0);
    cache_destroy(c);
    return 0;
}

Build and Run

gcc -std=c11 -Wall -Wextra -pedantic -O2 src/cachesim.c src/cache.c src/trace.c -o cachesim

small.trace in the repository has eight accesses to four blocks. In a two-line fully associative cache, LRU and FIFO give different results:

$ ./cachesim 128 assoc:2 lru 64 small.trace
Cache: 128 bytes, 64-byte blocks, 2-way, 1 set, LRU
Memory reads: 6
Memory writes: 2
Cache hits: 2
Cache misses: 6
Hit rate: 25.00%
$ ./cachesim 128 assoc:2 fifo 64 small.trace
Cache: 128 bytes, 64-byte blocks, 2-way, 1 set, FIFO
Memory reads: 7
Memory writes: 2
Cache hits: 1
Cache misses: 7
Hit rate: 12.50%

“Memory reads” counts blocks loaded on a miss, so it equals the misses; “Memory writes” counts writes, because each one goes through to memory.

Tracing a Real Program with Valgrind

matrix_sum.c fills a 256 × 256 matrix of int and adds it up, either row by row or column by column. In C a two-dimensional array is stored row by row, as the guide to arrays in C and C++ explains, so the row loop reads memory in order and the column loop jumps 1,024 bytes at a time. Valgrind’s Lackey tool records every memory access the program makes, about three million lines each, and the simulator replays them through a 32 KiB, 8-way cache with 64-byte blocks, a common L1 data cache size:

$ valgrind --tool=lackey --trace-mem=yes --log-file=row.trace ./matrix_sum row
sum = 16711680
$ ./cachesim 32768 assoc:8 lru 64 row.trace
Cache: 32768 bytes, 64-byte blocks, 8-way, 64 sets, LRU
Memory reads: 10033
Memory writes: 276818
Cache hits: 1108908
Cache misses: 10033
Hit rate: 99.10%
$ valgrind --tool=lackey --trace-mem=yes --log-file=col.trace ./matrix_sum col
sum = 16711680
$ ./cachesim 32768 assoc:8 lru 64 col.trace
Cache: 32768 bytes, 64-byte blocks, 8-way, 64 sets, LRU
Memory reads: 71473
Memory writes: 276819
Cache hits: 1047477
Cache misses: 71473
Hit rate: 93.61%

The two programs make almost the same number of accesses and do the same arithmetic. The column order misses 71,473 times against 10,033, about seven times as often. Both hit rates still look high because the program was built without optimization, so the trace includes every access to the loop counters and the running sum on the stack, which almost always hit.

To check the simulator, the same two programs were run under Cachegrind, Valgrind’s built-in cache simulator, configured with the same 32 KiB, 8-way, 64-byte data cache:

row: D1  misses:       10,029  (  5,533 rd   +  4,496 wr)
col: D1  misses:       71,469  ( 66,973 rd   +  4,496 wr)

The two simulators agree to within 4 misses out of about 10,000 and 71,000. They are separate runs, and the program’s stack addresses move slightly between runs, which changed the simulator’s own count by a few misses from run to run; Cachegrind also counts an instruction that reads and writes the same location as a single access, where Lackey reports a load and a store. Agreement this close from two independent implementations is good evidence that both model the cache the same way. The Cachegrind manual documents its simulator, including write-allocate on write misses.

Why the Column Walk Misses

The real trace mixes in other accesses. matrix_trace prints only the 65,536 matrix reads, so the effect of the access pattern is exact:

By rows, each 64-byte block holds 16 consecutive ints, so one access in 16 misses: 93.75%. By columns, the same cache misses every single time. Making the cache fully associative, same size, brings the column walk back to 93.75%, which shows the problem is not capacity: a column touches 256 blocks and the cache holds 512.

The problem is conflict misses. Consecutive rows are 1,024 bytes apart, 16 blocks, so the set index advances by 16 each row and wraps after 4 rows. All 256 blocks of a column land in just 4 of the 64 sets, 64 blocks competing for each set’s 8 ways. LRU evicts each block long before the next column comes back for it. Padding each row to 257 ints changes the stride to 1,028 bytes, and the same column spreads across all 64 sets, 4 or 5 blocks each. The cost is one unused int per row; the gain is the difference between 0% and 93.39%.

This is why matrix libraries pad rows and why “transpose a power-of-two matrix” is a classic slow case. On real hardware, prefetchers and larger L2 caches soften the effect, so the simulated numbers are not a timing prediction; they show which accesses can reuse a block at all.

Belady’s Anomaly: When a Bigger Cache Misses More

Intuition says more cache lines can only help. For LRU that is true. For FIFO it is not, and belady.c shows the classic case from page replacement:

References: 1 2 3 4 1 2 5 1 2 3 4 5
Lines  FIFO misses  LRU misses
    1           12          12
    2           12          12
    3            9          10
    4           10           8
    5            5           5

With three lines FIFO misses 9 times; give it a fourth line and it misses 10 times. LRU goes from 10 misses to 8, as expected. László Bélády and colleagues described this in Communications of the ACM in 1969. LRU cannot show the anomaly because it is a stack algorithm: the blocks held by a smaller LRU cache are always a subset of those held by a larger one. FIFO has no such property, so adding a line can change which blocks get evicted for the worse.

Three Mistakes That Break a Cache Simulator

A simulator that prints plausible numbers can still be wrong, and nothing in its output says so. Three mistakes are easy to make in C, and the tests in the repository were checked by putting each of them back on purpose.

Testing a flag nobody set. malloc does not clear memory, so a line allocated with it has a valid field holding whatever was there before. On Linux a fresh heap is usually zero, so the code appears to work. uninitialized_lines.c in the repository’s pitfalls directory runs five accesses to two blocks through a two-way set allocated that way; the correct answer is 3 hits. Run it normally, then with glibc’s MALLOC_PERTURB_ variable, which fills new allocations with a pattern:

$ ./uninitialized_lines
5 accesses to 2 blocks in a 2-way set: 3 hits
$ MALLOC_PERTURB_=165 ./uninitialized_lines
5 accesses to 2 blocks in a 2-way set: 0 hits

Same program, same accesses, different answer. Valgrind reports Conditional jump or move depends on uninitialised value(s) on the valid test. cache_create() uses calloc, and when the unit tests were run against a version that filled the lines with a non-zero pattern instead, six tests failed.

Storing addresses in an int. Traces from a 64-bit program contain addresses such as 1ffefffd40, wider than 32 bits. Read into an int, 0x7ffd00000100 and 0x7ffe00000100 become the same number, and the second access is counted as a hit on a block that was never loaded. The reader here uses uint64_t and strtoull and rejects values that do not fit; a unit test checks that those two addresses are different blocks.

Reading input without a limit. fscanf(file, "%s", buf) copies a token of any length into buf, so one long field in a trace file overflows it. A trace file is input like any other. trace.c reads each line with fgets into a fixed buffer, reports over-long and malformed lines with their line number, and cachesim.c checks every argument before using it.

Make It Your Own

• Write-back caches. Add a dirty bit to each line, count a memory write only when a dirty block is evicted, and compare the memory traffic with write-through.
• A second level. Send misses from one cache to a larger, slower one; the API already returns whether each access hit.
• Pseudo-LRU. Real 8-way caches often use a tree of bits instead of timestamps. Add it as a third policy and compare it with LRU on the matrix traces.
• Your own program. Record a trace of anything with valgrind --tool=lackey --trace-mem=yes --log-file=prog.trace ./prog. Traces are large: the 256 × 256 matrix sum produced about 3 million lines and 45 MB, so start with something small.

Key Takeaways

• LRU evicts the least recently used block; FIFO evicts the oldest loaded block. They differ by whether a hit updates the block’s timestamp.
• Access order can matter more than cache size. Summing a 256 × 256 matrix by columns missed on 100% of accesses in a 32 KiB, 8-way cache, against 6.25% by rows.
• Those were conflict misses, not capacity misses: a fully associative cache of the same size, or rows padded to 257 ints, fixed them.
• FIFO can miss more with more lines (Belady’s anomaly, 9 misses with 3 lines and 10 with 4); LRU never does.
• Check a simulator against an independent one. This one agreed with Cachegrind to within 4 misses on real traces.
• Initialize what you test. Lines allocated with malloc instead of calloc gave 3 hits or 0 on the same five accesses, depending on what the allocator returned.

Conclusion

A cache simulator is a small program with a large payoff: it turns “access memory in order” from advice into a number you can measure, and it shows effects that are hard to see any other way, like a column walk that never hits or a cache that gets worse when it grows. The numbers are only as good as the simulator, though, which is why this one is tested against hand-checked traces, a known anomaly and an independent simulator.

Try it on your own code next. A trace of the loop you think is slow will show whether it misses because the data is too big or because it is laid out badly, and those need different fixes. More C programs and tutorials are in the C programming section.

Source Code and Tests

All programs on this page are in the memory/cache-simulator directory of the MYCPLUS C examples repository.

Build and test:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the build checks. It compiles with GCC and Clang under C11 and C17 on Linux and with MSVC on Windows, treating warnings as errors. The unit tests cover configuration checks, the A, B, A, C example for LRU and FIFO, Belady’s anomaly, 48-bit addresses, accesses that span two blocks, write-through counts and the trace parser on good and malformed lines. belady and cachesim must print exactly the outputs on this page for the small traces and all four matrix cases, and bad arguments and malformed traces must be rejected. On Linux, uninitialized_lines must print 3 hits normally and 0 with MALLOC_PERTURB_=165. A sanitizer build runs everything under AddressSanitizer and UndefinedBehaviorSanitizer, and on Linux the workflow records real Lackey traces of matrix_sum and checks that the column order misses more than five times as often as the row order. The exact real-trace counts and the Cachegrind comparison above were run once for this article; they vary by a few misses between runs.