Memory Models in C++

Part II · Module 27 · Chapter 27.8 · Memory Models in C++

1. Why Sparse

The arithmetic settles it before any design discussion:

A. a flat array for a 32-bit byte-addressed space
   2^32 bytes = 4.0 GiB -- not allocatable, and 99% of it never touched

A 32-bit byte address space is four gibibytes. A 40-bit one is a tebibyte. Allocating that to run a test that touches a few thousand addresses is not a performance problem, it is an impossibility — and the second clause matters as much as the first: nearly all of it is never touched, so the memory you allocated would be answering questions nobody asked.

So the model stores only what has been written, which makes it an associative structure: a mapping from address to content. The question is what the key and the value are, and §3 is why that question cannot be answered in the abstract.

2. The Two Structures

Byte-granular. One entry per written byte.

using ByteMap = std::map<std::uint64_t, std::uint8_t>;

Exact, trivially correct, and it stores per-byte bookkeeping — which is what you want if you care about which bytes were written.

Page-granular. One entry per block of addresses, holding an array.

static const std::size_t kPage = 4096;
using PageMap = std::map<std::uint64_t, std::array<std::uint8_t, kPage>>;

One allocation serves 4,096 addresses, so sequential access is cheap — and a page touched once costs a whole page.

The folklore answer is that the page map is obviously better because it amortises. That is true for one access pattern and badly false for the other.

3. The Footprint, Measured

A thousand addresses, each structure, two access patterns. Allocation counted through a global operator new override, because std::map allocates its nodes there and a container-local allocator never sees it — a mistake this track has made twice before, in Modules 20 and 21, where a counting allocator reported allocs=0 and measured nothing.

B. 1000 SCATTERED addresses, 1 MiB apart
   std::map<addr,byte>  allocs=1000  bytes=  48000  (48.0 bytes/addr)
   page map (4 KiB)     allocs=1000  bytes=4136000  (4136.0 bytes/addr)

C. 1000 CLUSTERED addresses, consecutive
   std::map<addr,byte>  allocs=1000  bytes=  48000  (48.0 bytes/addr)
   page map (4 KiB)     allocs=   1  bytes=   4136  (4.1 bytes/addr)

The same two structures swap places, and nothing changed but the access pattern. Three things to take from that.

The byte map is pattern-independent. 48 bytes per address either way — a red-black tree node holding a 64-bit key and one byte of data, with the pointers and colour bit. It never wins big and it never loses big, which makes it the right default when you do not know the pattern.

The page map is a bet on locality, and the bet is leveraged both ways. Clustered, it is 4.1 bytes per address — better than the data itself, because one allocation amortises over 4,096 addresses. Scattered, it is 4,136 bytes per address, allocating an entire page to hold one byte. That is a factor of a thousand between its best and worst case, which is a much wider spread than the choice of container usually implies.

And "scattered" here is not pathological. One mebibyte apart is what a test walking a page table, touching one descriptor per region, or probing the corners of an address map actually does. A DMA test writing a contiguous buffer is the clustered case. Real regressions contain both, which is the argument for measuring your own workload rather than adopting either answer.

The page size is the tuning knob, and it moves the break-even: a 64-byte page would cost 64 bytes per scattered address instead of 4,136 and still amortise over 64 consecutive ones. If you choose the page structure, choose the page size from the measured stride of your accesses, not from the host's page size, which has nothing to do with it.

4. Access Widths

Hardware is word-addressed with byte enables, and the model has to match the design's actual capability rather than C++'s convenience.

Three questions the specification answers and the model must encode:

Can software write one byte of a 32-bit word? If the design has byte enables, yes, and the other three bytes keep their values. If it does not, a byte write is either ignored or faults — and a model that cheerfully updates one byte will disagree.

What about an unaligned access? A 32-bit read at address 0x1002 is either a fault, or split into two accesses, or silently truncated to the aligned address. These are three completely different behaviours and the model must pick the specified one.

And what happens at a page or region boundary? A burst crossing from a mapped region into an unmapped one is the case nobody models and the one where designs differ most.

The structure that keeps this honest is to make the model's interface mirror the bus rather than memory:

// not: std::uint8_t& at(addr)
// but: the operations the bus actually has
std::uint32_t read32(std::uint64_t addr);
void write32(std::uint64_t addr, std::uint32_t data, std::uint8_t byteEnables);

Taking byte enables as a parameter rather than inferring them forces every caller to say what the bus said, and makes the partial-write case the normal path rather than a special one. A model whose only entry point is a byte reference has already decided that every design supports byte writes.

5. The Initialisation Policy

This is the decision that silently determines whether a class of bug is detectable, and it has three defensible answers.

