[m-rev.] for review: Optimise dependency file index maps.

[Zoltan Somogyi]

On Tue, 6 Dec 2022 16:49:34 +1100, Peter Wang <novalazy at gmail.com> wrote:
> > Are you going to commit this? I would like to have a go at
> > rewriting this area of code to eliminate its "higher-order code
> > piled on top of more higher-order code" approach with
> > something much simpler.
> 
> We can get another decent speedup by caching the results of computing
> imports_012 (and maybe interface_file_dependencies). It seems fairly
> simple, but I'll wait if you are working on mmc --make.

I have replaced all the low-hanging fruit in terms of eliminating
unnecessary use of higher order. The remainder will be harder to get rid of.
At the moment, many parts of make.dependencies.m, including imports_012,
return lists of make targets to make in the form of a closure containing
lists of many nested closures, constructed using combine_deps. The
different elements in the nested closure lists invoke different functions,
so they are not simple folds. I have been thinking about replacing
the closure-containing-lists-of-closures with a first order data structure.

The idea is that instead of putting e.g. "module_target_int0 `of` ancestors"
into a combine_deps closure, you would put a first order term such as
"module_target(fk_int(ifk_int0), ancestors_of_cur_target)" into a list.
The closure output by combine_deps can be invoked only by predicates
that can pass it the extra arguments required by the find_module_deps type,
which almost requires predicates such as deps_set_foldl3_*. Likewise,
their replacement data structures would be interpreted by predicates
that closely resemble deps_set_foldl3_*, but instead of calling a closure,
they would interpret the corresponding element of the data structure,
which would tell them which first order call to make, and what arguments
to pass to it. The callee and the arglist would be the same as in the closure,
but the fold would get them from a first order list.

My work on this has just barely started, so you can go ahead and
add that cache if you want. The switchover to the above architecture
would probably require reimplementing that cache, but since it
sounds like you already have it implemented, there is no point
in you not committing it now.

Zoltan.