7 ms·

Author here. HVM is the ultimate conclusion to years of optimal evaluation research. I've been a great enthusiast of optimal runtimes. Until now, though, my mo

Author here. HVM is the ultimate conclusion to years of optimal evaluation research. I've been a great enthusiast of optimal runtimes. Until now, though, my most efficient implementation had barely passed 50 million rewrites per second. It did beat GHC in cases where optimality helped, like λ-encoded arithmetic, but in more real-world scenarios, it was still far behind. Thanks to a recent memory layout breakthrough, though, we managed to reach a peak performance of 2.5 billion rewrites per second, on the same machine. That's a ridiculous 50x improvement. That is enough for it to enjoy roughly the same performance of GHC in normal programs, and even outperform it when automatic parallelism kicks in, if that counts! Of course, there are still cases where it will perform worse (by 2x at most usually, and some weird quadratic cases that should be fixed [see issues]), but remember it is a 1-month prototype versus the largest lazy functional compiler in the market. I'm confident HVM's current design is able to scale and become the fastest functional runtime in the world, because I believe the optimal algorithm is inherently superior. I'm looking for partners! Check the notes at the end of the repository's README if you want to get involved.

auggierose 5y ago
And another question, is this for purely functional code only, or does it / could it also apply to mutable data structures. In particular, is it somehow related to copy-on-write techniques (like for example used for Swift's data structures), or is this something entirely different?
- herbstein 5y ago
  Based on my understanding on the HOW.md text this relies heavily on mathematical equality for performance. In its execution it is essentially constantly inlining operations as it goes.
- LightMachine 5y ago
  Since HVM is linear, adding some mutability would be completely fine and would NOT break referential transparency (because values only exist in one place!). So, we could actually have "pure mutable arrays". In order to make that mix up well with lazy cloning, though, we'd need to limit the size of array to about 16. But larger arrays could be made as trees of mutable 16-tuples. There was a post about it, but I can't find it right now.
  - auggierose 5y ago
    That makes sense to me; I am currently implementing a package with mutable data structures with shallow constant time cloning (via copy-on-write) for TypeScript, and the dup idea somehow seems to be compatible with that.
  - lcedp 5y ago
    But wouldn't it make mutability only useful in local scopes? ``` fn f(x) { *x = 42 // lazily cloning on write }; let x = 1; f(x); // x still equals 1 here ```
conaclos 5y ago
The How page [0] is nicely written! It was a real pleasure to read :) [0] https://github.com/Kindelia/HVM/blob/master/HOW.md https://github.com/Kindelia/HVM/blob/master/HOW.md
omginternets 5y ago
If I were serious about porting this project to Go, where would you recommend that I start?
- LightMachine 5y ago
  You mean, the whole project? Or just the runtime? The runtime has recently been ported to go by Caue F. He posted it in our Telegram: https://pastebin.com/0X0bbW8b https://pastebin.com/0X0bbW8b Perhaps you could team up?
  - omginternets 5y ago
    Oh my lord, this is seriously the best news of the last decade. You, sir -- along with Caue F. -- have just made my decade!! EDIT: is there a license for this? Can I use it?
    - LightMachine 5y ago
      This is MIT licensed, so feel free to fork, use, edit and sell it without even notifying me. Now go ahead and get rich!
      - omginternets 5y ago
        I'll get right on that. :) In all seriousness, thank you. I have exactly zero experience with Rust, but if I can help with anything, feel free to reach out: @lthibault on GitHub. Moreover, I'll likely be spinning this off into a full-fledged repo of some sort. I'll keep you updated, and am more than happy to coordinate our efforts. Thanks again, and congratulations on this incredible piece of engineering!
        cauefcr 5y ago
        Hey, this was my port, nice to see people interested. Yeah, it still needs a few changes on the HVM rust compiler to work, but we could figure it out together if you want. Hit me up on @Cauef on telegram, caue.fcr@gmail.com, or let's talk on the issue pages of HVM!
acchow 5y ago
This work is mindblowing me to me. Also I love the README! You did mention that you pretty much implement pages 14-39 of The Optimal Implementation of Functional Programming Languages. Any idea why the authors of the book didn't implement it themselves? Also, what lead you to this recent memory layout breakthrough. What was the journey of thinking towards this end?
- LightMachine 5y ago
  I don't think the authors are focused on engineering matters; they're researchers after all. But that's just my guess. Also, there is an obsession with covering the full λ-calculus, which the abstract algorithm doesn't. A lot of energy has been put in that. I think this is just wrong. Rust has severe limitations on how you can write lambdas. HVM has some, which seldom occur in practice. Regardless, some people did try implementing this in practice, dozens of times, including myself. It just wasn't that fast except for these cases where the asymptotics are superior. A naive implementation just stores graphs/edges on memory, but most of these edges are redundant. For example, a lambda doesn't need to point to its parent. By trying to turn the graph in a tree, I've ended up with SIC [0], which, once implemented efficiently, cut down memory and computation costs significantly. Doing so was tricky, specially because 1. the missing edges complicated the transversal; 2. some upward edges can't disappear (variables); 3. DUP nodes aren't part of expressions, they just "float", which was counter intuitive to get right. Finally, I learned to appreciate the fact that global rewrite rules are better than case-trees for recursive functions, since they greatly reduce the total rewrite count. So, in short, my journey was: 1. Learn the abstract algorithm 2. Implement it naively as a graph 3. Optimize it by making trees whenever possible 4. Favor rewrite equations over case-trees These steps lead to the design of HVM, which does fairly well in practice. [0] https://github.com/VictorTaelin/Symmetric-Interaction-Calculus https://github.com/VictorTaelin/Symmetric-Interaction-Calcul...
