Semantic Diff

#9153 Split let rec groups in linear time without the ordered hash map stack

3 commits

8e26a9ca6922aaecfe526792eaf3d2f194cdffb9..pr-9153

2e7b96b79 · cknitt + Claude · Oct 31, 2026, 10:16 UTC

Split let rec groups with plain arrays instead of an ordered hash map

Lambda_scc.preprocess_deps was the only user of Ordered_hash_map and Hash_set_ident_mask (468 lines with their test files). It now numbers the bindings with an array and a Hash_ident table, and collects each body's references in a bool array, still stopping the walk once every binding is hit. Edges come out in binding order; the generated JavaScript is unchanged across the test suites.

707e2680c · cknitt + Claude · Oct 31, 2026, 10:44 UTC

Find the edges of a let rec group in time linear in its bodies

Each body allocated and scanned a bool array as long as the group, so a group of n bindings cost O(n^2) on top of walking the bodies. One shared array now records which body last referred to each binding, and each body's edges are collected as found and sorted. A generated group of 16,000 bindings compiles in 2.7 s instead of 4.3 s (5.3 s on master); the generated JavaScript is unchanged.

b23f519f0 · cknitt + Claude · Nov 01, 2026, 06:55 UTC

Test how let rec groups are split into components

Codex review: the rewrite of preprocess_deps removed the old modules' tests and added none. ounit_lambda_scc_tests checks bind_rec's output: an edge to a binding an earlier body also referred to survives the shared seen array (a mutation that leaks it between bodies fails the test), a mixed group keeps cycles, self-recursion and plain lets apart in dependency order, and a body referring to every binding stops early correctly. let_rec_components_test runs such a group end to end.