Hacker News Reader

Comment by amelius | Hacker News Reader

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

View on HN

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!

Reply on news.ycombinator.com