[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>:

> +:- 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)
> +            ).

Something I forgot earlier: having a key this big can make searching
the map quite slow, especially when many keys in the map differ
from each other only in the later parts of the key. The way to fix that
is to make the map two-stage (or N-stage in general). In this case,
I would make it a map whose key is mer_type, and whose value
is effectively a map from f(list(bound_inst), uniqueness) for some f.
Putting the uniqueness up front guarantees lots of redundant test successes,
since most uniqueness values will be the same. I would even consider
putting an int representing the length of the list as a redundant first
arg of f, to speed up comparison failures between bound inst lists
that share a prefix but nevertheless differ, though I would commit to that
only after profiling.

All of the above matters only if you reuse caches. If you don't,
the caches probably won't grow big enough for any of this to matter.

Zoltan.