#70 performance problem

1.3.0
open-accepted
5
2009-06-23
2009-06-20
Anonymous
No

Hi,
i have the following input file
--------------------------------------------------------
powi : (PI,PI) -> List Integer
powi( m, n) ==
a : IntegerMod n
a := m
[a^i for i in 1..n-1] :: List Integer
-------------------------------------------------
calculating x := powi (3, 2^14) ; takes a long time !
(5) -> )set mess time on
(5) -> x := powi (3, 2^14) ;
Type: List Integer
Time: 19.57 (IN) + 28.16 (EV) + 8.68 (OT) = 56.41 sec

Discussion

  • The first source of slowness is the fact that the list
    comprehension interpreted as opposed to being
    compiled. That interpretation, in turn, comes from the
    interpreter spotting a use of dependent type (the type of
    the local variable 'a' depends on the function parameter
    'n', therefore declaring incapacity to compile.
    Another source is the interpreter building a list, then
    converting it to a vector, then converting that vector back
    to a list. Which is silly.

     
    • labels: --> interpreter
    • milestone: --> 1.3.0
    • assigned_to: nobody --> dos-reis
     
    • status: open --> open-accepted
     
  • Some data point. On my machine, different Lisp systems
    report different time.

    GCL: Time: 8.20 (IN) + 2.55 (EV) + 6.62 (OT) = 17.37 sec

    ECL: Time: 14.41 (IN) + 6.66 (EV) + 22.76 (OT) = 43.84 sec

    SBCL: Time: 8.62 (IN) + 11.65 (EV) + 5.88 (OT) = 26.14 sec

    -- Gaby

     
  • Further data. If you don't use dependent types, but you
    rewrite the function as

    powi : (PI,PI) -> List Integer
    powi(m, n) ==
    [positiveRemainder(m^i, n) for i in 1..n-1] :: List Integer

    x := powi(3,2^14)

    Then the timing drops dramatically for all Lisp-based OpenAxiom
    except SBCL:

    GCL: Time: 0.65 (IN) + 3.53 (EV) + 0.15 (OT) = 4.33 sec

    ECL: Time: 0.35 (IN) + 9.08 (EV) + 0.56 (OT) = 9.98 sec

    SBCL: ime: 0.26 (IN) + 23.59 (EV) + 0.55 (OT) = 24.40 sec

    -- Gaby