## #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