4 - Cost is layout - and you have a budget

Concept node: see the DAG and glossary entry 4.

A system is not handed a target rate; it chooses one. Work arrives as a stream - frames to draw, packets to route, sensor samples to fold in - and the only real decision is how finely to cut that stream into batches. Each batch is one tick, and the rate is the grain of the cut. Cut at one operation per tick and nothing batches: every operation carries its fixed overhead alone, and at a 1 GHz tick the budget is a few nanoseconds, too little to work in. Cut at one tick for all pending work and efficiency is maximal but nothing is answered until everything is: a tick a minute has no perceptible responsiveness. Every useful rate sits between those ends, balancing responsiveness against the efficiency of batching.

Two different things bound that band. Whether you can keep up at all is fixed by the per-item cost against the arrival rate: if work lands at rate λ and each item costs c, you survive only when λ · c ≤ 1, and c is a layout fact (§3), not a scheduling one. The rate itself is the second, separate choice: a faster tick means smaller batches and lower latency with less to amortise each fixed cost over; a slower tick means larger batches, better amortisation, and more latency. Batching only ever pays because there are fixed costs to spread - a dispatch, a cache warmup, a syscall, a kernel launch - which is the same amortisation §8 names over data, here run along time.

The responsiveness floor is set by whoever consumes the output. Roughly 24 to 30 frames a second is where discrete frames read as continuous motion for passive viewing, which is why film sits there; interactive rendering wants 60, and head-mounted VR wants 90 to 120 to stay comfortable. A control loop runs as fast as its plant needs a correction, often 1 kHz; an audio loop is pinned to its 48 kHz sample rate; an interactive shell answers as fast as a human can type. Different consumers, different floors, one calculus. The rate you choose is the coarsest batch its floor will tolerate, and it sets a budget - the time available for one tick of work. What you then spend against that budget is governed by layout, which is where the rest of this chapter goes.

Every operation the program does in one tick spends from that budget. Operations have very different costs: the arithmetic is virtually free, an L1 read is around 1 ns, an L3 read is around 10 ns, a RAM read is around 100 ns, a disk read is around 100 µs, a network round-trip is around 100 ms. A 30 Hz program spending one disk read per tick has lost a third of its budget on one operation.

Note - Three regimes are worth naming, because the rest of the book references them. A loop is compute-bound when its cost is dominated by arithmetic - typically when the data fits in L1 and the inner instructions are heavy (dot products, transcendentals, integer divides). It is bandwidth-bound when its cost is dominated by how fast the memory subsystem can deliver bytes - typically when the working set is bigger than L3 but the access pattern is sequential, so the prefetcher can fill lines ahead of demand. It is latency-bound when its cost is dominated by individual memory round-trips - typically when the access pattern is random, so the prefetcher cannot help. The three regimes have very different time budgets and very different power profiles. A sequential Vec<u64> sum on a modern desktop is bandwidth-bound at ~50 GB/s, roughly 0.15 ns per element. The same Vec accessed by random index is latency-bound at one full RAM round-trip per element, roughly 50-100 ns per element - three orders of magnitude slower, despite the same arithmetic. The lesson of node 4 is that complexity-class reasoning cannot tell these regimes apart, but they are the difference between a program that meets its tick budget and one that does not.

The unit of accounting is time - microseconds for most real-time work, nanoseconds for tight inner loops. A 30 Hz tick has 33 ms (33 000 µs) of budget; a 1 kHz tick has 1 000 µs; a 1 MHz tick has 1 µs. When a teacher asks you “what does this function cost?”, they are asking how many microseconds it takes. A function that costs 100 µs out of a 33 000 µs budget is fine - about 0.3% of the tick. The same function in a 1 000 µs budget is 10% of the tick. The same function in a 1 µs budget does not exist; there is no room for it.

Cost is also layout. The same algorithm that costs 100 µs on a sequential Vec may cost 5 ms on a hash map of the same size, because the loads scatter. Two programs with the same big-O complexity can differ by an order of magnitude on the same hardware, just because of where their data sits.

This gives you a design rule. Decide your target rate before you decide anything else. That sets the budget. Then when you choose data structures, ask whether the resulting working set fits in cache; ask how many memory loads per row your inner loop does; ask whether any single operation in the loop dominates the budget. Most decisions become forced once the budget is named.

The reverse direction is also useful. If you find yourself wanting to add something to the inner loop - a database query, a HashMap lookup, an allocation - count its cost in microseconds against the budget. Often the answer is “this single addition uses 80% of my tick”, and the right move is not to optimise it but to lift it out of the inner loop entirely.

The shape of this thinking is familiar to engineers in other domains. An electrical engineer designs a circuit by counting milliamps against a current budget. A structural engineer counts kilonewtons against a load budget. The data-oriented programmer counts memory loads and microseconds against a tick budget. Good design is measured in millivolts and microamps - and in nanoseconds and microseconds.

Note - Time is one budget. Power is another. Cache hits are energetically nearly free - the data is already next to the arithmetic units. Cache misses fire up the memory controller, the bus drivers, sometimes a DRAM refresh; that is where the watts go. A loop that fits in L2 spends most of its time on cheap arithmetic; a loop that pointer-chases through RAM spends most of its time waiting, and during the waiting the CPU drops clocks and the chip stays cool. The same SoA-and-sequential-access discipline that fits the time budget also fits a power budget. For embedded, mobile, control, and battery-powered work, power is the primary budget; time is downstream of it. The “millivolts and microamps” line above is literal, not metaphor.

