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

[Peter Wang]

On Mon, 12 Dec 2022 18:11:55 +1100 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> 
> 2022-12-12 16:04 GMT+11:00 "Peter Wang" <novalazy at gmail.com>:
> > I would like to fix the problem of .trans_opt files for the standard
> > library largely being made sequentially, instead of in parallel.
> > 
> > As a reminder, the standard library has a large cycle of modules that
> > import each other. The compiler imposes an arbitrary ordering on the
> > modules in the cycle so that "earlier" modules will not try to read from
> > the .trans_opt files of "later" modules before they have been made.
> > Thus the .trans_opt files can be made one by one, but not in parallel.
> > 
> > My idea is to introduce a mechanism to manually drop edges from the
> > .trans_opt dependency graph. For example, a pragma in module M of the
> > form:
> > 
> >     :- pragma no_trans_opt(foo).
> > 
> > would tell the compiler that it cannot read from foo.trans_opt
> > when making the M.trans_opt file.
> 
> I don't think this is the best way to achieve your objective.
> 
> What we want to specify is effectively a dag; if module B is reachable
> from module A, then module A may depend on B.trans_opt; otherwise,
> it may not. Each no_trans_opt pragma would put only one constraint
> on the dag, and there would be no easy way to check that two such
> pragmas in different modules basically rule out both A using B.trans_opt
> and B using A.trans_opt, which would not be a correctness problem,
> but may be a performance problem.
> 

Yes, I don't really mind that. (I don't think .trans_opt files provide
much value as it is, correct me if I'm wrong.)

> I think it would be better to specify the whole dag all at once,
> probably as the contents of a file, whose name can be passed
> to mmc in an option. Unfortunately, I don't know of a simple way
> to encode dag in a text file in a way that is
> 
> - unambiguous,
> - easy to read and understand,
> - but does not reduce all dags to a total order.
> 

An obvious place to start is something like the dot language, e.g.

    bar -> foo;
    baz -> bar;

Nodes (module names) may appear multiple times. It may be convenient to
reverse the order of the edges so that the imported module is written on
the left. As in dot, we may also allow grouping and/or nesting, say:

    foo <- {
	bar,
	baz <- quux
    }

I wrote a quick program see what it looks like on the standard library
(attached).


I'm not sure I like the "whole dag" approach better.

1. Changes to the module imports would need to be mirrored in the dag,
and it's likely people will forget (also being a pain). The compiler
could warn about edges that don't match a module import declaration,
but it can't tell the difference between an import that was accidentally
or deliberately left out of the dag. Pragmas placed near module import
declarations would be more visible.

2. Do we require modules that don't participate in a cycle to be
included in the dag? There's no technical reason to do so, so it's
just busywork. We might accept it for the standard library, whose
structure doesn't change quickly, but for other programs it would be
another impediment to enabling transitive intermodule optimisation
(apart from not being implemented in mmc --make).

3. Do we necessarily require a dag? Some smaller cycles may be
acceptable, letting the compiler impose its arbitrary ordering
as it does now.

