[Agda] timing for agda-prelude gcd
Sergei Meshveliani
mechvel at botik.ru
Thu Jun 22 13:50:09 CEST 2017
On Thu, 2017-06-22 at 07:44 +0200, Ulf Norell wrote:
>
>
> On Wed, Jun 21, 2017 at 10:20 PM, Sergei Meshveliani
> <mechvel at botik.ru> wrote:
> Dear all,
>
> Earlier there was discussed in this list the performance of _
> +_ and _*_
> on Nat. I provided a test program.
> And as I recall, the performance is high: as in the Haskell
> program for
> ghc-7.10.2.
>
> Now I need fast divMod and gcd for Nat.
> Standard library is very-very slow at this point.
>
> So I try agda-prelude.
> It shows considerably faster.
> But it is still slower than GHC.
> gcd is about 12 times slower,
> and divMod is about 4000 times slower (?).
>
>
> divMod isn't slow, the problem is that you are using ≤? from the
> standard library in
> your implementation of max. If you replace it by ≤? from agda-prelude
> the Agda code
> [..]
Thank you. I see now that divMod and gcd of agda-prelude are fast
enough.
I suspected some mistake of mine of this sort in the test.
Now, I tried first to replace _≤?_. This leads to using Bool.
Also
decimalDigit? c = ... (48 ≤? n) ∧ (n ≤? 57)
caused a strange report about not finding the Ord instance for
something.
So, I removed _≤?_ at all, and replaced max with sum.
And now the test is indeed almost as fast as the GHC library.
Improving Nat performance by using both Standard library and
agda-prelude meets various technical difficulties. A headache.
Probably, Standard library needs improvement in implementation of
_≤?_ and divMod.
Regards,
------
Sergei
More information about the Agda
mailing list