Tune `built-in.smli`

[julianhyde]

The built-in.smli test takes 26 seconds on Rust (debug mode), compared to 2 seconds on Java. This suggests that the Rust performance can be improved significantly. This task is to investigate the performance and suggest some tasks that will make it faster. Some questions:

• What is the balance of time between parsing, validation and execution?
• If comments and disabled regions (via mode=validate) are removed, do the numbers change significantly?
• Generate a flamegraph (or similar) and identify functions that are surprisingly slow.
• Is something building up and making everything slower? (Divide the test into smaller sections and see whether the total running time is greater than the sum of the parts.)
• Are some data structures slow?

[julianhyde]

Performance analysis

Setup: Release build with debug symbols; flamegraph via cargo flamegraph --test smile -- built_in.
Result: 3.67s (release) vs 2s Java. Debug mode is ~26s due to unoptimised Rust.

Where time is spent (flamegraph top-level)

%	Function
57%	TypeResolver::deduce_type (type-checking per statement)
49%	Unifier::unify (Hindley-Milner unification)
34%+15%	Unifier::act (constraint propagation inside unify)
~36%	im::nodes::hamt::Iter::next — HAMT iteration (see below)
10%	library::populate_env (rebuilding built-in env every statement)
6%	Type::clone
5%	Arc::drop_slow + SparseChunk::drop (HAMT node teardown)
5%	inliner::Env::multi
5%	resolver::Resolver::resolve_decl
5%	parse_statement

Root causes

1. im::HashMap (HAMT) used as the unifier's accumulator — the single biggest issue

Work.result: ImHashMap<Var, Term> (in unifier.rs) accumulates the substitution during unification. The im crate's persistent HAMT has much higher constant factors than std::collections::HashMap for the mutable-accumulator pattern used here. Every insertion clones tree nodes; every iteration traverses HAMT nodes. This shows up as 36%+ of total runtime in HAMT iteration alone.

im::HashSet (used for the active working set in act/act2) has the same problem.

Fix: Replace ImHashMap<Var, Term> in Work.result and Substitution.substitutions with std::collections::HashMap<Var, Term>, and im::HashSet with std::collections::HashSet. The mutable-accumulator pattern doesn't need persistence/clone-sharing.

2. Substitution::from_result clones the whole map inside the unify loop

At unifier.rs:1268, every time a variable-term pair is resolved and term_actions are non-empty, the code clones work.result into a Substitution to pass to act. With a large substitution and many term_actions, this is repeated cloning of the accumulator.

Fix: Pass a reference/view of work.result directly instead of cloning it into a Substitution.

3. act2 does O(n) scan of all substitution entries

act2 (lines 1388–1397) iterates over all substitution.substitutions entries looking for ones where the value is Term::Variable(variable), to trigger chained actions. With n substitution entries, this is O(n) per call to act.

Fix: Maintain a reverse index HashMap<Var, Vec<Var>> mapping each variable v to all variables whose substitution value is v. Update it on each insertion instead of scanning on each act call.

4. populate_env called on every statement evaluation (10% of runtime)

evaluate_node (shell/main.rs:610) calls library::populate_env to build a BTreeMap of all built-in functions and structures on every single statement. The library has ~500 entries; their Type values are cloned each time.

Fix: Build this map once at shell initialisation and cache it. It never changes.

Answers to the investigation questions

• Balance: ~57% type-checking/unification, ~10% populate_env, ~5% each for inliner/resolver/parser. Execution (eval) itself is negligible.
• Removing validate sections: validate mode already returns expected output without evaluating, so removing those sections would have minimal impact.
• Quadratic build-up: Timing quarters of the file showed flat (not quadratic) per-line cost, so no accumulation across statements.
• Slow data structures: Yes — im::HashMap (HAMT) is the primary one.

Suggested follow-up tasks

1. Replace im::HashMap/im::HashSet in unifier.rs with std:: equivalents
2. Cache populate_env output once per session
3. Avoid cloning work.result into Substitution on every act call inside the unify loop
4. Add reverse index in unifier to avoid O(n) scan in act2