
Hi, I have recently come across the curious phenomenon that ghci is sometimes much slower than hugs. The occasion that gave rise to it was in connection with continued fractions, where, having a continued fraction with quotients a(n), n >= 0, you get the numerators of the convergents by the recursion formula p(n) = a(n)*p(n-1) + p(n-2) starting with p(-2) = 0 and p(-1) = 1 (same recursion formula for the denominators, starting with q(-2) = 1 and q(-1) = 0). Now I implemented this algorithm first using 'zipWith': ms :: [Integer] -> [Integer] ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as) only to find it awfully slow, ms (replicate 27 2) for example took over 10 seconds, feeding a large list to 'ms' is inadvisable. Then I wrote a fast version of that algorithm, namely ps :: [Integer] -> [Integer] ps as = pStep 0 1 as where pStep :: Integer -> Integer -> [Integer] -> [Integer] pStep _ _ [] = [] pStep x y (a:as) = z:pStep y z as where z = a*y+x This works fine, so I wanted to find out what went wrong in the first version. In hugs, the 'zipWith'-version takes fewer reductions and both versions take more or less the same time, much less than 'ms' in ghci, more than 'ps' in ghci. The performance of 'ms' in ghci is significantly improved by a 'let' (or 'where') expression: pms :: [Integer] -> [Integer] pms as = let mas = pms as in zipWith (+) (zipWith (*) as (1:mas)) (0:1:mas) (no difference in hugs), however this is still much slower than 'ps', last (pms (replicate 1000 1)) takes about 2.75 secs, last (ps (replicate 1000 1)) about 0.01, even last (ps (replicate 10000 1)) took only 0.34 secs. Since usually ghci is MUCH faster than hugs, I am baffled by this behaviour. Does anybody know why this is so? And, apart from avoiding 'zipWith', what can be done to remedy the situation? Greetings, Daniel Fischer P.S.: ghci doesn't take 'zipWith' too well in other circumstances either, referring to the example of Fibonacci numbers in the book of Simon Thompson, the 'fastFib' function on page 76 runs faster in ghci than 'fibs' on page 431, in hugs, 'fibs!!n' takes fewer reductions (no big difference though).

On Tue, Dec 07, 2004 at 06:44:33PM +0100, Daniel Fischer wrote:
ms :: [Integer] -> [Integer] ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as)
This version seems to be faster, but I don't know if it addresses your concern: ms as = let l = zipWith (+) (zipWith (*) as (1:l)) (0:1:l) in l Best regards, Tomasz

Am Mittwoch, 8. Dezember 2004 10:22 schrieben Sie:
On Tue, Dec 07, 2004 at 06:44:33PM +0100, Daniel Fischer wrote:
ms :: [Integer] -> [Integer] ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as)
This version seems to be faster, but I don't know if it addresses your concern:
ms as = let l = zipWith (+) (zipWith (*) as (1:l)) (0:1:l) in l
Best regards, Tomasz
Thanks, indeed, this seems to produce roughly the same performance as 'ps' and I have a vague idea why this is better than 'pms', given that 'ms' is slower than 'ps'. But that is what baffled me in the first place, particularly because in hugs, things are different. Best regards, Daniel

On Wed, 8 Dec 2004, Daniel Fischer wrote:
Am Mittwoch, 8. Dezember 2004 10:22 schrieben Sie:
On Tue, Dec 07, 2004 at 06:44:33PM +0100, Daniel Fischer wrote:
ms :: [Integer] -> [Integer] ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as)
This version seems to be faster, but I don't know if it addresses your concern:
ms as = let l = zipWith (+) (zipWith (*) as (1:l)) (0:1:l) in l
Best regards, Tomasz
Thanks, indeed, this seems to produce roughly the same performance as 'ps' and I have a vague idea why this is better than 'pms', given that 'ms' is slower than 'ps'. But that is what baffled me in the first place, particularly because in hugs, things are different.
Is it possible and senseful for a compiler to extract common sub-expressions? Naively I think that for a given tree of an expression it is efficiently possible to find all common sub-trees. Referential transparency would assure that equal expressions have the same value, so they can be replaced by the same object. E.g. the example above could be automatically transformed to: ms as = let tmp0 = zipWith (+) (zipWith (*) as tmp1) (0:tmp1) tmp1 = 1:tmp0 in tmp0
participants (3)
-
Daniel Fischer
-
Henning Thielemann
-
Tomasz Zielonka