Speeding Up Transforms with Clustered Lists

I really should have benchmarked frames with a lot of entities before now. Each frame was around 190ms. Several systems were destroying performance: the Transform update system, the instanced Material collection system, the asteroid spawning system. I'd been getting away with a rough implementation while the rest of the engine caught up, but with tens of thousands of asteroids orbiting a planet, each with its own hierarchy entry, it wasn't acceptable any more.

#Where it started

The original HierarchicalTransformSystem leaned on Arch's ECS query system. Eight component tag types, Transform_Level0 through Transform_Level7, each marking an entity's depth in the hierarchy. Each depth had its own query, processed in order: roots first, then children, then grandchildren.

public record struct Transform(LocalTransform Local, WorldTransform World) : IEcsComponent
{
    public ulong Version = 0;
    public TransformDirtyFlag DirtyFlag { get; set; }
}

public readonly record struct LocalTransform
{
    public Vector3 Position { get; init; }
    public Quaternion Rotation { get; init; }
    public Quaternion VisualRotation { get; init; }
    public Vector3 Scale { get; init; }
}

public record struct Transform_Level0;
public record struct Transform_Level1;
public record struct Transform_Level2;
public record struct Transform_Level3;
public record struct Transform_Level4;
public record struct Transform_Level5;
public record struct Transform_Level6;
public record struct Transform_Level7;

That guaranteed parents were computed before their children needed them. Simple enough, but it had problems:

• Maximum depth was hardcoded to eight levels.
• Transform data lived in ECS archetypes, scattered across whichever chunk each entity landed in. Walking the hierarchy meant pointer-chasing between chunks.
• Reparenting an entity meant removing and re-adding tagged components to shift it between depth queries.

#Pulling transforms out of the ECS

The first change was creating TransformHierarchy, a centralised manager that owns all transform data in flat, parallel arrays. Transforms would then just be indices into the TransformHierarchy data.

public record struct Transform : IEcsComponent
{
    private TransformClusterIndex hierarchyIndex;
}

public readonly record struct LocalTransform
{
    internal readonly TransformClusterIndex hierarchyIndex;
    public Vector3 Position { get => Manager.GetLocalPosition(hierarchyIndex); }
    public Quaternion Rotation { get => Manager.GetLocalRotation(hierarchyIndex); }
    public Vector3 Scale { get => Manager.GetLocalScale(hierarchyIndex); }
}

The raw state looked something like this:

private Vector3[] localPosition;
private Quaternion[] localRotation;
private Vector3[] localScale;
private Quaternion[] localVisualRotation;
private Vector3[] worldPosition;
private Quaternion[] worldRotation;
private Vector3[] worldScale;
private Matrix4x4[] worldMatrix;
private int[] matrixVersion;
private TransformDirtyFlag[] dirtyFlags;
private EntityFlags[] entityFlags;
private int[] depth;
private int[] parentIndex;
private int[] version;
private Entity[] entityHandle;

// Mirror buffers (render thread snapshot)
private Vector3[] worldPositionMirror;
private Quaternion[] worldRotationMirror;
private Vector3[] worldScaleMirror;
private Matrix4x4[] worldMatrixMirror;
private int[] matrixVersionMirror;
private int[] versionMirror;

But the arrays were flat, with no grouping by depth. I still needed to process parents before children. My first attempt was to sort all the arrays by the depth array, in descending order. That way the deepest children sat at the front and roots sat at the back. New entities almost always start at depth 0, so they'd append to the end without triggering a re-sort.

This was awful. It got me down to 100 ms frames, which were better but nowhere near good enough. Structural changes (reparenting, despawning) would result in a sort pass across every array that caused a massive blip on the framegraph. I needed a better solution.

#The clustered list

I replaced the sort with ClusteredList.

CategorizedClusteredList<T> stores elements in fixed-size clusters of 128. Each cluster belongs to an integer category. For transforms, the category is the hierarchy depth. But the structure is generic; it only knows about categories and clusters.

#The master list

Clusters are doubly-linked in two overlapping chains:

1. A global list chains every active cluster, ordered by category.
2. Each category has its own sub-chain linking just its clusters.

Separate arrays store references to the head and tail clusters of each category, so accessing either end of any category's chain is O(1) without walking the global list.

For transforms, the global list gives category-ordered iteration across isolated transform depths. The per-category chains give targeted iteration over just one depth level. Both walk a linked list, touching only the clusters they need.

#Handles

Each element gets a ClusterIndex: a 64-bit value packing three fields.

Pool index identifies the cluster. Slot identifies the element's position within the cluster's 128-slot array. Generation is a version counter, incremented when a cluster gets freed and recycled. In debug builds, every access validates that the handle's generation matches the cluster's current one. Stale handles get caught immediately. The 128-slot clusters need only 7 bits for the slot.