Peter
-------------- next part --------------
array <- {
    array2d,
    hash_table,
    int,
    io,
    io.text_read,
    library,
    parsing_utils,
    pprint,
    pretty_printer,
    random,
    random.sfc32,
    random.sfc64,
    rtti_implementation,
    stream.string_writer,
    string.to_string,
    term_conversion,
}
array2d <- {
    library,
}
assoc_list <- {
    bag,
    bimap,
    digraph,
    hash_table,
    injection,
    io.environment,
    kv_list,
    library,
    map,
    multi_map,
    one_or_more_map,
    pqueue,
    psqueue,
    rbtree,
    robdd,
    string,
    tree234,
    varset,
    version_hash_table,
}
backjump <- {
    library,
}
bag <- {
    library,
}
benchmarking <- {
    io,
    library,
}
bimap <- {
    digraph,
    library,
}
bit_buffer <- {
    library,
}
bit_buffer.read <- {
    library,
}
bit_buffer.write <- {
    library,
}
bitmap <- {
    bit_buffer,
    bit_buffer.read,
    io,
    io.text_read,
    library,
    rtti_implementation,
    stream.string_writer,
    string.to_string,
    term_conversion,
}
bool <- {
    benchmarking,
    bit_buffer,
    bitmap,
    diet,
    dir,
    getopt,
    getopt_io,
    hash_table,
    io,
    library,
    mercury_term_parser,
    pretty_printer,
    random.system_rng,
    rbtree,
    robdd,
    rtti_implementation,
    set,
    set_bbbtree,
    set_ctree234,
    set_ordlist,
    set_tree234,
    set_unordlist,
    solutions,
    stream,
    string,
    string.format,
    table_statistics,
    term_io,
    term_to_xml,
    test_bitset,
    thread,
    thread.closeable_channel,
    thread.mvar,
    thread.semaphore,
    time,
    tree234,
    tree_bitset,
    version_bitmap,
    version_hash_table,
}
bt_array <- {
    library,
}
builtin <- {
    library,
}
calendar <- {
    library,
    stream.string_writer,
}
char <- {
    bitmap,
    calendar,
    dir,
    getopt,
    getopt_io,
    integer,
    io,
    io.primitives_read,
    io.primitives_write,
    io.text_read,
    library,
    mercury_term_lexer,
    mercury_term_parser,
    parsing_utils,
    pprint,
    pretty_printer,
    private_builtin,
    rtti_implementation,
    stream,
    stream.string_writer,
    string,
    string.builder,
    term_io,
    term_to_xml,
}
construct <- {
    deconstruct,
    library,
    term_conversion,
    term_to_xml,
}
cord <- {
    edit_seq,
    getopt,
    getopt_io,
    library,
    multi_map,
    one_or_more_map,
    psqueue,
    set_ctree234,
    set_ordlist,
    set_tree234,
}
counter <- {
    eqvclass,
    library,
    version_store,
}
deconstruct <- {
    io,
    library,
    pprint,
    pretty_printer,
    prolog,
    rtti_implementation,
    store,
    stream.string_writer,
    string,
    string.to_string,
    term_conversion,
    term_to_xml,
}
diet <- {
    library,
}
digraph <- {
    library,
}
dir <- {
    io,
    library,
}
edit_seq <- {
    library,
}
enum <- {
    bool,
    char,
    diet,
    digraph,
    fat_sparse_bitset,
    int,
    library,
    pprint,
    sparse_bitset,
    term,
    test_bitset,
    tree_bitset,
    uint,
}
eqvclass <- {
    library,
}
exception <- {
    array,
    bit_buffer,
    bitmap,
    dir,
    float,
    int,
    int16,
    int32,
    int64,
    int8,
    integer,
    io,
    library,
    math,
    random.system_rng,
    require,
    stm_builtin,
    string.format,
    test_bitset,
    thread.future,
    time,
    uint,
    uint16,
    uint32,
    uint64,
    uint8,
    version_array,
    version_hash_table,
}
fat_sparse_bitset <- {
    library,
}
float <- {
    hash_table,
    integer,
    library,
    math,
    mercury_term_parser,
    pretty_printer,
    private_builtin,
    random,
    rtree,
    string.format,
    table_statistics,
    version_hash_table,
}
gc <- {
    library,
}
getopt <- {
    library,
}
getopt_io <- {
    library,
}
hash_table <- {
    library,
}
injection <- {
    library,
}
int <- {
    array,
    array2d,
    bag,
    benchmarking,
    bit_buffer,
    bitmap,
    bt_array,
    builtin,
    calendar,
    char,
    construct,
    cord,
    counter,
    deconstruct,
    diet,
    dir,
    edit_seq,
    eqvclass,
    fat_sparse_bitset,
    float,
    hash_table,
    int16,
    int32,
    int64,
    int8,
    integer,
    io,
    io.text_read,
    library,
    list,
    map,
    mercury_term_lexer,
    multi_map,
    one_or_more,
    one_or_more_map,
    parsing_utils,
    pprint,
    pqueue,
    pretty_printer,
    private_builtin,
    prolog,
    psqueue,
    queue,
    ra_list,
    random,
    random.sfc16,
    random.sfc32,
    random.sfc64,
    ranges,
    rbtree,
    robdd,
    rtree,
    rtti_implementation,
    set_bbbtree,
    set_ctree234,
    set_tree234,
    sparse_bitset,
    std_util,
    stream.string_writer,
    string,
    string.format,
    string.parse_runtime,
    string.parse_util,
    string.to_string,
    table_statistics,
    term,
    term_conversion,
    term_io,
    term_to_xml,
    thread.barrier,
    time,
    tree234,
    tree_bitset,
    uint16,
    uint32,
    uint64,
    uint8,
    varset,
    version_array,
    version_array2d,
    version_bitmap,
    version_hash_table,
    version_store,
}
int16 <- {
    integer,
    io,
    library,
    pprint,
    private_builtin,
    rtti_implementation,
    string.format,
}
int32 <- {
    integer,
    io,
    library,
    pprint,
    private_builtin,
    rtti_implementation,
    string.format,
}
int64 <- {
    integer,
    io,
    io.text_read,
    library,
    pprint,
    private_builtin,
    string.format,
}
int8 <- {
    integer,
    io,
    library,
    pprint,
    private_builtin,
    string.format,
}
integer <- {
    library,
    mercury_term_lexer,
    mercury_term_parser,
    rational,
    stream.string_writer,
    string.format,
    term,
    term_conversion,
    term_int,
    term_io,
}
io <- {
    backjump,
    benchmarking,
    bit_buffer.read,
    bit_buffer.write,
    bitmap,
    calendar,
    dir,
    exception,
    gc,
    getopt,
    getopt_io,
    library,
    mercury_term_lexer,
    mercury_term_parser,
    par_builtin,
    pprint,
    pretty_printer,
    prolog,
    psqueue,
    random,
    region_builtin,
    robdd,
    stm_builtin,
    store,
    stream.string_writer,
    table_builtin,
    table_statistics,
    term_io,
    thread,
    thread.barrier,
    thread.channel,
    thread.closeable_channel,
    thread.mvar,
    thread.semaphore,
    time,
    tree234,
}
io.call_system <- {
    io,
    library,
}
io.environment <- {
    io,
    io.file,
    library,
}
io.file <- {
    dir,
    io,
    library,
}
io.primitives_read <- {
    io,
    io.text_read,
    library,
}
io.primitives_write <- {
    io,
    library,
}
io.stream_db <- {
    io,
    library,
    stream.string_writer,
}
io.stream_ops <- {
    io,
    library,
}
io.text_read <- {
    io,
}
kv_list <- {
    hash_table,
    library,
}
lazy <- {
    library,
}
library <- {
    mer_std,
}
list <- {
    array,
    array2d,
    assoc_list,
    backjump,
    bag,
    benchmarking,
    bimap,
    bit_buffer,
    bitmap,
    bool,
    bt_array,
    calendar,
    char,
    construct,
    cord,
    deconstruct,
    diet,
    digraph,
    dir,
    edit_seq,
    eqvclass,
    exception,
    fat_sparse_bitset,
    getopt,
    getopt_io,
    hash_table,
    injection,
    integer,
    io,
    io.environment,
    io.text_read,
    kv_list,
    library,
    map,
    maybe,
    mercury_term_lexer,
    mercury_term_parser,
    multi_map,
    one_or_more,
    one_or_more_map,
    parsing_utils,
    pprint,
    pqueue,
    pretty_printer,
    prolog,
    psqueue,
    queue,
    ra_list,
    random,
    ranges,
    rbtree,
    require,
    robdd,
    rtree,
    rtti_implementation,
    set,
    set_bbbtree,
    set_ctree234,
    set_ordlist,
    set_tree234,
    set_unordlist,
    solutions,
    sparse_bitset,
    stack,
    stream,
    stream.string_writer,
    string,
    string.builder,
    string.format,
    string.parse_runtime,
    string.parse_util,
    table_statistics,
    term,
    term_conversion,
    term_int,
    term_io,
    term_subst,
    term_to_xml,
    term_unify,
    term_vars,
    test_bitset,
    time,
    tree234,
    tree_bitset,
    type_desc,
    univ,
    varset,
    version_array,
    version_array2d,
    version_hash_table,
}
map <- {
    bag,
    bimap,
    digraph,
    edit_seq,
    eqvclass,
    getopt,
    getopt_io,
    injection,
    io,
    io.environment,
    io.stream_db,
    library,
    mercury_term_parser,
    multi_map,
    one_or_more_map,
    pprint,
    pretty_printer,
    robdd,
    term,
    term_subst,
    term_to_xml,
    term_unify,
    varset,
}
math <- {
    library,
    random,
}
maybe <- {
    benchmarking,
    bimap,
    bitmap,
    construct,
    deconstruct,
    diet,
    dir,
    exception,
    getopt,
    getopt_io,
    io,
    io.environment,
    io.stream_db,
    library,
    map,
    mercury_term_parser,
    parsing_utils,
    psqueue,
    random.system_rng,
    rbtree,
    rtti_implementation,
    string,
    table_statistics,
    term_to_xml,
    test_bitset,
    thread,
    thread.channel,
    thread.mvar,
    time,
    tree234,
    tree_bitset,
    varset,
}
mercury_term_lexer <- {
    library,
    mercury_term_parser,
    term_io,
}
mercury_term_parser <- {
    io,
    library,
}
multi_map <- {
    library,
    robdd,
}
mutvar <- {
    benchmarking,
    lazy,
    library,
    parsing_utils,
    random,
    solutions,
    thread.future,
    thread.mvar,
}
one_or_more <- {
    library,
    one_or_more_map,
}
one_or_more_map <- {
    library,
}
ops <- {
    library,
    mercury_term_parser,
    pprint,
    pretty_printer,
    stream.string_writer,
    string,
    string.to_string,
    term_io,
}
pair <- {
    assoc_list,
    bag,
    bimap,
    digraph,
    getopt,
    getopt_io,
    hash_table,
    injection,
    io.environment,
    kv_list,
    library,
    map,
    multi_map,
    one_or_more_map,
    pprint,
    pqueue,
    prolog,
    psqueue,
    rbtree,
    robdd,
    string,
    test_bitset,
    tree234,
    tree_bitset,
    varset,
    version_hash_table,
}
par_builtin <- {
    library,
}
parsing_utils <- {
    library,
}
pprint <- {
    library,
}
pqueue <- {
    library,
}
pretty_printer <- {
    array,
    char,
    float,
    int,
    int16,
    int32,
    int64,
    int8,
    library,
    list,
    one_or_more,
    string,
    tree234,
    uint,
    uint16,
    uint32,
    uint64,
    uint8,
    version_array,
}
private_builtin <- {
    library,
}
profiling_builtin <- {
    library,
}
prolog <- {
    library,
}
psqueue <- {
    library,
}
queue <- {
    library,
}
ra_list <- {
    bt_array,
    library,
}
random <- {
    library,
}
random.sfc16 <- {
    library,
}
random.sfc32 <- {
    library,
}
random.sfc64 <- {
    library,
}
random.system_rng <- {
    library,
}
ranges <- {
    library,
}
rational <- {
    library,
}
rbtree <- {
    library,
}
region_builtin <- {
    library,
}
require <- {
    array,
    array2d,
    assoc_list,
    bag,
    benchmarking,
    bimap,
    bit_buffer,
    bit_buffer.read,
    bitmap,
    bt_array,
    calendar,
    char,
    construct,
    deconstruct,
    diet,
    digraph,
    dir,
    edit_seq,
    enum,
    eqvclass,
    fat_sparse_bitset,
    getopt,
    getopt_io,
    hash_table,
    injection,
    int16,
    int32,
    int64,
    int8,
    integer,
    io,
    kv_list,
    library,
    list,
    map,
    mercury_term_lexer,
    mercury_term_parser,
    multi_map,
    one_or_more,
    one_or_more_map,
    ops,
    pqueue,
    pretty_printer,
    private_builtin,
    prolog,
    psqueue,
    ra_list,
    ranges,
    rational,
    rbtree,
    robdd,
    rtree,
    rtti_implementation,
    set,
    set_bbbtree,
    set_ctree234,
    set_ordlist,
    set_tree234,
    set_unordlist,
    solutions,
    sparse_bitset,
    stack,
    store,
    stream.string_writer,
    string,
    string.format,
    table_builtin,
    table_statistics,
    term_conversion,
    term_size_prof_builtin,
    term_subst,
    term_to_xml,
    test_bitset,
    thread,
    thread.barrier,
    time,
    tree234,
    tree_bitset,
    type_desc,
    uint,
    uint16,
    uint32,
    uint64,
    uint8,
    univ,
    varset,
    version_array2d,
    version_bitmap,
    version_hash_table,
}
robdd <- {
    library,
    pprint,
}
rtree <- {
    library,
}
rtti_implementation <- {
    construct,
    deconstruct,
    io,
    library,
    stream.string_writer,
    string.to_string,
    type_desc,
}
set <- {
    bag,
    digraph,
    eqvclass,
    fat_sparse_bitset,
    getopt,
    getopt_io,
    library,
    map,
    multi_map,
    one_or_more_map,
    ranges,
    set_tree234,
    solutions,
    sparse_bitset,
    test_bitset,
    tree234,
    tree_bitset,
    varset,
}
set_bbbtree <- {
    library,
    robdd,
}
set_ctree234 <- {
    library,
}
set_ordlist <- {
    library,
    set,
    test_bitset,
}
set_tree234 <- {
    library,
    list,
}
set_unordlist <- {
    library,
    robdd,
}
solutions <- {
    exception,
    getopt,
    getopt_io,
    library,
    test_bitset,
}
sparse_bitset <- {
    digraph,
    library,
    pprint,
    robdd,
}
stack <- {
    library,
}
std_util <- {
    dir,
    library,
}
stm_builtin <- {
    exception,
    library,
}
store <- {
    exception,
    library,
}
stream <- {
    bit_buffer,
    bitmap,
    io,
    library,
    pprint,
    pretty_printer,
    string.builder,
    term_io,
    term_to_xml,
}
stream.string_writer <- {
    io,
    library,
    term_io,
}
string <- {
    array,
    assoc_list,
    backjump,
    benchmarking,
    bitmap,
    calendar,
    diet,
    dir,
    exception,
    float,
    getopt,
    getopt_io,
    injection,
    int,
    int16,
    int32,
    int64,
    int8,
    integer,
    io,
    io.call_system,
    kv_list,
    library,
    list,
    mercury_term_lexer,
    mercury_term_parser,
    parsing_utils,
    pprint,
    pretty_printer,
    private_builtin,
    psqueue,
    random.system_rng,
    require,
    robdd,
    rtti_implementation,
    set_ctree234,
    set_tree234,
    stream.string_writer,
    table_statistics,
    term_conversion,
    term_io,
    term_to_xml,
    test_bitset,
    time,
    tree234,
    type_desc,
    uint,
    uint16,
    uint32,
    uint64,
    uint8,
    univ,
    varset,
    version_array,
}
string.builder <- {
    library,
}
string.format <- {
    library,
    string,
}
string.parse_runtime <- {
    string.format,
}
string.parse_util <- {
    library,
    string.format,
    string.parse_runtime,
}
string.to_string <- {
    string,
}
table_builtin <- {
    io,
    library,
    table_statistics,
}
table_statistics <- {
    library,
}
term <- {
    bag,
    fat_sparse_bitset,
    io,
    library,
    list,
    map,
    mercury_term_parser,
    pprint,
    robdd,
    set,
    set_ctree234,
    set_ordlist,
    set_tree234,
    sparse_bitset,
    term_conversion,
    term_int,
    term_io,
    term_subst,
    term_unify,
    term_vars,
    tree234,
    tree_bitset,
    varset,
}
term_context <- {
    library,
    mercury_term_parser,
    term,
    term_conversion,
    term_subst,
    term_unify,
}
term_conversion <- {
    io,
    library,
}
term_int <- {
    library,
    term,
    term_conversion,
}
term_io <- {
    char,
    library,
    pretty_printer,
    rtti_implementation,
    stream.string_writer,
    string,
    string.to_string,
}
term_size_prof_builtin <- {
    library,
}
term_subst <- {
    io,
    library,
    term,
    term_conversion,
    term_unify,
    varset,
}
term_to_xml <- {
    library,
}
term_unify <- {
    library,
    term,
}
term_vars <- {
    library,
    term,
    term_unify,
}
test_bitset <- {
    library,
}
thread <- {
    library,
}
thread.mvar <- {
    thread.barrier,
    thread.channel,
    thread.closeable_channel,
}
thread.semaphore <- {
    thread.future,
    thread.mvar,
}
time <- {
    calendar,
    io,
    io.file,
    library,
}
tree234 <- {
    library,
    map,
    pretty_printer,
}
tree_bitset <- {
    library,
    test_bitset,
}
type_desc <- {
    array,
    assoc_list,
    construct,
    deconstruct,
    io,
    kv_list,
    library,
    pprint,
    pretty_printer,
    private_builtin,
    require,
    rtti_implementation,
    stream.string_writer,
    string.to_string,
    term_conversion,
    term_to_xml,
    univ,
}
uint <- {
    char,
    counter,
    digraph,
    fat_sparse_bitset,
    int,
    int16,
    int32,
    int64,
    int8,
    integer,
    library,
    mercury_term_parser,
    ops,
    pretty_printer,
    private_builtin,
    random,
    random.sfc16,
    sparse_bitset,
    string,
    string.format,
    term,
    tree_bitset,
    uint16,
    uint32,
    uint64,
    uint8,
}
uint16 <- {
    char,
    int16,
    integer,
    io,
    library,
    pprint,
    private_builtin,
    random.sfc16,
    random.sfc32,
    random.sfc64,
    string.format,
}
uint32 <- {
    int32,
    integer,
    io,
    library,
    pprint,
    private_builtin,
    random,
    random.sfc16,
    random.sfc32,
    random.sfc64,
    string.format,
}
uint64 <- {
    int64,
    integer,
    io,
    library,
    pprint,
    private_builtin,
    random.sfc16,
    random.sfc32,
    random.sfc64,
    string.format,
}
uint8 <- {
    char,
    int8,
    integer,
    io,
    library,
    pprint,
    private_builtin,
    random.sfc16,
    random.sfc32,
    random.sfc64,
    string,
    string.format,
}
unit <- {
    dir,
    exception,
    getopt,
    getopt_io,
    library,
    parsing_utils,
    term_to_xml,
    version_hash_table,
    version_store,
}
univ <- {
    construct,
    deconstruct,
    exception,
    io,
    library,
    pprint,
    pretty_printer,
    prolog,
    rtti_implementation,
    stm_builtin,
    stream.string_writer,
    string.to_string,
    table_builtin,
    term_conversion,
    term_to_xml,
    version_store,
}
varset <- {
    library,
    mercury_term_parser,
    term_io,
}
version_array <- {
    library,
    pprint,
    pretty_printer,
    stream.string_writer,
    string.to_string,
    term_conversion,
    version_array2d,
    version_bitmap,
    version_hash_table,
    version_store,
}
version_array2d <- {
    library,
}
version_bitmap <- {
    library,
}
version_hash_table <- {
    library,
}
version_store <- {
    library,
}