# libgdx-0003: ModelInstance.invalidate — O(N²) Array.contains() in node-part loop

**Severity:** MEDIUM
**File:** gdx/src/com/badlogic/gdx/graphics/g3d/ModelInstance.java
**Line:** 258–276
**Status:** PATCHED

## Description

`ModelInstance.invalidate(Node)` is called during `ModelInstance` construction (via
`invalidate()`) to ensure every `NodePart`'s material is registered in the instance's
`materials` array. For each node-part it calls `materials.contains(part.material, true)` —
a linear scan of the `Array<Material>`.

With D node-parts across the whole hierarchy and T distinct materials, total cost is
**O(D × T)** per `ModelInstance` construction.

In games that spawn many model instances per frame (character spawning, particle-based
objects, dynamic world objects), this O(N²) construction cost compounds at runtime, not
just at load time.

## Root Cause

```java
// ModelInstance.java:257-277
private void invalidate (Node node) {
    for (int i = 0, n = node.parts.size; i < n; ++i) {
        NodePart part = node.parts.get(i);
        // ...
        if (!materials.contains(part.material, true)) {    // O(T) linear scan
            final int midx = materials.indexOf(part.material, false);
            if (midx < 0)
                materials.add(part.material = part.material.copy());
            else
                part.material = materials.get(midx);
        }
    }
    for (int i = 0, n = node.getChildCount(); i < n; ++i)
        invalidate(node.getChild(i));
}
```

`Array.contains(value, identity=true)` iterates `materials` with `==` comparison.
No set-based deduplication is used.

## Fix

Build a local `IdentityHashMap<Material, Material>` at the top of the `invalidate()`
dispatch method and pass it through the recursion, replacing the O(T) scan with O(1)
identity lookups.

```java
private void invalidate () {
    IdentityHashMap<Material, Material> seen = new IdentityHashMap<>();
    for (int i = 0, n = nodes.size; i < n; ++i)
        invalidate(nodes.get(i), seen);
}

private void invalidate (Node node, IdentityHashMap<Material, Material> seen) {
    for (int i = 0, n = node.parts.size; i < n; ++i) {
        NodePart part = node.parts.get(i);
        // ...
        if (!seen.containsKey(part.material)) {                  // O(1)
            final int midx = materials.indexOf(part.material, false);
            if (midx < 0) {
                part.material = part.material.copy();
                materials.add(part.material);
            } else {
                part.material = materials.get(midx);
            }
            seen.put(part.material, part.material);
        }
    }
    for (int i = 0, n = node.getChildCount(); i < n; ++i)
        invalidate(node.getChild(i), seen);
}
```

## Speedup

| Node-parts | Materials | Before | After |
|-----------:|----------:|-------:|------:|
| 200        | 20        | 4 000 comparisons | ~200 ops |
| 1 000      | 100       | 100 000 comparisons | ~1 000 ops |
| 5 000      | 500       | 2 500 000 comparisons | ~5 000 ops |

Estimated **20–500x** speedup for complex model instances. Most impactful in games that
instantiate many copies of complex models per frame.