Hacker News Reader

If you're interested in collecting a more diverse set of benchmarks, Stephanie Weirich presented her work [1] at the recent WITS workshop [2] comparing the efficiency of different reduction strategies in the untyped λ-calculus across a dataset of natural and synthetic terms. I would be curious to see how your implementation compares.

[1]: https://github.com/sweirich/lambda-n-ways

[2]: https://popl22.sigplan.org/home/wits-2022

> My reasoning was to just benchmark identical programs.

I would just report the results of a parallel Haskell program as well, and let people decide what programs they think are comparable. I don’t really think you come off well making the speed claims you do since many people who bother to dig in will conclude you are comparing apples to oranges.

> After all, it just returns the same result, faster.

That is not always true. There’s some overhead to introducing parallelization so it’s not always worth it unless you have a big enough chunk of work.

But the other reason fine grained parallelism isn’t often worth it even if it can provide a speedup for a single computation: you have other concurrent things going on, and plenty of potential parallelism from that. Think of a web server responding to many concurrent requests. In this situation, your program could easily have worse performance by injecting parallelism within each connection. Imagine we have k cores and k concurrent connections - we would likely be better off just giving each connection one core rather than having them all thrashing each other to use all the cores.

> Don't you find it compelling to write binary addition as "increment N times" and have it be as efficient as the add-with-carry operation?

It’s very cool in a “wow that’s neat” kind of way, but, well we already have machine ints that are even faster. :) I feel you need better examples to be compelling - people just don’t care very much about optimizing Peano arithmetic. If those speedups generalize to things people do care more about then you should show that and then people can be impressed! It sounds like you do have some ideas for examples, and I think your point about getting deforestation “for free” is cool… but, show us!

My other question - it seems like this approach requires giving up on separate compilation? Like you can’t compile a function in isolation, since it will do completely different things when composed with other functions? Or am I misunderstanding?

I wonder if there's been attempts at solving "when is auto-parallelization worth it" with profile feedback?

> That is not always true. There’s some overhead to introducing parallelization so it’s not always worth it unless you have a big enough chunk of work.

This isn't fine-grained parallelism though! As I said, HVM spawns threads on to-be-evaluated redexes closes to the root of the program's normal form. So, either there is a significant speedup, or the program is sequential (or too small), and there is no speedup, but the overhead is minuscule, since a bounded, small amount of spawn() occurs. To be clear: there is no situation where HVM's parallelism will make the program significantly slower, which *does* happen if you use too many sparks on Haskell. That will never happen on HVM.

> But the other reason fine grained parallelism isn’t often worth it even if it can provide a speedup for a single computation:

Yep that's definitely a good reason. Thanks for sharing. (You can just run HVM in a single thread, though.)

> It’s very cool in a “wow that’s neat” kind of way, but, well we already have machine ints that are even faster

I couldn't disagree more. Just because I used integers as an example, which happens to be optimized, it means an entire optimization technique isn't interesting? This applies to every data structure that can be defined algebraically.

> My other question - it seems like this approach requires giving up on separate compilation?

Compiling a function in isolation is fine, why wouldn't it be? Not sure I get it.

> You can just run HVM in a single thread, though.

How easy would it be to share data structures between different threads? Say I have a large binary tree in one thread, can I send it to another thread without much cost? How about lambdas?

That isn't how it works. HVM threads work transparently, you don't need to think about them. The same data structure *can* be visible to multiple threads under some conditions, through cloning; for example, consider the following program:

    (Sum Nil        )  = 0
    (Sum (Cons x xs))  = (+ x (Sum xs))
    (Head (Cons x xs)) = x

    (Main x) =
      let xs = (Cons 1 (Cons 2 (Cons 3 Nil)))
      (Pair (Sum xs) (Head xs))

The result of this program is `(Pair 6 1)`. Since `Pair` is the topmost (root) node of the normal form, each of its elements will be computed in a separate thread. Because of that, the same `[1,2,3]` list will be accessed by each thread. But that's not actually a shared reference, because values only exist in one place; instead, the lazy cloner makes copies of the list, layer-by-layer, and sends these copies to the thread that will handle them.

