Flexcomp compilation does quadratic work when removing unused points

[teerthsharma]

Intro

I found that removing unreferenced flexcomp points performs quadratic worst-case
work before the model is compiled.

My setup

• MuJoCo main at b04a18a00a55e6d4a23f56e5f5dd2d3a23d404bb
• C++ model-loading path
• Windows 11 x86-64
• MSVC 19.44.35224
• Release build

What's happening? What did you expect?

For direct, mesh, and GMSH flexcomps, mjCFlexcomp::Make first marks the points
referenced by elements. The current reindex construction then visits the full
suffix after every unused point:

for (int i=0; i < npnt; i++) {
  if (!used[i]) {
    for (int k=i+1; k < npnt; k++) {
      reindex[k]--;
    }
  }
}

For P points and U unused points this performs Theta(P * U) writes, or
Theta(P^2) when most points are unused. The resulting value has a simpler
definition:

reindex[k] = -count(i < k where point i is unused)

I expected this compaction bookkeeping to scale linearly with the number of
input points.

Steps for reproduction

I added a temporary Google Benchmark to parse_benchmark_test.cc. It generates
a rigid, direct, three-dimensional flexcomp containing one tetrahedron that
references points 0 through 3. Every later input point is unused. Each timed
iteration calls LoadModelFromString, exercising real XML parsing and model
compilation.

The compiled flex remains four vertices at every input size, so the scaling is
not caused by a growing output topology.

Across three fresh benchmark processes with seven repetitions per size, the
median of process medians was:

Input points	Current main	Linear prefix scan	Speedup
1,000	0.794 ms	0.901 ms	0.88x
2,000	0.987 ms	0.955 ms	1.03x
4,000	1.596 ms	1.247 ms	1.28x
8,000	3.343 ms	1.815 ms	1.84x
16,000	10.449 ms	3.123 ms	3.35x
32,000	51.218 ms	7.201 ms	7.11x

Google Benchmark selected a linear fit for the prefix implementation in all
three processes. The 1,000-point timings are around one millisecond and noisy.

As a negative control, a direct flexcomp in which every point was referenced
measured:

Input points	Current main	Linear prefix scan
1,000	2.32 ms	2.33 ms
4,000	7.56 ms	7.57 ms
16,000	32.00 ms	31.37 ms

Proposed change

Maintain the number of preceding unused points during one prefix scan and
assign its negation to each reindex entry. This is Theta(P), adds one integer
of state, and computes the exact same mapping.

I also have a characterization test covering leading, interleaved, and trailing
unused points, including element, texture-coordinate, pin, body, and flex-vertex
remapping. I will link the implementation as a draft PR after sanitizer and
repository testing.

Confirmations

• I searched the current documentation and source before posting.
• I searched existing MuJoCo issues and all paginated discussions for
  flexcomp unused-point, compilation, performance, and quadratic-scaling
  reports and found no duplicate.