New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Deterministic Component Init and Update Order #303

Closed
ilexp opened this Issue Mar 10, 2016 · 14 comments

Comments

1 participant
@ilexp
Member

ilexp commented Mar 10, 2016

Summary

Right now, Components are initialized and shut down on a per-GameObject basis. This should be changed in favor of a per-Component-Type approach to mirror the new Update order based on Component types.

Analysis

  • This affects Activate / Deactivate and Loaded / Saving / Saved.
  • In some cases, a single object or set of objects will require initialization or shutdown outside the regular Scene-switch case. Always consider the current group of objects when determining the order of initialization and shutdown.

@ilexp ilexp added Task Core labels Mar 10, 2016

@ilexp ilexp added this to the General Improvements milestone Mar 10, 2016

@ilexp ilexp added the Unit Tests label Mar 10, 2016

@ilexp

This comment has been minimized.

Member

ilexp commented Feb 10, 2017

Behavior

In preparation for issue #304 and also to keep the system consistent within itself, all iterative operations on groups of Components should be affected in the same way.

  • Activate, Loaded, Saved forward-iterate by component type.
  • Update forward-iterates by component type.
  • User-defined queries (gameObj.IterateComponents, scene.FindComponents) iterate by component type.
  • Deactivate, Saving backwards-iterate by component type.

Cases to handle

In the easiest case, no iteration happens at all and no special handling is required:

  • A single component is activated or deactivated individually.
  • A single component is added to or removed from a GameObject.

Very little special case handling is required in cases where the existing implementation already operates on a by-type basis.

  • Components that are assignable to type X are queried via scene.FindComponents - since scenes already organize components by type internally, all the implementation needs to do is concatenate the sub-lists in the right order.
  • Scene updates are already performed by-type. All that needs to be done is give these updates a fixed order.
  • Scene initialization and shutdown (changing the active scene) are not yet handled by-type, but all the required information is there and organized as needed.

Little special handling is required in cases where iteration remains local on a single GameObject, and in fact this could be solved by keeping a GameObject's internal component list sorted:

  • A single GameObject with no children is activated or deactivated individually.
  • A single GameObject with no children is added to or removed from its parent scene.
  • A flat Prefab (no GameObject hierarchy) is loaded or saved.
  • The components of a single GameObject are iterated on using IterateComponents.

Other cases are more complicated to handle, because they involve a GameObject hierarchy that has not been investigated in isolation before:

  • A single GameObject with children is activated, deactivated, added to or removed from its parent scene.
  • A deep Prefab (with a GameObject hierarchy) is loaded or saved.

Performance

The performance impact that is introduced by these changes should be kept as low as possible. It will be non-zero due to the added workload, but clever design could potentially move most of the work done to developer-time, rather than game-time:

  • Expose a sorting index directly in the Component base class, stored in a field so access can be direct, without added calculation. Cache this field in some by-type dictionary, so instantiating a Component is fast too.
    • Do some perf checks first - if it can be avoided, do not add this. This would represent permanent baggage with no use except during initialization. Instead, see how well dictionary-lookups are in this case, or consider some really optimized temp data structure.
  • Sort each GameObject's internal component list on load, but using a sorting algorithm that is optimized for cases where the list is pre-sorted, such as Insertion Sort - this is claimed to be the clear winner in this case.
  • Keep a Scene's internal component-by-type representation pre-sorted by desired component order.

Regardless of the above ideas, the problem of deep iteration in local GameObject graphs remains. It is no longer enough to iterate over all components of a GameObject and then move on to its child objects, because this would likely violate ordering (parent Y before child X).

  • Iterating on the entire hierarchy simultaneously would require a large number of iteration variables and lots of lookups for them.
  • Building a sorted component-by-type list first is likely more efficient, though of course less than not doing it at all. Make sure it only happens when there is a hierarchy.
  • While building that list, there should be a way to use the fact that both the full list and all individual object's lists are already sorted.

