Skip to content

Instantly share code, notes, and snippets.

@LilithSilver
Created October 23, 2023 11:25
Show Gist options
  • Save LilithSilver/fac8493d09ef7e0519ff3cae20b267d2 to your computer and use it in GitHub Desktop.
Save LilithSilver/fac8493d09ef7e0519ff3cae20b267d2 to your computer and use it in GitHub Desktop.
Draft Arch.Scheduled feature document

Typed this up to get a better handle on what might be necessary in an auto-dependency management thing for Arch, while bloating Arch.Core as little as humanly possible.

It's a first draft, so don't take it as gospel; feel free to change things, or to reject it entirely!

My biggest priority here was to separate things into its own assembly, so that it wouldn't hugely change Arch.Core or the existing bits of Arch.Extended.

Arch.Core

To attach a JobScheduler, call World.AttachScheduler(myScheduler)

To do a scheduled query...

JobHandle World.ScheduledQuery(in QueryDescription queryDescription, ForEach forEntity, JobHandle handle? = null); // Scheduled query
JobHandle World.ParallelQuery(in QueryDescription queryDescription, ForEach forEntity, JobHandle handle? = null, batchSize? = null); // Scheduled and parallel query

To do an inlined scheduled query...

JobHandle World.InlineScheduledQuery<T>(in QueryDescription queryDescription, JobHandle handle? = null); // Scheduled query
JobHandle World.InlineParallelQuery<T>(in QueryDescription queryDescription, JobHandle handle? = null, batchSize? = null); // Scheduled and parallel query

To actually run the handles, once you've scheduled them all:

myScheduler.Flush()

Or:

World.Scheduler.Flush();

To wait on the returned handles, just call handle.Complete().

If the user isn't using Arch.Scheduled, they must take explicit care to...

  • Never make structural changes on a different thread
  • Never make structural changes on the main thread while other queries might be running
  • Never make non-atomic modifications to components at the same time, or read from a component while a non-atomic operation is currently happening
  • Always Flush() the scheduler and Complete() the handles when necessary

Implementation notes:

  • We should benchmark a reasonable default for batchSize based on archetype/L1 cache/etc, but allow overriding, since we don't know how much work is being done in the user's query.
  • If we want to be super clear that the parallel query is also scheduled, we could do ScheduledParallelQuery and [Obsolete] the old one.
  • Arch.Core will need some additional hooks for ScheduledWorld (see below), but nothing impacting the public API

Arch.Scheduled

Arch.Scheduled is a new piece of Arch.Extended that lets you write parallel queries in a way that automatically tracks dependencies.

ScheduledWorld leverages the already-present QueryDescription to track dependencies. QueryDescription (see notes) has several new options...

queryDescription
    // Provides the ability to make structural changes to the query. Available for non-scheduled queries only, and causes a global sync point.
    .WithStructuralChanges()
    // Marks the provided components as read-only for the scheduling system, if they exist in the query. This is not validated in any way on Arch.Core queries!
    .WithRead<T0, T1...>()
    // Marks the provided components as writeable, if they exist in the query. Arch.Core queries use `Write` by default, unless they are otherwise specified as `WithRead`.
    .WithWrite<T0, T1...>(); 

Then, when you schedule a query with any of the regular Arch.Core query scheduling methods (ScheduledQuery etc), the ScheduledWorld overrides set up a dependency network. It is no longer necessary to provide a JobHandle to track dependencies; it automatically creates a graph based on the rule that multiple queries can read components simultaneously, but if a query writes a component, it has to come before future readers or writers.

The normal main-thread Query methods now prevent structural changes by default, Flush() the scheduler, and block the main thread until any scheduled dependencies have been completed.

Structural change methods, when run outside a query, will each Flush() the scheduler and block the main thread until all scheduled queries are completed.

At the end of a frame (or whatever desired period before operations begin repeating themselves), call ScheduledWorld.CompleteAllDependencies(). This will Flush() any un-flushed jobs and Complete() each handle scheduled so far.

Nested queries

