Automatically batch similar commands together to improve performance and robustness

[alice-i-cecile]

What problem does this solve or what need does it fill?

Commands are currently applied one at a time, in system graph order, and within that in the order they were sent within systems (FIFO). This causes some problems:

• Chained EntityCommands create useless temporary archetypes #5074
• Confusing interactions between despawning entities and other operations like in Command execution order does not always match system execution order in the case of ambiguous systems #10122 or Configurable error handling in commands #2004.
• Suboptimal performance, as we are violating the basic principles of data-oriented design

What solution would you like?

Automatically batch adjacent similar commands together.

What alternative(s) have you considered?

We could also reorder commands to reduce surprising errors and confusing interactions. A sample ordering might be:

• Spawn
• Insert
• Remove
• Despawn

This would avoid a large number of spurious failures without needing explicit command error handling or system ordering. I'm unsure if that should be done as part of this work, or even at all however.

Additional context

@maniwani has been investigating this, and thinks we should remove the general purpose Deferred system parameter to reduce the risk of unbatchable operations. I'm personally less convinced: wouldn't those arguments similarly apply to any custom commands?

[maniwani]

I'm personally less convinced: wouldn't those arguments similarly apply to any custom commands?

Custom commands are fine since they're still commands.

The batching implementation I'm investigating (used by flecs) reduces the number of moves per entity from N to 1. The more commands we can "batch" (i.e. all queued commands from all systems at the current sync point), the fewer moves. That kind of "bird's eye view" over all queued commands can't happen if there are deferred operations that aren't commands.

Those would interrupt the batching or we'd have to do things in a weird order (e.g. run commands first, deferred operations last). IMO just remove Deferred. Commands are general-purpose. Why do we need Deferred when custom commands exist?

The only thing to note about custom commands is that batching would be able to "move" entity commands to run before them.

(edit) If Deferred exists to avoid allocating on the heap like Commands does with CommandQueue, I intend to address that with the batching implementation. There are too many queues. I'd consolidate things so each system has a single, thread-safe command queue. No matter how many Commands params a system has, they'll all reference its one queue.

(edit 2) I'm not recommending we remove Deferred before implementing batching. I'd probably do both in the same PR.

[RedMindZ]

We could also reorder commands to reduce surprising errors and confusing interactions

Since commands modify the shared state of the world, I don't think they could be reordered safely, unless we know ahead of time the set of all commands and all of their interactions, which is impossible with custom commands and will make adding new commands very difficult and fragile.

By not reordering the commands, the user has more control over how the world is modified, which is critical when the commands are trying to reflect in the world modifications to the user's state. It also becomes the user's responsibility to ensure commands are added in a valid order, which is much easier to control and debug when the commands are executed in the order they are created in in the user's code.

[maniwani]

We could also reorder commands to reduce surprising errors and confusing interactions.

This would avoid a large number of spurious failures without needing explicit command error handling or system ordering.

I'm pretty sure batching is orthogonal to this.

Commands in general shouldn't even have errors, and all our built-in commands should be infallible.

The panic that happens when an insert or remove comes after a despawn is something we just arbitrarily do. They should just be ignored (with a debug! warning). It isn't a bug if two different systems from two different plugins want to despawn an entity at the same time for different reasons, or if a plugin system wants to despawn an entity at the same time user code wants to give it a component, assuming it'll still exist. Batching does not add anything new to this equation.

All we need to do is make a PR that (1) changes the panic to a debug! warning and (2) privates all fields of Insert, Remove, and Despawn so that users can only make these commands through EntityCommands. You can't get an EntityCommands for an entity unless that entity is alive (or will be), so all commands created through EntityCommands must be considered valid.

Since commands modify the shared state of the world, I don't think they could be reordered safely, unless we know ahead of time the set of all commands and all of their interactions, which is impossible with custom commands and will make adding new commands very difficult and fragile.

It's more nuanced than this. The batching implementation I am working on can and will re-order¹ the observed effects of commands, but in a specific way. Only entity commands would be re-ordered.

Take this queue for example.

