Hacker News Reader

Comment by harpocrates | Hacker News Reader

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.

View on HN

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.

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.

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.

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.

Under some workloads, GC pauses are definitely the primary bottleneck: http://stackoverflow.com/questions/36772017/reducing-garbage...

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.

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.

> So I don't see why Haskell's additional allocations should cause GC to be any more of an overhead.

In this kind of garbage collector, time of an individual garbage collection should not depend on the amount of garbage that has been generated. However, producing more garbage should mean more frequent collections, and so more time spent in GC overall.

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

Entertainingly, you can't create a cyclic data structure with 100% pure code.

You can in a lazy language, like Haskell.

That's interesting, how do you achieve that?

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...

There's even a purely functional graph library, allowing cycles: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl01...

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

    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.

The defintion of 'something' uses it twice.

Laziness gives pure semantics to a certain form of mutation. Technically you don't represent cycles but instead the infinite unfolding of that cycling structure... but you do so in a way where the compiler just makes the cycle. In pure code these two situations are indistinguishable.

I imagine that given linear arrows you could write something like Rust's Rc/Arc?

Rust uses something resembling linear heaps.

Rust has affine types. Linear = exactly once, affine = at most once.

Quite so

Reply on news.ycombinator.com