accidental un-parallelism
so i’ve been posting on bsky about it a lot lately — i’m working on a really, unnecessarily intricate simulation of a village of two hundred NPCs on a chunked, modifiable tile world, each of them with needs and moods and plans and opinions about each other, all of it deterministic, all of it replayable from a seed. the kernel is a fixed-tick discrete-event simulation — a tick is a tenth of a simulated second — and the design is that NPC thinking happens in parallel. parallel, read-only phases take &World, the one exclusive commit phase takes &mut World, and the borrow checker proves nothing mutates while the workers are out thinking. very clean. i love rust!!
the thing is that the parallelism did exist. the code was written and compiled, the rayon pool was there, the workers were spawned.
…they just never had anything to do.
the symptom
a village day cost far more than it should. the six hours of the night were fine, about 4 s each. from 07:00, once the village got up and started doing things, an hour of simulated time took anywhere from 30 to 80 s of wall time — on a machine with every core available to it.
i had claude profile it extensively, because i wanted to know what was actually expensive rather than what i assumed was expensive, and the first pass turned up two things that were plainly dumb, but also, blessedly, one thing that was interesting!
the dumb things first. Town::look_for, which is how an NPC searches for a thing of some kind within sight, was working out the height of the ground at each place it might look by generating the base terrain there — value noise, a seeded stream per chunk, the whole procedure — every time anyone looked for anything. the ground is already in the chunk store. it is loaded. it has every change ever made to it applied. there is no reason on earth to ask the generator what the terrain was before the villagers dug into it when you could just ask the terrain!
the second dumb thing was failed acts. about 250 of them in the first waking hour, rising past 800 an hour by mid-morning. a failed act is a plan made, begun, failed and made again, and because nothing was remembering the failure, the same plan would be made and failed on the next tick, and the next. the worst single case was a villager filling a barrel at a well whose water-drawing step had failed — the well was already in use — who then went on to plan the pouring step, with nothing to pour, roughly 3,500 times an hour. bless him.
both fixed, plus a few smaller things. what a villager has to hand gets counted once per think, instead of once per candidate action (this alone was ~16% of the hour); short walks go through plain A* before the portal graph (joining both ends to their chunk portals cost more than just finding the path), and line of sight gets traced once per tile rather than once per signal coming from that tile. a village working hour went from 63.7 s to 40.2 s. better. not enough, though!
the interesting thing
the interesting thing was the shape of the profile after all that. about 85% of the remaining time was thinking. fine, thinking is the expensive part, that’s expected. but it was thinking on one core. the other workers were sitting there for the entire hour, doing nothing.
here is how thinking is scheduled: NPCs don’t get polled; they schedule their own wakes on a hierarchical timer wheel, and most of the time they are asleep in it. a meter solves for when it will cross a threshold and books a wake at that tick. an action that takes twelve ticks books a wake twelve ticks out. every tick, the kernel drains the wheel for that tick, collects the NPCs with a think wake due, and hands them to the parallel phase to think against the frozen world:
// the shape of it, before
let mut due = due_for(THINK);
due.retain(|who| planned(who));
let thought: Vec<IntentBuffer> = due
.par_chunks(CHUNK) // CHUNK was 32
.map(|agents| {
let mut buffer = IntentBuffer::new(world);
for &who in agents {
let (intents, units) = think(world, who, &mut NoTrace);
buffer.charge(units);
for intent in intents {
buffer.actor(who).emit(intent);
}
}
buffer
})
.collect();
that is a perfectly reasonable piece of parallel code. it is also, given everything else about the design, almost never parallel. with a village of two hundred and a tick quantum of 0.1 s, any given tick has one, maybe two, think wakes due on it. two hundred villagers each thinking every second or so is two hundred thinks spread over ten ticks, which is twenty per tick on average — except that most of them aren’t thinking every second, they’re halfway through walking somewhere or kneading something, and the ones that are thinking are doing so on their own schedule, not all together. the actual distribution came out at one or two.
so par_chunks(32) over a list of length one produces one chunk, which goes to one worker, and the parallel think phase collapses back into what is effectively a single serial queue. there is no way to distribute the work if there is only one unit of work! the rayon pool was doing its job. i was just handing it nothing lol
when initially speccing the design out, my estimate for thinkers per tick was a few dozen, at least near to the player, and i think that was a reasonable estimate for a town with a few thousand people in it and a player standing in the middle of the market. it is not a reasonable estimate for a village of two hundred — my current, smaller-scale test scenario, kept a manageable size to make it easier to inspect and explain behaviours during development — and where everyone is quietly getting on with their morning. the tick is fine, the scheduler is fine, the parallel phase is fine. the three of them together just happen to have a load profile that starves the phase at… well, exactly the population sizes i’m testing at, it turns out
three ways out
so the question was how to give the think phase more to share.
i saw (still see) three basic approaches, here, although there may be more (and if you can contrive one, please, do tell me about it!):
(1) coarser think timing: thinks only fall due on ticks that are a multiple of some think_every; a wake gets rounded up to the next such tick. very simple, the kernel contract is untouched, determinism holds as it does now. the cost is that every wake rounds, and a think wake is also how an NPC takes the next step of an action, so walking and working would slow and coarsen along with the thinking. no
(2) thinking ahead in windows: every k ticks, every think due in the coming window runs against the world at the window’s start, and its intents are held and committed at their own tick. walking and working keep their pace, because every intent still lands where it was going to, and the only thing that changes is that what an NPC saw when it decided may be up to k − 1 ticks stale. the cost is complexity — held intents are state now, they need hashing and snapshotting or replay breaks inside a window — and the staleness itself
(3) speculating and checking: run upcoming thinks early, record everything each one read, and at its due tick use the result only if none of what it read has changed — else, think again. this should be bit-identical to the current behaviour. but it has a rub that i didn’t want to potentially have to deal with later — a read the recorder misses is a determinism fault that shows up rarely and late, which is the worst kind, and the whole gain depends on how often nothing changed, which i had no measurement for.
ultimately, i went with (2). option (1) changes the simulation’s timing; (3) changes nothing but introduces the risk of hard-to-notice nondeterminism; and (2) only changes how old an NPC’s information is when it acts. a few tenths of a second of staleness is about as long as a glance takes; in real life, people act on slightly stale information all the time. it is, in and of itself, arguably more realistic than the previous behaviour, which was that every villager had perfectly current knowledge of the world at the instant they decided anything!
the two constraints
obviously there are a couple of potential problems with “just think eight ticks early”, and they are the two things the whole kernel is built around (naturally):
(1) determinism: one thread and N threads have to produce identical state hashes, that is a CI test, and so does a replay from a snapshot taken at an arbitrary tick. anything that makes the window boundaries depend on load, wall-clock time or the number of workers is out immediately. so windows start at tick numbers that are multiples of think_ahead — content, not scheduling — and that’s the easy half!
the harder half is randomness. a think draws from the NPC’s RNG — the planner’s weighted pick among its top few candidates, perception noise, whether a process errs. if a think for tick 1,006 runs during tick 1,000, it has to draw the same numbers it would have drawn had it run at 1,006, or the result depends on when it ran. this is where a decision i made a while ago, for completely different reasons, turned out to matter. streams in ewsim are never stored. a Stream is derived fresh from (world seed, owner id, stream kind, tick), because the think phase is read-only and can’t advance a stream kept in world state anyway:
pub fn new<I: StableId>(seed: WorldSeed, owner: I, kind: StreamKind, tick: Tick) -> Stream {
let mut key = blake3::Hasher::new_derive_key(KEY_CONTEXT);
seed.stable_hash(&mut key);
I::KIND.stable_hash(&mut key);
owner.stable_hash(&mut key);
kind.tag().stable_hash(&mut key);
let mut rng = ChaCha8Rng::from_seed(*key.finalize().as_bytes());
rng.set_stream(tick.get());
Stream { rng }
}
the tick selects the chacha stream under the key. which means a think can be run at any wall-clock moment, on any worker, and so long as it is told which tick it is for, it draws the numbers that tick owns. per-job RNG, fast-forwardable to a specific game tick, because i’d refused to put mutable RNG state in the world months ago.
so there is now a think_at(world, who, at, …) beside think, which is the same think except that its needs, moods, streams and plan times are those of at rather than of the world’s current tick. the world it perceives is the world as it stands, and the villager it perceives with is the villager as they will be.
(2) causality itself: we are, now, quite literally, making plans for NPCs who shouldn’t have those plans yet. a think held for tick 1,006 was made with the world of tick 1,000. if, at tick 1,003, somebody walks up and offers that villager a job, the villager thinks about the offer at 1,003 — a wake made inside a window is thought on at its own tick, alone, as before — and then at 1,006 the held think fires, and the villager acts on a plan made before the offer existed, and walks off halfway through the conversation…
that one showed up in the failure counts immediately. 274 hires an hour failing for “no partner”, against 36 with the window set to a single tick. the fix here ended up being a rule, and the rule is that anything newer than a held think invalidates it. every think wake in the town now goes through one method
/// Wakes `who` to think at `at`. A think it holds was made before whatever wakes it now,
/// so it is dropped, and one made ahead in this same commit is not held.
pub(super) fn wake_to_think(&mut self, who: NpcId, at: Tick, fx: &mut Effects<'_, Town>) {
self.ahead.remove(&who);
self.woken.insert(who);
fx.wake(who, THINK, at, Priority::new(0));
}
a held think is dropped whenever the NPC is woken to think for any reason — a step just begun, a failure, an offer, a wait ending — and a think made ahead in the same commit that wakes the NPC is never held in the first place (that’s what woken is for, and it’s cleared every settle). held thinks live in the town domain as ahead: BTreeMap<NpcId, (Tick, Vec<TownIntent>)>, they are hashed when non-empty (so a world with none held hashes as it did before, and every pre-existing golden that didn’t move for other reasons didn’t move for this), and they are carried by snapshots with serde(default), so a replay from a snapshot taken inside a window matches the run it was taken from. there’s a test for each of those sentences.
what it looks like now
the driver, after. at every tick that is a multiple of think_ahead, our configurable tick interval for thinking job batching, it takes every planner-controlled NPC whose think wake falls within the window — the scheduler grew a due_by that reads the whole wheel without draining it, which sounds expensive and costs less than a single think — and thinks for all of them, each at its own tick, one think per intent buffer so they spread over every core.
let window = corpus().planner.think_ahead;
if window > 1 && now.get().is_multiple_of(window) {
let mut ahead: Vec<(NpcId, Tick)> = world
.due_by(now + Dur::new(window - 1))
.into_iter()
.filter(|w| w.kind == THINK && w.at > now)
.filter_map(|w| Some((w.actor.get::<NpcId>()?, w.at)))
.filter(|(who, _)| planned(who))
.collect();
ahead.sort_unstable();
thinks.extend(ahead);
}
let thought: Vec<IntentBuffer> = thinks
.par_chunks(CHUNK) // CHUNK is 1 now
.map(|thinks| {
let mut buffer = IntentBuffer::new(world);
for &(who, at) in thinks {
let (intents, units) = think_at(world, who, at, &mut NoTrace);
buffer.charge(units);
let mut emit = buffer.actor(who);
if at > now {
emit.emit(TownIntent::ThoughtAhead { who, at, intents });
continue;
}
if town.thought_ahead(who).is_some() {
emit.emit(TownIntent::Thought { who });
}
for intent in intents {
emit.emit(intent);
}
}
buffer
})
.collect();
a think due now is acted on now. a think due later is emitted as a ThoughtAhead intent, committed at the window’s start into ahead, and when its tick arrives the driver finds it there, emits Thought (which clears it) followed by the held intents, and those are checked at commit against the world as it is then, like any other intent. nothing about commit changed at all. the kernel doesn’t know thinking ahead exists. i am really proud of myself for designing things in such a way that no major kernel-level changes ended up being necessary here, lol
numbers
measured on an idle machine, release build, all cores, the village of two hundred at seed 1, from 09:30 to 10:30 of its first working morning, median of 3:
village working hour | |
main, before any of this | 63.7 s |
after the profiling fixes | 40.2 s |
after thinking ahead | 17.8 s |
2.24x from thinking ahead on its own, 3.6x across both 😎
the behavioural cost ends up being 61 additional, failed acts in the same simulated hour: 175 failed acts in that hour, against 114 on main and 127 with the window set to one tick. the difference is NPCs acting on a world up to seven ticks old, and most of it is one specific thing — an offer of work made to someone who has just that moment walked out of reach (79 against 36). i’m fine with this, tbh. it is, if anything, simple realism — sometimes you turn around to ask someone something and they’ve gone.
one more thing came out of it — the first round of fixes taught villagers to remember an act they’d failed at, on that thing, with that person, for a while (fail_for, ten minutes), so they don’t plan it and fail it tick after tick. i had deliberately exempted an errand’s own stages from that memory, on the eminently reasonable grounds that one pour that didn’t take is no reason to give up on filling the barrel. what i missed was a pour that cannot be planned — the only well is held by someone else, there is nothing to draw with — which then got tried blind every tick until something else won, six ticks running for a hired labourer on main and a quarter of an hour for one villager on the new branch. a failed errand step now leaves the errand fail_for at the stage it’s at, not given up. the filling resumes when the well is free. the hired labourer, who was broken by both of the other two fixes i tried first, is fine.
the moral, such as it is
i don’t think there’s a grand lesson here beyond the boring one, which is that “the code is parallel” and “the code runs in parallel” are different claims, and only one of them can be checked by reading. i had the first and assumed the second for weeks; it took claude about ten minutes fiddling with profiling to smoke that out.
the less boring observation, to the extent that there is one, is that every piece of this worked because of decisions made earlier for unrelated reasons. read-only think phases meant a think could run at any time. per-tick stream derivation meant it could draw the right numbers when it did. intents being checked at commit meant a stale plan simply fails like any other plan rather than corrupting anything. the town domain owning its own state meant the kernel never needed to know. none of those were made with thinking ahead in mind; thinking ahead was just the first thing to collect on all of them at once. this is, i think, the actual argument for being strict about determinism from day one — not that you’ll need replay, though you will, but that a system where every computation is a pure function of committed state is a system where you can move the computations around later and nothing breaks.
anyway it was a lot of fun to chew on and the village is three and a half times faster, so every gate is three and a half times faster, which means i get to be wrong about things three and a half times as often per hour. thanks for coming to my TED talk 👍