1. spawn e1
2. spawn e2
3. add Mass to e1
4. add Velocity to e2
5. add Velocity to e1
6. <custom command 1>
7. add Mass to e2
8. <custom command 2>
9. spawn e3

The batching process will link commands on each entity so that we only move it once, to its final archetype. This will "shift" all the operations on e1 ahead of all operations on e2 and "shift" the last e2 command ahead of <custom command 1>.

So with batching, things will happen in this order.

1. spawn e1 with Mass and Velocity
2. spawn e2 with Mass and Velocity
3. <custom command 1>
4. <custom command 2>
5. spawn e3

The reality is that custom commands should never make implicit assumptions about which entities exist and what components they may or may not have. i.e. If you pushed <custom command 1> assuming that Mass won't have been added to e2 yet, that isn't safe to assume. I don't think we explicitly encouraged assuming things before, but it'd be actively discouraged after this.

Also, this behavior is how flecs (a real ECS library that is currently faster and has more features than bevy_ecs) does command batching², so it is not impossible to implement or unbearably disruptive to users.

Footnotes

1. (edit) Before anyone says anything about performance, when I say "re-order" and "shift", I don't mean moving the commands around in memory. The command queue will just be iterated twice. Once to link the commands for the same entity together and a second time to apply. ↩

2. flecs does not support custom commands, but it says the same about its "observers" (which are custom user callbacks). There are some other, minor differences due to how flecs runs systems differently, but those aren't particularly important. ↩

[alice-i-cecile]

I'm pretty sure batching is orthogonal to this.

After more thinking, I agree.

[RedMindZ]

I think the core question here is what exactly is the purpose of Commands:
According to the docs:
Each command can be used to modify the World in arbitrary ways

I think the most valuable part of commands is the ability to delay mutating the world, thus allowing all of the non-mutating functionality to be executed in parallel. Giving all of the responsibility of mutating the world to Commands means that commands should have the full power to mutate the world in any order, and that power is lost by reordering the commands.
It is possible to instead delegate some of the responsibility of mutating the world to exclusive systems, but that should really be a last resort, given that they 'pause the world'. In some situations, it might be that case that all of the performance gained by batching the commands is dwarfed by the time wasted waiting for an exclusive system to mutate the world. Although, applying the commands is essentially the same as executing an exclusive system, so moving the work from commands to exclusive systems might not actually have a performance difference.

The reality is that custom commands should never make implicit assumptions about which entities exist and what components they may or may not have

Given your example queue, imagine that <custom command 1> ends up reducing to add Mass to e2. This could be the case if <custom command 1> is a more complex command, that in this specific invocation only ends up adding the Mass component to e2. Without batching, the final mass of the entity will be the one specified in command 7, but with batching the mass will be the one specified in command 6. Even thought the custom command didn't assume anything about the other commands, the results end up different.

I think that at best, it is possible to batch non-custom commands that don't cross custom command boundaries. And even that requires the engine developer to ensure that the type of commands being batched can be reordered safely, which increases the difficulty of developing the engine.

[maniwani]

Given your example queue, imagine that <custom command 1> ends up reducing to add Mass to e2. This could be the case if <custom command 1> is a more complex command, that in this specific invocation only ends up adding the Mass component to e2.

Without batching, the final mass of the entity will be the one specified by command 7, but with batching the mass will be the one specified in command 6. Even thought the custom command didn't assume anything about the other commands, the results end up different.

Today, you can already write two systems that queue add T to e1, with those commands set to be applied at the same sync point. You can't assume which one runs first unless you ordered the systems. It's already fragile. You already can't rely on a total order of commands in all cases.

You don't know what systems plugins have scheduled. And if we merge #9822 (which I want to do), you won't even know exactly when commands are applied.

I think that at best, it is possible to batch non-custom commands that don't cross custom command boundaries. And even that requires the engine developer to ensure that the type of commands being batched can be reordered safely, which increases the difficulty of developing the engine.

I don't see room for compromise. We can't make any exceptions because we will run into this exact same problem when we try to implement our own version of flecs observers (custom callbacks with the same powers as custom commands) to react to things like "T was added to an entity".