The budget is a curve, not a cliff

So far the budget has been a single number: name the rate, get the time per tick. But the work in a tick is rarely fixed. It grows with the problem - more entities to step, more packets to route, more rows to fold - and if the per-item cost holds, the tick time grows with it. So the rate you can actually sustain is not a constant either; it falls as the work rises, roughly as one over the size for a loop that costs O(N). Thirty hertz is not a wall you meet at some population and shatter against. It is one point on a slope that reads thirty, twenty-five, twenty, fifteen as the work climbs.

That moves the engineering question. It is seldom “does it hit thirty hertz” and almost always “where does the curve fall, and is that fall tolerable”. A control loop specified at thirty may be well served by twenty under a heavier load; a visualisation at fifteen is still watchable. So the useful design conversation names two numbers, not one: the target rate, and the tolerance - the slowest rate the consumer will accept - then reads off the scale at which the curve crosses the tolerance. You characterise the budget around the target instead of slamming into it, and “how many can we handle” becomes a number you read off a measured curve rather than a guess you defend in a meeting.

Part II puts real numbers on this slope, measured on the simulator across two orders of magnitude of scale, where a tick that holds comfortably above the target at one size slides to a fraction of the rate at a hundred times the work - all along the same one-over-N curve.

Exercises

1. Pick your rates. For each of these systems, name a plausible target rate and the resulting per-tick budget: a card game; a real-time strategy game; a market data feed; an embedded sensor controller; a web API endpoint a user is waiting for; an offline batch job that processes a billion rows.

2. Count an operation. Time a single HashMap::get on a map of 1 000 000 entries. Note its cost in microseconds. How many can you fit in a 30 Hz tick (33 ms)? In a 1 kHz tick (1 ms)?

3. The layout difference. Sum 1 000 000 u64s in a Vec<u64>. Sum 1 000 000 u64s in a HashMap<u32, u64>. Both are O(N). What is the per-element time difference (in nanoseconds)? Where did it go?

4. The cliff. With your numbers from §1 exercise 4, pick a Vec size that just fits in L2 and one that just doesn’t. Time a sum loop at each size. The cliff is real.

5. Working backwards from the budget. You target 60 Hz; your inner loop runs over 100 000 entities; each entity touches one cache line. Estimate the cost of the loop in microseconds and compare to your 60 Hz budget (16 666 µs). Where is your headroom?

6. A bad design. Construct a design that is “obviously fast” by big-O reasoning but blows the 30 Hz budget on a million entities. (Hint: object-graph traversal with one heap allocation per node is a classic.)

7. Find your CPU’s TDP. Look up your CPU’s rated thermal design power on the manufacturer’s spec sheet, or read it locally on Linux with sudo dmidecode -t processor | grep -i 'power\|TDP'. Note the value. TDP is what the chip can dissipate sustained without thermal throttling - burst can be 1.5-2× higher for tens of seconds; sustained settles back to TDP.

8. Battery budget. A typical laptop battery holds about 50 Wh. Your simulator runs at 30 Hz and draws an average of 8 W (mostly memory bandwidth on the inner loop). How many hours of simulation does a full charge buy? If a layout change pushes more loads to RAM and raises the average draw to 14 W, how many hours then? Express the cost of the layout change as a percentage of battery life.

9. Measure delta power. A ready-made workload generator lives at code/measurement/. In one terminal: cargo run --release --bin power_loop -- sequential (then in a second run: ... -- random). In another terminal, while the loop is running: sudo perf stat -a -e power/energy-pkg/ -- sleep 30 reads the package-energy counter over 30 seconds. Run the perf command three times - idle, sequential, random - and write the joules down. Convert each to average watts. The random-access run should draw more watts than the sequential one, which should draw more than idle.

   While you are there: from power_loop’s iteration count, compute your sequential read bandwidth - iterations × 10⁷ × 8 / 45 gives bytes per second - and compare to the published peak of your DDR generation. If you get within a factor of two of peak, your inner loop is bandwidth-bound (the regime named in the prose). The random mode’s iteration count, divided into wall time, gives your effective per-element latency in nanoseconds; that is the latency-bound regime.

10. (stretch) Joules per access. Approximate energies per memory read: L1 hit ≈ 0.1 nJ, L2 ≈ 1 nJ, RAM ≈ 30 nJ (rough; published numbers vary by chip and process). Estimate the total energy of summing 10⁷ u64s sequentially (mostly prefetched, near-L1 cost) versus by random indices (mostly RAM misses). Convert both to milliwatt-hours and express as a fraction of a 50 Wh battery. The absolute numbers are tiny; the ratio is what your battery life and your data-centre electricity bill care about.

11. The budget is a curve. Take the loop from exercise 5 (100 000 entities, one cache line each, 60 Hz). Hold the per-entity cost fixed and sweep the entity count: 100 000, 300 000, 1 000 000, 3 000 000. Compute the tick time and the sustained rate at each. At what size does the sustainable rate cross 30 Hz? 15 Hz? Plot rate against size and confirm the one-over-N shape, then name the largest scale that still meets a 15 Hz tolerance. (This is the curve Part II measures on the simulator; here you derive it from the per-item cost.)

Reference notes in 04_cost_and_budget_solutions.md.

What’s next

You now have the machine model (§1), the data widths (§2), the table primitive (§3), and the budget calculus (§4). The next section is the conceptual heart of the book: §5 - Identity is an integer. The card game is waiting.