engine: LTM element-level circuit enumeration spends most of its time in string canonicalization/rotation churn (cross-product shapes)

[bpowers]

Summary

Profiling the exhaustive/discovery element-level loop enumeration path shows its time is dominated not by graph search itself but by string-based canonicalization, rotation, and subscript-stripping churn performed per enumerated circuit. On cross-product (conservative) element-edge shapes, Johnson enumerates many element-level circuits, and each circuit repeatedly allocates and canonicalizes Idents, so cost scales with (number of circuits x cycle length) in string operations.

Observation

The integration test ltm_array_agg::square_owner_whole_rhs_declines_and_skips_loudly (src/simlin-engine/tests/integration/ltm_array_agg.rs) takes ~2.9s in a debug build for a 4-variable model (cube[D1,D1,D2] / pop[D1,D1] / x[D1,D1], 2x2x2 = 8 elements), i.e. ~1.45s per compile across its two sub-invocations (exhaustive + discovery). Sibling square-decline tests with smaller shapes take ~0.3s.

A perf record profile of the single test shows the time spread across the element-level enumeration path rather than one hotspot:

• db::ltm::loops::build_element_subscripted_links (src/simlin-engine/src/db/ltm/loops.rs)
• ltm::lex_smallest_rotation_start (src/simlin-engine/src/ltm/mod.rs)
• ltm::graph::loop_id_sort_key (src/simlin-engine/src/ltm/graph.rs)
• ltm::indexed::IndexedGraph::johnson_circuit (src/simlin-engine/src/ltm/indexed.rs)
• ltm::strip_subscript (src/simlin-engine/src/ltm/mod.rs)

plus heavy common::is_canonical / canonicalize / Ident::new churn, Arc clone/drop traffic, and hashbrown/indexmap operations.

The declined-square shape keeps references on the conservative cross-product element-edge path (DynamicIndex / declined-shape edges), so Johnson enumerates many element-level circuits, and each circuit does string-based canonical-rotation and subscript-stripping work.

Why it matters

The same machinery runs in production model_ltm_variables / model_detected_loops for any arrayed model with cross-product element edges -- not just tests. Small element counts already cost ~1.5s per compile in a debug build (tens of ms release), and the string churn grows multiplicatively with dimension sizes, so real arrayed models with declined/dynamic-index shapes pay this at scale.

Components affected

• src/simlin-engine/src/db/ltm/loops.rs (build_element_subscripted_links)
• src/simlin-engine/src/ltm/mod.rs (lex_smallest_rotation_start, strip_subscript)
• src/simlin-engine/src/ltm/graph.rs (loop_id_sort_key)
• src/simlin-engine/src/ltm/indexed.rs (IndexedGraph::johnson_circuit)
• src/simlin-engine/src/common.rs (canonicalization / Ident::new volume, global interner traffic)

Possible directions (not investigated in depth)

• Intern/reuse Ident allocations in the rotation / sort-key path instead of re-canonicalizing per circuit.
• Do rotation canonicalization on integer node ids (the IndexedGraph NodeId space) instead of strings, deferring string materialization to final Loop construction.
• Defer subscript-string materialization until after dedup, so only surviving circuits pay the string cost.

Relationship to existing issues

• Distinct from ltm-finding: SearchGraph clones Ident<Canonical> in per-timestep DFS hot path #481 (string-backed idents in the discovery per-timestep DFS in ltm_finding.rs); this issue is the exhaustive/element-level enumeration path. Same underlying pattern (String-keyed hot paths), different code site -- a shared NodeId/interning approach may serve both.
• Distinct from ltm: C-LEARN LTM compile-time dominated by per-fragment fixed overhead (DimensionsContext clone, O(D^2) intern_name, repeated parse) #655 (per-fragment fixed overhead in LTM fragment compilation); this cost is in loop enumeration, before/independent of fragment compiles.
• ltm: enumerate variable-level loops first, expand only cross-element subgraph #482 (closed) introduced tiered enumeration so only cross-element/mixed cycles hit element-level Johnson; this issue is about the residual per-circuit cost on the shapes that still legitimately take that path.
• Part of the LTM epic epic: Loops that Matter (LTM) -- tracking known issues and improvements #488 (Performance & scale section).

Discovered

Identified while profiling the test suite (perf record on the single slow test) on main at 553dbeb, 2026-07-12.