Comment by LightMachine | Hacker News Reader

Comment by LightMachine | Hacker News Reader

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.

The How page [0] is nicely written! It was a real pleasure to read :)

[0] https://github.com/Kindelia/HVM/blob/master/HOW.md

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?

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

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

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

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

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?

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

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?

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.

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.

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.

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

```

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.

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

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)

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

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

Perhaps you could team up?

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?

This is MIT licensed, so feel free to fork, use, edit and sell it without even notifying me. Now go ahead and get rich!

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!

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!

Have to say this is the most excited comment I've ever seen on this website.

This is amazing!!

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.

JFYI, the "This book" link on 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?

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.

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

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

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

Reply on news.ycombinator.com