Auditing determinism

[alice-i-cecile]

Determinism is important for reliable tests, (lockstep) networking and scientific simulation (#1678) in Bevy.

There are several key sources of non-determinism that we need to carefully iron out (for at least some users and scenarios):

1. Platform inconsistencies: largely at the floating point level
2. System execution order. This need not be fully static (i.e. no ambiguities), but must be specifiable in a reproducible way even at the cost of performance for these use cases. Using a single threaded executor will resolve this.
3. Entity iteration order (Ordered iteration over Queries #1470). In multiplayer contexts, you must sort each query by a stable key if iteration order matters.
4. Pseudorandom number generation. Getting this right across threads and gameplay systems is tricky enough that we should have clear examples (and perhaps helpers) for how to do it right (and audit that it worked!). bevy_rand is a solid crate focused entirely on this use case.
5. Commands and EventReader evaluation order. Currently these are both fixed by the topological order of the system execution, so solving 2 would solve this.

Solving this needs to be a concerted, organized effort in both Bevy and its dependencies: individual developers are not empowered to reasonably make the changes needed on a per-game basis.

Tools to build out:

• checksum-based desync detection, operating on a per-tick (or per-system) basis
• a test harness to run complete Bevy games in realistic conditions (cargo test chokes on both GPU support and multithreading)

Engine fixes to make:

• verify or ensure that entity iteration order is deterministic (perhaps with a global opt-in if the perf cost is measurable)

Engine features to build

• precise system execution order control, obeying the given constraints in an arbitrary but fixed order. This must allow runtime parallelism but still affect the toposort, resolving 2 and 5.

[alice-i-cecile]

Notes on cross-platform floating point determinism from @james7132:

• Know your rounding mode. A procedural macro that wraps and forces functions to use a specific floating point rounding mode universally may he necessary. In Rust, it's UB to change the rounding mode mid execution, but we're linking against non-Rust binaries (i.e. graphics backends) that might not have been compiled with this in mind. Architectures like RISC-V may not map 1:1 with x86 or ARM rounding modes, so we should choose one that has identical behavior universally.
• for ensuring IEEE-754 2008 compliance, there should be a compile-time AND run-time check for AVX support. SSE2 is usually compliant, but it's not guaranteed to be.
• Disable x87 support entirely. There are over 100+ bugs in it's implementation that are still in processors today, maintained for backwards compatibility. It also uses an unusual floating point representation which makes it impossible to match operation for operation across platforms.
• ARM has been compliant with the standard from the start.
• isolated platform specific floating point bit-for-bit equality tests may be needed to ensure nothing is broken.
• GPUs typically are not compliant due to how shaders are generally compiled and run. Do not use GPUs for networked simulation.
• Use consistent software based implementations for iteration based functions. Do not trust the standard lib for these functions.

[alice-i-cecile]

Gaffer's post on this is also very detailed and links to many other resources: https://gafferongames.com/post/floating_point_determinism/

This is worth reading in full when digging into the problem.

[bjorn3]

for ensuring IEEE-754 2008 compliance, there should be a compile-time AND run-time check for AVX support.

is_x86_feature_detected!("avx") always returns true when -Ctarget-feature=+avx is used, even if the CPU doesn't support it. It is UB to enable target features that the CPU doesn't support. At least on x86 new target features can and do change the behavior of byte sequences already accepted by older CPU's. This means that trying to use a new target feature on a CPU that doesn't support it can result in unintended instructions being executed instead of getting a SIGILL. For example lzcnt is interpreted as bsr on older CPU's.

https://stackoverflow.com/questions/25683690/confusion-about-bsr-and-lzcnt/43443701#43443701

[bjorn3]

Disable x87 support entirely. There are over 100+ bugs in it's implementation that are still in processors today, maintained for backwards compatibility. It also uses an unusual floating point representation which makes it impossible to match operation for operation across platforms.

All x86_64 and i686 userspace targets enable at least SSE2, which means that they don't use x87 floats. Only the i586 targets don't enable SSE and as such use x87 floats. (kernel targets generally disable it to reduce the amount of registers that need to be saved and restored on syscalls/interrupts)

[james7132]

is_x86_feature_detected!("avx") always returns true when -Ctarget-feature=+avx is used, even if the CPU doesn't support it. It is UB to enable target features that the CPU doesn't support. At least on x86 new target features can and do change the behavior of byte sequences already accepted by older CPU's. This means that trying to use a new target feature on a CPU that doesn't support it can result in unintended instructions being executed instead of getting a SIGILL. For example lzcnt is interpreted as bsr on older CPU's.

By runtime check, I meant a startup runtime check, perhaps via cpuid, that ends initialization instead of hard crashing via SIGILL mid execution. This is a usability feature over anything else.

All x86_64 and i686 userspace targets enable at least SSE2, which means that they don't use x87 floats. Only the i586 targets don't enable SSE and as such use x87 floats. (kernel targets generally disable it to reduce the amount of registers that need to be saved and restored on syscalls/interrupts)

Is it an effective no-op to then do use -Ctarget-feature=-x87 for these targets? I'm still opting to explicitly state that in the case it does change in the future, but this is good to know.

[bjorn3]

Is it an effective no-op to then do use -Ctarget-feature=-x87 for these targets? I'm still opting to explicitly state that in the case it does change in the future, but this is good to know.

The sentiment within the compiler team is that x87 floats are a bad thing as far as I am aware, so I consider it highly unlikely that this will ever change.

[james7132]

One other sticking point here is education. The benefits of a deterministic game engine is not common knowledge, nor is the responsibility solely on the engine maintainers, so if this is to be a major selling point for Bevy, useful examples and and well-worded justification may be needed.

Finally is ease of use to enable these features. IMO, there should at least be an optional enhanced-determinism feature flag that attempts to make all bevy_math public APIs internally cross-platform deterministic. If needed, we may want this on other crates that are in the game simulation hot path as well, enabled with a feature-flag at the top bevy crate. glam already has a libm flag that forces num-traits to use libm where possible, so we should enable that flag when the enhanced-determinism flag is enabled. It should be publicly documented that this may have a significant impact on runtime performance.

[ypoonse]

I agree, some pointers to resources from the bevy doc would be very useful as we make progress here. I'm new to gamedev. After some reading up, I indeed now understand the benefit of trying to make your game as deterministic as possible. It's also nice to see several experiments and libraries being built at the moment (GGPO, rollback-rs, crystalorb). I believe the trade-offs are important to educate as well. You probably want to trade off pure determinism (at the cost of the things mentioned in this thread, such as performance, added complexity in managing state, order, ...) against the possibility to send snapshots around at given intervals to fix divergence.

For now I'll try to keep what I create deterministic as much as I can to be prepared. In my case I made a globally accessible random generator, and pass it to the systems that require to sample values. I know it will break as soon as multiple systems ask for a value in the same time step and when I don't set a system order :).

[ghost]

I am very interested in Bevy determinism. System execution order and to a lesser degree entity iteration order seems like the big issues.

For sum checking is Sse4_2 Crc32C deterministic? I would think it would be.

[alice-i-cecile]

For system execution order, my plan is:

• get Improvements to execution order ambiguity reporting #4299 merged
• squash existing internal ambiguities
• create some nice follow-up PRs, including tools to forbid ambiguities at a crate-level for use by plugin authors

For entity iteration order, I think we should proceed with a simple solution to #1470, and then work on optimizing performance.

[stnbu]

This is probably off-topic, but to me it's interesting and relevant, and maybe relevant here. I post in the spirit of "would this work?" (while feeling unqualified to interject 😄)

I have done a lot of "hobby" grade n-body gravity simulation experimentation, usually involving Bevy. For my use-case, I wondered if I could assume and start with rational XYZ coordinates, do all the newtonian math and handle irrationals symbolically.

For example, sqrt(2) would come up a lot. These terms can be handled symbolically throughout. Sometimes they may "cancel out" and become rational after a few frames of simulation, but if not, we can always turn the coordinates back into floats before handing them to anything that requires such (like Translation of course).

I think I'm saying: One could extend the field of rational numbers with irrational roots, n^(1/p) [where p is prime and n has no factors that are a power of p].

In the above case, one should only be dealing with roots of the form n^(1/2) ...I think

I've got a simple [simple!] nugget of the idea here https://github.com/stnbu/qpow

[just an idea/bevy is cool]

[HackerFoo]

Rational numbers have two main drawbacks:

1. Rational arithmetic will be much slower than floating point arithmetic.
2. The size of rational numbers can grow independent of magnitude e.g. 1 / 1 = 2^128 / 2^128. One attempt to avoid this is to normalize the numerator and denominator by dividing both by the greatest common denominator, but this will not work if they are relatively prime (2^128 - 1 / 2^128). Any attempt to trade precision for size will have the same problems as floating point precision loss.

Introducing symbolic irrational terms will compound both of these problems.

[stnbu]

Nice to know and includes some things I hadn't considered. Thanks.

[therealbnut]

Why Not Both? Game Logic vs View Logic

I want to ensure we consider allowing a mix of determinism and non-determinism, with a clean separation between the two.

Consider the separation of a render mesh and a physics mesh. In many games the physics might win the cost-benefit analysis for determinism, but the rendering might not. There are many architectures like MVVM/MVP that separate game or business logic from view or presentation logic, with well documented advantages, however here I'm presenting them as a boundary for determinism. You likely care more about determinism in the game logic, and care more about speed in the view logic.

Match-3 Example

In the simple but concrete example of a match-3 game your architecture might have a low update rate grid-based state machine for the main game logic and model, and variable framerate non-grid aligned flashy effects in a view model on top of that.

The game model is essentially a state machine with a 2-dimensional array. Determinism matters here, as this is the core logic of the game, and you want to be able to test and verify various states, and transitions.

The view and view model is things like dropping animations, match effects, sound, music, and ui interaction. A large part of the view model is directly derived from the game model, it's essentially an animated visualisation derived from the state machine's transitions. It doesn't have as many advantages from determinism, and will likely just have performance issues from it. This is because generally it runs at a much higher or variable frame rate, directly reflects high frequency user input, or is computed from the deterministic model.

Granted Vec2 floating point determinism doesn't have any impact in the case of a grid based state machine, but system execution order, HashMap random state, sort vs sort_unstable, etc. may.

Possible Feature Flag Solution

To support a mix of determinism a feature flag should not necessarily be all-or-nothing. One possible solution would be to expose deterministic and non-deterministic versions, for example bevy_math::deterministic::Vec2 and bevy_math::fast::Vec2. The developer can then choose which one they need. This would mean you may sometimes have to convert between the two explicitly, but you should probably be deliberate when crossing that boundary anyway. In this example if you only enable one of fast and deterministic then you can just expose it as bevy_math::Vec2.

Clean Separation Support

I don't think it makes sense to force a seperation of view and game logic on bevy users, but I'd love to have better support for those kinds of architectures. I'm interested to explore the idea of supporting a SubApp for the deterministic game logic. A clean separation between game logic and the game view logic is also great for networking, testing, and efficiently serialising game state. A clean separation also allows us to easily verify when we're using non-deterministic code in the wrong part of the game. A SubApp would let us keep any overheads of determinism isolated, especially where it relates to things like system execution order.