The zero policy is the default nobody chose, because it is what std::map::operator[] does and what a calloced array does. Its weakness is specific: if the design has a bug where it reads an address it never wrote, and the hardware happens to return zero, and the model returns zero — the comparison passes. The bug is real, the data is wrong, and the regression is green.

The tracked policy is the strongest and costs one bit per byte or one std::set of written addresses. A read of an untracked address is then a finding in its own right, reported independently of whether the value matched:

std::optional<std::uint8_t> peek(std::uint64_t addr) const;   // empty = never written

Returning std::optional makes the uninitialised case impossible to ignore — Chapter 22.7 §2's argument for optional as a return type, applied to a case where the absence genuinely means something.

And whichever you choose, the design's real behaviour must be matched. If the DUT's memory comes out of reset as zeros, the model has to too, and then the tracking is a separate channel — the value is zero, and the model additionally knows nobody wrote it. Those two facts are both needed: the comparison uses the value, and the report uses the tracking.

6. What Else the Model Owns

Three responsibilities beyond storing bytes.

Regions and their attributes. A real address map has ranges with different behaviour — read-only firmware, write-through, device memory where a read has a side effect, holes. A single flat mapping cannot express that, so the model is usually a list of regions, each with its own storage and rules, and a decode step in front — the same shape as Chapter 27.7 §5's register map, and for the same reason.

The unmapped case, explicitly. Chapter 27.7 §5's onUnmappedRead hook applies unchanged: a read outside every region does something the specification names, and defaulting it to zero is choosing an answer by accident.

And loading and dumping. A memory model that cannot be preloaded from a file cannot run a firmware image, and one that cannot be dumped cannot be compared at the end of a test or inspected after a failure. Both want the sparse format — address and data pairs, or a standard hex format — and Chapter 23.8's file discipline applies: a header saying what produced it, and a reader that refuses what it does not understand rather than skipping it.

7. Choosing, Concretely

A short decision procedure, given §3's result that there is no universal answer.

Start with the byte map. It is pattern-independent at 48 bytes per address, trivially correct, and it gives per-byte tracking for free. For the overwhelming majority of tests — thousands or tens of thousands of addresses — 48 bytes each is nothing at all, and the right answer is to stop thinking about it.

Measure before switching. The page structure is a bet on locality and §3 shows the bet losing by 86× when the pattern is scattered. The thing to measure is your own access stride, and the thing to count is allocations through global operator new, which is the only place the containers' own allocations are visible.

And size the page from the stride if you do switch — 64 or 256 bytes is often right for a model, and the host's 4,096 is almost never the relevant number.

The scale check that makes this concrete: a test touching 100,000 addresses costs 4.8 MB in the byte map. That is irrelevant on any machine this will run on, which means the structural question only becomes real for models holding tens of millions of addresses — a full firmware image, a frame buffer, a long DMA soak — and those are exactly the cases that are clustered and where the page map wins.

8. The Table

9. What to Actually Do

• Store only what was written. A flat array for a real address space is not an option.
• Default to the byte-granular map. 48 bytes per address, pattern-independent, per-byte tracking included.
• Measure your access stride before switching to pages, and count allocations through a global operator new override.
• Size the page from the measured stride, not from the host page size.
• Make the interface mirror the bus — sized accesses with explicit byte enables, not a byte reference.
• Decide the unaligned and boundary-crossing behaviour from the specification, and encode it.
• Choose the initialisation policy deliberately, and prefer tracking which addresses were written — returning std::optional from the peek path.
• Use find, never operator[], on any read path, and declare that path const so the compiler enforces it.
• Model regions with attributes and an explicit unmapped-address behaviour.
• Support preload and dump in a sparse format, with a header and a reader that refuses what it does not understand.

10. Mistakes Worth Making Once

A flat array for a 32-bit space. 4 GiB, 99% untouched.

A page map for scattered accesses. 4,136 bytes to store one byte.

A byte map for a 64 MB firmware image. 48 bytes per address, where 1 would do.

Choosing 4,096 as the page size because the host does. The relevant number is your access stride.

Counting allocations with a container-local allocator. It reports zero and measures nothing.

operator[] on the read path. The model now believes an address was written because something asked about it.

Returning zero for unwritten addresses by default. A design that reads uninitialised memory and gets zero now passes.

A byte-reference interface. You have assumed every design supports byte writes.

Ignoring unaligned accesses. Three plausible behaviours, and the model silently picked one.

No preload or dump. The model cannot run a firmware image or be inspected after a failure.

11. Interview Relevance

The frozen curriculum marks this High, and the question is usually how would you model a large memory? The expected answer is "sparsely, with a hash map or a tree". That is correct and thin, and there are three ways to go deeper.