Profiling

Overall, the key in optimizing this is profiling. Make sure to construct a robust test case and verify all changes using that. Test cases to compare before / after and optimize should involve:

Expecting no change

  • Scene Update, Init and Shutdown.
  • The components of a single GameObject are iterated on using IterateComponents.
  • A single GameObject without children is activated, deactivated, added to or removed from its parent scene.
  • A flat Prefab (no GameObject hierarchy) is loaded or saved.

Expecting load time increase

  • Scene load.
  • Prefab load.

Expecting runtime increase

  • scene.FindComponents with a type constraint that includes multiple component types.
  • A single GameObject with children is activated, deactivated, added to or removed from its parent scene.
  • A deep Prefab (with a GameObject hierarchy) is loaded or saved.
  • Constructing GameObjects at runtime due to sorted AddComponent.
@ilexp

This comment has been minimized.

Member

ilexp commented Feb 19, 2017

Immediate ToDo

  • Create a new component-order-wip branch for this feature, based on master.
  • Design and implement a ComponentOrder class.
    • Later, it will use reflection to derive a deterministic update order for all components, e.g. an order index per component type.
    • For now, it will derive the order index from a hash over the type's full name.
  • Write unit tests that check whether a(ny) specified update order is applied. Make sure they all fail first, then skip each of them until starting to work on it, so the CI build doesn't complain.
    • Scene update
    • Scene init
    • Scene shutdown (backwards order)
    • Scene load
    • Scene saving (backwards order)
    • Scene saved
    • Prefab load
    • Prefab saving (backwards order)
    • Prefab saved
    • Scene iteration via FindComponents
    • GameObject activate
    • GameObject deactivate (backwards order)
    • GameObject add
    • GameObject remove (backwards order)
    • GameObject iterate via IterateComponents
  • Implement deterministic ordering one by one to make the above test cases pass.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Feb 27, 2017

Progress

  • Created a new component-order-wip branch based on master.
  • Implemented a first version of the ComponentExecutionOrder class, to be expanded.
  • Implemented a first set of tests for the above class, to be expanded.
    • Basic functionality
    • Scene update

Immediate ToDo

  • Write unit tests that check whether a(ny) specified update order is applied. Make sure they all fail first, then skip each of them until starting to work on it, so the CI build doesn't complain.
    • Scene init
    • Scene shutdown (backwards order)
    • Scene load
    • Scene saving (backwards order)
    • Scene saved
    • Prefab load
    • Prefab saving (backwards order)
    • Prefab saved
    • Scene iteration via FindComponents
    • GameObject activate
    • GameObject deactivate (backwards order)
    • GameObject add
    • GameObject remove (backwards order)
    • GameObject iterate via IterateComponents
  • Implement deterministic ordering one by one to make the above test cases pass.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 2, 2017

Progress

  • Tweaked and refactored test code to make way for more tests.
  • Implemented more tests:
    • Scene init
    • Scene shutdown (backwards order)
    • Scene load

Immediate ToDo

  • Write unit tests that check whether a(ny) specified update order is applied. Make sure they all fail first (but for the right reasons), then skip each of them until starting to work on it, so the CI build doesn't complain.
    • Scene saving (backwards order)
    • Scene saved
    • Prefab load
    • Prefab saving (backwards order)
    • Prefab saved
    • Scene iteration via FindComponents
    • GameObject activate
    • GameObject deactivate (backwards order)
    • GameObject add
    • GameObject remove (backwards order)
    • GameObject iterate via IterateComponents (forward or backwards order)
  • Implement deterministic ordering one by one to make the above test cases pass.
    • Implement scene update order and FindComponents first, they should be essentially free performance-wise.
    • Expand from there, keep a close eye on performance and profile these cases.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.

@ilexp ilexp changed the title from Component Init-By-Type to Deterministic Component Init and Update Order Mar 4, 2017

@ilexp

