93 lines
3.8 KiB
Markdown
93 lines
3.8 KiB
Markdown
# libgdx-0002: ModelBuilder.rebuildReferences — O(N²) Array.contains() inside node-part loop
|
||
|
||
**Severity:** HIGH
|
||
**File:** gdx/src/com/badlogic/gdx/graphics/g3d/utils/ModelBuilder.java
|
||
**Line:** 371–381
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
`ModelBuilder.rebuildReferences()` is the public static utility called after model
|
||
construction to rebuild the model's flat `materials`, `meshParts`, and `meshes` arrays from
|
||
the node hierarchy. For each `NodePart` of each `Node` (recursively), it calls
|
||
`Array.contains()` three times — once each for `model.materials`, `model.meshParts`, and
|
||
`model.meshes`.
|
||
|
||
`Array.contains(value, identity)` is a linear scan: O(M) where M is the current array
|
||
size. With N node-parts and M accumulated distinct entries, total cost is **O(N × M)** —
|
||
quadratic in the number of parts.
|
||
|
||
This is invoked from `ModelBuilder.end()` every time a model is built from parts, and is
|
||
also exposed as a public API (`ModelBuilder.rebuildReferences(Model)`), making it a
|
||
potential hotspot any time a user re-syncs model references.
|
||
|
||
## Root Cause
|
||
|
||
```java
|
||
// ModelBuilder.java:371-381
|
||
private static void rebuildReferences (final Model model, final Node node) {
|
||
for (final NodePart mpm : node.parts) {
|
||
if (!model.materials.contains(mpm.material, true)) // O(M) linear scan
|
||
model.materials.add(mpm.material);
|
||
if (!model.meshParts.contains(mpm.meshPart, true)) { // O(P) linear scan
|
||
model.meshParts.add(mpm.meshPart);
|
||
if (!model.meshes.contains(mpm.meshPart.mesh, true)) // O(X) linear scan
|
||
model.meshes.add(mpm.meshPart.mesh);
|
||
model.manageDisposable(mpm.meshPart.mesh);
|
||
}
|
||
}
|
||
for (final Node child : node.getChildren())
|
||
rebuildReferences(model, child);
|
||
}
|
||
```
|
||
|
||
`Array<T>.contains(value, identity=true)` iterates all elements with `==` comparison.
|
||
No `IdentityHashSet` or `ObjectSet` is used for deduplication.
|
||
|
||
## Fix
|
||
|
||
Build identity-based sets in the public `rebuildReferences(Model)` method and pass them
|
||
into the recursive helper to replace O(N) `contains()` calls with O(1) set lookups.
|
||
|
||
```java
|
||
public static void rebuildReferences (final Model model) {
|
||
model.materials.clear();
|
||
model.meshes.clear();
|
||
model.meshParts.clear();
|
||
// Identity sets for O(1) deduplication
|
||
IdentityHashMap<Material, Boolean> matSeen = new IdentityHashMap<>();
|
||
IdentityHashMap<MeshPart, Boolean> partSeen = new IdentityHashMap<>();
|
||
IdentityHashMap<Mesh, Boolean> meshSeen = new IdentityHashMap<>();
|
||
for (final Node node : model.nodes)
|
||
rebuildReferences(model, node, matSeen, partSeen, meshSeen);
|
||
}
|
||
|
||
private static void rebuildReferences (final Model model, final Node node,
|
||
IdentityHashMap<Material, Boolean> matSeen,
|
||
IdentityHashMap<MeshPart, Boolean> partSeen,
|
||
IdentityHashMap<Mesh, Boolean> meshSeen) {
|
||
for (final NodePart mpm : node.parts) {
|
||
if (matSeen.put(mpm.material, Boolean.TRUE) == null) // O(1)
|
||
model.materials.add(mpm.material);
|
||
if (partSeen.put(mpm.meshPart, Boolean.TRUE) == null) { // O(1)
|
||
model.meshParts.add(mpm.meshPart);
|
||
if (meshSeen.put(mpm.meshPart.mesh, Boolean.TRUE) == null) // O(1)
|
||
model.meshes.add(mpm.meshPart.mesh);
|
||
model.manageDisposable(mpm.meshPart.mesh);
|
||
}
|
||
}
|
||
for (final Node child : node.getChildren())
|
||
rebuildReferences(model, child, matSeen, partSeen, meshSeen);
|
||
}
|
||
```
|
||
|
||
## Speedup
|
||
|
||
| Node-parts | Materials | Before | After |
|
||
|-----------:|----------:|-------:|------:|
|
||
| 500 | 50 | 25 000 comparisons | ~500 ops |
|
||
| 2 000 | 200 | 400 000 comparisons | ~2 000 ops |
|
||
| 10 000 | 1 000 | 10 000 000 comparisons | ~10 000 ops |
|
||
|
||
Estimated **50–1000x** speedup for large model hierarchies (animated characters, skeletal
|
||
meshes with many sub-meshes, procedurally-generated geometry).
|