[m-rev.] for review: Speed up retrieval of foreign imports.

[Peter Wang]

On Thu, 24 Nov 2022 11:58:51 +1100 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> 
> 2022-11-23 12:28 GMT+11:00 "Peter Wang" <novalazy at gmail.com>:
> > For a do-nothing build of Prince with intermodule optimisation enabled,
> > mmc --make spends a large fraction of its time computing foreign imports,
> > or rather looking up the cached results of such. (There are 650 modules,
> > and the results for each module are looked up tens to hundreds of
> > thousands of times each.)
> 
> Do you know where those lookups are coming from? Speeding up
> the lookups is good, but eliminating them would be even better.
> 
> When I converted the compiler from Fergus's "lists of items"
> representation to using file-kind-specific parse trees, I noted
> that there were a lot of operations that scanned item lists
> looking for foreign imports, together with a varying set of
> other kinds of items. I thought I eliminated most of the
> redundant passes, though I did not try to eliminate them all,
> having bigger fish to fry. But if a single piece of info is looked up
> 10k+ times, then this fish was bigger than I thought :-)

I *think* due to Mantis bug #564 or something like that,
a large number of modules end up foreign-importing each other.

I'm looking at caching the result one level up, in
find_module_foreign_imports instead of find_module_foreign_imports_2.
We spend a lot of time computing the unions of, it turns out,
the same bitsets.

Peter