The structure choice is a measurement, not a preference. Say that you default to a byte-granular ordered map and switch to page granularity only on evidence, then give the numbers: for a thousand addresses a mebibyte apart, the byte map cost 48 bytes per address and a 4 KiB page map cost 4,136 — 86× worse; for a thousand consecutive addresses the page map cost 4.1 bytes per address and won by 11.7×. The same two structures swapping places on nothing but the access pattern is the whole point, and it pre-empts the "just use pages" instinct.

The interface should mirror the bus. Sized accesses with explicit byte enables rather than a byte reference, because whether the design supports a byte write into a word is a property of the design and the model must not assume it. Mentioning unaligned and boundary-crossing accesses as specification questions shows you have read one.

And the initialisation policy is the senior point. A model that returns zero for an address nobody wrote agrees with a design that reads uninitialised memory and happens to get zero, so the bug passes. Tracking which addresses were written — and returning std::optional from the inspection path — turns that into a reportable finding. If there is room, the operator[] trap is a memorable detail: a read through operator[] inserts the key, so the model's record of which addresses were written is corrupted by the act of checking it, and the fix is find plus a const read path so the compiler enforces it.

12. What You Should Be Able to Say Now

• That a flat array is impossible — 2^32 bytes is 4.0 GiB and almost none of it is touched — so the model is associative.
• That for scattered addresses a byte map cost 48 B/addr against the page map's 4,136 B/addr — 86× worse — and for clustered addresses the page map cost 4.1 B/addr and won by 11.7×.
• That the byte map is pattern-independent and therefore the right default, and that the page map's spread between best and worst case is about a thousandfold.
• That "scattered" is not pathological — page tables, address-map corners and descriptor walks all look like it.
• That the page size should come from the measured access stride, not the host page size.
• That allocation must be counted through a global operator new, because container-local allocators never see std::map's node allocations.
• That the interface should mirror the bus — sized accesses with explicit byte enables — and that unaligned and boundary-crossing behaviour are specification questions.
• The three initialisation policies, and that zero is the dangerous default because it agrees with a design reading uninitialised memory.
• That operator[] inserts on read, corrupting the written-address set, and that find plus a const read path is the fix the compiler can enforce.
• That 100,000 addresses in the byte map is 4.8 MB, so the structural question is only real for very large models — which are usually the clustered ones.

13. Exercises

Exercise 1 — the footprint. Build both structures, count allocations and bytes through a global operator new, and reproduce §3's four rows.

Exercise 2 — find the break-even. Vary the stride from 1 to 4,096 bytes and find where the two structures cross. Then vary the page size and watch the crossing move.

Exercise 3 — the local allocator trap. Try to measure the same thing with a container-local counting allocator and confirm it reports nothing.

Exercise 4 — the insert on read. Reproduce §5's transcript. Then build a model that tracks written addresses, read an unwritten one through operator[], and confirm the tracking is now wrong.

Exercise 5 — make it impossible. Give your model a const read path returning std::optional and confirm operator[] no longer compiles there.

Exercise 6 — byte enables. Implement write32 with byte enables and test a partial write. Then implement the variant where the design does not support them, and confirm the two models disagree on that access.

Exercise 7 — the initialisation policy. Run a test where the DUT reads an address it never wrote. Confirm the zero-policy model passes it and the tracked-policy model reports it.

14. Summary

• A memory model must be sparse: a 32-bit byte space is 4.0 GiB and nearly all of it is never touched.
• Measured, 1,000 addresses: scattered 1 MiB apart, the byte map cost 48 bytes per address and a 4 KiB page map cost 4,136 — 86× worse. Clustered consecutively, the page map cost 4.1 bytes per address with a single allocation and won by 11.7×.
• The same two structures swap places on nothing but the access pattern, so there is no universal answer; the byte map is pattern-independent at 48 bytes per address and is the right default.
• Count allocations through a global operator new. A container-local allocator never sees std::map's nodes — a mistake this track has made twice.
• Size a page from the measured access stride, never from the host's page size.
• Make the interface mirror the bus: sized accesses with explicit byte enables, plus specified behaviour for unaligned and boundary-crossing accesses.
• Choose the initialisation policy deliberately. Returning zero for an unwritten address agrees with a design that reads uninitialised memory and gets zero, so the bug passes; tracking which addresses were written turns it into a finding, and std::optional makes that impossible to ignore.
• operator[] inserts on read — measured: reading an untouched address returned 0x00 and grew the map from one entry to two — which corrupts the written-address set by the act of checking it. find does not insert, and a const read path makes the compiler enforce that.
• Model regions with attributes and an explicit unmapped-address behaviour, and support sparse preload and dump so the model can run a firmware image and be inspected after a failure.
• And keep the scale in view: 100,000 addresses is 4.8 MB in the byte map, so the structural question only becomes real for models an order of magnitude larger — which are usually clustered, and where the page map is the right bet.

Chapter 27.9 is the other half of data modelling: turning a packet specification into types whose layout and byte order are stated rather than inherited.