6 ms·

This is very cool research that I’ve been loosely following for a while but I feel the benchmarks you’ve presented are very misleading. They are comparing paral

This is very cool research that I’ve been loosely following for a while but I feel the benchmarks you’ve presented are very misleading. They are comparing parallelized code to sequential code and then making a big deal that it’s faster. Of course, you could also write a parallel Haskell version of the same benchmarks in about the same amount of code, and I’d expect similar speedups. Haskell doesn’t parallelize every independent expression because it’s a general purpose language and that’s unlikely to be the correct choice in all contexts. I don’t have much of an intuition for whether the optimal evaluation stuff will be useful in practice for the kinds of programs people actually write. Like I get that it helps a lot if you’re doing multiplication with Church numerals… but can you give some more compelling examples?

LightMachine 5y ago
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.

LightMachine 5y ago

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.