5 ms·

Analyzing Three Space Leaks in Haskell

59 points by okasaki 11y ago

lolo_ 11y ago
A quick google suggests space leak == memory leak, is that correct?
- dan00 11y ago
  No, the memory isn't lost, it's still reachable. It's more about using more memory than really needed, holding the unevaluated computation in memory instead of just the result of the computation.
  - userbinator 11y ago
    It's more about using more memory than really needed That's a statement which could apply to a lot of programs... Whatever it's called/how it occurs exactly, the result is the same: excessive memory usage. This is what most people will notice, and the term "memory leak" is usually used to encompass all the ways in which this can happen.
    - pdpi 11y ago
      Personally, If I read "memory leak", I expect c-style "lost all pointers to allocated memory" problems. If I read "space leak", I expect haskell-style "built up way too many thunks", like this. While the end results are similar, the mechanisms are wildly different, and just because _you_ don't differentiate between them doesn't mean that other people can't, or that it's not a useful distinction.
    - kryptiskt 11y ago
      The nasty thing about a space leak as compared to a traditional memory leak is that the thunk will likely get evaluated or discarded eventually. That's a good thing in that the memory used often won't grow unbounded in a long-running process, it's just larger than it should be, but it makes it way harder to find the source of the problem.
    - david-given 11y ago
      Haskell is weird. Imagine you're in a loop, where every iteration you add one to a number. In C, you increment the number, write it back, and everyone is happy. In Haskell, the number is not incremented then and there, but instead the runtime replaces the value with the unevaluated expression (n+1). The expression is only evaluated when its used. Then the value is replaced with the result of the expression. If you don't evaluate the expression, though, then the next iteration you get ((n+1)+1). And then (((n+1)+1+1). And so on until you run out of memory and the process falls over. While this is, technically, just another memory leak, they're distinctive enough to have acquired a different name. (To distinguish from, say, cached data building up in a data structure.) This is one of the biggest gotchas with Haskell programming, unfortunately; because the program is actually correct it's very hard to debug these. (Note that the author has to rely on trial and error a lot, and gives up completely on the last one. And the author's an experienced Haskell programmer!)
      - tetrep 11y ago
        > While this is, technically, just another memory leak... I wouldn't consider it a memory leak* at all, the memory is not lost as it is in a leak, space leaks get cleaned up if they are evaluated before you exhaust memory. Memory leaks are not cleaned up until your process dies. I can cause a 1gb space leak 100k times and it will only ever use 1gb of memory. I cannot do that with a memory leak. * the literal combination of "memory" and "leak" greatly imply the loss of the memory, as is generally what happens when you describe something as leaking; you lose it. additionally, wikipedia[0] seems to agree that the loss of memory is part of the definition. [0]: https://en.wikipedia.org/wiki/Memory_leak https://en.wikipedia.org/wiki/Memory_leak
    - chriswarbo 11y ago
      Memory leaks are logical errors. The program is wrong. The only way to fix the problem is by altering the source code to produce a different input/output behaviour; ie. to produce a different program. Space leaks are an implementation detail. The program may be correct, but not perform well on some particular implementation of the language; it may perform well on a different implementation. To fix the problem, we can either alter the implementation (eg. adding supercompilation, adding fusion rules, performing speculative evaluation, etc.) or we can alter the source code. In either case, the input/output behaviour is the same: we get a different implementation of the same program.
- okasaki 11y ago
  Usually, a space leak is an abnormal/unexpected amount of unevaluated data in a lazy language. A memory leak is data in the process heap that isn't referenced by the process.
  - deleted 11y ago
    [deleted]
- psibi 11y ago
  A more detailed explanation here: https://queue.acm.org/detail.cfm?id=2538488 https://queue.acm.org/detail.cfm?id=2538488 (from the same author of the post).
tempodox 11y ago
What, by All That Is Curried, is a space leak?
- the_af 11y ago
  As someone else already posted, here is a more detailed explanation: https://queue.acm.org/detail.cfm?id=2538488 https://queue.acm.org/detail.cfm?id=2538488
maxander 11y ago
This sort of problem is Haskell's downfall, and very nearly negates all the other wonderful features of the language. It doesn't matter how fun it was to write or how the type system promised you up and down it was correct- if your program is taking up 20Gb of memory to run in simple cases it's going nowhere. And as this post shows, solving such problems is easily as laborious a process as tracking down memory leaks or buffer overflows in C; in these cases nearly all of Haskell's great and powerful abstractions are working against you. The guys behind Haskell are utterly brilliant and seem to come up with profound new programming concepts on a regular basis, so I'm surprised they've not introduced fundamental features to solve or mitigate this problem. Until they do most people are going to be too scared to use Haskell for serious projects.
- outworlder 11y ago
  This seems to be a tooling issue. Given the right hooks, it should be much easier to profile and debug this sort of issue than chasing memory leaks in other languages. This is like trying to debug leaks in C with printf. It is just not done. Where's Haskell's valgrind-like tool?
  - gmfawcett 11y ago
    There's quite a bit of tooling already: http://book.realworldhaskell.org/read/profiling-and-optimization.html http://book.realworldhaskell.org/read/profiling-and-optimiza... https://wiki.haskell.org/ThreadScope https://wiki.haskell.org/ThreadScope http://www.slideshare.net/tibbe/highperformance-haskell http://www.slideshare.net/tibbe/highperformance-haskell
    - outworlder 11y ago
      Thanks for the links! I'll consume them as time allows. The question then becomes, why couldn't the author use them to help pinpoint the source of his issues?
      - gmfawcett 11y ago

59 points by okasaki 11y ago

lolo_ 11y ago

A quick google suggests space leak == memory leak, is that correct?

dan00 11y ago
No, the memory isn't lost, it's still reachable. It's more about using more memory than really needed, holding the unevaluated computation in memory instead of just the result of the computation.
- userbinator 11y ago
  It's more about using more memory than really needed That's a statement which could apply to a lot of programs... Whatever it's called/how it occurs exactly, the result is the same: excessive memory usage. This is what most people will notice, and the term "memory leak" is usually used to encompass all the ways in which this can happen.
  - pdpi 11y ago
    Personally, If I read "memory leak", I expect c-style "lost all pointers to allocated memory" problems. If I read "space leak", I expect haskell-style "built up way too many thunks", like this. While the end results are similar, the mechanisms are wildly different, and just because _you_ don't differentiate between them doesn't mean that other people can't, or that it's not a useful distinction.
  - kryptiskt 11y ago
    The nasty thing about a space leak as compared to a traditional memory leak is that the thunk will likely get evaluated or discarded eventually. That's a good thing in that the memory used often won't grow unbounded in a long-running process, it's just larger than it should be, but it makes it way harder to find the source of the problem.
  - david-given 11y ago
    Haskell is weird. Imagine you're in a loop, where every iteration you add one to a number. In C, you increment the number, write it back, and everyone is happy. In Haskell, the number is not incremented then and there, but instead the runtime replaces the value with the unevaluated expression (n+1). The expression is only evaluated when its used. Then the value is replaced with the result of the expression. If you don't evaluate the expression, though, then the next iteration you get ((n+1)+1). And then (((n+1)+1+1). And so on until you run out of memory and the process falls over. While this is, technically, just another memory leak, they're distinctive enough to have acquired a different name. (To distinguish from, say, cached data building up in a data structure.) This is one of the biggest gotchas with Haskell programming, unfortunately; because the program is actually correct it's very hard to debug these. (Note that the author has to rely on trial and error a lot, and gives up completely on the last one. And the author's an experienced Haskell programmer!)
    - tetrep 11y ago
      > While this is, technically, just another memory leak... I wouldn't consider it a memory leak* at all, the memory is not lost as it is in a leak, space leaks get cleaned up if they are evaluated before you exhaust memory. Memory leaks are not cleaned up until your process dies. I can cause a 1gb space leak 100k times and it will only ever use 1gb of memory. I cannot do that with a memory leak. * the literal combination of "memory" and "leak" greatly imply the loss of the memory, as is generally what happens when you describe something as leaking; you lose it. additionally, wikipedia[0] seems to agree that the loss of memory is part of the definition. [0]: https://en.wikipedia.org/wiki/Memory_leak https://en.wikipedia.org/wiki/Memory_leak
  - chriswarbo 11y ago
    Memory leaks are logical errors. The program is wrong. The only way to fix the problem is by altering the source code to produce a different input/output behaviour; ie. to produce a different program. Space leaks are an implementation detail. The program may be correct, but not perform well on some particular implementation of the language; it may perform well on a different implementation. To fix the problem, we can either alter the implementation (eg. adding supercompilation, adding fusion rules, performing speculative evaluation, etc.) or we can alter the source code. In either case, the input/output behaviour is the same: we get a different implementation of the same program.
okasaki 11y ago
Usually, a space leak is an abnormal/unexpected amount of unevaluated data in a lazy language. A memory leak is data in the process heap that isn't referenced by the process.
- deleted 11y ago
  [deleted]
psibi 11y ago
A more detailed explanation here: https://queue.acm.org/detail.cfm?id=2538488 https://queue.acm.org/detail.cfm?id=2538488 (from the same author of the post).

tempodox 11y ago

What, by All That Is Curried, is a space leak?

the_af 11y ago
As someone else already posted, here is a more detailed explanation: https://queue.acm.org/detail.cfm?id=2538488 https://queue.acm.org/detail.cfm?id=2538488

maxander 11y ago

This sort of problem is Haskell's downfall, and very nearly negates all the other wonderful features of the language. It doesn't matter how fun it was to write or how the type system promised you up and down it was correct- if your program is taking up 20Gb of memory to run in simple cases it's going nowhere. And as this post shows, solving such problems is easily as laborious a process as tracking down memory leaks or buffer overflows in C; in these cases nearly all of Haskell's great and powerful abstractions are working against you. The guys behind Haskell are utterly brilliant and seem to come up with profound new programming concepts on a regular basis, so I'm surprised they've not introduced fundamental features to solve or mitigate this problem. Until they do most people are going to be too scared to use Haskell for serious projects.

outworlder 11y ago
This seems to be a tooling issue. Given the right hooks, it should be much easier to profile and debug this sort of issue than chasing memory leaks in other languages. This is like trying to debug leaks in C with printf. It is just not done. Where's Haskell's valgrind-like tool?
- gmfawcett 11y ago
  There's quite a bit of tooling already: http://book.realworldhaskell.org/read/profiling-and-optimization.html http://book.realworldhaskell.org/read/profiling-and-optimiza... https://wiki.haskell.org/ThreadScope https://wiki.haskell.org/ThreadScope http://www.slideshare.net/tibbe/highperformance-haskell http://www.slideshare.net/tibbe/highperformance-haskell
  - outworlder 11y ago
    Thanks for the links! I'll consume them as time allows. The question then becomes, why couldn't the author use them to help pinpoint the source of his issues?
    - gmfawcett 11y ago