5 ms·

Speaking of Haskell and laziness.. I found myself wondering last night, what was the issue with laziness again? I think it was that it's making it difficult to

by clarry 7y ago

Speaking of Haskell and laziness.. I found myself wondering last night, what was the issue with laziness again? I think it was that it's making it difficult to parallelize things. Why would that be? Is it just an implementation artefact, or are the rules of lazy evaluation actually disallowing the compiler/runtime from batching things appropriately for parallel computation? EDIT: Guess I was thinking of this: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3806 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3... > we have shown that lazy languages, even when implemented using a framework well-suited for parallelism, can generate only small amount of parallelism. [..] this result, when combined with the result concerning the low parallelism for really lazy programs, can also be interpreted as saying that there is not much hope for lazy languages as far as parallelism is concerned: in effect, they are saying that we can hope to obtain parallelism from programs written in a lazy language only when the programs do not need to be written in a lazy language! That's a really old paper though (1995), if there are more recent relevant studies or results, I'd be interested..

lmm 7y ago
The big problem with laziness is that it becomes impossible to reason about performance, because performance becomes noncompositional. If y = g(x) then we expect the computation time of f(g(x)) to be the computation time of g(x) plus the computation time of f(y), but in the presence of laziness that's no longer true. Any sufficiently large codebase hits a performance problem (usually a trivial one that ought to be easily resolved) eventually, and at that point you lose the ability to refactor fearlessly that's the great advantage of Haskell-like languages.
- tome 7y ago
  Hmm, I'm not sure that's quite right. The time taken by f(g(x)) under lazy evaluation is known to be no more than the time taken under strict evaluation. It's the space usage that can be hard to predict.
  - reitzensteinm 7y ago
    It's not more operations, but that extra space usage can mean the difference between creating and freeing objects with bump allocation in Eden that fits in cache, and walking over the heap doing a full GC so you don't run out of memory. There's a very real difference between what a simplified model of time complexity says should happen, and what actually happens when the layer of abstraction underlying the ivory tower start to spring a leak.
  - lmm 7y ago
    > The time taken by f(g(x)) under lazy evaluation is known to be no more than the time taken under strict evaluation. True but irrelevant (particularly given that idiomatic Haskell involves a lot of constructions that would take infinite time under strict evaluation). If x < a, y < b, z < c and a + b = c, that doesn't give you any useful relationship between x, y and z.
    - tome 7y ago
      A fair point. An example would be something like take 10 (map (+1) [1..])
  - TheCoelacanth 7y ago
    I don't think that's true in practice because excessive memory usage can lead to slower execution.

by clarry 7y ago

lmm 7y ago

The big problem with laziness is that it becomes impossible to reason about performance, because performance becomes noncompositional. If y = g(x) then we expect the computation time of f(g(x)) to be the computation time of g(x) plus the computation time of f(y), but in the presence of laziness that's no longer true. Any sufficiently large codebase hits a performance problem (usually a trivial one that ought to be easily resolved) eventually, and at that point you lose the ability to refactor fearlessly that's the great advantage of Haskell-like languages.

tome 7y ago
Hmm, I'm not sure that's quite right. The time taken by f(g(x)) under lazy evaluation is known to be no more than the time taken under strict evaluation. It's the space usage that can be hard to predict.
- reitzensteinm 7y ago
  It's not more operations, but that extra space usage can mean the difference between creating and freeing objects with bump allocation in Eden that fits in cache, and walking over the heap doing a full GC so you don't run out of memory. There's a very real difference between what a simplified model of time complexity says should happen, and what actually happens when the layer of abstraction underlying the ivory tower start to spring a leak.
- lmm 7y ago
  > The time taken by f(g(x)) under lazy evaluation is known to be no more than the time taken under strict evaluation. True but irrelevant (particularly given that idiomatic Haskell involves a lot of constructions that would take infinite time under strict evaluation). If x < a, y < b, z < c and a + b = c, that doesn't give you any useful relationship between x, y and z.
  - tome 7y ago
    A fair point. An example would be something like take 10 (map (+1) [1..])
- TheCoelacanth 7y ago
  I don't think that's true in practice because excessive memory usage can lead to slower execution.