#O(1) insertion

Adding an element needs a cluster with space in the right category. Searching the category chain for a non-full cluster would be O(n), but the cluster layout avoids that.

Within each category, partial clusters sit at the head and full clusters sit at the tail. Adding always targets the head. When an add fills a cluster to 128, that cluster is unlinked from the head position and re-linked at the tail. The next add hits the new head, or allocates a fresh cluster from the pool if none remain.

If the next add finds no partial cluster at the head, a fresh one is popped from the free pool (or allocated if the pool is empty), linked at the head of the category, and the element goes in at slot 0.

#O(1) swap-with-back removal

Removing an element from the middle of a cluster would leave a gap. Shifting elements to close it is O(n) and invalidates handles. Instead, the removed slot is overwritten by the last element in the cluster, and the count decrements.

The cost is that the swapped element has changed position. Remove() returns the displaced element's new ClusterIndex, so the caller is responsible for updating the now-stale index. For TransformHierarchy, that means updating the entity-to-index dictionary.

If removal drops the cluster below full, it moves back to the head of its category chain, making it available for insertions again.

The ClusteredList operation itself is O(1). The consumer's stale-key fix-up may not be. TransformHierarchy performs one dictionary write; the material system described below ignores the move.

#Compaction

When a cluster's count hits zero, it's unlinked from both chains and pushed onto the free pool stack. Its generation increments, invalidating any outstanding handles that might still reference the old contents. Recycling is O(1).

#Recategorisation

When an entity gets reparented, its depth changes, and it needs to move categories. Recategorize() handles this as a removal from the old category followed by an insertion into the new one. It returns both the element's new index and the index of any element displaced by the swap.

For TransformHierarchy, reparenting is recursive. The entity moves, then each of its children must recategorise too. All seventeen parallel lists stay in lockstep.

#Everything in order

With categories as depths, iterating categories 0, 1, 2 gives breadth-first processing. The update loop walks all roots, then all their children, then grandchildren. At each depth, parent world transforms are already computed.

int maxDepth = localPosition.MaxCategory;

for (int depth = 0; depth <= maxDepth; depth++)
{
    foreach (ClusterRef cluster in localPosition.EnumerateCategory(depth))
    {
        Span<Vector3> positions = localPosition.GetBlockSpan(cluster);
        Span<Quaternion> rotations = localRotation.GetBlockSpan(cluster);

        for (int i = 0; i < cluster.Count; i++)
        {
            // Parent world data is already computed at this point.
            // Combine local and parent to produce world transform.
        }
    }
}

#Parallel processing

Within each category, clusters are 128-element contiguous spans. That's a natural unit for parallel dispatch; each cluster can be processed on its own thread with no synchronisation between them.

The job interface is minimal. You implement one method:

public interface IClusterJob
{
    void Execute(ClusterRef cluster);
}

Then hand it to ParallelClusteredListJob.Execute() along with an enumeration of clusters. The system collects every ClusterRef into a flat array and schedules one job per cluster. The scheduler's work-stealing deques handle the rest: idle workers steal jobs from busy workers, so uneven cluster costs get absorbed automatically.

A ClusterRef from one list can index into any of the parallel lists since they're all structurally synchronised, so one dispatch drives access across all seventeen arrays.

If there's no scheduler available, or only one cluster to process, it falls back to sequential execution on the calling thread. This avoids scheduler overhead in the simple case.

Going back to the transform system, the requirement there is stricter. Depth 0 must finish before depth 1 can start, depth 1 before depth 2, and so on; a parent's world transform has to be computed before any of its children read it. CategoryBarrieredParallelClusteredListJob handles this. It walks categories in order, dispatching all clusters within one category in parallel, then waits for them all to complete before moving to the next.

for (int cat = 0; cat <= list.MaxCategory; cat++)
{
    ParallelClusteredListJob.Execute(
        list.EnumerateCategory(cat), scheduler, ref job);
    // implicit barrier: Execute() waits for all jobs in this category
}

Within each depth, it's the same work-stealing dispatch as before. The barriers just make sure children never run ahead of their parents.

#Other applications

Another major cost in the original frame profile was GatherMeshesSimd, which gathered and CPU-frustum-culled meshes while building instanced transform buffers. The non-instanced path had the same problem, but the asteroids used instancing.

RenderableRegistry now uses the same structure. Its category is a unique index for each MaterialHost, a combination of material, mesh, and flags suitable for an instanced draw chunk. Iterating a category yields contiguous renderables that share a material and are ready for instanced draws. The structure also suits SIMD: I store X, Y, Z, and radius in separate arrays and load them directly into vectors for the frustum cull.

I have also used it in AsteroidSpawnerSystem to track spawned "cells" eligible for collection.

#Other candidates

Other candidates are lists that do not need stable references or per-element ordering. I will probably try it in more places than I should.