[GHC] #876: Length is not a good consumer

[GHC]

#876: Length is not a good consumer
--------------------------------------+-------------------------------------
  Reporter:  ariep@…                  |          Owner:                  
      Type:  bug                      |         Status:  closed          
  Priority:  lowest                   |      Milestone:  7.6.2           
 Component:  libraries/base           |        Version:  6.5             
Resolution:  fixed                    |       Keywords:  length          
        Os:  Linux                    |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |     Difficulty:  Unknown         
  Testcase:  perf/should_run/T876     |      Blockedby:                  
  Blocking:                           |        Related:                  
--------------------------------------+-------------------------------------
Changes (by simonpj):

  * status:  new => closed
  * testcase:  list003 => perf/should_run/T876
  * resolution:  => fixed


Comment:

 This patch to `GHC.List` makes `length` a good consumer, for what it's
 worth. The nofib numbers didn't budge.

 Simon

 {{{
 commit 82f56e5a331f9bbd5c8afda9e8d8ad71059e934b
 Author: Simon Peyton Jones <simonpj at microsoft.com>
 Date:   Thu Feb 14 08:22:08 2013 +0000

     Make 'length' into a good consumer, fixing Trac #876

     Trac #876 is the oldest ticket I have fixed in a long time.
     I finally figured out how to make foldr behave in a non
     space-leaky way for length.

     Thanks to Andy for re-opening.

 >---------------------------------------------------------------

  GHC/List.lhs |   23 ++++++++++++++++++-----
  1 files changed, 18 insertions(+), 5 deletions(-)

 diff --git a/GHC/List.lhs b/GHC/List.lhs index 02d6965..049aa2a 100644
 --- a/GHC/List.lhs
 +++ b/GHC/List.lhs
 @@ -114,12 +114,25 @@ null (_:_)              =  False
  -- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.
  -- It is an instance of the more general 'Data.List.genericLength',
  -- the result type of which may be any kind of number.
 +{-# NOINLINE [1] length #-}
  length                  :: [a] -> Int
 -length l                =  len l 0#
 -  where
 -    len :: [a] -> Int# -> Int
 -    len []     a# = I# a#
 -    len (_:xs) a# = len xs (a# +# 1#)
 +length l                =  lenAcc l 0#
 +
 +lenAcc :: [a] -> Int# -> Int
 +lenAcc []     a# = I# a#
 +lenAcc (_:xs) a# = lenAcc xs (a# +# 1#)
 +
 +incLen :: a -> (Int# -> Int) -> Int# -> Int incLen _ g x = g (x +# 1#)
 +
 +-- These rules make length into a good consumer
 +-- Note that we use a higher-order-style use of foldr, so that
 +-- the accumulating parameter can be evaluated strictly
 +-- See Trac #876 for what goes wrong otherwise {-# RULES
 +"length"     [~1] forall xs. length xs = foldr incLen I# xs 0#
 +"lengthList" [1]  foldr incLen I# = lenAcc  #-}

  -- | 'filter', applied to a predicate and a list, returns the list of
  -- those elements that satisfy the predicate; i.e.,
 }}}

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