That kind of immediate reactivity will put us in a situation where custom user code is potentially running right after every entity command, and if custom code creates boundaries, then we'd be back to zero batching, which is not acceptable.

Giving all of the responsibility of mutating the world to Commands means that commands should have the full power to mutate the world in any order, and that power is lost by reordering the commands.

Commands have no outside context. A command can't assume what happened before it or what will happen after it. And that will be even more true with the reactivity I just mentioned.

From my perspective, we have a lot to gain (performance and reactivity, the lack of which are real, tangible problems) and little to lose by batching over custom code. The fact that flecs has adopted the behavior I described (it's where I got the idea from) and has never looked back is a pretty strong indicator that it won't be nearly as bad as you're worrying it will be.

[RedMindZ]

A command can't assume what happened before it or what will happen after it

I think this could lead to very unintuitive code if taken to the extreme. For example, if we have the following system:

fn my_system(mut commands: Commands) {
    let entity = commands.spawn_empty().id();
    commands.add(MyCustomCommand::new(entity));
    commands.entity(entity).insert(Transform::default());
}

I would find it very surprising to discover that Insert was executed before MyCustomCommand. If this is the path we take, there should at least be a warning in the docs of Commands that commands can execute in an arbitrary order.

The fact that flecs has adopted the behavior I described (it's where I got the idea from) and has never looked back is a pretty strong indicator that it won't be nearly as bad as you're worrying it will be

My main worry comes from my own experience with #10122; The core problem comes from systems that share mutable state through a resource: these systems are unware of their own execution order, and therefore they can only generate commands based on the state that they observe when they run. They always generate the correct commands for the state, and the purpose of these commands is to reflect the state into bevy's world. But then the commands don't get applied in the same order as they are spawned, which in the best case would lead to a desync between the state and bevy's world, and in the worst case, a panic.

For my personal issue, infallible commands will work, but I'm just not sure this is a solution that scales: the current bevy commands can easily become infallible, but what if in the future a new command gets added where its not trivial to make it infallible? and even worse, now all users who implement custom commands will have to be aware of the delicacies of implementing custom commands that never fail and are completely order-independent. This can lead to extremely hard-to-debug bugs.

I hope batching won't be problematic and yield good performance, but I just got burnt by #10122 and I hope I can help the future implementation avoid the problems I faced.

[maniwani]

I would find it very surprising to discover that Insert was executed before MyCustomCommand. If this is the path we take, there should at least be a warning in the docs of Commands that commands can execute in an arbitrary order.

That's fine. The docs should definitely call these things out. It's just pointless to implement batching if we also had to enforce a rule that it must stop at custom code. That's just not an actionable path to take.

What if in the future a new command gets added where its not trivial to make it infallible?

"Infallible" was a poor choice of words on my part. I was only talking about the panic that happens when entity commands just exist in the "wrong order", like remove being in line after a despawn command. When we finally decide to stop panicking over that, I can't imagine a command we could possibly add that would introduce a new ordering dependency.

users will have to be aware of the delicacies of implementing custom commands

If there are situations where a user can understandably write custom commands that depend on order (unrelated to the existing panic), it'd help to highlight some examples, because I'm drawing a blank. If those patterns exist, maybe custom commands aren't the right tool, something else could be better.

Also, I only said "infallible" with respect to our built-in commands. If users want their custom commands to error, by all means, but I don't think those errors would result from stuff happening between the command's dispatch and its application.

[RedMindZ]

It's just pointless to implement batching if we also had to enforce a rule that it must stop at custom code

I agree, most of the benefit would be lost this way.

If there are situations where a user can understandably write custom commands that depend on order (unrelated to the existing panic), it'd help to highlight some examples

I think the main example here is using commands to sync up the different parts of the state while avoiding taking a mutable reference to them to enable parallelism:
Let's say we have 2 systems (A and B) that take a mutable reference to GameState. Both of these systems want to update the Score resource based on the current GameState, but they don't even take a reference to the Score to reduce the dependency between them and other systems. Now, system A correctly responds to the game state and adds the command Score += 5. Then, system B runs, correctly responds to the state, and adds the command Score *= 2. If the order of the commands from A and B gets switched, the score would end up incorrect.
In this example, we could also replace the Score commands with Insert commands of the same component, and if the order is unreliable, you may end up with the component inserted by A rather then the component inserted by B.

Of course, this example could be fixed by either guaranteeing that custom (and Insert) commands maintain their relative order, or simply by taking a mutable reference to the score. I don't think this example is perfect, but I think it hints at a potential issue.

Given that I don't have a better example, I think I am coming around to the idea of batching, and maybe the ultimate solution for now is to add batching with good docs that detail the potentially surprising pitfalls that could catch users by surprise. If eventually someone has a real world example where batching is unsatisfactory, it should probably become configurable during application creation for users who would rather have ordered commands instead of faster commands.

[maniwani]

Let's say we have 2 systems (A and B) that take a mutable reference to GameState. Both of these systems want to update the Score resource based on the current GameState, but they don't even take a reference to the Score to reduce the dependency between them and other systems. Now, system A correctly responds to the game state and adds the command Score += 5. Then, system B runs, correctly responds to the state, and adds the command Score *= 2.

Is there any significance to taking a mutable reference to GameState in this example? The problem would still happen if both systems had a Res<GameState> instead.

If the order of the commands from A and B gets switched, the score would end up incorrect.

In this specific example, I don't think A or B would have come from a plugin if they're updating the game score. Presumably they're both the user's code, so scheduling B.after(A) would be the appropriate resolution. If you know a correct order, you have to tell the scheduler. Are you expecting app.add_systems(Foo, (A, B)) to just infer B.after(A) from the tuple order and both systems having a ResMut<GameState>?

If two systems have no discernible direct or transitive order (i.e. it's a toss-up who runs first) and both take a mutable reference to the same thing, bevy won't pick an order, but they'll be reported by the ambiguity checker.

I think the main example here is using commands to sync up the different parts of the state while avoiding taking a mutable reference to them to enable parallelism.

Mutable reference or not, if two systems with an ambiguous order both run and queue commands modifying X, then you can't know the final value of X with certainty.

This problem seems intrinsic to parallel system execution and the constraint-based scheduling approach.

Of course, this example could be fixed by either guaranteeing that custom (and Insert) commands maintain their relative order, or simply by taking a mutable reference to the score. I don't think this example is perfect, but I think it hints at a potential issue.

A guarantee that command queues are applied in the same order the systems ran would help users debug/identify a case of #10122, but I don't think that would address a broader thing—if systems can have a non-deterministic order and this is inherited by their command queues, then their commands also run in a non-deterministic order.

Something that's come up for discussion recently is whether or not the scheduler actually improves performance. Workloads that can actually benefit from parallel system execution—ones where the time saved by running systems at the same time is more than the time lost to the added overhead—are rare (most systems finish very quickly). In many of bevy's tests, the SingleThreadedExecutor performs roughly the same or slightly better than the MultiThreadedExecutor, and we lack data from actual games to know if/where that changes.

Anyway, making serial system execution the default (and also relegating the scheduler to a targeted optimization tool) is a possible outcome that would also resolve this issue.

(edit: Worth pointing out that serial execution still allows for rayon-esque parallel iteration inside the systems.)

If eventually someone has a real world example where batching is unsatisfactory, it should probably become configurable during application creation for users who would rather have ordered commands instead of faster commands.

I think it's too early to consider this. IMO the first response should be to see if there's a way a user can revise their code to do what they want. That pattern could then be highlighted in the documentation.

Just because something doesn't work how a user initially expects, doesn't mean the library needs to meet those expectations (by making it optional). I personally don't think batching should be something the user can turn off (or something they should even want to turn off). If an app was "large enough", you probably couldn't even get away with turning it off. I don't like the idea of a common piece of advice ("turn batching off") only working for, say, jam games.

(edit: For reference, commands are a known time sink for bevy, especially when it comes to preparing to render, and flecs's author shared some info about the performance impact of batching in flecs in this Discord discussion. So my speculation is the difference in performance is very significant and why sufficiently complex apps would simply be unable to turn it off.)