Remember type path lookups within a compilation
Why
Typechecking a 552 module React app calls Env.find_type_full 1.76M times, and normalize_path 666k times from expand_abbrev. Most calls look up the same few paths against the same environment: option alone is 528k of them, followed by string, array, Jsx.element. Each lookup walks the open layers of env.types, and expanding a type that isn't an abbreviation also normalizes its path, which raises and catches Not_found to return the path unchanged.
A direct-mapped table now remembers successful lookups and unchanged normalizations. An entry is only reused while the environment tables the lookup read are physically the same (env.types for a Pident, env.components for a Pdot, env.modules and env.components for a normalization), and only within the request that stored it. Changed normalizations are computed again, so paths in types are allocated as before. Paths with a functor application aren't cached, the memo is skipped while loading .cmi files is disabled, and it is emptied when a request ends and when a loaded module is replaced.
The two tables start empty and grow from 64 to 4096 slots as entries are stored, and a replaced entry is updated in place, so a small compilation allocates little for them: fixed 4096 slot tables made each runtime file allocate about 3% more words than master. Now the file that grows most, Dom.res, allocates 0.24% more, and the runtime and Belt in total 0.06% less.
On the corpus 94% of lookups and 96% of normalizations hit, and the output is byte identical to master.
Review
- Can an entry be stale? The tables an entry depends on are immutable, so the same physical table gives the same answer. New unit tests bind the same path differently in two environments within one request (recursive type placeholders, recursive module approximations, an alias) and fail if any of these checks is removed.
- Can growing or reusing an entry return a wrong result? Growth moves each entry to the slot of its path in the larger table, and a lookup still checks the path, the epoch and the tables of each entry it finds. An entry is only referenced from its slot, so updating it in place changes no result a caller holds. A unit test looks up 3000 types across the growth and fails if a replaced entry keeps its old result.