Cache-Aware Data Layout

Why this lesson matters

In Low-Latency C++ for HFT, you learned that the hot path is where nanoseconds disappear. You also saw the first version of a layout experiment.

Now we go one level deeper: how should market state be arranged in memory so the CPU can reach it quickly and predictably?

A trading loop often looks simple:

market event -> find instrument -> update state -> check signal -> maybe act

But inside that loop, data layout decides whether the CPU touches a few nearby bytes or waits on scattered memory.

Today we focus on:

• cache lines and locality,
• padding and struct size,
• hot/cold field separation,
• arrays versus pointers,
• practical layout choices for instrument state.

We will stay inside one process and mostly one thread. Networking comes next in Networking & Kernel Bypass.

The CPU fetches neighborhoods

Your code may ask for one field, like best_bid, but the CPU usually fetches a small block of nearby memory called a cache line.

A common cache line size is 64 bytes. Exact details vary, but the mental model is useful:

Memory bytes:
[ 0 ... 63 ][ 64 ... 127 ][ 128 ... 191 ]
   line A       line B          line C

Read one double inside line A -> nearby fields in line A may arrive too

This is why nearby data can be cheap, and far-away data can be expensive.

For trading state, ask:

When one quote update arrives, which fields do I almost always read or write?

Those are your hot fields. They should be easy for the CPU to fetch together.

A strategy receives a quote update and immediately reads bid, ask, and last_sequence for the same instrument.

Which layout is most cache-friendly for that hot path?

Struct layout is not just your field list

C++ may insert padding bytes so fields are properly aligned. This is normal and usually helpful for the CPU, but it means two structs with the same fields can have different sizes.

Compile and run this small check:

g++ -O2 -std=c++17 padding_check.cpp && ./a.out

Notice how field order changes memory size. In a trading engine that stores millions of events or instrument states, extra bytes can affect cache pressure.

```cpp
#include <cstdint>
#include <iostream>

struct PoorOrder {
    char type;          // 1 byte
    double price;       // 8 bytes, often needs alignment
    std::uint32_t qty;  // 4 bytes
    char venue;         // 1 byte
};

struct BetterOrder {
    double price;       // 8 bytes
    std::uint32_t qty;  // 4 bytes
    char type;          // 1 byte
    char venue;         // 1 byte
};

int main() {
    std::cout << "sizeof(PoorOrder)=" << sizeof(PoorOrder) << "\n";
    std::cout << "sizeof(BetterOrder)=" << sizeof(BetterOrder) << "\n";

    std::cout << "PoorOrder fields:  type, price, qty, venue\n";
    std::cout << "BetterOrder fields: price, qty, type, venue\n";
}
```

Do not drag cold data through the hot path

A beginner-friendly cache rule:

Keep data needed on every event separate from data needed only for logging, display, or debugging.

For an instrument, hot fields might be:

• bid
• ask
• last_trade
• seq

Cold fields might be:

• full symbol string
• exchange description
• debug counters
• last error text

The example below compares scanning compact hot state versus scanning a large mixed struct. Results vary by machine, but the habit is the point: measure the layout you expect to be hot.

```cpp
#include <chrono>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

struct MixedInstrument {
    double bid;
    double ask;
    double last_trade;
    std::uint64_t seq;
    char symbol[24];
    char venue[16];
    std::uint64_t debug_counter;
};

struct HotInstrument {
    double bid;
    double ask;
    double last_trade;
    std::uint64_t seq;
};

volatile double sink = 0.0;

template <typename F>
long long time_ns(F&& f) {
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
}

int main() {
    constexpr std::size_t N = 2'000'000;

    std::vector<MixedInstrument> mixed(N);
    std::vector<HotInstrument> hot(N);

    for (std::size_t i = 0; i < N; ++i) {
        double p = 100.0 + static_cast<double>(i % 100) * 0.01;
        mixed[i].bid = p;
        mixed[i].ask = p + 0.01;
        mixed[i].last_trade = p - 0.02;
        mixed[i].seq = i;
        mixed[i].debug_counter = 0;

        hot[i] = HotInstrument{p, p + 0.01, p - 0.02, i};
    }

    double sum_mixed = 0.0;
    auto mixed_ns = time_ns([&] {
        for (const auto& x : mixed) {
            sum_mixed += x.bid + x.ask;
        }
    });

    double sum_hot = 0.0;
    auto hot_ns = time_ns([&] {
        for (const auto& x : hot) {
            sum_hot += x.bid + x.ask;
        }
    });

    sink = sum_mixed + sum_hot;

    std::cout << "sizeof(MixedInstrument)=" << sizeof(MixedInstrument) << "\n";
    std::cout << "sizeof(HotInstrument)=" << sizeof(HotInstrument) << "\n";
    std::cout << "mixed_scan_ns=" << mixed_ns << "\n";
    std::cout << "hot_scan_ns=" << hot_ns << "\n";
    std::cout << "checksum=" << sink << "\n";
}
```

