Make the Flame Component System core more efficient

[spydon]

Motivation

An investigation into the performance of the Flame Component System (update/render traversal, lifecycle processing, priority changes, hit testing) found that most of the framework overhead came from the children container and from per-frame allocation churn, not from game logic. The parent/children tree structure and the developer experience were to be preserved (this was not an ECS rewrite), but breaking changes were acceptable.

Implementations considered

Children container. Three full replacements for the SplayTreeMap<num, Set<Component>>-backed OrderedSet were implemented, each passing the entire test suite, and benchmarked head-to-head (full comparison table):

• Flat sorted array (chosen): one contiguous list sorted by (priority, insertion order), with the container and slot index stored intrusively on the component, null tombstones for removals (compacted once per tick), and a stable sort on priority changes that is skipped when nothing actually reordered. Best or within noise on nearly every benchmark, and no pathological case.
• Intrusive doubly-linked list (bench/linked-list): _prevSibling/_nextSibling pointers, O(1) link/unlink. Fastest pure update walk, but pointer-chasing loses on rendering (contiguous pointer arrays prefetch, dependent loads serialize), priority changes cost about 2.7x more than the array, and any structural mutation must invalidate live iterators.
• Priority-bucketed arrays (bench/priority-buckets): one dense array per distinct priority, so a priority change is a bucket move instead of a sort. Middling everywhere and pathological under y-sort, where 1000 distinct priorities degenerate into 1000 single-element buckets and it lands slower than the old OrderedSet.

