6 ms·

I didn't want to be misleading, sorry. My reasoning was to just benchmark identical programs. I personally think Haskell's approach to parallelism is wrong, th

I didn't want to be misleading, sorry. My reasoning was to just benchmark identical programs. I personally think Haskell's approach to parallelism is wrong, though, since it demands in-code annotations to work. The problem is that the decision on whether an expression should be parallelized doesn't depend on the code itself, but on where the expression is used. For example, 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)`), but if it is called in a deeply nested list node, you don't. That information isn't available on the code of `fib`, so placing "spark" annotations seems conceptually wrong. HVM parallelizes by distributing to-be-evaluated redexes of the normal form among available cores, prioritizing these close to root. Here is an animation: https://imgur.com/a/8NtnEa3 https://imgur.com/a/8NtnEa3. That always seems like the right choice to me. After all, it just returns the same result, faster. I could be wrong, though. In which case you think parallelism isn't the correct choice? Is it because you don't always want to use the entire CPU? Would love to hear your reasoning. > Like I get that it helps a lot if you’re doing multiplication with Church numerals… This isn't about multiplication with Church numerals. 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? Making mathematically elegant code fast matters, and HVM does that. See the overview [0] for instance. Also, this allows us to have all the "deforestation" optimizations that Haskell applies on List with hardcoded #rewrite pragmas, for any user-defined datatype, which is also quite useful. There are certainly many uses that I'm not creative enough to think of. [0] https://github.com/Kindelia/HVM/blob/master/HOW.md#bonus-abusing-beta-optimality https://github.com/Kindelia/HVM/blob/master/HOW.md#bonus-abu...

pchiusano 5y ago
> 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?
- fulafel 5y ago
  I wonder if there's been attempts at solving "when is auto-parallelization worth it" with profile feedback?
- LightMachine 5y ago
  > 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.
  - pchiusano 5y ago
    > 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?
bmc7505 5y ago
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 https://github.com/sweirich/lambda-n-ways [2]: https://popl22.sigplan.org/home/wits-2022 https://popl22.sigplan.org/home/wits-2022
AlexCoventry 5y ago
> 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.
skybrian 5y ago
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?
- tome 5y ago
  > 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-unrepresentable/ http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr...
- JoelMcCracken 5y ago
  > 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
- capableweb 5y ago
  > 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.
JoelMcCracken 5y ago
I vaguely recall reading in https://www.amazon.com/Parallel-Concurrent-Programming-Haskell-Multithreaded/dp/1449335942 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
- pchiusano 5y ago
  I’d love to see this as well.

pchiusano 5y ago

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

fulafel 5y ago
I wonder if there's been attempts at solving "when is auto-parallelization worth it" with profile feedback?
LightMachine 5y ago
> 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.
- pchiusano 5y ago
  > 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?

bmc7505 5y ago

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 https://github.com/sweirich/lambda-n-ways [2]: https://popl22.sigplan.org/home/wits-2022 https://popl22.sigplan.org/home/wits-2022

AlexCoventry 5y ago

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

skybrian 5y ago

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?

tome 5y ago
> 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-unrepresentable/ http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr...
JoelMcCracken 5y ago
> 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
capableweb 5y ago
> 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.

JoelMcCracken 5y ago

I vaguely recall reading in https://www.amazon.com/Parallel-Concurrent-Programming-Haskell-Multithreaded/dp/1449335942 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

pchiusano 5y ago
I’d love to see this as well.