True or false: The smallest possible struct layout is always the fastest layout for a trading hot path.

Contiguous beats scattered for predictable scans

A pointer is not slow by itself. The problem is where it points.

If each instrument state lives in a separate heap allocation, the CPU may jump around memory:

vector of pointers -> object -> object -> object
                    scattered across memory

For many hot-path loops, a contiguous vector is easier for the CPU to prefetch:

vector of objects -> [state][state][state][state]

Run this example and compare the timing on your machine.

```cpp
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <memory>
#include <vector>

struct InstrumentState {
    double bid;
    double ask;
    std::uint64_t seq;
};

volatile double sink = 0.0;

template <typename F>
long long time_ns(F&& f) {
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
}

int main() {
    constexpr std::size_t N = 1'000'000;

    std::vector<InstrumentState> contiguous(N);
    std::vector<std::unique_ptr<InstrumentState>> scattered;
    scattered.reserve(N);

    for (std::size_t i = 0; i < N; ++i) {
        double p = 50.0 + static_cast<double>(i % 50) * 0.01;
        contiguous[i] = InstrumentState{p, p + 0.01, i};
        scattered.push_back(std::make_unique<InstrumentState>(InstrumentState{p, p + 0.01, i}));
    }

    double sum1 = 0.0;
    auto contiguous_ns = time_ns([&] {
        for (const auto& s : contiguous) {
            sum1 += s.bid;
        }
    });

    double sum2 = 0.0;
    auto scattered_ns = time_ns([&] {
        for (const auto& p : scattered) {
            sum2 += p->bid;
        }
    });

    sink = sum1 + sum2;

    std::cout << "contiguous_scan_ns=" << contiguous_ns << "\n";
    std::cout << "scattered_pointer_scan_ns=" << scattered_ns << "\n";
    std::cout << "checksum=" << sink << "\n";
}
```

The CPU often fetches nearby memory in fixed-size chunks commonly called cache ____.

Array of structs or struct of arrays?

There is no single winner. Pick based on the access pattern.

Array of structs, or AoS

[bid ask seq][bid ask seq][bid ask seq]

Good when each event works on one instrument and needs several fields together.

Example: update one instrument, then check its bid/ask spread.

Struct of arrays, or SoA

bids: [bid bid bid]
asks: [ask ask ask]
seqs: [seq seq seq]

Good when scanning one field across many instruments.

Example: find all instruments with bid > threshold.

HFT-friendly rule

Design around the operation you do most often, not the structure that looks nicest on a whiteboard.

A practical review before optimizing

When you add state to the trading lab, review the layout before it lands in the hot path.

Ask these questions:

1. What fields are touched on every market event?

   • Keep those compact and nearby.

2. What fields are cold?

   • Move strings, diagnostics, descriptions, and rarely used metadata away from hot state.

3. Will this grow during trading?

   • Pre-size containers during startup when possible.

4. Am I scanning many instruments or updating one?

   • This guides AoS versus SoA.

5. Did I measure the layout?

   • Use timing experiments before claiming improvement.

The next lesson zooms outward from memory layout to packets, sockets, and the network boundary. The same principle stays alive: know the path, then remove avoidable work.

One Pager Cheat Sheet

• Cache-aware layout reduces hot-path waiting by keeping frequently used trading state close and predictable.
• A cache line is a small memory neighborhood; hot fields should live where one fetch brings useful nearby data.
• Fields used together in the hot path should usually be stored together.
• C++ padding can change struct size; field order matters when many objects must fit efficiently in cache.
• Separate hot fields from cold metadata so scans and updates move fewer useless bytes through cache.
• Small structs help cache density, but measured access patterns matter more than size alone.
• Pointer-heavy layouts can force scattered memory access; contiguous vectors often make hot scans more predictable.
• Cache lines are the memory chunks the CPU moves and reuses.
• Use AoS when touching many fields of one item; use SoA when scanning one field across many items.
• Review hot fields, cold fields, growth, access pattern, and measurements before accepting a hot-path layout.