Nested queries need some special consideration. They must be treated as an extension of their parent query, or terrible things happen. Imagine if you run a query that has its parent as a dependency -- you get deadlocked!

As a result, ScheduledWorld treats nested queries as an extension of their parent query. They can only run if the parent QueryDescription is the same or larger in scope to theirs. For example, if one query writes Alpha and reads Beta and Gamma, it can only run child queries that write (or read) Alpha, and read Beta and Gamma.

This special case is the main use-case for QueryDescription.WithWrite<...>(): It allows specifying writable components that might not be present on the parent query's entities, but are necessary for child queries.

New error handling

ScheduledWorld introduces several new restrictions for dealing with queries. The following are explicitly prohibited:

  • Not allowed: Scheduling other queries from within any query
  • Not allowed: Running main-thread queries within another query, unless their QueryDescription has compatible dependency restrictions with the enclosing query
    • If the parent is scheduled, the children will run synchronously on the thread that is running the parent.
    • (How do we validate this implementation-wise? not sure.)
  • Not allowed: Making structural changes in a different thread, or without WithStructuralChanges() on the QueryDescription
    • I.e. main-thread queries must specifically opt-in to structural changes.
    • Use an ECB if you want to delay the sync point until later.

Hooking into the automatic system

Maybe you want to run a custom scheduled job, before or alongside your query. You can override the default dependency behavior by providing a JobHandle to the query, just like before. However, to ensure your query can work with automatic component dependencies, you need to grab this handle with your Entity's queryDescription and use it somewhere in your dependency chain:

JobHandle GetDependency(in QueryDescription description)

For example, if you wanted to run a custom InitArrayJob job prior to running a query to fill the array:

var customHandle = world.Scheduler.Schedule(new InitArrayJob());
var queryDescription = new QueryDescription(...);
var dependency = world.Scheduler.CombineDependencies(new[] { customHandle, scheduledWorld.GetDependency(queryDescription) });
scheduledWorld.ScheduledQuery(queryDescription, (...) => { ... }, dependency);

If you don't use the handle, your query might run at the same time as a conflicting query, so be careful when overriding the default behavior!

Implementation notes:

  • For the QueryDescription API, it would require the ability to extend QueryDescription somehow, but I'd like to avoid bloating Arch.Core. I'm not sure how.
    • One option is to add the methods in Arch.Core but make them internal, and use InternalsVisibleTo to make extension methods for them in Arch.Scheduled.
      • That might not be possible though -- does InternalsVisibleTo work across Nuget packages? I've never tried. If this works it's my favourite solution for sure.
    • Another option is to create a custom QueryDescription and force the user to use separate overrides on ScheduledWorld. That seems a bit confusing, though.
    • The last option is to have the API present in Arch.Core, but without any purpose. Not ideal at all.
  • For ScheduledWorld to override World, there would need to be some manner of method abstraction, but we definitely can't use virtual methods if we want to keep things speedy.
    • One option is a hook system. Wherever we need a hook for Arch.Scheduled, add a special protected Action? on World, that is normally null. So, the only overhead in Arch.Core is checking to see if that hook is null. Then, ScheduledWorld actually sets those hooks:
      • Action<QueryDescription>? BeforeQuery, so ScheduledWorld can Complete() any needed dependencies and disallow structural changes.
      • Action<QueryDescription>? AfterQuery, so ScheduledWorld can stop tracking nested queries and re-enable structural changes.
      • Action<QueryDescription>? BeforeScheduledQuery, so ScheduledWorld can do validation on a query before it has been scheduled (i.e. disallow structural changes)
      • Action<QueryDescription, JobHandle>? AfterScheduledQuery, so ScheduledWorld can track the produced handle in the dependency graph
      • Action? BeforeStructuralChange, so ScheduledWorld can prevent a non-specified structural change if within a query, and Complete() all dependencies outside of one.
    • Another solution is to make ScheduledWorld a wrapper around a private World, mirroring each method as necessary, but that's a lot more work. It is, however, the most efficient solution: everything can be inlined!
      • Maybe there's a source-generator thing we could do, to automatically create wrappers? Seems hard, but it might be necessary, especially considering Accessors.g.cs generating a bunch of World methods. Not to mention the many many World extension methods in both Arch and Arch.Extended... yikes.