Note that if the same expression was written in a deeper position of the normal form, it would be evaluated sequentially. This is what avoids the fine-grained parallelism issue. It also means that in many cases HVM will not be as parallel as it could, though! But when the parallelism kicks in, it is always productive.

Ok. I'd be interested in the following benchmark: A program that reads in a large map of key-value pairs; it then reads in a list of keys, and produces a list of values (order of the output is not important). The map can be modeled by e.g. a red/black tree.

I'd be interested in the performance in Haskell, if it was implemented using a number of worker threads (each with their own reference to the map), versus the best implementation you can think of in HVM.

Looks good. I'll keep that in mind and let you know if we write such a benchmark. Opening an issue would be helpful to remind us!

I think I very much agree with your points and approach to parallelism.

> This applies to every data structure that can be defined algebraically.

Is this a mutually true? I’d expect this to hold for inductive algebraic data types but not co-inductive types?

> As I said, HVM spawns threads on to-be-evaluated redexes closes to the root of the program's normal form. So, either there is a significant speedup, or the program is sequential (or too small), and there is no speedup, but the overhead is minuscule, since a bounded, small amount of spawn() occurs.

To me that sounds like overhead. Rather than just computing 1 + 1 as a single assembly language instruction you’re sending the 1 + 1 expression tree to a thread’s work queue or something? If I’m misunderstanding can you clarify?

> Compiling a function in isolation is fine, why wouldn't it be? Not sure I get it.

It seems like optimal evaluation is a whole program optimization - you need the whole program available in order to do it, you can’t just compile one function to assembly language in isolation, and then link that against other precompiled functions. Do I have the wrong idea here?

> Just because I used integers as an example, which happens to be optimized, it means an entire optimization technique isn't interesting? This applies to every data structure that can be defined algebraically.

I do think it sounds cool as I said, but I want to see it on an example I care about, not Peano arithmetic. Especially since deforestation is already an optimization that is used by languages that don’t do optimal evaluation. So I want to see how HVM does it better, if that’s the case. And not just you telling me how it’s theoretically better. :)

Lastly, a while ago I remember you mentioning that you couldn’t compile arbitrary lambda calculus terms. Is that still the case and if so can you better describe what can’t be compiled?

> if `fib(42)` is the topmost node of your program's normal form, you always want to parallelize its branches (`fib(41)` and `fib(40)`)

How does that make things more efficient? Naively, it seems like the fib(40) and fib(41) threads are going to do almost exactly the same computation, assuming they're also defined recursively.

It's neat when code that looks wildly inefficient goes fast anyway, but might that mean minor changes can have unpredictable effects on performance? We see that a fair bit with JavaScript, where there is a happy path for performance but you can fall off if it with apparently minor changes.

Perhaps, with more experience, the performance of programa targeting HVM will be predictable, but I suspect it will mean a lot of relearning intuitions about what makes programs slow?

Do Haskell programmers have good intuition about performance? It seems like laziness would make it hard?

> Do Haskell programmers have good intuition about performance? It seems like laziness would make it hard?

It’s very hard. I’ve found most experienced Haskell devs still get it wrong at times. It’s one of the things that makes me think that we need to rethink the overall approach to laziness

> Do Haskell programmers have good intuition about performance? It seems like laziness would make it hard?

Laziness in data structures usually gives you good enough performance in most cases, but harder to make sure it's consistent and reason about when you need to adjust it. For common operations with an average requirement of performance, laziness seems to give the developer an easier chance of good performance, with the higher possibility to screw it up if the requirement is really strict.

> Do Haskell programmers have good intuition about performance? It seems like laziness would make it hard?

The solution is to just not use laziness when you don't need it, then reasoning about Haskell performance is the same as in any other language.

http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr...

I vaguely recall reading in https://www.amazon.com/Parallel-Concurrent-Programming-Haske... that there was research done into this in ghc but it wasn’t possible to generalize the behavior so that there weren’t situations which were very bad. I’ll look for it soon, see if I can find it

I’d love to see this as well.