Re: [Haskell-cafe] what is a stack overflow?
On Wed, Jan 26, 2005 at 01:04:29PM -, Simon Marlow wrote: > On 25 January 2005 16:04, S. Alexander Jacobson wrote: > > Is there a way to profile stack usage using GHCi > > (without compiling) to find the problem? > > +RTS -xt -RTS will include the stack in a heap profile. See > > http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html > > It will show you the size of the stack over time, but not the contents > of the stack. BTW, has anyone considered making a stackless Haskell implementation? For example, SML compiler SML/NJ allocates "stack" frames on the heap. Best regards, Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] what is a stack overflow?
On 25 January 2005 16:04, S. Alexander Jacobson wrote: > Ok. I guessed I was producing a big expression > of the form > >addToFM (addToFM (addToFM (addToFM (addToFM ...) > > I tried to solve it by doing > >(addToFM $! fm) key val > > But still got an error. I then tried the same > with the wrapper code, but still got the error. > > Is there a way to profile stack usage using GHCi > (without compiling) to find the problem? +RTS -xt -RTS will include the stack in a heap profile. See http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html It will show you the size of the stack over time, but not the contents of the stack. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is a stack overflow?
Ok. I guessed I was producing a big expression of the form addToFM (addToFM (addToFM (addToFM (addToFM ...) I tried to solve it by doing (addToFM $! fm) key val But still got an error. I then tried the same with the wrapper code, but still got the error. Is there a way to profile stack usage using GHCi (without compiling) to find the problem? -Alex- On Mon, 24 Jan 2005, Iavor Diatchki wrote: hi, it may happen for different reasons, but a common one is when you have a foldl pattern (programming with an accumulator), for example like this: sumList1 [] accum = accum sumList1 (x:xs) accum = sumList1 xs (x + accum) this adds a list of numbers with an accumulator. because haskell is lazy however, the additions (the accumulator) are not evaluated, instead the compiler builds a big expression, that is to be evaluated later. for example: sumList1 [1,2,3] 0 = sumList1 [2,3] (1 + 0) = sumList1 [3] (2 + (1 + 0)) = sumList1 [] (3 + (2 + (1 + 0)) = 3 + (2 + (1 + 0) notice that the accumlator is not evaluated as you go along. now the way this expression is evaluated (roughly) is: start pushing... (stack on the rhs) 3 + (2 + (1 + 0) [] 2 + (1 + 0)[3] 1 + 0[2,3] 0 [1,2,3] now poping... 1 [2,3] 3 [3] 6 [] and the result is 6. if the list is very long, you will need to push very many things on the stack to evaluate the expression, and so you might run out of stack. the way to avoid this problem is to not create the big expression, by forcing the accumulator to be evaluated "as you go along" rather then once at the end. this can be done like this: sumList2 [] accum = accum sumList2 (x:xs) accum = sumList2 xs $! (x + accum) ($!) is like ($) except that it forces the evaluation of its arguments. now the expression is likely to be evaluated using very little stack (if the compiler notices that we have a tail recursive call, and it should) hope this helped -iavor On Mon, 24 Jan 2005 19:19:09 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: Thank you iavor. But the -K option doesn't appear to work with ghci. And I guess the bigger question is what sort of code causes a stack overflow. If 5M is enough stack for most programs then I obviously have some basic coding error which is causing a stack overflow... What sort of code causes that? -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com On Mon, 24 Jan 2005, Iavor Diatchki wrote: hi, programs compile with GHC have a bunch of command line switches. you can see them by typing: myProg +RTS -help one of them enables you to specify stack space, e.g. myPorg +RTS -K5M (very briefly) the stack is a part of memory used by the compiler to pass around arguments to functions, and for temporary computations. -iavor On Mon, 24 Jan 2005 17:16:08 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: GHC assumes the user knows the difference between the heap and the stack. I don't. No matter how much heap I specify on the GHCi command line, I get a stack overflow exception. I have no idea what that means or how to remedy it. Hints? Note: My program is basically creating a few 100k item FiniteMaps. I don't think that should exceed the memory on my laptop -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is a stack overflow?
Also, how do I get the profiler to tell me whether I am consuming heap or stack? -Alex- On Mon, 24 Jan 2005, Iavor Diatchki wrote: hi, it may happen for different reasons, but a common one is when you have a foldl pattern (programming with an accumulator), for example like this: sumList1 [] accum = accum sumList1 (x:xs) accum = sumList1 xs (x + accum) this adds a list of numbers with an accumulator. because haskell is lazy however, the additions (the accumulator) are not evaluated, instead the compiler builds a big expression, that is to be evaluated later. for example: sumList1 [1,2,3] 0 = sumList1 [2,3] (1 + 0) = sumList1 [3] (2 + (1 + 0)) = sumList1 [] (3 + (2 + (1 + 0)) = 3 + (2 + (1 + 0) notice that the accumlator is not evaluated as you go along. now the way this expression is evaluated (roughly) is: start pushing... (stack on the rhs) 3 + (2 + (1 + 0) [] 2 + (1 + 0)[3] 1 + 0[2,3] 0 [1,2,3] now poping... 1 [2,3] 3 [3] 6 [] and the result is 6. if the list is very long, you will need to push very many things on the stack to evaluate the expression, and so you might run out of stack. the way to avoid this problem is to not create the big expression, by forcing the accumulator to be evaluated "as you go along" rather then once at the end. this can be done like this: sumList2 [] accum = accum sumList2 (x:xs) accum = sumList2 xs $! (x + accum) ($!) is like ($) except that it forces the evaluation of its arguments. now the expression is likely to be evaluated using very little stack (if the compiler notices that we have a tail recursive call, and it should) hope this helped -iavor On Mon, 24 Jan 2005 19:19:09 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: Thank you iavor. But the -K option doesn't appear to work with ghci. And I guess the bigger question is what sort of code causes a stack overflow. If 5M is enough stack for most programs then I obviously have some basic coding error which is causing a stack overflow... What sort of code causes that? -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com On Mon, 24 Jan 2005, Iavor Diatchki wrote: hi, programs compile with GHC have a bunch of command line switches. you can see them by typing: myProg +RTS -help one of them enables you to specify stack space, e.g. myPorg +RTS -K5M (very briefly) the stack is a part of memory used by the compiler to pass around arguments to functions, and for temporary computations. -iavor On Mon, 24 Jan 2005 17:16:08 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: GHC assumes the user knows the difference between the heap and the stack. I don't. No matter how much heap I specify on the GHCi command line, I get a stack overflow exception. I have no idea what that means or how to remedy it. Hints? Note: My program is basically creating a few 100k item FiniteMaps. I don't think that should exceed the memory on my laptop -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is a stack overflow?
hi, it may happen for different reasons, but a common one is when you have a foldl pattern (programming with an accumulator), for example like this: sumList1 [] accum = accum sumList1 (x:xs) accum = sumList1 xs (x + accum) this adds a list of numbers with an accumulator. because haskell is lazy however, the additions (the accumulator) are not evaluated, instead the compiler builds a big expression, that is to be evaluated later. for example: sumList1 [1,2,3] 0 = sumList1 [2,3] (1 + 0) = sumList1 [3] (2 + (1 + 0)) = sumList1 [] (3 + (2 + (1 + 0)) = 3 + (2 + (1 + 0) notice that the accumlator is not evaluated as you go along. now the way this expression is evaluated (roughly) is: start pushing... (stack on the rhs) 3 + (2 + (1 + 0) [] 2 + (1 + 0)[3] 1 + 0[2,3] 0 [1,2,3] now poping... 1 [2,3] 3 [3] 6 [] and the result is 6. if the list is very long, you will need to push very many things on the stack to evaluate the expression, and so you might run out of stack. the way to avoid this problem is to not create the big expression, by forcing the accumulator to be evaluated "as you go along" rather then once at the end. this can be done like this: sumList2 [] accum = accum sumList2 (x:xs) accum = sumList2 xs $! (x + accum) ($!) is like ($) except that it forces the evaluation of its arguments. now the expression is likely to be evaluated using very little stack (if the compiler notices that we have a tail recursive call, and it should) hope this helped -iavor On Mon, 24 Jan 2005 19:19:09 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: > Thank you iavor. But the -K option doesn't appear > to work with ghci. And I guess the bigger > question is what sort of code causes a > stack overflow. If 5M is enough stack for most > programs then I obviously have some basic coding > error which is causing a stack overflow... > > What sort of code causes that? > > -Alex- > __ > S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com > > On Mon, 24 Jan 2005, Iavor Diatchki wrote: > > > hi, > > programs compile with GHC have a bunch of command line switches. > > you can see them by typing: > > myProg +RTS -help > > one of them enables you to specify stack space, e.g. > > myPorg +RTS -K5M > > > > (very briefly) the stack is a part of memory used by the compiler to > > pass around arguments > > to functions, and for temporary computations. > > -iavor > > > > > > > > > > On Mon, 24 Jan 2005 17:16:08 -0500 (Eastern Standard Time), S. > > Alexander Jacobson <[EMAIL PROTECTED]> wrote: > >> GHC assumes the user knows the difference between > >> the heap and the stack. I don't. No matter how > >> much heap I specify on the GHCi command line, I > >> get a stack overflow exception. I have no idea > >> what that means or how to remedy it. Hints? > >> > >> Note: My program is basically creating a few 100k > >> item FiniteMaps. I don't think that should exceed > >> the memory on my laptop > >> > >> -Alex- > >> > >> __ > >> S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com > >> ___ > >> Haskell-Cafe mailing list > >> Haskell-Cafe@haskell.org > >> http://www.haskell.org/mailman/listinfo/haskell-cafe > >> > > > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is a stack overflow?
Thank you iavor. But the -K option doesn't appear to work with ghci. And I guess the bigger question is what sort of code causes a stack overflow. If 5M is enough stack for most programs then I obviously have some basic coding error which is causing a stack overflow... What sort of code causes that? -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com On Mon, 24 Jan 2005, Iavor Diatchki wrote: hi, programs compile with GHC have a bunch of command line switches. you can see them by typing: myProg +RTS -help one of them enables you to specify stack space, e.g. myPorg +RTS -K5M (very briefly) the stack is a part of memory used by the compiler to pass around arguments to functions, and for temporary computations. -iavor On Mon, 24 Jan 2005 17:16:08 -0500 (Eastern Standard Time), S. Alexander Jacobson <[EMAIL PROTECTED]> wrote: GHC assumes the user knows the difference between the heap and the stack. I don't. No matter how much heap I specify on the GHCi command line, I get a stack overflow exception. I have no idea what that means or how to remedy it. Hints? Note: My program is basically creating a few 100k item FiniteMaps. I don't think that should exceed the memory on my laptop -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] what is a stack overflow?
GHC assumes the user knows the difference between the heap and the stack. I don't. No matter how much heap I specify on the GHCi command line, I get a stack overflow exception. I have no idea what that means or how to remedy it. Hints? Note: My program is basically creating a few 100k item FiniteMaps. I don't think that should exceed the memory on my laptop -Alex- __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe