Replies: 10 comments 35 replies
-
|
Links to relevant conversations, for context. Any ideas are in no way final. In no particular order; feel free to add your own. |
Beta Was this translation helpful? Give feedback.
-
Beta Was this translation helpful? Give feedback.
-
|
adding this message from Joy which discusses motivation for a run criteria hierarchy |
Beta Was this translation helpful? Give feedback.
-
|
XR needs a way to hook into the app lifecycle |
Beta Was this translation helpful? Give feedback.
-
|
Adding in the old PR's of the v2 rework |
Beta Was this translation helpful? Give feedback.
-
|
Some discussion here about nested system sets and requirements for app state |
Beta Was this translation helpful? Give feedback.
-
Problem-scoping questionsThese questions are intended to scope and define the questions we want to answer and think carefully about in these designs. If you have more (or less!) questions that think should be tackled as part of this Gordian knot, please chime in.
|
Beta Was this translation helpful? Give feedback.
-
|
We've been discussing these complex control flows in this Discord thread. Emergent nomenclature is "decoupled game loops", which covers both turn-based and fixed-timestep control flows. Obviously there may be even more complex control flow patterns needed, but this seems to cover most of it. Async task spawning is the other wrinkle; it's looking like spawning tasks from within the loop and then checking back on them is a solid stop-gap. |
Beta Was this translation helpful? Give feedback.
-
|
I would also to add the ease of use and also powerful abstractions. It's already hard for new users to grasp about using ECS and data-driven, the system scheduling should be easy for new users to reason about and also powerful enough to experienced users build their abstraction of top of it. Like any API, we have to find the line between more properties and more meaningless abstraction. Maybe we should focus on a low-level API and let third party build ease of use abstractions on top of it? Dunno. |
Beta Was this translation helpful? Give feedback.
-
|
I'm reluctant to delegate all the abstractions to third-parties. That will make interop harder, and also prevent the engine itself from using these patterns to make the codebase more maintainable / correct / efficient. |
Beta Was this translation helpful? Give feedback.
-
Current answers to problem-scoping questionsThese replies are mostly written working out of memory; if there's an important detail that I've missed / gotten confused about, please let me know and I can correct this post. Many thanks to @TheRawMeatball for corrections and feedback. How are systems collected and organized?Systems are converted into system descriptors, then stored in stages, which are in turn owned by a schedule. Systems can be grouped into system sets, which can be described en-masse but do not persist past initialization. Functions which modify the world during a hard sync point are conceptualized as exclusive systems (or, when queued from ordinary systems, commands). How do we add systems from other sources to our app?Plugins take the main app, and mutate it. Plugins can add systems and new hard sync points. Plugins cannot directly configure the order of existing systems in any way, and cannot set timing relative to systems from other plugins (except via stages) unless those labels are deliberately made public. Some exceptions to this ordering exist, due to the transitive nature of ordering. Suppose A and B are publicly labeled, and have no order specified between them. By inserting C which runs after A but before B, a new order is induced. How do we control the relative order of systems?There are two approaches:
How do we define hard sync points?Hard sync points are defined globally as a side-effect of inserting a stage. Plugins can insert their own hard-sync points into the app by adding their own stages. Looping run criteria cause hard sync points to repeat. The full stage execution model in Bevy 0.5 is:
How can we enable and disable systems?Systems are enabled and disabled via run criteria, which are attached to the system as a descriptor. Run criteria are themselves systems that return States are widely used for cohesively manipulating which systems should run en-masse. States cannot span hard sync points and are limited to a single stage. How can we opt-in to complex control flows?There are several tools for this:
|
Beta Was this translation helpful? Give feedback.
-
Design goals
System scheduling
Control flow
Plugins
|
Beta Was this translation helpful? Give feedback.
-
|
Like the perf at stake here is not much, so giving sync points a negative connotation and getting users all concerned about concurrency is counterproductive. Instead of telling people to just avoid sync points, it'd be better to have examples on how to reduce their number after you have things working. IMO making them something you have to deliberately add is enough to discourage unnecessary usage. |
Beta Was this translation helpful? Give feedback.
-
|
For the most part, I'm concerned that "add a sync point at position X" is the wrong abstraction for users, because it doesn't actually correspond to their needs. It's simple and explicit and controllable, but the actual logic they care about is "commands must be flushed between these two systems". Irrespective of perf, a design that focuses on explicit global and manual sync point management is going to be very hard to reason about and scale, because you need to be careful not to break undocumented, unenforced logical dependencies between systems. |
Beta Was this translation helpful? Give feedback.
-
I can see how manually adding lone sync points would be awkward. Is "commands must be flushed between these two systems" how people really think about things though? I feel like the most natural reasoning is a hierarchy of stages, hence the general "have stages be labeled pairs of sync points" idea. Edit: To be clear, I think we should think about how to represent stages and sub-stages under a global executor, instead of the nested schedule pattern we have now. |
Beta Was this translation helpful? Give feedback.
-
It is how I think about things 😆 But I'm not representative on this topic I'm sure. I tend to build and design in vertical slices, where this logic makes much more sense, rather than coming in with a full "this is how my game works" design. A user came in with experience from
Interesting thought here: do these sync points need to be adjacent. If not, this gives us a really interesting representation of hierarchical structures. |
Beta Was this translation helpful? Give feedback.
-
Nope, they can be non-adjacent, and yep I think that would enable representing stage hierarchies. Just like now, stages on the same tree level can touch but not overlap. Child stages could start or end on the same sync point as their parent. The executor could have one |
Beta Was this translation helpful? Give feedback.
-
System control flow patternsRendering-coupled loopDescription: The game loops in real time. Rendering is part of the game loop, and so one frame is equivalent to one tick. Examples: Factory builders (as we can't make computations cheaper, we slow down the frame rate instead), simple traditional arcade games Current tools: Single schedule Potential changes: None Strict turn-basedDescription: The game loop only advances when new input is provided. Examples: Play-by-mail chess, choose-your-own-adventure terminal games Current tools: Custom runner Potential changes: None Hybrid turn-basedDescription: Much of the game loop only advances when new input is provided, but animations, sound and so on advance in real-time. Examples: Turn-based RPGs, digital board games Current tools: Run criteria and game-state storage in resources (or Potential changes: Improve run criteria combination and interactions with states. Fixed timestep, decoupled renderingDescription: Much of the game loop (typically physics) only advances when a certain fixed amount of time has passed. Note that this control flow pattern and the hybrid turn-based pattern above can be unified into a decoupled game loop control flow, where the criteria differs. Examples: FPS, tower defense Current tools: Fixed timestep run-criteria, pipelined rendering Potential changes: Improve run criteria combination and interactions with states. Stack processingDescription: Some parts of the game loop must be processed repeatedly until a stack is empty. Examples: Magic the Gathering, complex turn-based game effects Current tools: Hierarchical schedules with run criteria, exclusive systems that manually run a schedule stored in a resource Potential changes: Clarify and promote nested schedule design. Store multiple schedules in the Parallel simulationDescription: Many copies of the same app should be run completely independently without user input but with slightly varied hyperparameters which control the simulation details Examples: Scientific simulation Current tools: Custom runner Potential changes: Allow multiple worlds to be stored in the Many-worlds branching AIDescription: Game AI repeatedly simulates a game state and then evaluates it before proceeding within a world Examples: Chess engine, Sudoku solver Current tools: Exclusive systems that manually run a schedule stored in a resource plus sub-worlds stored in a resource Potential changes: Allow multiple worlds to be stored in the Long-running tasksDescription: Some tasks are too long-lived or computationally expensive to be completed in a given framing Examples: Waiting for input in a hybrid turn-based game, AI pathfinding Current tools: Async tasks and manual polling each time a system is run Potential changes: None at the moment Streaming dataflowDescription: The app listens for events and only runs when there is new data to process. Examples: Extract-transform-load data processing Current tools: Custom runners which batch data and then execute a schedule when enough time has elapsed or a batch is full. Potential changes: Multiple worlds would make separating unprocessed and processed data more ergonomic. |
Beta Was this translation helpful? Give feedback.
-
Slightly varied what? 😅 |
Beta Was this translation helpful? Give feedback.
-
|
Hyperparameters! Fixed, thanks 😅 |
Beta Was this translation helpful? Give feedback.
-
I can't tell what's being said in the parentheses here. Is this true? I guess arcade cabinet games could have gotten away with this, but I would think most classics were especially likely to be in the "decoupled game loop" camp, since consistency was important (i.e. "frame" perfect) and hardware wasn't all that powerful. AFAIK the "rendering-coupled loop" exclusively benefits UI. I think stack processing is also a "decoupled game loop." Nested schedules seems like the current tool for all three. Edit: In general, I think these coalesce into framerate-dependent, framerate-independent, and async. The current tools and potential changes suggest this as well. Parallel feels like its on a different axis. |
Beta Was this translation helpful? Give feedback.
-
Yeah, I think this pattern should be avoided for most gameplay applications. However, Factorio uses this to good effect. It cannot drop / cheapen computations, so the approach that is taken is to instead continually drop the frame rate: the game stays playable and users can enjoy megabases even on middling hardware.
Yep, I think so too.
This is a solid categorization, and should be very helpful to us going forward.
Definitely agree. It seems clear that we're going to need:
|
Beta Was this translation helpful? Give feedback.
-
|
Here's my best attempt at diagramming out all of the dependencies of these problems.
I've attached the diagrams.io diagram for editing as may be needed. |
Beta Was this translation helpful? Give feedback.
-
|
I tried to group those dependencies together a bit, with my own assumptions about what's likely/important. |
Beta Was this translation helpful? Give feedback.
-
|
Discussed all these ideas here bevyengine/rfcs#35 |
Beta Was this translation helpful? Give feedback.
-
|
wrote up my thoughts on a potential implementation for stageless bevyengine/rfcs#34 |
Beta Was this translation helpful? Give feedback.
-
|
Useful Discord discussion yesterday where Sander talked about how flecs handles system ordering and sync points. I think I'm on board with "stageless" now. Feels clearer to me now. Summarizing my takeaways. 1. Remove stage and just expose its individual parts
To get rid of
I think we can (and should) order exclusive systems following the topological order instead of special insertion points (they're unnecessary). (Edit: Example if we stored all systems inside // systems sorted in a topological order (assume sync points have also been inserted as exclusive systems)
let remaining = &mut self.systems[..];
loop {
// Find the next exclusive system.
if let Some(index) = remaining.iter().position(|&sys| sys.is_exclusive()) {
let (concurrent, remaining) = remaining.split_at_mut(index);
let (exclusive, remaining) = remaining.split_first_mut().unwrap();
self.executor.run_systems(concurrent, world);
exclusive.system_mut().run(world);
} else {
// No exclusive systems remaining.
self.executor.run_systems(remaining, world);
break;
}
}2. Make run criteria return boolWe can have this if loops and nested schedules are black-boxed inside exclusive systems, then each schedule remains a DAG. fn fixed_update(world: &mut World) {
world.resource_scope(|world, mut fixed_timestep: Mut<FixedTimestep>| {
while fixed_timestep.sub_step().is_some() {
simulation_schedule.run(&mut world);
}
}
}Would also be cool to have a way to mark systems as exclusive (nothing else running) without the 3. Define states betterStates don't really have a solid definition, but we need to nail one down to proceed. How exactly do we want the app-level state machine to interact with a schedule? From my POV, there are two mutually exclusive options:
Def. 1 reflects the current behavior (an app's I don't like states being literal stages/schedules. It's counter-intuitive that you have to clear the stack and return to the default state to actually end a frame (although that is something we could change). I prefer Def. 2 where states are passive and persistent but transitions can still trigger on-demand behavior. It gives an individual schedule more flexibility while being less open-ended. Either way, I think the on-demand execution means state transitions are only provably safe during sync points, so "flush pending commands" would really be "flush pending commands and then flush pending transitions." Related Future Work
|
Beta Was this translation helpful? Give feedback.
-
Oh, I see. I'd still say the user is responsible resolving ordering ambiguities. We don't need to make it hurt less when they don't.
A schedule is just a sorted list of systems. Whether one is atomic or not depends on if it ends in a sync point. When I wrote about auto-derived sync points, I still meant that they'd be inserted when the schedule is built. I did not mean that the executor would opportunistically decide if a sync is necessary depending on which systems ran. That would definitely complicate things (but is not what I'm suggesting). (And more granular sync points are out-of-scope IMO.)
Right before the executor runs a system, we need to check its criteria. I think we can handle that internally in a straightforward manner without introducing a new primitive. We also want to reuse any still-valid results when we're mixing and piping run criteria.
Like, a plugin could just dump all of its systems into the app or it could check which labels you imported and add only those specific systems. Either way is fine. The executor will only see the systems mentioned by the schedule. The systems could be added ready to go, with the imported labels applied and the internal label relationships already set. E.g. |
Beta Was this translation helpful? Give feedback.
-
I think I still disagree here. Take a slightly more complicated graph. If it gets a bad sorting, this becomes something like EPEPEP. While optimally this is EEEPPP. You could add an edge like this: which would turn it into the optimal sorting, but I think this is going to get complicated in more complex graphs. |
Beta Was this translation helpful? Give feedback.
-
|
I don't think these graphs are possible with the label ordering I had in mind. I want the labels used to build a schedule to be arranged in a tree (a hierarchical sequence), so there would be no "parallel" labels. (Edit: To clarify, each label in the tree can have a corresponding system DAG, but the tree itself is a sequence.) e.g. Only systems that have the exact same label path could run concurrently. (Edit: Well, if we fed the entire top-sorted schedule into the executor, that would depend on where sync points are inserted. But I think we need to iterate the labels to handle their run criteria.) To get the parallel branches pictured in your examples, you'd need a full graph of labels, and that would be really difficult to grok. Exclusive systems can't run concurrently with anything else, so a label graph would be misrepresenting what's actually possible. In general, I think we have to be reasonable about where we introduce concurrency. IMO the executor already does all we can do at the system-level, aside from auto-deriving sync points. Any higher-level concurrency requires stronger isolation, like tasks and threads (e.g. main thread, render thread, input thread), where we upfront avoid race conditions by cloning data in and out. |
Beta Was this translation helpful? Give feedback.
-
|
The graphs I was showing would just be the system DAG. The branches aren't showing parallelism, but sequences of before/after dependencies. Ah. I think I was misunderstanding what you mean by "Attach a run criteria to a label directly." I was thinking of labeling like it is now, but you were thinking of it like in this tree format. I would advocate for this then, rather than the second option. It matches with what I was arguing before about run criteria. |
Beta Was this translation helpful? Give feedback.
-
|
I guess you're right that those are valid system dependency graphs. Graph of labels, tree of labels, either way, we can make a schedule builder that only looks at a certain set of labels. Before we discuss adding heuristics to choose a topological order (optimal topsorting is an NP-hard problem), I think we need to see some IRL examples where ambiguities are unavoidable (so user-plugin and plugin-plugin conflicts) and those ambiguities cost a lot of perf. If it's easy to always pick a good topsort, then sure, but it doesn't seem like it. Like, whatever builtin executor |
Beta Was this translation helpful? Give feedback.
-
More BenchmarksI think one of the first things we need to do before rewriting the scheduler is to add some more benchmarks. There are already some for parallel systems, but we should probably add some more.
Maybe add:
Please suggest any more that you can think of. |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
reserved
Beta Was this translation helpful? Give feedback.
All reactions