[m-dev.] making .trans_opt files in parallel

[Peter Wang]

Hi Zoltan,

A quick response for now.

On Sat, 17 Dec 2022 21:11:03 +1100 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
>  Note that having a separate .dot file for each scc, instead of a single
>  .dot file for the whole system, should prevent the make the generated
>  graphs small enough to be easily explored in most cases. (An scc that
>  contains dozens of modules would probably still yield a hard-to-grasp
>  graph.)

The SCC at the core of the standard library is 77 modules big,
and the import graph is indeed unreadable. Every other SCC is only one
module big.

> - The tool could also output a .trans_opt_order file. This file would
>   contain a list of entries, each of which would be a list of one or more
>   module names:
> 
>     module_z    module_y module_x
>     module_y    module_u
>     module_x    module_u module_t
>     ...
> 
>   These lines implicitly describe a directed graph, by stating that there is
>   an edge from the first module on the line (the target), to each of the
>   following modules on the line (the sources).
> 
>   The meaning of each graph would be: the compiler invocation writing the
>   .trans_opt file of each module, e.g. module_z, is allowed to read
>   
>   - the .trans_opt files of the modules reachable from it directly
>     (for module_z, this means module_y and module_x), and
>   - the .trans_opt files of the modules reachable from it indirectly
>     (for module_z, this means at least module_u and module_t,
>     and maybe more).
> 
>   This graph, call it the trans_opt order graph,  would of course
>   not allow any cycles.
> 

I have a working POC which implements something like the
.trans_opt_order file you describe, though I just used term syntax,
and it doesn't complain about cycles. I will post the change
for inspection tomorrow or early next week.

>   If we give mmc --make access to this file, then, when it builds .trans_opt
>   files, it could build the .trans_opt files in bottom-up order. Given
>   an entry such as
> 
>     module_x    module_u module_t
> 
>   it could start building module_x.trans_opt as soon as module_u.trans_opt
>   and module_t.trans_opt are complete.
> 

Parallel mmc --make doesn't work on a dynamic work queue, where tasks
can be started once all its dependencies are ready. Instead, tasks are
done in stages. First all interface files are built. Then all target
files. Then object files, etc.

The model is starting to show its deficiency. A machine with many
threads will be largely sitting around waiting for the last tasks within
a stage to finish before it can continue. Also, each stage sets up and
tears down the parallel infrastructure separately, which is wasteful.

I think the deficiencies would be amplified if we built .trans_opt files
bottom up, by stages, as there would be many stages of few files to get
through. Given the marginal benefits, I would not attempt to support
transitive intermodule optimisation in mmc --make until the parallelism
support is improved, at least.

Peter