fulafel 5y ago
A huge improvement by improving memory layout sounds fascinating. For example the described "pointer-heavy graph to something else" sounds like a transformation class that could in some cases be made in a compiler/tooling assisted way. I wish compilers (or other automated tooling) would help more with memory layout optimization. Anyone know if there's any interesting work going on in this area in the FP world (or outside, for that matter)?
The_rationalist 5y ago
How does it compare to https://github.com/beehive-lab/TornadoVM https://github.com/beehive-lab/TornadoVM
- HelloNurse 5y ago
  > TornadoVM accelerates parts of your Java applications on heterogeneous hardware devices such as multicore CPUs, GPUs, and FPGAs. So a HVM-like interpreter could be written in Java or variants thereof (instead of Rust), in order to take advantage of TornadoVM to run efficient lazy evaluation on exotic devices.
auggierose 5y ago
JFYI, the "This book" link on https://github.com/Kindelia/HVM/blob/master/HOW.md https://github.com/Kindelia/HVM/blob/master/HOW.md goes to a research gate page which has the wrong book for download (something about category theory). So, this dup primitive, is that explained in the book as well, or is this a new addition in your implementation?
- LightMachine 5y ago
  I fixed the link. This is all part of the system described on the book, HVM is merely a very fast practical implementation. The additions (thinks like machine integers and constructors) don't affect the core.
pchiusano 5y ago
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...
toomanydoubts 5y ago
I've seen your post in /r/brasil. Nice work.
tayistay 5y ago
Could this lazy cloning be applied to an eager language like Rust? (sorry if that's a dumb question. This isn't my area of expertise)
vintermann 5y ago
This is the sort of project which causes even me to break from wasting time on HN and go actually download things and try things. In particular, a while back I came across an interesting tree-based hugenum representation in Haskell, Paul Tarau's "Hereditarily Binary Natural Numbers". It might be something (somewhat) practical that HVM can be used for right now. I'll see if I can translate it and get it to run.
deleted 5y ago
[deleted]
jevoten 5y ago
Could HVM let Haskell entirely eliminate its GC, doing away with GC pauses and enabling its use in real-time applications? That could be just as revolutionary as the beta-optimality.
- LightMachine 5y ago
  It does that! There are no GC pauses on HVM's model. Compiling Haskell to it would be neat.

auggierose 5y ago

And another question, is this for purely functional code only, or does it / could it also apply to mutable data structures. In particular, is it somehow related to copy-on-write techniques (like for example used for Swift's data structures), or is this something entirely different?

herbstein 5y ago
Based on my understanding on the HOW.md text this relies heavily on mathematical equality for performance. In its execution it is essentially constantly inlining operations as it goes.
LightMachine 5y ago
Since HVM is linear, adding some mutability would be completely fine and would NOT break referential transparency (because values only exist in one place!). So, we could actually have "pure mutable arrays". In order to make that mix up well with lazy cloning, though, we'd need to limit the size of array to about 16. But larger arrays could be made as trees of mutable 16-tuples. There was a post about it, but I can't find it right now.
- auggierose 5y ago
  That makes sense to me; I am currently implementing a package with mutable data structures with shallow constant time cloning (via copy-on-write) for TypeScript, and the dup idea somehow seems to be compatible with that.
- lcedp 5y ago
  But wouldn't it make mutability only useful in local scopes? ``` fn f(x) { *x = 42 // lazily cloning on write }; let x = 1; f(x); // x still equals 1 here ```

conaclos 5y ago

The How page [0] is nicely written! It was a real pleasure to read :) [0] https://github.com/Kindelia/HVM/blob/master/HOW.md https://github.com/Kindelia/HVM/blob/master/HOW.md

omginternets 5y ago

If I were serious about porting this project to Go, where would you recommend that I start?