This comment has been minimized.

Member

ilexp commented Mar 6, 2017

Progress

  • Fixed a bug in event order filtering of the existing test code.
  • Implemented more tests:
    • Scene saving (backwards order)
    • Scene saved

Immediate ToDo

  • Write unit tests that check whether a(ny) specified update order is applied. Make sure they all fail first (but for the right reasons), then skip each of them until starting to work on it, so the CI build doesn't complain.
    • Prefab load
    • Prefab saving (backwards order)
    • Prefab saved
    • Scene iteration via FindComponents
    • GameObject activate
    • GameObject deactivate (backwards order)
    • GameObject add
    • GameObject remove (backwards order)
    • GameObject iterate via IterateComponents (forward or backwards order)
  • Implement deterministic ordering one by one to make the above test cases pass.
    • Implement scene update order and FindComponents first, they should be essentially free performance-wise.
    • Expand from there, keep a close eye on performance and profile these cases.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 8, 2017

Progress

  • Completed the set of unit tests:
    • Prefab load
    • Prefab saving (backwards order)
    • Prefab saved
    • Scene iteration via FindComponents
    • GameObject activate
    • GameObject deactivate (backwards order)
    • GameObject add
    • GameObject remove (backwards order)
    • GameObject iterate via IterateComponents (forward or backwards order)

Immediate ToDo

  • Implement deterministic ordering one by one to make the above test cases pass.
    • Implement scene update order and FindComponents first, they should be essentially free performance-wise.
    • Expand from there, keep a close eye on performance and profile these cases.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 10, 2017

Progress

  • Implemented deterministic component order for Scene updates and component queries.

Immediate ToDo

  • Implement deterministic ordering one by one to make the above test cases pass.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 12, 2017

Progress

  • Implemented deterministic component order for Scene and Prefab init / shutdown:
    • Scene activate / deactivate
    • Scene load
    • Scene save / saving
    • Prefab load
    • Prefab save / saving

Immediate ToDo

  • Implement deterministic ordering one by one to make the above test cases pass.
    • GameObject activate / deactivate
    • GameObject add / remove
    • GameObject iterate (sort on load, insert on add)
  • Remove now-unused GameObject event delivery methods such as OnLoaded or OnActivate.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 18, 2017

Progress

  • GameObjects now enforce deterministic Component list order after loading and when adding new Components.

Immediate ToDo

  • Implement deterministic ordering one by one to make the above test cases pass.
    • GameObject activate / deactivate
    • GameObject add / remove
  • Remove now-unused GameObject event delivery methods such as OnLoaded or OnActivate.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 19, 2017

Progress

  • GameObjects now enforce deterministic Component list order when being de/activated, including their entire tree of child objects.
  • They do not yet enforce per-tree deterministic order when being added to or removed from an already active scene, but they do enforce per-object order.
  • Removed unused internal GameObject event delivery methods.

Immediate ToDo

  • Find a patch / hack to enforce per-tree order in the above case until the proper solution can be implemented in issue #512.
  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 19, 2017

Progress

  • Implemented a non-breaking issue #512 version on the master branch.
  • Fixed per-tree ordering in add / remove cases on active Scenes.

Immediate ToDo

  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 21, 2017

Progress

  • Started working on #304.
  • Some minor cleanup in GameObject internal methods.

Immediate ToDo

  • Proceed with issue #304 before merging back, as a new deterministic order that is chosen arbitrarily might break a previously non-deterministic order that might have happened to do the right thing for a subset of components.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 25, 2017

Progress

  • Done with issue #304

Immediate ToDo

  • Test a bit more: Make sure that the samples still work as expected, set some breakpoints in real-world code, etc.
  • Merge back component-order-wip to master.
  • Run a binary release.
  • Merge to develop-3.0 and simplify code where possible.
@ilexp

This comment has been minimized.

Member

ilexp commented Mar 25, 2017

Done and released..

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