Parallel Finonacci on Ocaml.org

Community
1

On OCaml.org, the playground interpreter (OCaml Playground ) proposes the following code:

let rec fib_par n d =
  if d <= 1 then fib n
  else
    let a = fib_par (n-1) (d-1) in
    let b = Domain.spawn (fun _ -> fib_par (n-2) (d-1)) in
    a + Domain.join b

It doesn’t seem to be parallel. a is called in the main domain, and when after its computing, we create a new domain, but the calling domain is immediately blocked on join.

I would create the new domain sooner:

let rec fib_par n d =
  if d <= 1 then fib n
  else
    let a = Domain.spawn (fun _ -> fib_par (n-1) (d-1)) in
    let b = fib_par (n-2) (d-1) in
    Domain.join a + b
1 Like
2

Rather scratch the whole example… That’s not the way domains are supposed to be used, they are heavy-weight structures the number of which you have should be tied to the number of cpu cores your machine has.

3 Likes
3

It also isn’t correct. If you change the value of num_domains beyond 11 it will start giving you a different result.
Edit: or if you instead change n to 0 or 1 you get 2 instead of 1 as result.

4

Yes, in the exemple, we have a number of domains probably proportional with the exponential of num_domains. Then the num_domains name is misleading.

But my version (with an easy fix for the small n values issue) would be more appropriate for the Domain demo of the playground (its default d=2 value will use only 2 cores. A d=3 values would use 4 of them… (probably we should not decrement d, but divide it by 2 at each call).

And if we really want a number of domain bound to the CPU, a pool of workers would be better but probably over the aims of a basic domain playground example.

5

This code is literally teaching the wrong way to use domains, it should just be replaced by something else, not be saved.

3 Likes
6

With d=3, the Fibonacci number of 20 is computed by parallel of Fibanacci 20 and 19, which call parallel Fibonacci of 19, 18, 18, and 17. With d=1.

Since at this level, d=1 these 4 domains will switch into a non-parallel computation. Then they all will have enough task to justify the heavy domain creation.

Then it seems a good use case for domains if d is well chosen (log2(nb of CPU)+1). But sure, we can’t use fully a 24 core CPU, and some domains will have less work than others. But sure, with d=11 it would be inappropriate.

And for a playground example we should have something quite simple. Not something very useful. (Sure, Fibonacci computation would be faster with matrix powers)

7

Yes, the parallel version is buggy for small values. And with num_domains=11, the function remains in parallel mode for 21, 19, 17, 15… 1… when calling each Fibonacci (n-2).

Fixing the parallel version is however easy.

8

@dbuenzli is correct, this code is terrible and I’m not a fan of showing it to newcomers. I think that if we want to include multi-domain examples in the playground, it should link with Domainslib or Moonpool etc.

2 Likes
9

Though not parallel, the binary tree example from the old site was very nice. There is example code before clicking “Try the playground” which looks a bit noisy IMO, and doesn’t even use the same syntax coloring. These nitpicky beauty touches are probably not very high on the list of priorities but the bar for entry on them is very low and I don’t think the site maintainers would mind proposed improvements to them.