Opened 9 years ago

Closed 9 years ago

Last modified 7 years ago

#741 closed bug (fixed)

full laziness

Reported by: guest Owned by:
Priority: normal Milestone:
Component: Compiler Version: 6.4.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

GHC 6.4.1 isn't fully lazy as the following code snippet demonstrates.

> module Test where

> data Nat = Z | S Nat
>            deriving (Show, Eq)
>
> memo f       =  \ n -> case n of Z   -> f_Z
>                                  S n -> f_S n
>   where f_Z  =  f Z
>         f_S  =  memo (\ y -> f (S y))
>
> fib :: Nat -> Integer
> fib Z          =  0
> fib (S Z)      =  1
> fib (S (S n))  =  fib (S n) + fib n
>
> fib' :: Nat -> Integer
> fib'             =  memo fib
>   where
>   fib Z          =  0
>   fib (S Z)      =  1
>   fib (S (S n))  =  fib' (S n) + fib' n

Hugs calculates the memoized version of fib much faster.

Test> :set +s Test> map fib [0 .. 30] [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040] (21162936 reductions, 29882544 cells, 30 garbage collections) Test> map fib' [0 .. 30] [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040] (18924 reductions, 25176 cells)

By contrast, GHCi gives:

*Test> :set +s *Test> map fib [0 .. 30] [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040] (5.71 secs, 423333160 bytes) *Test> map fib' [0 .. 30] [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040] (19.75 secs, 2430652680 bytes)

The memoized version is actually slower. The flags

-no-full-laziness and -ffull-laziness seem to have no influence on the performance.

> instance Num Nat where
>   fromInteger 0        =  Z
>   fromInteger (n + 1)  =  S (fromInteger n)
>   Z + n                =  n
>   S m + n              =  S (m + n)
>   Z * n                =  Z
>   S m * n              =  (m * n) + n
>   Z - n                =  Z
>   S m - Z              =  S m
>   S m - S n            =  m - n
>
> instance Enum Nat where
>   succ                 =  S
>   pred Z               =  Z
>   pred (S n)           =  n
>   toEnum               =  fromInteger . toInteger
>   fromEnum Z           =  0
>   fromEnum (S n)       =  fromEnum n + 1

Change History (4)

comment:1 Changed 9 years ago by simonmar

  • Resolution set to fixed
  • Status changed from new to closed

GHC doesn't claim to implement full-laziness, although the documentation is a little vague on this point. I've expanded it a bit now.

Full-laziness is an optimisation that is performed when -O is on (and hence never when using GHCi). Even so, it isn't applied consistently, so you shouldn't rely on GHC performing full-laziness.

comment:2 Changed 9 years ago by simonpj

Actually Simon's comment is wrong. this program should be fast regardless of full laziness. It's a bug in 6.4.1, but it was not present in 6.4 and has been fixed in 6.4.2 (not yet released) and the HEAD.

For those who care, it was in preInlineUnconditionally.

Still, it's a nice test, and I'll add it to the test suite

Simon

comment:3 Changed 7 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:4 Changed 7 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple
Note: See TracTickets for help on using tickets.