#2754: Strictness analyzer fails on an implementation of foldl
--------------------------------------+-------------------------------------
Reporter: nimnul | Owner:
Type: run-time performance bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 6.8.3
Severity: normal | Resolution:
Keywords: | Difficulty: Unknown
Testcase: | Architecture: x86
Os: Windows |
--------------------------------------+-------------------------------------
Comment (by nimnul):
You just replace foldl with foldA and foldB. The test code fragments are
{{{ main = print $ foldA (+) 0 l }}} and {{{ main = print $ foldB (+) 0 l
}}}
First of all, {{{foldl}}} works - it takes my pc about a second to
calculate the correct answer - {{{987459712}}}, without excessive heap or
stack usage.
While {{{foldA}}} is semantically equivalent to {{{foldl}}}, it has
different spatial complexity than current implementation of {{{foldl}}} in
{{{Prelude}}} - I get heap overflow with such a big list {{{l}}}.
The bug is that ghc generates inefficient code for a naive implementation
of {{{foldl}}}.
This behavior is strange, because in similar cases the optimizer works
perfectly. Even if you just "inline {{{op}}}", I mean substitute {{{op}}}
for its value {{{(+)}}}, memory is not eaten up any more:
{{{
foldC r [] = r
foldC r (x:xs) = foldC ((+) r x) xs
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2754#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
