6 ms·

Avoiding space leaks at all costs

56 points by ghuntley 4y ago

MauranKilom 4y ago
Wait, the first suggested fix for "lazy evaluation consumes too much memory" is "make it eager"? I'm sure I'm missing some nuance here, but that seems backwards.
- Arnt 4y ago
  Lazily evaluating 2+2 requires storing two numbers and an operator for a while, eagerly evaluating requires storing just one number (4, the result). This can be a real problem, for example if you read potentially large network input eagerly and use it to compute a small result lazily. IMO it's always a mistake and IMNSHO the proper solution is always something more nuanced than just "make it eager" or "make it properly lazy".
- mrkeen 4y ago
  In all languages, sometimes you want eager evaluation and sometimes you want lazy evaluation. If things are lazy by default, you simply need to put a "!" before the term to evaluate in order to get eagerness. If things are eager by default, you need to rewrite the algorithm as a streaming algorithm.
  - cvoss 4y ago
    There's no inherent reason why doing lazy evaluation in an eager-by-default language should be any harder than the reverse. I can imagine a language that is eager by default but has a '#' operator that holds expressions in unevaluated form until terms are requested.
    - ParetoOptimal 4y ago
      > There's no inherent reason why doing lazy evaluation in an eager-by-default language should be any harder than the reverse. lazy by default enables better composition and local reasoning. https://publish.obsidian.md/paretooptimaldev/Advantages+of+lazy+evaluation https://publish.obsidian.md/paretooptimaldev/Advantages+of+l...
    - shirogane86x 4y ago
      Sadly even though what you say is true, I do not know of any languages that get that right. Even those that do care enough to give you a way to make lazy values, they require you to explicitly wrap them and force them all over the place, making lazy programming effectively so noisy it's unusable. Which is the main reason why I still find myself coming back to haskell (stuff like parser combinators is just so unwieldy without laziness and do notation...)
      - MauranKilom 4y ago
        Counterpoint: C++ expression templates have existed for a long time, and require no explicit work on the user side. They are incredibly unwieldy to write and debug though.
        shirogane86x 4y ago
        I am gonna be completely honest, I have never quite been able to understand expression templates properly. is it possible to use them to get hassle-free laziness? is there any example of a library that does this (just to look at it and see how it's done)?
        MauranKilom 4y ago
        Define hassle-free. In readability of user code? Yes. In getting clean compiler errors? No. One example would be Eigen: https://eigen.tuxfamily.org/index.php?title=Main_Page https://eigen.tuxfamily.org/index.php?title=Main_Page See also their page on lazy evaluation: https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html Of course, C++ is powerful enough that using specific tools can make the expression template abstraction fall apart (e.g. auto), but fundamentally you can write matrix code very cleanly and get great lazy-evaluated performance.
    - Quekid5 4y ago
      While you're technically right, it's only in the same sense that any TC language can do anything any other TC language can -- you can theoretically always delay any computation behind a lambda, but the ergonomics have wide-ranging consequences. You also don't get any memoization that way -- without further runtime support. There was a good Reddit thread recently where a lot of experts weighed in: https://www.reddit.com/r/haskell/comments/wpbs4z/what_things_would_be_awkward_to_do_in_a/ikhtng3/ https://www.reddit.com/r/haskell/comments/wpbs4z/what_things... I recommend reading the thread -- lot's of great stuff in there, but... TL;DR: It's a lot more complicated than it seems at first and it's far from obvious that strict-by-default is worth the cost.
    - chas 4y ago
      The combination of lazy evaluation and state mutation/side effects can be pretty difficult to reason about. For example, if you have a function that changes a global variable as a part of a lazy computation, once that function could have been called you have no way of knowing if or when that global variable will change in the future. If you have other functions that depend on the value of that variable, their future behavior is now much more challenging to reason about than in a strict language. You can also imagine something akin to a race condition in which there are multiple lazy computations which could eventually set that variable to different values and the actual sequence of state transitions depends entirely on the dependency order of a possibly unrelated piece of code. In practice, this means that in languages that are strict by default, lazy computations are often forced to run in order to reason about the code, rather than because the actual results of the computation are required. Since pure functions compute the same results under lazy or strict evaluation and require that any data dependencies they have are explicitly provided as inputs, they interact with lazy computations in a much more tractable way. This means that adding a strictness operator to a lazy language is much easier than adding a laziness operator a a strict language. An alternate approach is what python did with generators where there is a data type for lazy computation, but it lives apart from the rest of the language, so it is mostly used for e.g. stream processing where a default-lazy approach is conceptually straightforward and is less likely to lead to extremely non-trivial control flow. This approach does, however, basically give up on having a laziness operator that will turn a strict computation into a lazy one.
  - Joker_vD 4y ago
    > you simply need to put a "!" before the term to evaluate in order to get eagerness That's wrong. With the bang pattern, evaluation only goes up to WHNF, not the whole way — it's just a syntax sugar around "seq" which has been around since always. If you need to fully evaluate the term, look at the deepseq package: it's implementation is non-trivial.
- Joker_vD 4y ago
  Yes. Which is my main criticism of Haskell: sure, sometimes laziness is very handy, sometimes it's even indispensable... but most of the time, eager is what you want, with judicious sprinkles of explicitly lazy structures (btw, OCaml has "lazy" keyword exactly for that). Sure, GHC goes to heroic lengths and turns as much lazy computations as it can into eager ones, but there is always a limit to what it can do on its own, and you inevitably end with the programmer having to slap strict patterns and seqs and deepseqs wherever they can reach.
  - Quekid5 4y ago
    In OCaml lazy data is fundamentally incompatible with strict data -- you have to explicitly evaluate it, e.g. when passing to a function which takes strict data. This means you end up with two disjoint 'worlds' where you need to write algorithms twice, etc. (In fact you'd have to do that for every possible variant of where exactly the laziness lies.) The ergonomics become incredibly bad, unfortunately. (Also see my link to a Reddit thread elsewhere in this thread further ideas on why strict-by-default is not a simple win.)
    - Joker_vD 4y ago
      The same split exists in Haskell as well: Data.Text.Text vs Data.Text.Lazy.Text, etc. And in LISP IIRC lazy data are type-compatible with strict data.
      - Quekid5 4y ago
        Yes, it's true, and the split is also painful in Haskell. The split exists in Haskell for a choice few data structures where it truly matters for performance -- it also exists for Set/Map. (And I'd argue it is actually a bad thing from a purely language perspective, but sometimes practicality does win out, even in Haskell.) I think it might actually have been a mistake to have the lazy variants of these data structures, esp. Text/ByteString. IME it's extremely rare to want laziness for these... and it's usually just when building output strings (where there are better solutions like Builders). Anyway, I digress... IME the same applies to lazy Map/Set, but I'm less familiar with uses for the lazy versions of these. (IIRC they're only spine-lazy, which is rarely what you want, tho.) > And in LISP IIRC lazy data are type-compatible with strict data. LISP is dynamically typed -- it's trivial to do there. Also not the directionality: You can go from lazy to strict (that's just evaluation which the runtime will do for you), but you can NOT go the other way automatically. Recovering laziness from strictness is impossible. The problem with the split happens when you have mismatching types that your compiler will shout at you for.
eptcyka 4y ago
> Fortunately, this is easily possible with Haskell. You need to enable the BangPatterns feature and use exclamations ! in front of patterns for variables where you want the evaluation to be performed eagerly. Of course, this is simple - you just enable a language extension so that the language you are referring to Haskell is no longer really Haskell. I think Haskell is a fine language, but given the amount of various language extensions that are needed for it to be usable in production without friction, it seems it will forever be a research language - and there is nothing wrong with that.
- ParetoOptimal 4y ago
  > I think Haskell is a fine language, but given the amount of various language extensions that are needed for it to be usable in production without friction, it seems it will forever be a research language - and there is nothing wrong with that. This isn't really a problem in the real world, only in theory.
- nequo 4y ago
  It is Haskell, just not Haskell2010. It is included in GHC2021. Would you say that a company that uses a subset of C++ as a policy is not using C++? Their definition of the subset is as arbitrary as another’s that uses BangPatterns.
  - eptcyka 4y ago
    Sure, this language feature is mainstream now. But most real-world haskell codbases vary greatly in which language extensions they've chosen to use.
    - kzrdude 4y ago
      Is this a C++ benefit, that the competing implementations GCC and LLVM give each other's extensions to the language more legitimacy by having a second implementation? It doesn't seem like language extensions get so much attention in C++ codebases (but maybe I'm mistaken)?
skywhopper 4y ago
I have tried and failed to comprehend Haskell for my own uses. Certainly most of the examples in this article are meaningless gibberish to my smooth, practical brain. So kudos to those who grok the underlying math and find it a useful language. That said, I am a fan of lazy evaluation in the right circumstances, and often find myself implementing lazy data structures (particularly in my Ruby programs). Ultimately, though, I’m confused by this article which seems to be all about removing laziness from Haskell in ways that seem entirely counter to what I take to be its purpose. If you have to bend over backwards and rewrite your code in awkward ways to get the language to behave the way you want, maybe the project itself isn’t right for the language? It’s one thing to hack around a couple of isolated space issues in a larger context, but if you are enabling language extensions across the board by default to prefer eager evaluation, why are you using Haskell at all?
- ParetoOptimal 4y ago
  > Certainly most of the examples in this article are meaningless gibberish to my smooth, practical brain My smooth practical brain struggles in languages that aren't Haskell.
- daniel-cussen 4y ago
  I've never heard of or met a circumstance that actually warranted Haskell. Not even in finance, those guys are totally wasting their time. It's an attractive (I'm going to say "it seems" though you ought to take that for granted) intellectual rathole. Like some forms of philosophy, like many things. Thank GOD (despite being unbelieving at the time) I went with Lisp instead. And I got real speedups.
  - ParetoOptimal 4y ago
    > I've never heard of or met a circumstance that actually warranted Haskell. Sounds like you are biased to conclude it has no purpose to begin with.
  - benreesman 4y ago
    Algorithmic finance might be the most ruthlessly Darwinian area of industrial software, it’s way up there certainly. It’s also notoriously opaque, which makes it especially hard to know that so-and-so is wasting their time. How about “I don’t like Haskell and/or OCaml because X, I recommend Lisp instead because Y” as an alternative formulation? That one I’d be interested to read!
Traubenfuchs 4y ago
> all mainstream languages have eager evaluation models That is incorrect, e.g. Java Streams (Javas built in library for functional processing of data) are lazy, which can surprise beginners. You say it's just an std lib and not a lazy programming language? Ok, the much older (but just as lazy) C# linq is directly integrated in the C# language, making the C# language both eager and lazy by default, depending on which parts you use.
- ufo 4y ago
  Arguably Java streams aren't really lazy evaluation at the language level, because the programmer must use explicit lambdas around the lazy bits. Java itself is still eager.
userbinator 4y ago
The phrase "space leak" seemed unusual and a bit of a "tortured phrase", since I'm more familiar with this concept as "memory bloat" or just inefficiency in general. Upon a little more searching it appears to be mainly Haskell jargon.
- assbuttbuttass 4y ago
  It's the equivalent of "memory leak" for a garbage-collected language
pie_flavor 4y ago
> For now, this has nothing to do with lazy evaluation. Such implementation will be slow in every language. It happens because add doesn’t use tail-call recursion. This is why I'll never really trust Haskell to be usable in a serious context. Haskellers will talk your ear off about how such restricted abstractions enable the compiler to optimize it to hell and back, and perfectly idiomatic Haskell can be compiled to almost-perfect machine code, but in point of fact GHC basically never does, and you still have to care about things like tail calls and design APIs to do things like continuation passing.

56 points by ghuntley 4y ago

Wait, the first suggested fix for "lazy evaluation consumes too much memory" is "make it eager"? I'm sure I'm missing some nuance here, but that seems backwards.

Arnt 4y ago
Lazily evaluating 2+2 requires storing two numbers and an operator for a while, eagerly evaluating requires storing just one number (4, the result). This can be a real problem, for example if you read potentially large network input eagerly and use it to compute a small result lazily. IMO it's always a mistake and IMNSHO the proper solution is always something more nuanced than just "make it eager" or "make it properly lazy".
mrkeen 4y ago
In all languages, sometimes you want eager evaluation and sometimes you want lazy evaluation. If things are lazy by default, you simply need to put a "!" before the term to evaluate in order to get eagerness. If things are eager by default, you need to rewrite the algorithm as a streaming algorithm.
- cvoss 4y ago
  There's no inherent reason why doing lazy evaluation in an eager-by-default language should be any harder than the reverse. I can imagine a language that is eager by default but has a '#' operator that holds expressions in unevaluated form until terms are requested.
  - ParetoOptimal 4y ago
    > There's no inherent reason why doing lazy evaluation in an eager-by-default language should be any harder than the reverse. lazy by default enables better composition and local reasoning. https://publish.obsidian.md/paretooptimaldev/Advantages+of+lazy+evaluation https://publish.obsidian.md/paretooptimaldev/Advantages+of+l...
  - shirogane86x 4y ago
    Sadly even though what you say is true, I do not know of any languages that get that right. Even those that do care enough to give you a way to make lazy values, they require you to explicitly wrap them and force them all over the place, making lazy programming effectively so noisy it's unusable. Which is the main reason why I still find myself coming back to haskell (stuff like parser combinators is just so unwieldy without laziness and do notation...)
    - MauranKilom 4y ago
      Counterpoint: C++ expression templates have existed for a long time, and require no explicit work on the user side. They are incredibly unwieldy to write and debug though.
      - shirogane86x 4y ago
        I am gonna be completely honest, I have never quite been able to understand expression templates properly. is it possible to use them to get hassle-free laziness? is there any example of a library that does this (just to look at it and see how it's done)?
        MauranKilom 4y ago
        Define hassle-free. In readability of user code? Yes. In getting clean compiler errors? No. One example would be Eigen: https://eigen.tuxfamily.org/index.php?title=Main_Page https://eigen.tuxfamily.org/index.php?title=Main_Page See also their page on lazy evaluation: https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html Of course, C++ is powerful enough that using specific tools can make the expression template abstraction fall apart (e.g. auto), but fundamentally you can write matrix code very cleanly and get great lazy-evaluated performance.
  - Quekid5 4y ago
    While you're technically right, it's only in the same sense that any TC language can do anything any other TC language can -- you can theoretically always delay any computation behind a lambda, but the ergonomics have wide-ranging consequences. You also don't get any memoization that way -- without further runtime support. There was a good Reddit thread recently where a lot of experts weighed in: https://www.reddit.com/r/haskell/comments/wpbs4z/what_things_would_be_awkward_to_do_in_a/ikhtng3/ https://www.reddit.com/r/haskell/comments/wpbs4z/what_things... I recommend reading the thread -- lot's of great stuff in there, but... TL;DR: It's a lot more complicated than it seems at first and it's far from obvious that strict-by-default is worth the cost.
  - chas 4y ago
    The combination of lazy evaluation and state mutation/side effects can be pretty difficult to reason about. For example, if you have a function that changes a global variable as a part of a lazy computation, once that function could have been called you have no way of knowing if or when that global variable will change in the future. If you have other functions that depend on the value of that variable, their future behavior is now much more challenging to reason about than in a strict language. You can also imagine something akin to a race condition in which there are multiple lazy computations which could eventually set that variable to different values and the actual sequence of state transitions depends entirely on the dependency order of a possibly unrelated piece of code. In practice, this means that in languages that are strict by default, lazy computations are often forced to run in order to reason about the code, rather than because the actual results of the computation are required. Since pure functions compute the same results under lazy or strict evaluation and require that any data dependencies they have are explicitly provided as inputs, they interact with lazy computations in a much more tractable way. This means that adding a strictness operator to a lazy language is much easier than adding a laziness operator a a strict language. An alternate approach is what python did with generators where there is a data type for lazy computation, but it lives apart from the rest of the language, so it is mostly used for e.g. stream processing where a default-lazy approach is conceptually straightforward and is less likely to lead to extremely non-trivial control flow. This approach does, however, basically give up on having a laziness operator that will turn a strict computation into a lazy one.
- Joker_vD 4y ago
  > you simply need to put a "!" before the term to evaluate in order to get eagerness That's wrong. With the bang pattern, evaluation only goes up to WHNF, not the whole way — it's just a syntax sugar around "seq" which has been around since always. If you need to fully evaluate the term, look at the deepseq package: it's implementation is non-trivial.
Joker_vD 4y ago
Yes. Which is my main criticism of Haskell: sure, sometimes laziness is very handy, sometimes it's even indispensable... but most of the time, eager is what you want, with judicious sprinkles of explicitly lazy structures (btw, OCaml has "lazy" keyword exactly for that). Sure, GHC goes to heroic lengths and turns as much lazy computations as it can into eager ones, but there is always a limit to what it can do on its own, and you inevitably end with the programmer having to slap strict patterns and seqs and deepseqs wherever they can reach.
- Quekid5 4y ago
  In OCaml lazy data is fundamentally incompatible with strict data -- you have to explicitly evaluate it, e.g. when passing to a function which takes strict data. This means you end up with two disjoint 'worlds' where you need to write algorithms twice, etc. (In fact you'd have to do that for every possible variant of where exactly the laziness lies.) The ergonomics become incredibly bad, unfortunately. (Also see my link to a Reddit thread elsewhere in this thread further ideas on why strict-by-default is not a simple win.)
  - Joker_vD 4y ago
    The same split exists in Haskell as well: Data.Text.Text vs Data.Text.Lazy.Text, etc. And in LISP IIRC lazy data are type-compatible with strict data.
    - Quekid5 4y ago
      Yes, it's true, and the split is also painful in Haskell. The split exists in Haskell for a choice few data structures where it truly matters for performance -- it also exists for Set/Map. (And I'd argue it is actually a bad thing from a purely language perspective, but sometimes practicality does win out, even in Haskell.) I think it might actually have been a mistake to have the lazy variants of these data structures, esp. Text/ByteString. IME it's extremely rare to want laziness for these... and it's usually just when building output strings (where there are better solutions like Builders). Anyway, I digress... IME the same applies to lazy Map/Set, but I'm less familiar with uses for the lazy versions of these. (IIRC they're only spine-lazy, which is rarely what you want, tho.) > And in LISP IIRC lazy data are type-compatible with strict data. LISP is dynamically typed -- it's trivial to do there. Also not the directionality: You can go from lazy to strict (that's just evaluation which the runtime will do for you), but you can NOT go the other way automatically. Recovering laziness from strictness is impossible. The problem with the split happens when you have mismatching types that your compiler will shout at you for.

eptcyka 4y ago

> Fortunately, this is easily possible with Haskell. You need to enable the BangPatterns feature and use exclamations ! in front of patterns for variables where you want the evaluation to be performed eagerly. Of course, this is simple - you just enable a language extension so that the language you are referring to Haskell is no longer really Haskell. I think Haskell is a fine language, but given the amount of various language extensions that are needed for it to be usable in production without friction, it seems it will forever be a research language - and there is nothing wrong with that.

ParetoOptimal 4y ago
> I think Haskell is a fine language, but given the amount of various language extensions that are needed for it to be usable in production without friction, it seems it will forever be a research language - and there is nothing wrong with that. This isn't really a problem in the real world, only in theory.
nequo 4y ago
It is Haskell, just not Haskell2010. It is included in GHC2021. Would you say that a company that uses a subset of C++ as a policy is not using C++? Their definition of the subset is as arbitrary as another’s that uses BangPatterns.
- eptcyka 4y ago
  Sure, this language feature is mainstream now. But most real-world haskell codbases vary greatly in which language extensions they've chosen to use.
  - kzrdude 4y ago
    Is this a C++ benefit, that the competing implementations GCC and LLVM give each other's extensions to the language more legitimacy by having a second implementation? It doesn't seem like language extensions get so much attention in C++ codebases (but maybe I'm mistaken)?

skywhopper 4y ago

I have tried and failed to comprehend Haskell for my own uses. Certainly most of the examples in this article are meaningless gibberish to my smooth, practical brain. So kudos to those who grok the underlying math and find it a useful language. That said, I am a fan of lazy evaluation in the right circumstances, and often find myself implementing lazy data structures (particularly in my Ruby programs). Ultimately, though, I’m confused by this article which seems to be all about removing laziness from Haskell in ways that seem entirely counter to what I take to be its purpose. If you have to bend over backwards and rewrite your code in awkward ways to get the language to behave the way you want, maybe the project itself isn’t right for the language? It’s one thing to hack around a couple of isolated space issues in a larger context, but if you are enabling language extensions across the board by default to prefer eager evaluation, why are you using Haskell at all?

ParetoOptimal 4y ago
> Certainly most of the examples in this article are meaningless gibberish to my smooth, practical brain My smooth practical brain struggles in languages that aren't Haskell.
daniel-cussen 4y ago
I've never heard of or met a circumstance that actually warranted Haskell. Not even in finance, those guys are totally wasting their time. It's an attractive (I'm going to say "it seems" though you ought to take that for granted) intellectual rathole. Like some forms of philosophy, like many things. Thank GOD (despite being unbelieving at the time) I went with Lisp instead. And I got real speedups.
- ParetoOptimal 4y ago
  > I've never heard of or met a circumstance that actually warranted Haskell. Sounds like you are biased to conclude it has no purpose to begin with.
- benreesman 4y ago
  Algorithmic finance might be the most ruthlessly Darwinian area of industrial software, it’s way up there certainly. It’s also notoriously opaque, which makes it especially hard to know that so-and-so is wasting their time. How about “I don’t like Haskell and/or OCaml because X, I recommend Lisp instead because Y” as an alternative formulation? That one I’d be interested to read!

Traubenfuchs 4y ago

> all mainstream languages have eager evaluation models That is incorrect, e.g. Java Streams (Javas built in library for functional processing of data) are lazy, which can surprise beginners. You say it's just an std lib and not a lazy programming language? Ok, the much older (but just as lazy) C# linq is directly integrated in the C# language, making the C# language both eager and lazy by default, depending on which parts you use.

ufo 4y ago
Arguably Java streams aren't really lazy evaluation at the language level, because the programmer must use explicit lambdas around the lazy bits. Java itself is still eager.

userbinator 4y ago

The phrase "space leak" seemed unusual and a bit of a "tortured phrase", since I'm more familiar with this concept as "memory bloat" or just inefficiency in general. Upon a little more searching it appears to be mainly Haskell jargon.

assbuttbuttass 4y ago
It's the equivalent of "memory leak" for a garbage-collected language

pie_flavor 4y ago

> For now, this has nothing to do with lazy evaluation. Such implementation will be slow in every language. It happens because add doesn’t use tail-call recursion. This is why I'll never really trust Haskell to be usable in a serious context. Haskellers will talk your ear off about how such restricted abstractions enable the compiler to optimize it to hell and back, and perfectly idiomatic Haskell can be compiled to almost-perfect machine code, but in point of fact GHC basically never does, and you still have to care about things like tail calls and design APIs to do things like continuation passing.