Ticket #876 (new bug)

Opened 2 years ago

Last modified 10 months ago

Length is not a good consumer

Reported by: ariep@xs4all.nl Assigned to: simonpj
Priority: normal Milestone: 6.10 branch
Component: libraries/base Version: 6.5
Severity: normal Keywords:
Cc: rich.neswold@gmail.com Difficulty: Unknown
Test Case: list003 Architecture: x86
Operating System: Linux

Description

The program

module Main where

main = print $ length . filter odd $ [0 .. 999999999]

, compiled with ghc-6.5.20060508 or later with optimisation turned on (-O), overflows the stack when run. It seems that the generated code is not tail-recursive. 6.4.2 and 6.5 snapshots up to 20060507 do not have this problem.

This may be a silly example, but the same thing happens if you replace 'odd' with some more interesting predicate, and let the length of the input list be chosen by the user.

Change History

08/24/06 06:03:22 changed by simonmar

  • milestone set to 6.6.

Thanks for narrowing this down to a particular day! I'd be willing to bet money that this is the culprit:

http://www.haskell.org/pipermail/cvs-libraries/2006-May/004996.html

08/29/06 11:54:03 changed by igloo

I've confirmed that the patch Simon M indicates is indeed the problem, and I've copied it below for reference.

It makes sense to me that the above behaviour is seen: length is now a good consumer, but it generates 1+(1+(1+(1+... as it is consuming, and this causes a stack overflow. I don't think we can fix this while staying with fold/build fusion, so it looks to me like the patch should be reverted and the whole problem looked at post-6.6.

Do you agree, Simon PJ?

Thanks Ian

[Make length a good consumer
simonpj@microsoft**20060508142726

 Make length into a good consumer.  Fixes Trac bug #707.

 (Before length simply didn't use foldr.)

] {
hunk ./GHC/List.lhs 114
-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 :: [a] -> Int
+length l = lenAcc 0# l
+
+{-# RULES
+"length" [~1] forall xs. length xs = foldr incL (I# 0#) xs
+"lenAcc" [1]  forall n#. foldr incL (I# n#) = lenAcc n#
+ #-}
+
+incL :: a -> Int -> Int        -- Internal
+{-# NOINLINE [0] incL #-}
+incL x n = n `plusInt` oneInt
+
+lenAcc :: Int# -> [a] -> Int   -- Internal
+lenAcc a# []     = I# a#
+lenAcc a# (_:xs) = lenAcc (a# +# 1#) xs
}

08/30/06 05:59:20 changed by simonmar

  • component changed from Compiler to libraries/base.
  • milestone changed from 6.6 to 6.6.1.

I rolled back the patch for 6.6 - linear stack space is more important than the constant factor speedup from fusion. Let's look at this again for 6.6.1.

09/28/06 03:34:48 changed by simonpj

  • summary changed from stack overflow on 'length . filter odd $ [0 .. 999999999]' to Length is not a good consumer.

Changing title to reflect current bug

09/28/06 03:34:59 changed by simonpj

  • owner set to simonpj.
  • milestone changed from 6.6.1 to 6.8.

09/28/06 04:02:45 changed by simonpj

This will probably get fixed as a result of revising list fusion: task #915

10/21/06 09:16:35 changed by igloo

  • testcase set to list003.

07/03/07 03:28:29 changed by guest

probably this ticket should be joined to the #915?

07/03/07 06:02:59 changed by guest

  • cc set to rich.neswold@gmail.com.

11/12/07 06:38:18 changed by simonmar

  • milestone changed from 6.8 branch to 6.10 branch.