#2002: problems with very large (list) literals
------------------------------------------+---------------------------------
Reporter: Isaac Dupree | Owner:
Type: compile-time performance bug | Status: new
Priority: high | Milestone: 6.8.3
Component: Compiler | Version: 6.8.2
Severity: normal | Resolution:
Keywords: | Difficulty: Unknown
Testcase: | Architecture: x86
Os: Linux |
------------------------------------------+---------------------------------
Comment (by igloo):
Looking at modules like this:
{{{
module W where
w :: [Int]
w =
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]
}}}
one problem is in !OccAnal.
As we go down the desugared list syntax tree we go around this loop:
{{{
occAnal env app@(App _ _) = occAnalApp env (collectArgs app)
occAnalApp env (Var fun, args)
= case occAnalArgs env args of
(args_uds, args') -> (fun_uds +++ f args_uds, _)
occAnalArgs _env args
= case mapAndUnzip (occAnal arg_env) args of
(arg_uds_s, args') -> (f arg_uds_s, _)
}}}
As written, we build up a huge closure of `+++`s, which gives a stack
overflow
when we try to evaluate it. If we rewrite it along the lines of
{{{
occAnalApp env (Var fun, args)
= case occAnalArgs env args of
(args_uds, args') ->
let uds = fun_uds +++ f args_uds
in uds `seq` (uds, _)
}}}
then we have to go all the way along the spine to do the top-level `seq`,
so we get a stack overflow again.
It's not immediately obvious whether or not we can make the occurence
analyser pass the usage details around as an accumulating parameter, along
with a little more state, to avoid the stack usage.
----
When compiling with
{{{
ghc -cpp -fglasgow-exts -fforce-recomp -fasm -funbox-strict-fields -c W.hs
+RTS -p -hyTSO -h -xt
}}}
This table shows the fewest list elements needed for the stack to need to
grow to a given size:
{{{
number of list elements Stack size (kB) bytes per list element
300 250 833
600 500 833
1200 1000 833
2300 2000 870
4500 4000 889
8900 8000 899
}}}
(where the stack size is the peak usage of the heap graph).
So that looks linear to me, and about 100 words per stack element.
That's an order of magnitude more than I'd have expected, but it's not
completely inplausible. However, even if we made it an order of
magnitude smaller, I think people would still run into the limit.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2002#comment:5>
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