LightMachine 5y ago
You mean, the whole project? Or just the runtime? The runtime has recently been ported to go by Caue F. He posted it in our Telegram: https://pastebin.com/0X0bbW8b https://pastebin.com/0X0bbW8b Perhaps you could team up?
- omginternets 5y ago
  Oh my lord, this is seriously the best news of the last decade. You, sir -- along with Caue F. -- have just made my decade!! EDIT: is there a license for this? Can I use it?
  - LightMachine 5y ago
    This is MIT licensed, so feel free to fork, use, edit and sell it without even notifying me. Now go ahead and get rich!
    - omginternets 5y ago
      I'll get right on that. :) In all seriousness, thank you. I have exactly zero experience with Rust, but if I can help with anything, feel free to reach out: @lthibault on GitHub. Moreover, I'll likely be spinning this off into a full-fledged repo of some sort. I'll keep you updated, and am more than happy to coordinate our efforts. Thanks again, and congratulations on this incredible piece of engineering!
      - cauefcr 5y ago
        Hey, this was my port, nice to see people interested. Yeah, it still needs a few changes on the HVM rust compiler to work, but we could figure it out together if you want. Hit me up on @Cauef on telegram, caue.fcr@gmail.com, or let's talk on the issue pages of HVM!

acchow 5y ago

This work is mindblowing me to me. Also I love the README! You did mention that you pretty much implement pages 14-39 of The Optimal Implementation of Functional Programming Languages. Any idea why the authors of the book didn't implement it themselves? Also, what lead you to this recent memory layout breakthrough. What was the journey of thinking towards this end?

LightMachine 5y ago
I don't think the authors are focused on engineering matters; they're researchers after all. But that's just my guess. Also, there is an obsession with covering the full λ-calculus, which the abstract algorithm doesn't. A lot of energy has been put in that. I think this is just wrong. Rust has severe limitations on how you can write lambdas. HVM has some, which seldom occur in practice. Regardless, some people did try implementing this in practice, dozens of times, including myself. It just wasn't that fast except for these cases where the asymptotics are superior. A naive implementation just stores graphs/edges on memory, but most of these edges are redundant. For example, a lambda doesn't need to point to its parent. By trying to turn the graph in a tree, I've ended up with SIC [0], which, once implemented efficiently, cut down memory and computation costs significantly. Doing so was tricky, specially because 1. the missing edges complicated the transversal; 2. some upward edges can't disappear (variables); 3. DUP nodes aren't part of expressions, they just "float", which was counter intuitive to get right. Finally, I learned to appreciate the fact that global rewrite rules are better than case-trees for recursive functions, since they greatly reduce the total rewrite count. So, in short, my journey was: 1. Learn the abstract algorithm 2. Implement it naively as a graph 3. Optimize it by making trees whenever possible 4. Favor rewrite equations over case-trees These steps lead to the design of HVM, which does fairly well in practice. [0] https://github.com/VictorTaelin/Symmetric-Interaction-Calculus https://github.com/VictorTaelin/Symmetric-Interaction-Calcul...

fulafel 5y ago

A huge improvement by improving memory layout sounds fascinating. For example the described "pointer-heavy graph to something else" sounds like a transformation class that could in some cases be made in a compiler/tooling assisted way. I wish compilers (or other automated tooling) would help more with memory layout optimization. Anyone know if there's any interesting work going on in this area in the FP world (or outside, for that matter)?

The_rationalist 5y ago

How does it compare to https://github.com/beehive-lab/TornadoVM https://github.com/beehive-lab/TornadoVM

HelloNurse 5y ago
> TornadoVM accelerates parts of your Java applications on heterogeneous hardware devices such as multicore CPUs, GPUs, and FPGAs. So a HVM-like interpreter could be written in Java or variants thereof (instead of Rust), in order to take advantage of TornadoVM to run efficient lazy evaluation on exotic devices.

auggierose 5y ago

JFYI, the "This book" link on https://github.com/Kindelia/HVM/blob/master/HOW.md https://github.com/Kindelia/HVM/blob/master/HOW.md goes to a research gate page which has the wrong book for download (something about category theory). So, this dup primitive, is that explained in the book as well, or is this a new addition in your implementation?

LightMachine 5y ago
I fixed the link. This is all part of the system described on the book, HVM is merely a very fast practical implementation. The additions (thinks like machine integers and constructors) don't affect the core.

pchiusano 5y ago

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

toomanydoubts 5y ago

I've seen your post in /r/brasil. Nice work.

tayistay 5y ago

Could this lazy cloning be applied to an eager language like Rust? (sorry if that's a dumb question. This isn't my area of expertise)

vintermann 5y ago

This is the sort of project which causes even me to break from wasting time on HN and go actually download things and try things. In particular, a while back I came across an interesting tree-based hugenum representation in Haskell, Paul Tarau's "Hereditarily Binary Natural Numbers". It might be something (somewhat) practical that HVM can be used for right now. I'll see if I can translate it and get it to run.

deleted 5y ago

[deleted]

jevoten 5y ago

Could HVM let Haskell entirely eliminate its GC, doing away with GC pauses and enabling its use in real-time applications? That could be just as revolutionary as the beta-optimality.

LightMachine 5y ago
It does that! There are no GC pauses on HVM's model. Compiling Haskell to it would be neat.