Howto program thread-based parallel list iteration

Question

I need as an example how to program a parallel iter-function using ocaml-threads. My first idea was to have a function similiar to this:

let procs = 4 ;;

let rec _part part i lst =   match lst with
      [] -> ()
    | hd::tl -> 
        let idx = i mod procs in
        (* Printf.printf "part idx=%i\n" idx; *)
        let accu = part.(idx) in
          part.(idx) <- (hd::accu);
          _part part (i+1) tl ;;

Then a parallel iter could look like this (here as process-based variant):

let iter f lst =   let part = Array.create procs [] in
    _part part 0 lst;
    let rec _do i =
      (* Printf.printf "do idx=%i\n" i; *)
      match Unix.fork () with
          0 -> (* Code of child *)
            if i < procs then 
              begin
                (* Printf.printf "child %i\n" i; *)
                List.iter f part.(i) 
              end
        | pid -> (* Code of father *)
            (* Printf.printf "father %i\n" i; *)
            if i >= procs then ignore (Unix.waitpid [] pid)
            else _do (i+1)
    in
      _do 0 ;;

Because the usage of Thread-module is a little bit different, how would I code this using ocaml's thread module?

And there is another question, the _part() function must scan the whole list to split them into n parts and then each part will be piped through each own processes (here). Still exists there a solution without splitting a list first?

Answer 1

If you have a function which processes a list, and you want to run it on several lists independently, you can call Thread.create with that function and every list. If you store your lists in array part then:

let threads = Array.map (Thread.create (List.iter f)) part in
Array.iter Thread.join threads

INRIA OCaml threads are not actual threads: only one thread executes at any given time, which means if you have four processors and four threads, all four threads will use the same processor and the other three will remain unused.

Where threads are useful is that they still allow asynchronous programming: some Thread module primitives can wait for an external resource to become available. This can reduce the time your software spends blocked by an unavailable resource, because you can have another thread do something else in the mean time. You can also use this to concurrently start several external asynchronous processes (like querying several web servers through HTTP). If you don't have a lot of resource-related blocking, this is not going to help you.

As for your list-splitting question: to access an element of a list, you must traverse all previous elements. While this traversal could theoretically be split across several threads or processes, the communication overhead would likely make it a lot slower than just splitting things ahead of time in one process. Or using arrays.

Answer 2

Answer to a question from the comments. The answer does not quite fit in a comment itself.

There is a lock on the OCaml runtime. The lock is released when an OCaml thread is about to enter a C function that

• may block;
• may take a long time.

So you can only have one OCaml thread using the heap, but you can sometimes have non-heap-using C functions working in parallel with it.

See for instance the file ocaml-3.12.0/otherlibs/unix/write.c

memmove (iobuf, &Byte(buf, ofs), numbytes); // if we kept the data in the heap
                                            // the GC might move it from
                                            // under our feet.
enter_blocking_section();                   // release lock.
                                            // Another OCaml thread may
                                            // start in parallel of this one now.
ret = write(Int_val(fd), iobuf, numbytes);
leave_blocking_section();                   // take lock again to continue
                                            // with Ocaml code.