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