[GHC] #7436: Derived Foldable and Traversable instances become extremely inefficient due to eta-expansion

[GHC]

#7436: Derived Foldable and Traversable instances become extremely inefficient due
to eta-expansion
---------------------------------+------------------------------------------
    Reporter:  shachaf           |       Owner:                         
        Type:  bug               |      Status:  new                    
    Priority:  normal            |   Milestone:                         
   Component:  Compiler          |     Version:  7.6.1                  
    Keywords:                    |          Os:  Unknown/Multiple       
Architecture:  Unknown/Multiple  |     Failure:  Runtime performance bug
  Difficulty:  Unknown           |    Testcase:                         
   Blockedby:                    |    Blocking:                         
     Related:                    |  
---------------------------------+------------------------------------------
Changes (by simonpj):

  * difficulty:  => Unknown


Old description:

> The following program:
>
> {{{
> {-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
> import Prelude hiding (foldr)
> import Data.Foldable
>
> data List a = Nil | Cons a (List a)
>     deriving (Functor, Foldable)
>
> mkList :: Int -> List Int
> mkList 0 = Nil
> mkList n = Cons n (mkList (n-1))
>
> main :: IO ()
> main = print $ foldr (\x y -> y) "end" (mkList n)
>   where n = 100000
> }}}
>
> Takes `n^2` time to run with GHC 7.6.1 -O2.
>
> The generated `Foldable` code looks something like this:
>
> {{{
> instance Foldable List where
>     foldr f z Nil = z
>     foldr f z (Cons x xs) = f x (foldr (\a b -> f a b) z xs)
> }}}
>
> Eta-reducing the function, i.e.
>
> {{{
> instance Foldable List where
>     foldr f z Nil = z
>     foldr f z (Cons x xs) = f x (foldr f z xs)
> }}}
>
> Makes the program linear in `n` (in this case, runtime goes from 8.160s
> to 0.004s).
>
> The `Traversable` instance also has the same issue.
>
> There seem to be three different issues:
>
> * Derived `Foldable` and `Traversable` instances are nearly unusable for
> large
> structures.
>
> * An eta-expanded definition like `foldr` becomes asymptotically worse
> for some
> reason.
>
> Maybe this is expected behavior for this function, since `f` gets eta-
> expanded
> at each iteration?
>
> * `Foldable` instances are generated with `foldr` instead of `foldMap`.
>
> This isn't directly related, since the code would have the same problem
> either
> way, but since I'm already writing about it... `foldMap` can allow
> asymptotically better operations on a structure than `foldr` (for
> example,
> finding the rightmost leaf of a binary tree using `Data.Monoid.Last`), so
> it
> should probably be generated instead. A `foldMap` definition should look
> like a
> simpler version of `traverse`, which is already derivable. Maybe this
> should be
> a separate ticket.

New description:

 The following program:

 {{{
 {-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
 import Prelude hiding (foldr)
 import Data.Foldable

 data List a = Nil | Cons a (List a)
     deriving (Functor, Foldable)

 mkList :: Int -> List Int
 mkList 0 = Nil
 mkList n = Cons n (mkList (n-1))

 main :: IO ()
 main = print $ foldr (\x y -> y) "end" (mkList n)
   where n = 100000
 }}}

 Takes `n^2` time to run with GHC 7.6.1 -O2.

 The generated `Foldable` code looks something like this:

 {{{
 instance Foldable List where
     foldr f z Nil = z
     foldr f z (Cons x xs) = f x (foldr (\a b -> f a b) z xs)
 }}}

 Eta-reducing the function, i.e.

 {{{
 instance Foldable List where
     foldr f z Nil = z
     foldr f z (Cons x xs) = f x (foldr f z xs)
 }}}

 Makes the program linear in `n` (in this case, runtime goes from 8.160s to
 0.004s).

 The `Traversable` instance also has the same issue.

 There seem to be three different issues:

  * Derived `Foldable` and `Traversable` instances are nearly unusable for
 large structures.

  * An eta-expanded definition like `foldr` becomes asymptotically worse
 for some reason. Maybe this is expected behavior for this function, since
 `f` gets eta-expanded at each iteration?

  * `Foldable` instances are generated with `foldr` instead of `foldMap`.

 This isn't directly related, since the code would have the same problem
 either
 way, but since I'm already writing about it... `foldMap` can allow
 asymptotically better operations on a structure than `foldr` (for example,
 finding the rightmost leaf of a binary tree using `Data.Monoid.Last`), so
 it
 should probably be generated instead. A `foldMap` definition should look
 like a
 simpler version of `traverse`, which is already derivable. Maybe this
 should be
 a separate ticket.

--

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7436#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler