7 ms·

This is a big deal. Right now, Haskell (like most GC-ed languages) has one big heap that gets GC-ed regularly. The _only_ time memory is reclaimed is when the G

This is a big deal. Right now, Haskell (like most GC-ed languages) has one big heap that gets GC-ed regularly. The _only_ time memory is reclaimed is when the GC runs. By retrofitting Haskell with linear types, there would be another linear heap. In that heap, there is no GC - resources get freed as soon as the linearly typed value is used. On can imagine programs properly annotated with linear types that don't even need ANY GC. This is an even bigger deal in Haskell than in most other languages because Haskell, being immutable, performs a ton of allocations. Want to update a field? Nope, but you can allocate the whole object again with just that field changed. If most of that work could be moved to a linear heap which doesn't need GC... well you get the point.

charlieflowers 10y ago
Doesn't Haskell use persistent data structures? If so, doesn't that directly compensate for the problem you mention? Though it is still true that a purely functional language will need to allocate more than a typical imperative language.
- harpocrates 10y ago
  That does help, yes. For example, inserting into a tree only takes a logarithmic number of allocations because of the fact the subtrees are persistent. That said with every insertion/deletion into that same tree, there is still at least log(n) garbage produced, which currently has to be handled by the GC. Linear types would let us free that garbage up as soon as it is produced and without GC pauses.
chombier 10y ago
If I am not mistaken you will always need a GC for cyclic data structures, which you can't type linearly.
- moomin 10y ago
  Entertainingly, you can't create a cyclic data structure with 100% pure code.
  - taejo 10y ago
    You can in a lazy language, like Haskell.
    - moomin 10y ago
      That's interesting, how do you achieve that?
      - merijnv 10y ago
        Well, one of the usual examples would be: let ones = 1 : ones in ones Here ':' is the cons operator, prepending something to a list, so here you defines 'ones' to be '1' followed by 'ones', which in (GHC) Haskell, compiles down to a datatype that has a pointer to the list element ('1') and the tail ('ones', i.e. itself). EDIT: I realised I forgot to say what it actually does, in case that's not obvious. It's an infinite list of, well, ones...
      - unhammer 10y ago
        There's even a purely functional graph library, allowing cycles: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl01...
        pdexter 10y ago
        It's not a 'cyclic data structure' though. It allows cycles in that every node has an ID and you can freely point to nodes to create cycles. For a cyclic graph with true cycles see https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf
      - runeks 10y ago
        repeat :: a -> [a] repeat something = [something] ++ repeat something print (head (repeat "hello")) For performance reasons, you wouldn't implement it exactly like this, but the principle is the same. The list can contain an infinite number of elements, but not unless some function tries to consume all elements does it become a problem.
- tel 10y ago
  I imagine that given linear arrows you could write something like Rust's Rc/Arc?
chalst 10y ago
Rust uses something resembling linear heaps.
- mafribe 10y ago
  Rust has affine types. Linear = exactly once, affine = at most once.
  - chalst 10y ago
    Quite so
theseoafs 10y ago
I have not seen any evidence that GC is the primary bottleneck in Haskell, or that a form of compiler-driven manual memory management would be faster.
- runeks 10y ago
  Under some workloads, GC pauses are definitely the primary bottleneck: http://stackoverflow.com/questions/36772017/reducing-garbage-collection-pause-time-in-a-haskell-program http://stackoverflow.com/questions/36772017/reducing-garbage...
- tupshin 10y ago
  GC has non-zero overhead compared with linearly typed de-allocations, but that's not the main point. The title mentions predictability, and one of the big blockers to using almost any GC-ed language is the lack of predictability about runtime latency, which is very different than throughput, which I generally associate with the term bottleneck. Additionally, predictable performance is about what the programmer can predict (whether you are talking about throughput or latency), and the argument is that linear types make it much easier to reason about the performance of a system, hence making it more predictable.
  - jholman 10y ago
    IANA expert, but as far as I can tell... 1) When it comes to sources of unpredictability, laziness is a way bigger problem than garbage collection 2) Assuming that by "GC" we mean "some variation on mark-and-sweep" (rather than meaning "any type of automatic memory management", which I hope is not the usage of anyone in this conversation), GC cost (in terms of CPU-time consumed) doesn't care how many allocations you've done, nor how much garbage it needs to collect. All it cares about is the size of the working set at the time that it runs. As such, all those lingering copies of the old tree nodes (etc, etc) are irrelevant. So I don't see why Haskell's additional allocations should cause GC to be any more of an overhead.
    - dllthomas 10y ago
