System scheduling

[davidscherer]

The Bevy website says:

We are also actively seeking feedback on the new executor. We believe that the new implementation is easier to understand and encourages self-documenting code. The improved parallelism is also nice! But we want to hear from users (both new users starting fresh and old users porting their codebases to the new executor). This space is all about design tradeoffs and feedback will help us ensure we made the right calls.

I am really hoping that this is true. I am a new user of Bevy, and I have found that I like most of its design decisions a lot, but I have grave concerns in this area. I think that it is possible to move the frontier of tradeoffs, not just move along it.

Please read my comments in a respectful and constructive tone!

First of all, I think that the major advantage of the current ("new") executor interface is actually one that is not stated very clearly on the page linked above: it provides a way to specify the interleaving of systems that are defined by different plugins. This is a very important capability in a plugin-based engine architecture and must be addressed by any proposed improvements.

Secondly, so you understand where I am coming from, I think there are usually only two reasonable choices of goal for the end effect of the schedule in a particular game: either (a) perfect determinism (as required by deterministic netcode, replay, etc; it's also the easiest model to reason about, test, and debug), or (b) qualitative determinism (there may be small errors because e.g. floating point addition is not commutative, and intentionally random behavior may be sampled differently, but the probability distribution of behavior of the game does not depend qualitatively on scheduling decisions). My personal belief is that perfect determinism should be the default in the ecosystem, because it is the safest, most easily testable, and most composable choice. (For example: It's fairly easy to test if a plugin you are considering adopting is perfectly deterministic, but very hard to tell the difference between one that is qualitatively deterministic and one that has bugs but only if the number of CPU cores is not a multiple of 4. And you know that any combination of two deterministic plugins is deterministic, but the combination of two qualitatively deterministic plugins might not be qualitatively deterministic!) But there are costs in effort and performance that can add up, so reasonable minds could differ on this point. In any case both must be supported, and in any case there is no use for schedules that produce materially ambiguous results; those are almost by definition difficult-to-reproduce bugs waiting to emerge on particular combinations of hardware, room temperature, changes to unrelated systems, and situations in the game.

Unfortunately, the current design makes materially ambiguous schedules the default, and makes it unergonomic, error-prone, and slow to do anything else. In many cases the material problem caused by an ambiguity will not manifest until long after it is introduced or after the plugin containing it is combined with others. I think this is a very serious problem that will compound over time. Even if I fix this for myself, I have to expect that third party plugins are going to be buggier than they otherwise would be (and that their bugs might arise only in combination), just as undefined behavior and data race issues make dependencies risky in a C++ engine.

I do not find that the duplicated information about system inputs and outputs in my build code makes my code particularly "self-documenting". The reason that system A needs to run before system B is, for example, that system A produces a component each frame that system B consumes. Even if I write some traits that let me "document" that, like

    .add_system(determine_dt.system()
        .sole_producer::<DT>()
        .consumes::<Time>())
    .add_system(controls.system()
        .ordered_producer::<Transform>(&mut transform_order)
        .ordered_producer::<Momentum>(&mut momentum_order)
        .consumes::<Input<KeyCode>>()
        .consumes::<Mass>()
        .consumes::<DT>())
    .add_system(drag.system()
        .ordered_producer::<Momentum>(&mut momentum_order)
        .consumes::<Drag>())
    .add_system(momentum.system()
        .ordered_producer::<Transform>(&mut transform_order)
        .consumes::<Momentum>()
        .consumes::<Mass>()
        .consumes::<DT>())

I have just mechanically duplicated (and have to maintain) a bunch of information that was already in the type signatures of the systems involved. I can use ReportExecutionOrderAmbiguities to verify that the resulting schedule is not ambiguous, but it can't verify that the duplicated information here isn't wrong or out of date (and perhaps restricting the schedule unnecessarily), and it will also, necessarily, demand ambiguity sets for systems that Bevy, at runtime, could prove are not conflicting. The ergonomics of this entire process are bad, which is very sad because so much effort has gone, from what I can tell successfully, into making the other parts of Bevy's ECS painless to use.

Moreover, it's not actually that great for performance. For one, the second easiest thing to do (after leaving the schedule completely ambiguous, most likely creating a combinatorial explosion of bugs) is to make the schedule completely serial, which likely gives up much more performance than just constraining the order. Secondly, specifying the order of two systems always forces the scheduler to execute them serially, even if it turns out (e.g. because of the exact set of archetypes at run time) that they could execute not just in either order but in parallel. Thirdly, having more bugs to track down means having less time to optimize. Worst of all, systems are not really the right granularity for parallelism. If you are serious about performance, you are going to want expensive systems to generate multiple tasks using, for example, .par_for_each_mut(). But the proper dependencies among these tasks permit much more parallelism (not just more reordering!) than dependencies among the systems that generate them! If system A mutates a component which system B consumes, then the task that consumes that query in system B for the first 1024 entities in archetype X can't be started until the tasks (if any!) that mutate the first 1024 entities of archetype X in system A are complete. But that doesn't mean that the two systems cannot significantly overlap, even in a perfectly deterministic schedule!

I think it is possible to be more ergonomic, faster, deterministic by default, and still make interleaving between plugins specifiable. But I do not think it can be done entirely by layering something on top of the existing interface.

The following proposals should be understood as very tentative. I'm far from an expert on Bevy yet.

1. At minimum, I think something like an interface distinction between after and as_if_after is needed at a low level (in the executor itself). after is documented and implemented as ensuring that the execution of the systems does not overlap in time at all (serial execution); as_if_after would constrain the executor only to ensure that any effects of an "earlier" system in this graph visible to the "later" system through components or resources are visible to the "later" system as it executes (serializable execution). as_if_after cannot be implemented efficiently in terms of is_after; after cannot be implemented at all in terms of as_if_after without the ability to add some kind of false conflict.

2. Given a good implementation of as_if_after, specifying an ordered sequence of systems with it will produce a serializable schedule at least as performant as the best schedule that would currently pass ReportExecutionOrderAmbiguities without ambiguity sets (and sometimes a better one, because sometimes a conflict can only be proved impossible at runtime). If you want a schedule faster than that, you should opt out of serializability in some way, asserting (as with ambiguity sets) that you have proven (and commit to maintain) some systems sufficiently commutative.

3. To improve the ergonomics while preserving plugin interleaving, I suggest an algebra of system sets (this PR might be a starting point for this part?), perhaps very roughly like

    // SerializableSystemSet systems run exactly "as if" in the order defined with respect to all 
    // components and resources, but systems may *actually* run in parallel or in a different order.
    SerializableSystemSet::new()
        .defines_label( PublicLabel1 )
        .then( OtherPlugin::Label5 )
        .then( system1 )
        .then( system2 )
        .then( OtherPlugin::Label6 )
        .then( system3.system().defines_label(PublicLabel2) )
        .then(
            PerfectlyCommutativeSystemSet::new()
                // These systems will run with the maximum mutual parallelism consistent
                // with memory safety, no matter what apparent conflicts they have. They 
                // will still be serializably ordered with respect to the systems in the parent
                // system set. Ideally, automated tests will fail if changing the order of the
                // systems changes the outputs.
                .add_system( system4a )
                .add_system( system4b )
            )
        .then(
            AlmostCommutativeSystemSet::new()
                // Behaves like PerfectlyCommutativeSystemSet in qualitative determinism
                // mode, and like SerializableSystemSet in perfect deterministic mode. Alas,
                // there is no good automated way to test this assertion.
                .then( system5a )
                .then( system5b )
        )
        .then(
            CompletelySerialSystemSet::new()
                // These systems will run with no mutual parallelism whatsoever, i.e. 
                // separated by `after`. They will still be (only) serializably ordered with respect
                // to the systems in the parent system set
                .then( system5 )
                .then( system6 )
        )
        .then( system7 )

4. Although this algebra makes it painless to specify serializable schedules for a single plugin, the underlying model is still defaulting to ambiguity, so you can still get undeclared ambiguity where components and resources cross plugins (e.g. just omit the references to OtherPlugin labels in the above example). I think it might be OK to rely on ReportExecutionOrderAmbiguities for that if it can be enabled by default. A more radical approach might be to tie bringing components from another plugin "into scope" for the systems in your SystemSet to including an appropriate label from that plugin into your SystemSet - essentially this would be a similar check but it could be stricter and the error message would be more helpful: "system1 wants OtherPlugin::Component1 but it has not been brought into scope for it. Try giving it or an enclosing SystemSet a dependency on OtherPlugin::Label5 or OtherPlugin::Label6." This is not a fully baked idea, but the mental model is that every SystemSet (including individual systems) gets its inputs and provides its outputs to either an enclosing SystemSet or to/from a SystemSet or label that it mentions explicitly. So if I want to use Transform in my plugin, I can either .then( Renderer::Render ) afterward (so that something I explicitly mention consumes the component) or else callers of my plugin must consume Transform for me (e.g. by .then( MyPlugin::FrobTransform ).then( Renderer::Render )).

5. Task-level dependencies could be a separate project, focused entirely on (primarily opt-in) optimization. For example: ParallelQuery only exposes .par_* methods (which don't wait for completion? have to think about that), and a system taking a ParallelQuery could therefore be scheduled without regard to any conflicts created by that query. Then .par_for_each would equip each of its tasks with the necessary dependencies created by those conflicts. Or you might actually need AsyncQuery, so that the system can be rescheduled when its tasks are finished. There are lots more potential parallelism killers to attack (ResMut, commutatively mutable components, etc)

I hope this is understandable and a helpful starting point for discussion.

I have some sympathy for more radical approaches like #2259, because although I want modularity I never asked for the requirement of writing the top levels of my game not in Rust but in a language with just global variables, conditionals, and function calls (but not function parameters or definitions), even without the additional requirement to explicitly specify the dataflow dependency graph between every line of code in it. I suspect that the problems with modularity could be addressed somehow; perhaps for example where today a plugin would export a label so that you can inject systems into the middle of its processing it would instead accept a function over all the components and resources available at that point? But it is very speculative and I think there are some tough challenges, and so it would probably be a mistake to make solutions to (what I see as) serious problems dependent on that.

[alice-i-cecile]

Plugin interop

First of all, I think that the major advantage of the current ("new") executor interface is actually one that is not stated very clearly on the page linked above: it provides a way to specify the interleaving of systems that are defined by different plugins. This is a very important capability in a plugin-based engine architecture and must be addressed by any proposed improvements.

I agree with this; being able to convince plugins to play nice with each other (and your own app structure) is one of the major benefits of label exporting. See #2160 for some more discussion on this, and how we might extend it further. The fundamental tradeoff to be made here is configurability vs leaking internal details everywhere and making it far too easy to break the invariants of your dependencies.

[alice-i-cecile]

As-if dependencies

I think something like an interface distinction between after and as_if_after is needed at a low level (in the executor itself). after is documented and implemented as ensuring that the execution of the systems does not overlap in time at all (serial execution); as_if_after would constrain the executor only to ensure that any effects of an "earlier" system in this graph visible to the "later" system through components or resources are visible to the "later" system as it executes (serializable execution). as_if_after cannot be implemented efficiently in terms of is_after; after cannot be implemented at all in terms of as_if_after without the ability to add some kind of false conflict.

I agree; this is a solid idea. The distinction is meaningful, particularly with many-to-many labels.

We should add these as primitives, and then build higher level APIs to support both flavors of dependency edges.

[alice-i-cecile]

Some early thoughts on names:

• as_if_before: very unclear to new users, quite academic. Technically accurate, but requires a lot of context.
• prefer_before: simple and reasonably intuitive. The exact nature of the hinting being done is ambiguous though, and I expect we'll want other forms of perf-oriented ordering hints in schedules eventually
• before_if_needed: clear and technically accurate, but a bit long for something that will probably be a better default than before when working with multiple systems. I like the fact that it starts with before for autocomplete reasons.
• before_if_conflicting: even clearer, even longer.

[TheRawMeatball]

An alternative we should consider is renaming the current before to something like strict_before and making as_if the default

[alice-i-cecile]

That would be a painful migration: code would continue to work, but with important and subtle distinctions scattered across the entire code base :(

I also think Ratys is right: explicit, simple behaviour should get the simple name, even if as_if_before is the behaviour users will tend to want in larger code bases.

[alice-i-cecile]

Higher-level system ordering APIs

These are definitely needed. #2381 is a solid starting point IMO; what additional functionality would you like to see?

Obviously we'd want some way to specify that subgraphs use as-if logic, but that's handled easily enough via some form of API specialization.

But I do not think it can be done entirely by layering something on top of the existing interface.

I fundamentally disagree with this. The existing parallel executor enforces the minimum possible set of forbidden system-overlaps; this is the correct starting point. Ordered dependencies ala .before are the natural edges in the system ordering graphs: any higher level API is going to construct these edges as a final step.

Task-level cross-system dependencies go beyond those primitives, but I don't think they're are a feasible idea. But I'll get into that in another comment to try and keep things organized :)

[davidscherer]

I do feel strongly that a solution to this is needed in Bevy (though not necessarily as the lowest level public interface in Bevy), and not just as a third party crate, because of the effects on the ecosystem of having most plugins have totally ambiguous schedules.

[Ratysz]

Apparently I was not clear.

Perhaps. The proposal mentions that the solution is not possible to be built on top of existing API, then lists several points, only one of which needs core changes.

However, I'm not sure you are right that something like my proposal 3 is less general [...]

I was referring to the desire to tie order to types. I think I've misunderstood that as being part of the proposal, rather than motivation for it.

Speaking of types, there's a fundamental issue with any API built on them as the source of truth for dataflow: types don't always map one-to-one to data they act on. Every time there's any sort of interior mutability, be it references or channels or anything else, the same data can be accessed through a different type. This is not an uncommon case, either: events are used throughout Bevy and are very popular with users, if codebases I've seen are indicative. (events don't use interior mutability, they're a funky double buffer that's accessed through a unified type for reading and writing)

This will have to be well-documented for as_if_after and APIs built on it.

[TheRawMeatball]

This is not an uncommon case, either: events are used throughout Bevy and are very popular with users, if codebases I've seen are indicative.

Events don't use interior mutability though.

[davidscherer]

Yes, I agree that interior mutability is an important limitation regarding the "as if".

It might also be worth discussing some use cases for interior mutability to see if there is anything the ECS can do to aid some of them other than shrug its shoulders.

[davidscherer]

For what it's worth, I don't particularly want to tie order to types. As discussed downthread, as_if ordered operations should happily overlap or change order if they happen to be touching different archetypes in a particular frame, and if we have task level dependencies they could overlap even more. I do want to overspecify rather than underspecify order by default without paying unnecessary performance penalties.

[alice-i-cecile]

Task-level dependencies

Fundamentally, these are going to play very, very poorly with Rust and Bevy's ownership model. As I understand it, (table-stored) data within the ECS is ultimately broken down into archetype-component blocks for efficient, dense memory storage.

Having two systems operating on different parts of the same data at once in sequence seems like a very large source of complexity and risk, and would require communication and polling of partially complete state. I worry that as your systems change during development, you'll need to be extremely careful to ensure that the invariants you need to safely perform this split are upheld.

However, you're absolutely correct that between-system parallelism is not the panacea: much of the work in many games is in fact going to be bottlenecked by a few heavy systems. I feel quite strongly that the correct path forward is to further optimize our very basic par_for_each tools (and related) tasks.

Ultimately, if you have extra threads free while waiting for a heavy system, why bother dealing with the complexity to split the work across multiple systems when you can just throw more threads at the heavy system directly?

[davidscherer]

This is not a hill I particularly want to die on personally - I don't forseeably need the performance. I mentioned this largely as an olive branch to people who care about maximizing parallelism more than anything else. If you ever want to do anything like this, you need something like as_if_after to provide enough scheduling freedom to do it.

However I absolutely think it is feasible without sacrificing memory or data race safety. You might need unsafe somewhere within the ECS to implement it efficiently, but it should be safe (and even perfectly deterministic) for users. The burden on users would just be to use appropriate query interfaces that allow the system to be suspended - either async or a variant of par_for_each that doesn't block the calling system. Doing this sort of thing without the support of the ECS would be absolutely bonkers dangerous.

Between-system pipelining could be very good for performance even if every heavy system is parallelized. You would need fewer tasks per system (and, hence, less overhead) to get good parallelism. You would lose less performance to variation in task time and to the "join" between dependent heavy systems. And it could be better for cache performance, too (having one CPU compute A->B and then B->C for a cache scale amount of data uses less memory bandwidth than doing all the A->B and then all the B->C). And there are probably also some systems that can be pipelined but cannot be parallelized.

[Rijaspb]

https://www.rijasexports.com/

[alice-i-cecile]

System order ambiguities

I'm very sympathetic to your concerns about the prevalence of system order ambiguities, and the "allow-by-default" stance that Bevy currently takes. I agree that they tend to create cascading risk as the project grows, and the bugs that they can introduce are very hard to identify (and right now, impossible to fix by default).

The idea of "deterministic by default" is appealing: see #2480 for some of my own thoughts on the matter. However, the proponents of the current approach have some solid points:

1. Aggressively enforcing ordering, either via the old implicit insertion-order approach or something like your CompletelySerialSystemSet, is prone to introducing serious fragility and nonlocal behavior. As you refactor in seemingly cosmetic ways, you may break these complex chains of dependencies, introducing new and terrible bugs. The inconsistent ordering can serve as a chaos monkey: breaking the fragile setup sooner rather than later.
2. Adding more dependencies inherently reduces system parallelism.
3. Rightly or wrongly, qualitative determinism and "consistent behavior" is the standard that games are developed to, particularly in the prototype stage. Thinking about system ordering can be a tedious distraction, especially when our tools to resolve ambiguities and specify complex dependencies are poor.

On that note, let's think about how we can improve those tools and bridge the gap. My opinion is still that system order ambiguities are sufficiently painful that they should be forbidden by default, but we're not likely to convince the rest of the dev team or user base until resolving every ambiguity is intuitive and maintainable.

Here's the steps I think we can take to get there. On the ambiguity front:

1. Improve the ambiguity detector's usability, following Simple improvements to ambiguity reporting clarity #1484.
2. Allow users to "lock in" a particular schedule, despite the presence of ambiguities. This is analogous to random number seeding, and is critical for debugging and could be useful for scientific and networking use cases. App executions should report this information in a reproducible way.
3. Add the ability to permute the order of two ambiguous systems from a locked system order (as described in 2).
4. Use 3 to create a user-friendly tool to automatically check permutations against a test-suite (see Allow bevy to be run as an integration test inside a #[test] #1057 and Cannot create Bevy app in tests due to non-main thread #1720 for some prerequisite work for integration testing) for failures. Allow for narrowing by component or resource type in question.
5. Allow users to change the ambiguity detector's behavior to "panic on failure".
6. Resolve all Bevy-internal ambiguities.
7. Consider implementing Archetype Invariants #1481.

2 and 3 must be permitted to pierce the plugin veil, otherwise bugs will not be able to be tracked down.

For system ordering:

1. Add a powerful system schedule visualization tool. This should show dependencies, run criteria, stages, labels and ambiguities. We'll need strong filtering tools for this in order to restrict to the slices that the user is currently thinking about.
2. Introduce a higher level graph API ala Add SystemGraph as a handle-based method for explicitly creating system dependency graphs #2381 which can be used in favor of the current labelling approach in many cases.
3. Reduce the strength of stage boundaries in various ways.
4. Improve the state abstraction to play nicer with other scheduler concepts.
5. Add "label properties", where system behaviours can be specified en-masse by adding the property to a label, which propagates down.
6. Rethink plugin configurability, ala Plugins should be more customizable and work with states #2160. This is an essential part of this work to ensure that users can resolve ambiguities with any plugin systems.
7. Add the "as if system dependencies" that you discussed in this post.

[davidscherer]

The thing that makes this intractable today is the requirement to specify the minimal set of dependencies between systems (or lose all parallelism) because after is too strong.

Once you have as_if_after and SystemGraph, the easiest thing to do in a plugin is to order all its systems (which, thanks to as_if_after, shouldn't produce particularly bad performance, and which guarantees no nondeterminism or ambiguities within the plugin). And plugins that have a dependency on other plugins should normally express their own relative ordering to those. The only remaining source of ambiguities is between plugins that share components but don't know about each other (e.g. two different things that mess with Transform). I think it is probably reasonable to use the ambiguity detector to detect and resolve these.

Once your schedule is free of "passive ambiguity", the only schedule-related source of nondeterminism is systems explicitly marked as commutative that aren't. And those can be detected rather precisely by running them a second time each frame in a randomized order and comparing the results. So you would run your game in determinism-checking mode, and it would give you specific errors like "System x is nondeterministic." or "Systems a and b are declared perfectly commutative, but are not" at the cost of doubled CPU usage.

This sort of testing could be very valuable even to someone who isn't shooting for determinism, in that it can be used to verify the commutativity of systems that you intend to not have any order dependencies.

[alice-i-cecile]

[Subtle nondeterminism] can be detected rather precisely by running them a second time each frame in a randomized order and comparing the results

I think this is a sensible strategy, but this will force PartialEq and Clone trait bounds on all components and resources. I'm not entirely opposed to that, but it's a cost worth bearing in mind. You could possibly bypass it / restrict it to a subset with some reflection nonsense (see #1515 for discussion), but I'd rather not delve down that rabbit-hole.

The largest issue there is actually Clone on resources: some outward-looking resources that interface with other libraries are not Clone for good reason.

[davidscherer]

Maybe something like a TryClone trait? I am too much of a Rust noob to know if it's possible to get a default impl for everything (that fails).

[alice-i-cecile]

Runtime ambiguity detection

[The ambiguity detector] will also, necessarily, demand ambiguity sets for systems that Bevy, at runtime, could prove are not conflicting.

This is a dangerous path: runtime detection is unreliable as the sets of archetype in the world may change at any hard sync in any way. The consequences of failure are critical: you will get crashes, horrible bugs, and genuine unsoundness.

The obvious solution is to run the runtime check each hard sync point, and then log and panic if it's detected. This is expensive and frustrating. Moreover, any guarantees that you receive here are provisional: prone to breaking suddenly during refactors, when loading scenes or when a previously unexplored corner case is hit.

#1481 attempts to bypass this, by forcing users to explicitly write out rules about the archetype identities that can be used by, among other things, the ambiguity checker. These would be enforced at component insertion and removal as well, but would represent explicit promises that we could use and reason about for other important things.

Archetype invariants are very much an experimental research project though. I'm quite fond of them, but it remains to be seen if they would be feasible for the average end user to reason about, and performant in production.

[davidscherer]

The ambiguity detector has to assume the worst, exactly because archetypes can change at runtime. An Orc picks up a torch, and suddenly there is a conflict between enemy_move and cull_lights.

But the executor's implementation of as_if_after does not have to assume the worst. When it wants to schedule cull_lights it can notice that enemy_move is as_if_before it and that this frame their queries have an archetype in common.

[Ratysz]

But the executor's implementation of as_if_after does not have to assume the worst. When it wants to schedule cull_lights it can notice that enemy_move is as_if_before it and that this frame their queries have an archetype in common.

This is how the executor works already, the only thing that's missing is the ordering bias.

[alice-i-cecile]

@davidscherer, would you be up for making a PR to introduce the "as-if" dependency edges and expose them in is_if_before and as_if_after? I think that we have agreement that such functionality would be a useful primitive, and it seems like the right place to start.

We should find a more intuitive name, but that's something we can discuss in the PR thread.

[cart]

This is close to the approach we currently take; nearly negating 3 as a constraint. Restrictions are calculated based on "any possible archetype", and ignore the run time state about which archetypes exist completely. Note that this is subtly different that "operate on the component level only", as this approach allows clever use of Without (or hypothetical archetype invariants) to reduce the conflicts significantly.

This is only true "inside systems" (ex: checking if queries conflict). The actual system scheduler is archetype-aware.

[alice-i-cecile]

This is only true "inside systems" (ex: checking if queries conflict). The actual system scheduler is archetype-aware.

Ah, that's where my confusion arose. Thanks.

[bilsen]

Should not the simple algorithm of adding every "as_if" as a hard dependency and then removing them wherever possible (the systems actually do not have conflicts) be sufficient?

[davidscherer]

@bilsen unfortunately not. It would be both sound and optimal to (1) take the transitive closure of the soft dependency graph, and then (2) remove the dependencies between pairs of systems that do not conflict. But the transitive closure may have O(N^2) edges, so it is not efficient. If you don't take the transitive closure first, it is not sound. (If A.as_if_before(B) and B.as_if_before(C) and A and C conflict, there must be a direct or indirect dependency of C on A, but that dependency edge is not one of the soft edges A<B or B<C.) And if you redefine the interface so this is not true, then making the scheduler efficient becomes easy but making, say, a simple ordered schedule of N systems will require O(N^2) calls to as_if_* and then the scheduling will still be slow (asymptotically fast in terms of a huge input).

[bilsen]

@davidscherer I see. The problem seems to be that for AIB (= as if before) to be a well-defined partial ordering then the graph must logically be extended with a transitive closure. I still think it is fine to do the transitive closure since 1) An O(n^2)* complexity is fine since the schedule is so rarely rebuilt 2) In the general case the dependency graph will be more "thick" than "deep" which means that the size of the transitive closure will not grow quite n^2. 3) If speed is still a concern, when the schedule is rebuilt the previous "actual" dependencies can be used as a starting guess which will make the process even quicker. * I realize now that its not quite O(n^2) since every edge must check wheter the accesses of the systems are disjoint, which is an intersection of two bitsets.