Arch.System/Arch.System.SourceGenerator

Tag a query with [Scheduled] or [Parallel] to tell it to schedule on execution instead of immediately running. It causes the generated query method to return a JobHandle.

Use [WithStructuralChanges] on a non-scheduled [Query] to cause it to create a global sync-point when run, and allow structural changes from within the query.

in vs. ref on the query method parameters is equivalent to specifying WithRead() or WithWrite() on the QueryDescription, and comes with strict validation on struct components! For class components, in doesn't prevent you from modifying the class data, so make sure to either avoid writing an in class, or make your classes concurrent.

However, if your source-generated query references nested queries, you can tag a query with [Read<T0, ...>] and [Write<T0, ...>] to allow the nested query to run on those components, without having the parent component require them.

@genaray
Copy link

genaray commented Oct 24, 2023

Looking fine so far! ^^

The only "problem" is the number of overrides required to realize ScheduledWorld.
Overriding all structural change methods and all queries to make them a sync-point is incredible much work. However, integrating it directly into arch is a no-go. I wonder if there's a more decoupled approach.

What if we just let the user control the sync points without any automation? It would be a bit more "dangerous", however this way we would not need to override any methods or wrap them. We could however provide an analyzer that checks the code to provide feedback to the user, like : "You forgot a sync point there, add it!" or "You create entities, u sure that there's a sync point?".

Arch.Scheduled could just act as a source generator to generate fitting code within systems. Or we could just implement it into the system source generator directly. Or just less automation in general for Arch.Scheduled? Is there an alternative to callbacks from Arch.Core (E.g. callbacks when structural changes happen)?

Its really very complex, there must be a "clean" way without any major drawbacks.

@genaray
Copy link

genaray commented Oct 24, 2023

The more i think of... the more i like the idea of a ScheduleWorld being a whole wrapper and we just generate all the required methods. In the end its the fastest solution. Furthermore generating all those methods is "fairly" easy. Probably we can even use a source gen to do that, like picking all required methods from Arch.Core, generating wrapper ones that synchronize the world upon call automatically.

@LilithSilver
Copy link
Author

LilithSilver commented Oct 24, 2023

Yeah, I think that's the move too. There has to be a way to do this with sourcegen. What if in Arch.Core we tagged methods with [StructuralChange], and treated those specially?

We could also introduce an IWorld Interface in Core so that the extension methods would work with both? There would be slight overhead due to vtable dispatch though

@LilithSilver
Copy link
Author

LilithSilver commented Oct 24, 2023

One alternative for extension methods (if the vtable is too much for those for interface) is we tag them with [WorldExtensions] and copy them wholesale. That would actually be really easy. The tough part is arch.extended.... Cross dependencies between assemblies get weird.

@genaray
Copy link

genaray commented Oct 25, 2023

Yeah, I think that's the move too. There has to be a way to do this with sourcegen. What if in Arch.Core we tagged methods with [StructuralChange], and treated those specially?

We could also introduce an IWorld Interface in Core so that the extension methods would work with both? There would be slight overhead due to vtable dispatch though

That's a really good idea. Arch could simply annotate the methods to give them a "meaning". We get in the source-gen simply all methods that are relevant to us, based on the attributes, wrap them and call them in the wrapper. And boom we have a scheduled world with high-performance, without virtual calls or events. We could also potentially just extend world (so existing extensions work for both) ^^ we would have duplicated methods in that case, but its still faster than an interface. (Wondering how much slower an common IWorld interface is actually... ).

@LilithSilver
Copy link
Author

Calling from IWorld would be roughly equivalent to a virtual call, since it has to look up the vtable, so it's probably best to avoid the interface.

I'm working on a wrapper sourcegen and it's already working pretty well with minimal effort. It'll just need some fine-tuning. I think this is a good plan!

I don't think extending World is the way to go, because if we override methods with new, the bad methods are still accessible.