dllthomas 10y ago
You're right that reducing pause times is made more practical here and this is a part of why people excited (and rightly so). That said, it's worth noting that a naïve attempt to free resources ASAP can be a performance hit and sometimes mean long pauses. For instance if you find yourself no longer needing a large tree, the regular GC lets you just forget about it. Freeing the whole tree would be walking the whole tree, and the naïve approach does that synchronously. Of course there are ways around that - they add some complexity, this kind of tooling will help get them right when they're needed. All in all, performance is complicated, there are usually tradeoffs, and this seems some great tooling.

charlieflowers 10y ago

Doesn't Haskell use persistent data structures? If so, doesn't that directly compensate for the problem you mention? Though it is still true that a purely functional language will need to allocate more than a typical imperative language.

harpocrates 10y ago
That does help, yes. For example, inserting into a tree only takes a logarithmic number of allocations because of the fact the subtrees are persistent. That said with every insertion/deletion into that same tree, there is still at least log(n) garbage produced, which currently has to be handled by the GC. Linear types would let us free that garbage up as soon as it is produced and without GC pauses.

chombier 10y ago

If I am not mistaken you will always need a GC for cyclic data structures, which you can't type linearly.

moomin 10y ago
Entertainingly, you can't create a cyclic data structure with 100% pure code.
- taejo 10y ago
  You can in a lazy language, like Haskell.
  - moomin 10y ago
    That's interesting, how do you achieve that?
    - merijnv 10y ago
      Well, one of the usual examples would be: let ones = 1 : ones in ones Here ':' is the cons operator, prepending something to a list, so here you defines 'ones' to be '1' followed by 'ones', which in (GHC) Haskell, compiles down to a datatype that has a pointer to the list element ('1') and the tail ('ones', i.e. itself). EDIT: I realised I forgot to say what it actually does, in case that's not obvious. It's an infinite list of, well, ones...
    - unhammer 10y ago
      There's even a purely functional graph library, allowing cycles: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl01...
      - pdexter 10y ago
        It's not a 'cyclic data structure' though. It allows cycles in that every node has an ID and you can freely point to nodes to create cycles. For a cyclic graph with true cycles see https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf
    - runeks 10y ago
      repeat :: a -> [a] repeat something = [something] ++ repeat something print (head (repeat "hello")) For performance reasons, you wouldn't implement it exactly like this, but the principle is the same. The list can contain an infinite number of elements, but not unless some function tries to consume all elements does it become a problem.
tel 10y ago
I imagine that given linear arrows you could write something like Rust's Rc/Arc?

chalst 10y ago

Rust uses something resembling linear heaps.

mafribe 10y ago
Rust has affine types. Linear = exactly once, affine = at most once.
- chalst 10y ago
  Quite so

theseoafs 10y ago

I have not seen any evidence that GC is the primary bottleneck in Haskell, or that a form of compiler-driven manual memory management would be faster.

runeks 10y ago
Under some workloads, GC pauses are definitely the primary bottleneck: http://stackoverflow.com/questions/36772017/reducing-garbage-collection-pause-time-in-a-haskell-program http://stackoverflow.com/questions/36772017/reducing-garbage...
tupshin 10y ago
GC has non-zero overhead compared with linearly typed de-allocations, but that's not the main point. The title mentions predictability, and one of the big blockers to using almost any GC-ed language is the lack of predictability about runtime latency, which is very different than throughput, which I generally associate with the term bottleneck. Additionally, predictable performance is about what the programmer can predict (whether you are talking about throughput or latency), and the argument is that linear types make it much easier to reason about the performance of a system, hence making it more predictable.
- jholman 10y ago
  IANA expert, but as far as I can tell... 1) When it comes to sources of unpredictability, laziness is a way bigger problem than garbage collection 2) Assuming that by "GC" we mean "some variation on mark-and-sweep" (rather than meaning "any type of automatic memory management", which I hope is not the usage of anyone in this conversation), GC cost (in terms of CPU-time consumed) doesn't care how many allocations you've done, nor how much garbage it needs to collect. All it cares about is the size of the working set at the time that it runs. As such, all those lingering copies of the old tree nodes (etc, etc) are irrelevant. So I don't see why Haskell's additional allocations should cause GC to be any more of an overhead.
  - dllthomas 10y ago

dllthomas 10y ago

You're right that reducing pause times is made more practical here and this is a part of why people excited (and rightly so). That said, it's worth noting that a naïve attempt to free resources ASAP can be a performance hit and sometimes mean long pauses. For instance if you find yourself no longer needing a large tree, the regular GC lets you just forget about it. Freeing the whole tree would be walking the whole tree, and the naïve approach does that synchronously. Of course there are ways around that - they add some complexity, this kind of tooling will help get them right when they're needed. All in all, performance is complicated, there are usually tradeoffs, and this seems some great tooling.