[m-rev.] HLC backend speedup for N-queens

[Julien Fischer]

Hi Fabrice,

On Mon, 18 Jan 2021, fabrice nicol wrote:

> Below is a benchmark of N-queens runs for N=14 to N=16, using the Mercury 
> repository test file cqueens.m, slightly modified using an extra `solutions' 
> predicate added to `main' and cutting down on output.

Do you mind posting your modified version of the benchmark?

> Mercury does a good job, somewhere in-between two fairly naive C++ 
> implementations, and twice as fast as the closest Prolog compiler.
>
> The C benchmark is only given as incidental reference, since its algorithm is 
> heavily optimized using geometrical properties and low-level techniques.
>
> What struck me particularly is that the HLC backend now outperforms the LLC 
> one significantly in this test case, which is pleasantly unexpected. Further, 
> the speedup increases with N (Table 2).

...

> *Table 2   HLC to LLC speedup for N-queens*
>
> *    N                       14     15    16*
>     ----------------------------------------
>
>     speedup                 12%    14%   16%
>
> However, optimization options (-O1 to -O6) had no statistically significant 
> effect on either Mercury grades, performance-wise.

There's not a great deal of scope in that benchmark for applying most of
the higer level optimizations that the Mercury compiler implements.
(Increasing the C compiler optimization level may improve things
slightly for the hlc version.)

> If these results proved essentially correct for other common test cases,

Our standard benchmark is the Mercury compiler itself compiling its ten
largest modules.  With that hlc.gc is usually (slightly) faster than
asm_fast.gc.  Historically, this has varied, sometimes asm_fast.gc
is faster, sometimes hlc.gc is.

> it might be relevant to switch the default Unix compilation grade from
> asm_fast.gc (as is currently the case) to hlc.gc.

It already is the default on anything where the asm_fast grades are
not supported (e.g. macOS with clang as a C compiler).  We are intending
to swap it around after the compiler's command line options for dealing
with grade component selection have been revised (e.g. so the --debug
option does something sensible when the default grade is set to hlc.gc.)

Julien.