[m-rev.] for review: Optimise hash table bucket lookup/set.

[Zoltan Somogyi]

On Thu,  1 Dec 2022 13:13:46 +1100, Peter Wang <novalazy at gmail.com> wrote:

> hash_table is implemented on top of array, and version_hash_table is
> implemented on top of version_array. To look up an array element, it is
> necessary to pass a type_info representing the element type to the
> lookup predicate. But the type_info is never used, so constructing it
> dynamically is a waste of time.

Are some lines missing from the front here? If not, please capitalize
the first word, and add a summary for git.
 
> The following change to version_hash_table.m improves the run time of a
> do-nothing build of Prince (using mmc --make) on my machine
> from 1.6 s to 1.55 s, with the standard library and compiler
> built at the default optimisation level. When version_hash_table.m is
> built with -O3, the run time improves further to 1.43 s.

What was the time with the old code before the diff, at -O3? The
transformation you are doing by hand should have very similar,
if not identical, effect due to the unused arg elimination, if it
works with intermodule optimization (which I don't remember
whether it is supposed to or not).

The diff is fine, except for a style issue:

> +unsafe_lookup_bucket(Buckets0, Slot, AL) :-
> +    % array.unsafe_lookup takes a type_info argument but does not use it.
> +    % Cast Buckets0 to a monomorphic type so the lookup call does not incur the
> +    % cost of dynamically constructing a type_info.
> +    private_builtin.unsafe_type_cast(Buckets0, Buckets),
> +    array.unsafe_lookup(Buckets, Slot, AL0 : c_pointer),
> +    private_builtin.unsafe_type_cast(AL0, AL).

Normally, Name0 and Name should have the same type, but here,
they don't. I would therefore rename Buckets to CastBuckets,
Buckets0 back to Buckets, and AL0 to CastAL.

> +unsafe_set_bucket(Slot, AL0, !Buckets) :-
> +    % Similarly for array.unsafe_set.
> +    private_builtin.unsafe_type_cast(!Buckets),
> +    private_builtin.unsafe_type_cast(AL0, AL : c_pointer),
> +    array.unsafe_set(Slot, AL, !Buckets),
> +    private_builtin.unsafe_type_cast(!Buckets).

A variant of the same issue here (all versions of a state variable
should have the same type), and with the corresponding code in version_array.m.

Zoltan.