Skip to content

refactor quadratic search in warnMissingHomeModules

Fixes #24778 (closed).

I've replaced the naive search with lookup in two sets. The previous implementation performed multiple checks with different filepath variants, but it seems to me that comparing normalized paths without extension should be sufficent. At least the tests for this warning seem to agree.

I added a perf test intended to catch issues like this when they are introduced, by running a build on 10k modules. I hope this is not too coarse for a perf test. This problem manifested as a ~ 30 second delay when running ghc -M, and turned out to occur also for --make. Since the latter also takes a lot of time compiling those modules, I only used -M in the test for now. Since we cannot benchmark time, the allocations will have to do, but they look pretty meaningful:

Old:
large-project-makedepend-4000(normal)  ghc/alloc  9,132,932,296
large-project-makedepend-10000(normal) ghc/alloc 51,858,022,888

New:
large-project-makedepend-4000(normal)  ghc/alloc  1,274,688,040
large-project-makedepend-10000(normal) ghc/alloc  3,172,322,728

Note the superlinear complexity in the old state.

Merge request reports