[m-rev.] for review: Optimise modechecking of coerce for large types.

[Zoltan Somogyi]

2021-04-20 15:16 GMT+10:00 "Peter Wang" <novalazy at gmail.com>:
> @@ -179,6 +180,15 @@ modecheck_coerce_vars(ModuleInfo0, X, Y, InstX, InstY, Res, !ModeInfo) :-
>     uniqueness::in, mer_type::in, mer_inst::out) is det.
>  make_bound_inst_for_type(ModuleInfo, Seen0, Uniq, Type, Inst) :-
> +    make_bound_inst_for_type_with_cache(ModuleInfo, Seen0, Uniq, Type, Inst,
> +        map.init, _Cache).

This code throws away the cache after each call to make_bound_inst_for_type.
Are you sure that the benefit of keeping the cache *across* calls, either
in a data structure kept by its caller(s) or in a mutable, is less than the
cost of the required code complexity?

Have you measured the benefit you get from the cache?

> @@ -292,6 +316,16 @@ ground_or_unique_inst(Uniq) =
>  %---------------------------------------------------------------------------%
> +:- type bound_inst_cache == map(type_and_bound_inst, mer_inst).
> +
> +:- type type_and_bound_inst
> +    --->    type_and_bound_inst(
> +                mer_type,
> +                % These fields are from a bound() inst.
> +                uniqueness,
> +                list(bound_inst)
> +            ).
> +
>     % Check that a bound() inst only includes functors that are constructors of
>     % the given type, recursively. Insts are otherwise assumed to be valid for
>     % the type, and not checked to be valid for the type in other respects.
> @@ -303,6 +337,15 @@ ground_or_unique_inst(Uniq) =

I would have expected to see the definition of the cache type
either before the first code that uses the cache. or just before the code
that implements the cache. Seeing it in the middle, next to code that it is
not strongly related to, is ... strange.

Since in this case the cache is added to in several places, putting the
type definition up front would seem to be better.

>  check_bound_functors_in_type(ModuleInfo, Type, Inst0, Inst) :-
> +    check_bound_functors_in_type_with_cache(ModuleInfo, Type, Inst0, Inst,
> +        map.init, _Cache).

Same issue here with throwing away the cache.

> -check_bound_functors_in_defined_type(ModuleInfo, Type, Inst0, Inst) :-
> +check_bound_functors_in_defined_type(ModuleInfo, Type, Inst0, Inst, !Cache) :-
>     require_complete_switch [Inst0]
>     (
>         Inst0 = bound(Uniq, _InstResults0, BoundInsts0),
> -        type_to_ctor(Type, TypeCtor),
> -        % type_constructors substitutes type args into constructors.
> -        type_constructors(ModuleInfo, Type, Constructors),
> -        list.map(
> -            check_bound_functor_in_du_type(ModuleInfo, TypeCtor, Constructors),
> -            BoundInsts0, BoundInsts),
> -        % XXX A better approximation of InstResults is probably possible.
> -        Inst = bound(Uniq, inst_test_no_results, BoundInsts)
> +        TypeAndBoundInst0 = type_and_bound_inst(Type, Uniq, BoundInsts0),
> +        ( if map.search(!.Cache, TypeAndBoundInst0, CachedInst) then
> +            Inst = CachedInst
> +        else
> +            type_to_ctor(Type, TypeCtor),
> +            % type_constructors substitutes type args into constructors.
> +            type_constructors(ModuleInfo, Type, Constructors),
> +            list.foldl(build_ctors_map, Constructors, map.init, CtorsMap),

Again, you build CtorsMap, and then throw it away when this predicate returns.

I think there should already be something in the type table entry for TypeCtor
that should do the job of CtorsMap, even if it is not exactly equivalent to it.
That should be built just once, when TypeCtor is defined. If I am wrong, and
there no nothing relevant in the type table, then I think we should fix that.

> +:- type ctors_map == map(ctor_name_and_arity, constructor).
> +
> +:- type ctor_name_and_arity
> +    --->    ctor_name_and_arity(string, int).
> +
> +:- pred build_ctors_map(constructor::in, ctors_map::in, ctors_map::out) is det.
> +
> +build_ctors_map(Ctor, !CtorsMap) :-
> +    Ctor = ctor(_, _, ConsName, _, Arity, _),
> +    unqualify_name(ConsName) = Name,
> +    NameArity = ctor_name_and_arity(Name, Arity),
> +    map.det_insert(NameArity, Ctor, !CtorsMap).

This code should not be needed (see above), but if it is, move the code
for calling it with list.foldl with info from a type table entry here as well,
to make it stand alone.

The diff is otherwise fine.

Zoltan.