Intern entity identifiers to cut graph-build memory and allocation churn

[Iron-Ham]

Intern entity identifiers to cut graph-build memory and allocation churn

Summary

Entity IDs are long, fully-qualified strings (e.g. app/services/user.ts::function::createUser) stored as owned Strings in many structures at once. On a large monorepo (~71k files, ~2.7M entities) this duplication is a major contributor to the cold graph build's peak memory (which reaches ~27 GB) and to allocation churn from cloning IDs into multiple maps. Replacing the runtime identifier with an interned integer handle (the string materialized only at output and cache boundaries) should cut peak RSS and reduce the clone/alloc traffic during graph assembly.

This is primarily a memory and allocation optimization. It is not expected to speed up the per-reference resolution loop — that loop hashes short reference names, not entity IDs (see #321 and #324 for the resolution-speed levers).

Background / evidence

In crates/sem-core/src/parser/graph.rs, each entity ID is duplicated across several long-lived structures:

• EntityGraph.entities: HashMap<String, EntityInfo> — the ID is both the map key and EntityInfo.id, plus the optional EntityInfo.parent_id.
• EntityGraph.dependents and EntityGraph.dependencies: HashMap<String, Vec<String>> — every edge contributes cloned IDs to the forward/reverse indexes.
• EntityGraph.edges: Vec<EntityRef> where EntityRef { from_entity: String, to_entity: String, .. }.
• symbol_table: HashMap<String /*name*/, Vec<String /*entity IDs*/>> — the IDs are the values (the key is the entity name).

So an entity with incident edge degree d is stored in several fixed places, plus O(d) additional edge/index copies. For example, an outgoing edge stores the source ID in EntityRef::from_entity and in the target's dependents vector; an incoming edge stores it in EntityRef::to_entity and in the source's dependencies vector. The exact count varies with in/out degree, parent status, and map-key reuse, but at ~2.7M entities and ~1.7M edges this is still millions of duplicated identifier strings. It also drives allocation churn: graph assembly clones these IDs repeatedly — EntityGraph::from_parts and the edge-index build clone from_entity/to_entity into the dependents/dependencies maps, and edge de-duplication keys a HashSet on cloned (from, to) ID pairs.

Note that the raw content of each entity (a separate issue) is likely the single largest byte contributor to the 27 GB; entity IDs are notable for the number of copies and the resulting allocation/clone traffic, not for total bytes.

Proposal

Introduce an interner that maps each entity ID String ↔ a compact handle (u32 newtype, e.g. EntityId(u32)), built once during entity extraction. Internally the graph and resolution maps key on the handle:

• entities: HashMap<EntityId, EntityInfo>, with EntityInfo.id/parent_id as handles.
• symbol_table: HashMap<String /*name*/, Vec<EntityId>>.
• edges, dependents, dependencies over EntityId.

Resolve handles back to the canonical string only when serializing (sem graph/impact/context formatters) and when reading/writing the SQLite cache. The on-disk schema (id TEXT, from_entity TEXT, to_entity TEXT) can stay string-based — the interner is rebuilt on load — so the first cut is runtime-only with no cache migration. A HashMap<EntityId, EntityInfo> (rather than a dense Vec indexed by handle) is the safer first form because the incremental path deletes and re-adds entities.

Risks / considerations

• Blast radius. EntityGraph's fields are pub and read directly by many internal consumers — notably crates/sem-core/src/parser/verify.rs and crates/sem-core/src/parser/context.rs, plus the CLI formatters (impact, graph, context) which are the output boundary that must re-materialize strings. Interning changes these field types, a breaking change to the library surface; decide whether to expose handles or keep string-typed accessors.
• Incremental path. The interner must span both EntityGraph::build and build_incremental_with_metadata, where some IDs arrive from disk (strings) and some are freshly minted within one build. IncrementalBuildMetadata and the cache's edge delete/insert-by-ID logic all thread String/Vec<String>/HashSet<String> IDs and would need a handle/string boundary.
• Determinism. Handle assignment must be derived from a stable entity order, not from HashMap iteration or SQLite row order. Cache loads currently select entities/edges without an explicit ORDER BY, so rebuilding handle IDs directly from cache row order would risk changing handles across runs or SQLite versions.
• Account for interner overhead. The interner itself adds a HashMap<String, u32> + Vec<String>; measure net RSS after the graph is returned.

Acceptance criteria

• Materially lower peak RSS on a large-repo cold build, measured after the graph is returned (net of interner overhead), with no wall-time regression.
• sem graph --json produces identical entities and edges before/after across several real repos (TS/JS, Rust, Python, Go), compared via sorted-output diffing. (Today this comparison is flaky at the margins — see Non-deterministic edges: graph output varies run-to-run for ambiguous calls #323 — so either land that first or compare modulo its known envelope.)
• Full test suite passes.

Related: #321 (the resolution-speed lever), #324 (which compounds with smaller integer keys), and #322 (the largest byte contributor).