Degraded scaling for the FIFO scheduler

[Drup]

As we discussed on discord, I run a benchmark recently for parallel map on trees. It makes for an interesting embarrassingly parallel (recursive) task. The core function is the map_par_full function below:

open Picos

type 'a tree = N of 'a * 'a tree * 'a tree | L

let async e =
  let p = Computation.create () in
  let fiber = Fiber.create ~forbid:false p in
  Fiber.spawn fiber (fun _ -> Computation.return p @@ e ());
  p

let rec map_par_full f t = async @@ fun () -> match t with
  | L -> L
  | N (v , tl , tr ) ->
    let task_tl = map_par_full f tl in
    let task_tr = map_par_full f tr in
    N (f v,
       Computation.await task_tl,
       Computation.await task_tr)

I run this with Picos' and Moonpool's schedulers. Here are the results for a tree of size 10000 with medium-sized tasks on a Intel Xeon E5-2630 (so, 12 cores * 2 hyperthreading). Time is normalized to a non-async baseline.

The two immediate conclusions are that

1. Multithreading is crap on this workload (welp)
2. Workstealing is great, congrats !
3. The scaling for Moonpool's FIFO scheduler is quite poor, and much worse than the multififo scheduler from picos, which should behave similarly.

cc ocaml-multicore/picos#374 on the Picos bug tracker.

[c-cube]

I'm not sure it's really a bug, the FIFO scheduler isn't meant to be used for super fine grained parallelism. It's there mostly as a simple scheduler for big tasks. The work-stealing scheduler is definitely more adequate, I'm glad the benchmark looks that good! :)

[Drup]

Indeed, I just though you would be interested by the plot. ;)

I agree it's not a "bug", more of an area of improvement, notably compared to Picos.multififo, which I expect gives similar fairness guarantee but scales better.

FWIW, at 12 domains, we end with roughly 20 to 30% overhead for the WS scheduler compared to the optimal scaling, which is quite nice !