Which floating-point sources of non-determinism would you suspect when a lockstep strategy game's two clients drift apart after ten minutes despite identical inputs?
answer
- same inputs, different last bits
- addition is not associative
- a*b+c rounded once or twice
- flags that let the compiler reorder
- sin and cos are not correctly rounded
basics
~20 sSuspect anything that changes a last bit: a different operation order, fused multiply-add on one build, fast-math compiler flags, differing sin and cos implementations, and a changed rounding or denormal mode. Per-tick state hashes locate the first divergent tick.
solid answer
~50 sIEEE 754 makes `+ - * /` and square root correctly rounded, so the same operations on the same values in the same order and precision give the same bits on any conforming hardware; desyncs come from breaking one of those conditions. **Order:** float addition is not associative, so a parallel reduction, a varying job order or a container iterated in address order changes results. **Fused multiply-add:** one build contracts `a*b + c` into one rounding, another rounds twice. **Fast-math flags** allow reassociation, approximate reciprocals and flushing denormals. **Transcendentals** like `sin` and `pow` are not required to be correctly rounded, so libraries differ. Legacy 80-bit intermediates and a library changing the rounding mode do the same. To find it, I hash simulation state bitwise every tick, compare across clients, then replay the recorded inputs with finer per-system hashes until the first differing field.
code
pseudocode · 10 lines// IEEE 754 single precision; floats near 1e8 are 8 apart
values = [100000000.0, 1.0, -100000000.0]
leftToRight = (values[0] + values[1]) + values[2]
// 1e8 + 1.0 rounds back to 1e8, then 1e8 - 1e8 = 0.0
reordered = (values[0] + values[2]) + values[1]
// 1e8 - 1e8 = 0.0, then 0.0 + 1.0 = 1.0
// leftToRight == 0.0, reordered == 1.0: same values, different ordergo deeper
Recall that floating-point addition is not associative, so the same numbers summed in a different order can give a slightly different result.
Explain which operations IEEE 754 rounds correctly and name what breaks bit-identical results: operation order, fused multiply-add, fast-math flags and math library functions.
Describe the hunt: bitwise per-tick state hashes, recorded inputs replayed with finer hashes until the first differing field, then the generated code inspected for contraction, vector reductions or library calls.
Decide which code sits inside the deterministic boundary, which build flags and math routines it must use, and how continuous integration proves cross-platform determinism on every change.
## What IEEE 754 guarantees, and what it does not A lockstep game sends only player inputs; every client runs the same simulation and must reach **bit-identical** state on every tick. IEEE 754 gives a strong but narrow guarantee: - **Guaranteed:** addition, subtraction, multiplication, division and square root are correctly rounded, so for the same inputs, in the same precision, under the same rounding mode, every conforming CPU returns the same bits. This holds across x86 and ARM. - **Not guaranteed:** functions such as `sin`, `cos`, `exp`, `log` and `pow`. The standard recommends correctly rounded versions but does not require them, and real libraries trade the last bit for speed differently. - **Not the standard's business:** the order in which your code and your compiler evaluate operations, and whether intermediates are kept in a wider format. So a desync almost always means two clients did **not** execute the same sequence of correctly rounded operations. (Whether the integration step itself is deterministic, fixed step size and all, is a separate concern; here the step is assumed identical.) ## The usual suspects | source | how it changes the bits | the fix | |---|---|---| | operation order | `(a + b) + c` can differ from `a + (b + c)` | fixed iteration order, deterministic reductions | | fused multiply-add | `a*b + c` rounded once instead of twice | disable contraction for simulation code, or use it explicitly on every platform | | fast-math flags | reassociation, approximate reciprocals, denormals flushed, NaN assumed absent | strict floating-point settings for the simulation | | transcendental functions | different libraries differ in the last bit | own implementations built only from basic operations | | extended-precision intermediates | 80-bit x87 registers rounded only when spilled to memory | scalar SIMD-register float math, no legacy x87 paths | | floating-point environment | rounding or flush-to-zero mode changed by a driver or library | set and assert the mode at the start of every tick | Order deserves the most attention because it hides in innocent code: - a sum computed by worker threads that finish in different orders; - a vectorised loop that sums in four or eight lanes and then combines the lanes, while the scalar fallback on another CPU sums left to right; - iterating a hash container whose order depends on memory addresses, so units are processed in a different order on each machine. In single precision, `(1e8 + 1) - 1e8` is `0.0`, because floats near `1e8` are 8 apart and `1e8 + 1` rounds back to `1e8`, while `(1e8 - 1e8) + 1` is `1.0`. ## Why the symptom appears after ten minutes A one-ULP difference in one unit's position changes nothing visible. It does change later arithmetic, and eventually a **comparison flips**: one client computes `distance < attackRange` as true and the other as false, one unit attacks and the other does not, and from that branch onward the states diverge completely. The long delay is the time for a tiny difference to reach a decision boundary, which is why the visible desync points far away from its cause. Strategy games are especially exposed because hundreds of units make thousands of threshold decisions per tick, and a single flipped decision is enough. ## Finding the first divergence 1. **Hash state every tick**, over the raw bits of positions, velocities, health, timers and random-generator state, and exchange the hash; a few bytes per tick is cheap. 2. **Record the inputs** of every match, so a desync can be replayed offline. 3. **Replay on both builds or platforms** with finer hashes, per system and then per entity, around the first mismatching tick. 4. **Bisect to the first field that differs**, then to the expression that produced it, and inspect the generated code for contracted multiply-adds, vector reductions or calls into a math library. 5. **Add a regression test**: replay recorded matches on every target platform in continuous integration and compare final hashes, so the next compiler upgrade cannot reintroduce it silently. Hash raw bits rather than rounded values: rounding to a few decimals hides one-ULP differences until they have grown large enough to change a printed digit, and the tick it reports is long after the real cause.
- Does running the same executable on two CPUs of the same architecture guarantee identical results?Not automatically. Code that selects a vectorised path by detected CPU features can reduce in a different order or use fused multiply-add on one machine only, and a driver or overlay can change the floating-point control mode. Pin the simulation to one code path and assert the rounding and denormal mode every tick.
- Why hash the raw bits of floats rather than values rounded to a few decimals?Rounding hides one-ULP differences until they grow enough to change a kept digit, so the reported tick comes long after the first divergence. Hashing the bits flags the first tick where any value differs, which is where the cause lies, and keeps the replay window small.
- Why does a one-ULP difference take minutes to become a visible desync?The difference stays tiny until some comparison sits right at its threshold, such as a range check or a target choice, and the two clients take different branches. After that branch the states differ in whole decisions, not in last bits, and diverge quickly. The visible symptom therefore appears long after the cause.
- IEEE 754 guarantees identical results everywhere, so float desyncs cannot happen.
- Fast-math flags only change speed, never the results.
- sin and cos return the same bits in every math library because IEEE 754 standardises them.
- Switching the simulation to double precision makes it deterministic across platforms.
- Comparing positions rounded to two decimals is enough to find the first divergence.
- A float desync must be a hardware fault in one player's CPU.