Update traversal. Keeping the recursive updateTree was compared against a root-owned flattened pre-order list. The flat list won once two problems were solved: overridden traversals being silently skipped (solved by making updateTree non-virtual behind a CustomTraversal marker + updateSubtree), and rebuild cost under churn (solved by structure versioning with lazy rebuilds that are fused into the same tick's update pass).

Considered and rejected:

• Flattening the render pass: rendering is hierarchical through canvas transforms, clips, decorators, and render contexts, and renderTree has many legitimate overriders; the render pass stays recursive and virtual. Render-order work continues as the RenderLayer proposal in Add a RenderLayer system for global render ordering #3967.
• Rewriting engine hit testing as an explicit-stack traversal: componentsAtLocation is an overridden extension point (CameraComponent, Route, ecosystem), so a parallel path would silently skip those overrides. Root-level counters of mounted pointer-event handlers attack the same per-event cost safely instead.
• First-class timeScale on Component: rarely used; it stays in the opt-in HasTimeScale mixin, which now composes through updateSubtree.

Decision

Implemented in #3960:

• ComponentList (the flat sorted array) replaces OrderedSet; the dependency is removed. query<T>()/register<T>() are kept, childrenFactory is replaced by an overridable createComponentList() with an optional comparator for custom orderings such as y-sort.
• The update pass runs over the root-owned flattened list; CustomTraversal components are barriers that drive their own subtrees via updateSubtree. A new updatePaused pauses a subtree's updates entirely (and now backs Route.stopTime()).
• Allocation hygiene throughout the hot paths: no per-frame decorator or camera closures, lazy render contexts and debug caches, generator-free removal teardown, an early-out for lifecycle processing and for hit tests in games without pointer handlers, and a near-linear insertion sort in the Sweep broadphase.

Golden tests pin lifecycle ordering, hit-test order, and equal-priority ordering across the rewrite. Migration notes are in #3960 and in the migration guide.

Benchmarks

Container candidates, measured with each backing as a drop-in children container (JIT, ms per run, lower is better; the old OrderedSet on then-main as baseline):

Benchmark	OrderedSet	Flat sorted array	Linked list	Priority buckets
Update wide tree (10k x 1)	8.09	5.84	3.93	6.49
Render wide tree (10k x 1)	12.81	8.78	10.94	9.37
Update nested tree (1k x 10)	16.96	7.41	6.11	7.30
Render nested tree (1k x 10)	23.05	10.15	11.21	11.49
Update deep tree (100 levels)	18.14	6.33	5.65	7.31
Lifecycle churn (100/tick, 10k pop)	12.56	7.57	6.81	8.07
Mass add/remove (1k per cycle)	3.43	2.41	2.38	2.47
Priority change (1 child per parent)	74.46	5.99	15.75	9.65
Priority change (y-sort, all children)	22.61	5.95	8.99	31.10
Game-like update pass	185.29	111.24	122.71	115.43

Final state of #3960 (container plus flattened traversal plus allocation hygiene) versus main:

Benchmark	main	#3960	speedup
Update wide tree (10k x 1)	8.09	3.44	2.4x
Update nested tree (1k x 10)	16.96	3.97	4.3x
Update deep tree (100 levels)	18.14	3.36	5.4x
Update barrier tree (10% time-scaled)	20.45	4.47	4.6x
Render wide tree (10k x 1)	12.81	4.64	2.8x
Render nested tree (1k x 10)	23.05	8.25	2.8x
Render deep tree (100 levels)	27.44	6.89	4.0x
Lifecycle churn (100/tick, 1k pop)	5.10	2.54	2.0x
Lifecycle churn (100/tick, 10k pop)	12.56	8.63	1.5x
Mass add/remove (1k per cycle)	3.43	1.31	2.6x
Priority change (1 child per parent)	74.46	6.92	10.8x
Priority change (y-sort, all children)	22.61	5.82	3.9x
Type-query churn (2 registered queries)	6.95	5.16	1.3x
Game-like update pass	185.29	95.31	1.9x
Hit test + delivery (cached)	90.93	39.06	2.3x
Flat collision detection	9.24	3.35	2.8x
Nested collision detection	15.41	3.52	4.4x

Numbers are flutter test JIT on one desktop machine, for relative comparison; AOT device numbers are pending and should show smaller but same-ranked multiples.

Related: #1938 (first item).

[spydon]

Phase 2 container experiments: three backings built and benchmarked

To pick the Phase 2 container, three candidate backings were implemented end to end as drop-in children containers. Each one passes the full flame test suite and was measured with the benchmark suite from #3959 on the same desktop machine (JIT via flutter test, asserts on, so relative comparison only; per the design notes above, expect smaller but same-ranked multiples under AOT).

A. Flat sorted array (chosen, merged with the Phase 2 plan on perf/component-set-backing): one contiguous List sorted by (priority, insertion order); intrusive slot index and container pointer on Component give O(1) remove/contains; removals leave null tombstones compacted once per parent per tick; rebalance is an O(n) sortedness check plus an in-place stable sort only when something actually reordered.

B. Intrusive doubly-linked list (bench/linked-list): _prevSibling/_nextSibling on Component, container stores head and tail. O(1) link/unlink, no tombstones; rebalance collects into a list and merge-sorts; query caches rebuilt lazily after reorders.

C. Priority-bucketed arrays (bench/priority-buckets): one dense array per distinct priority in a sorted bucket list (the old SplayTreeMap<num, Set> shape, but with flat arrays and intrusive bucket references); a priority change is a bucket move instead of a global sort.

Results (ms per run, lower is better)

Benchmark	OrderedSet (main)	A: sorted array	B: linked list	C: buckets
Update wide tree (10k x 1)	8.09	5.84	3.93	6.49
Render wide tree (10k x 1)	12.81	8.78	10.94	9.37
Update nested tree (1k x 10)	16.96	7.41	6.11	7.30
Render nested tree (1k x 10)	23.05	10.15	11.21	11.49
Update deep tree (100 levels)	18.14	6.33	5.65	7.31
Render deep tree (100 levels)	27.44	10.29	10.26	11.09
Update barrier tree (10% time-scaled)	20.45	7.89	8.91	8.63
Lifecycle churn (100/tick, 1k pop)	5.10	3.60	3.47	3.64
Lifecycle churn (100/tick, 10k pop)	12.56	7.57	6.81	8.07
Mass add/remove (1k per cycle)	3.43	2.41	2.38	2.47
Priority change (1 child per parent)	74.46	5.99	15.75	9.65
Priority change (y-sort, all children)	22.61	6.21	8.99	31.10
Type-query churn (2 registered queries)	6.95	6.13	6.09	6.55
Game-like update pass	185.29	114.88	122.71	115.43
Flat collision detection	9.24	3.56	3.57	5.19
Nested collision detection	15.41	4.95	4.64	6.61

(The componentsAtPoint suites are omitted: they are dominated by game logic and their run-to-run variance exceeds the container deltas; within-run comparisons show hit testing is roughly free under all three designs.)

Takeaways

• A is best or within noise on nearly everything and has no pathological case. Headline vs the current OrderedSet: 12.4x on single-child priority changes, 3.6x on y-sort, 2.4 to 3x on traversal and collision detection, 1.6x on the end-to-end game-like update pass.
• B is the fastest pure update walker but gives it back elsewhere: rendering does real per-child work, and the array's contiguous pointer block prefetches while the list serializes dependent loads (see the wide-tree render row). It is also 2.6x slower than A on priority changes, and any structural mutation must invalidate live iterators.
• C empirically confirms the y-sort design note above: a bucket-per-priority shape degenerates to singleton buckets under y-sort (1000 distinct priorities) and lands slower than the old container (31.1 vs 22.6). Priority buckets only pay off when priorities are few and stable.
• The A numbers in the table are from the final combined implementation (ComponentList, childrenFactory removed, comparator support); the pre-rename prototype measured the same within noise.

Remaining before merge: AOT numbers on a device for the go/no-go, and the Phase 1 hygiene items which are untouched by this work.