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

[Peter Wang]

On Thu, 01 Dec 2022 13:56:04 +1100 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> 
> 
> 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 summary is in the Subject line.

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

Oh, I thought the compiler couldn't eliminate the typeinfo arguments,
but it can if the version_array predicates are opt-exported.

I've rerun some tests.

 *  version_hash_table.m at -O3
    The typeinfo is NOT eliminated.

    Time (mean ± σ):      1.568 s ±  0.016 s    [User: 1.546 s, System: 0.019 s]
    Range (min … max):    1.534 s …  1.594 s    10 runs

 *  Force version_array.lookup to be opt-exported
    Compile version_hash_table.m and version_array.m at -O3 --intermod-opt
    The typeinfo is eliminated.

    Time (mean ± σ):      1.446 s ±  0.013 s    [User: 1.423 s, System: 0.022 s]
    Range (min … max):    1.427 s …  1.471 s    10 runs

 *  version_hash_table.m with this typecast hack (-O2)
    (a better result than I got before but of course it varies)

    Time (mean ± σ):      1.526 s ±  0.008 s    [User: 1.504 s, System: 0.020 s]
    Range (min … max):    1.514 s …  1.540 s    10 runs

 *  version_hash_table.m with this typecast hack (-O3)

    Time (mean ± σ):      1.430 s ±  0.010 s    [User: 1.406 s, System: 0.021 s]
    Range (min … max):    1.413 s …  1.451 s    10 runs

 *  version_hash_table.m with typecast hack, plus
    Force version_array.lookup to be opt-exported
    Compile version_hash_table.m and version_array.m at -O3 --intermod-opt

    Time (mean ± σ):      1.426 s ±  0.011 s    [User: 1.404 s, System: 0.019 s]
    Range (min … max):    1.404 s …  1.440 s    10 runs

I think we should add the pragma inlines to force version_array.lookup
predicate to be opt-exported. It will help other users of version_array
as well.

The typecast change is ugly but is contained within a few lines,
so it might be okay to keep it.

Peter