[m-users.] Too Slow

[Matthias Guedemann]

Hi Robert,

> -disable-most-grades option. I am very disappointed with the slowness
> of the procedures written for Mercury, and sometimes memory usage
> begins to blow up (slowly, over time as the process runs. Some of
> these run overnight). When I say I'm disappointed in the Mercury
> performance, I mean that by comparison with similar procedures I run
> written in Prolog, Erlang, Haskell, and Scheme, Mercury is much too
> slow, often taking 10 times or more as much time to complete. The
> Mercury runs I've made (not including those abandoned because of
> memory blowup) do complete and get correct results, but take way too
> much time to run.

In my opinion, the principal reason for this is that the Mercury
implementation for big integers is written in pure Mercury. In contrast,
Haskell calls GMP via FFI. GMP is a highly optimized library written in
C. For the other languages, it depends on the implementation, but very
likely they also use GMP or a similar library directly. The downside of
using GMP or another library is the added dependency, of course.

> Does anyone have any suggestions for speedup, other than "Avoid using
> Mercury for this purpose"? I'm attaching copies of the source code of
> the procedures that run so slowly.

A while ago, I implemented a faster multiplication algorithm for Mercury
(parallel for asm_fast.par.gc.stseg), but IIRC Miller-Rabin requires
primarily fast modulo and division. I am interested in optimizing these
routines, too, but have not yet put any work into it. In my opinion,
there is potential in optimizing the division and modulo algorithms and
maybe also in optimizing the representation of big integers (currently
lists of 14 bit digits), but to be honest, I think that reaching the
speed of anything based directly on GMP is unrealistic.

Best regards,
Matthias