search

evaera / matter

A modern ECS library for Roblox.
https://eryn.io/matter/
MIT License
144 stars 34 forks source link

Fixed loop scheduling #96

Closed metrowaii closed 8 months ago

metrowaii commented 8 months ago

There are two problems with the current loop scheduler. The first being that the order of systems after the initial table.sort was non-deterministic. The second being that the logic for cycle detection was incorrect.

To solve the first problem I switched the "_systems" table from a set to a list. Switching it to a list should not have that big of an impact on performance as games will most likely not have more than a few hundred systems (if that). I also added logic to handle the case where system names are equal - in that case we simply fall back to the original unordered list systems effectively relying on the order provided by the user.

The second problem came up when we had a system with dependencies on other systems. If the initial table.sort call returned an order such that this system (the system with dependencies on other systems) appeared first in the list the cycle detection logic would incorrectly error. For example if we had three systems, systemA, systemB, and systemC, and systemA had a dependency on systemB. If the initial sorting returned an order such that systemA appears first, systemB appears second and systemC appears last then by the time systemB is to be scheduled it would see that systemA is still in the explore phase and throw an error for a cycle which is incorrect.

I overhauled the scheduling logic to use a more straightforward approach - recursive DFS with colors or phases in this implementation.

Closes #92

Ukendio commented 8 months ago

Overall I think I am happier with this change than without. Because it is more readable with the recursion over iteration here. I am going to check this out locally and see if there are any regressions.

Additionally I might have more comments later on.

benbrimeyer commented 8 months ago

Should we add tests for the cycle behavior to help pin it? The test would also help describe the problem you are solving

metrowaii commented 8 months ago

Should we add tests for the cycle behavior to help pin it? The test would also help describe the problem you are solving

Checked the loop tests file and the "should call systems in order" test covers the example I gave. Just imagine that the order produced by the table.sort function (before my changes) was systemC -> systemB -> systemA. If you run through the old logic with this order in mind you'll notice that the cycle detection logic gets triggered incorrectly.

LastTalon commented 8 months ago

I haven't had a chance to look at these changes myself yet, but if there were two things that regressed I would ideally like tests that cover each before merging.

metrowaii commented 8 months ago

Moved PR to https://github.com/matter-ecs/matter/pull/1