The big question is still extension methods though. Arch.Core extensions are easy, we just sourcegen duplicate those. Arch.Relationships is the only other package that uses them, so we've got four options:

  1. Reference Relationships in Scheduled and sourcegen them
  2. Reference Scheduled in Relationships and write out the overrides (there's not much)
  3. Make a third assembly that combines the two
  4. Make an IWorld interface, and eat the vtable lookup cost for Relationships.

Which one would be best? (Or am I missing anything?)

@LilithSilver
Copy link
Author

Oh, I just thought of something: Regardless of if we actually use an IWorld interface, we absolutely should make one. Because: Documentation! It's pretty difficult to grab documentation in a source generator (we'd have to load in a pdb into Roslyn probably, somehow). But it's easy to use <inheritdoc/>.

@genaray
Copy link

genaray commented Oct 25, 2023

We should take another look there. I think even if you don't call the interface method directly, there is no overhead. Only when you work with the interface this happens. So theoretically the whole thing could still be inlined.

But that would be a lot of fucking work to push all the methods into an interface now. So I would almost say that we do that later and concentrate on the rest for now xD

@LilithSilver
Copy link
Author

Ha, yeah, that makes sense! And yep, you're right, the only overhead is if you actually use the interface. Nothing wrong with just having one.

We can skip all that for now and address Arch.Relationships later.

I just have two more questions before it's clear to me exactly what to do:

  1. QueryDescription needs WithRead, WithWrite, and WithStructuralChanges. A couple options:

    • Add them to Arch.Core, keep them internal.
    • Create a sourcegen ScheduledQueryDescription wrapper that is only used by the wrapped query methods of note. Write extension methods and implicit operators to make compatibility easier. (probably needs internal access for component arrays).
    • Don't use QueryDescription: use some other structure, and pass an extra parameter to all the query methods.
  2. Is InternalsVisibleTo for Arch.Scheduled OK/even possible? I've already run into an issue while experimenting with a prototype: Group<T0...>.Types is internal, but Scheduled probably needs access to determine reading components. I think there are probably more internal things needed too. The alternative would be to copy a bunch of stuff over, or make some things public (maybe both).

@genaray
Copy link

genaray commented Oct 25, 2023

Ha, yeah, that makes sense! And yep, you're right, the only overhead is if you actually use the interface. Nothing wrong with just having one.

We can skip all that for now and address Arch.Relationships later.

I just have two more questions before it's clear to me exactly what to do:

  1. QueryDescription needs WithRead, WithWrite, and WithStructuralChanges. A couple options:

    • Add them to Arch.Core, keep them internal.
    • Create a sourcegen ScheduledQueryDescription wrapper that is only used by the wrapped query methods of note. Write extension methods and implicit operators to make compatibility easier. (probably needs internal access for component arrays).
    • Don't use QueryDescription: use some other structure, and pass an extra parameter to all the query methods.
  2. Is InternalsVisibleTo for Arch.Scheduled OK/even possible? I've already run into an issue while experimenting with a prototype: Group<T0...>.Types is internal, but Scheduled probably needs access to determine reading components. I think there are probably more internal things needed too. The alternative would be to copy a bunch of stuff over, or make some things public (maybe both).

  1. Would it be hard to add a sourcegen to create a wrapper for QueryDescription? Couldnt we just add WithRead etc. as pure extension methods without any wrapping and stuff?

  2. No not really... but we can provide more API to make such classes accessible from the outside ^^
    I could also imagine that in some cases we would need slightly modified versions (e.g. the group<t...> could store more meta-data for us?) .

@LilithSilver
Copy link
Author

Would it be hard to add a sourcegen to create a wrapper for QueryDescription? Couldnt we just add WithRead etc. as pure extension methods without any wrapping and stuff?

Yep, that would probably work!

No not really... but we can provide more API to make such classes accessible from the outside ^^
I could also imagine that in some cases we would need slightly modified versions (e.g. the group<t...> could store more meta-data for us?) .

Maybe, yeah; it depends on how the tracking ends up working!

Regardless, I'll get started on a prototype and see how far I get. Might be a little while though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment