[Caml-list] Faking concurrency using Unix forks and pipes
Jon Harrop
Has anyone implemented a parallel map function in OCaml using Unix forks,
pipes and maybe marshalling?
This seems like an easy way to get concurrency in OCaml...
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Erik de Castro Lopo
>
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
I've been thinking of something like that, but with sockets
replacing pipes so its possible to do distributed as well as
parallel programming. I was actually going to do C at the
lowest level (for generality more than anything else) and put
an Ocaml wrapper around it.
Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"Perl as a language has less a design than a thousand special
features flying in close formation."
-- From the c2 wiki
Jonathan Bryant
On May 29, 2007, at 11:42 PM, Jon Harrop wrote:
>
> Has anyone implemented a parallel map function in OCaml using Unix
> forks,
> pipes and maybe marshalling?
I've implemented a toy version of this, so I can say it does work and
is not too hard, although I don't still have the code. My OSP
project is a concurrency library that would make implementing this
pretty trivial though: it extends the Event module to work over UNIX
& TCP sockets and to have a common interface for thread creation /
forking / remote process creation.
>
> This seems like an easy way to get concurrency in OCaml...
It would also be nice to have a Apply in Parallel / Parallel List
Comprehension syntax for it a la NESL (http://www.cs.cmu.edu/~scandal/
nesl.html).
Mike Lin
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
>
> This seems like an easy way to get concurrency in OCaml...
I've been using Gerd's RPC library for this (on his suggestion when I
asked the same question some months ago). It's a slight inconvenience
to write XDR for every transaction, but in return you get type safety.
And you don't have to think that much harder to go distributed.
-Mike
Oliver Bandel
On Wed, May 30, 2007 at 04:42:59AM +0100, Jon Harrop wrote:
>
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
I have thought about such stuff, but ot implemented
(because there was no real need for it).
Since I found OCamlP3l, I'm not shure if implementing
such stuff would make sense, because using OCamlP3l
might be the right way.
OCamlP3l: http://camlp3l.inria.fr/eng.htm
I didn't tried it so far.
If people already have done (or will do now),
I would be interested in feedback.
Ciao,
Oliver
P.S.: Why did you write "Faking concurrency"?
If the processes are running on a multi-core/multi-processor
machine, using processes can achieve paralellism.
Florian Hars
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
I've been toying with something like
module type MR =
functor (D1: DICT_TYPE) ->
functor (D2: DICT_TYPE) ->
sig
val mapreduce :
(D1.key -> D1.value -> (D2.key * 'a) list) ->
( D2.key -> 'a list -> D2.value option) ->
D1.t ->
D2.t
end
and have one implementation that forks a set of worker processes
and then marshalls data of types
type 'a command = Quit | Execute of 'a
type ('a, 'b) response = Result of 'a | Error of 'b
through a pipe.
Not very robust right now, but it seems to work if none of the
workers dies prematurely...
Yours Florian.
Loup Vaillant
> Hi,
>
> On Wed, May 30, 2007 at 04:42:59AM +0100, Jon Harrop wrote:
> >
> > Has anyone implemented a parallel map function in OCaml using Unix forks,
> > pipes and maybe marshalling?
>
> Since I found OCamlP3l, I'm not shure if implementing
> such stuff would make sense, because using OCamlP3l
> might be the right way.
I've just read some of the user manual, and can notice a small
syntactic burden, as well as the unavoidable fact that one must learn
it to use it. (This is not a complaint. Any library is like that.)
Jon, were you talking about reimplementing List.map and the like, so
users have concurrency for free? A simple solution would be to use a
third party tool, like OcamlP3l.
Cheers,
Loup Vaillant
Jon Harrop
> I have thought about such stuff, but ot implemented
> (because there was no real need for it).
I feel dirty when one of my cores is idling.
> Since I found OCamlP3l, I'm not shure if implementing
> such stuff would make sense, because using OCamlP3l
> might be the right way.
>
> OCamlP3l: http://camlp3l.inria.fr/eng.htm
May I just ask Xavier et al. what the ETA is on ocamlp3l? Its just, I really
want to take over the world and this is holding us up. ;-)
> P.S.: Why did you write "Faking concurrency"?
> If the processes are running on a multi-core/multi-processor
> machine, using processes can achieve paralellism.
Well, yes, I mean it is the ugly sister of concurrent GC. Better than nothing
though.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Jon Harrop
> Jon, were you talking about reimplementing List.map and the like, so
> users have concurrency for free?
Exactly, yes. Just having a concurrent Array.map would help enormously.
> A simple solution would be to use a third party tool, like OcamlP3l.
I'm having a look at it now. I had thought that it was an experimental version
of OCaml that with a concurrent GC but that seems to be completely wrong.
Will OCaml have a concurrent GC in the future?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Erik de Castro Lopo
> I'm having a look at it now. I had thought that it was an experimental version
> of OCaml that with a concurrent GC but that seems to be completely wrong.
>
> Will OCaml have a concurrent GC in the future?
How much does a concurrent GC actually buy in comparison to
multiple processes each with their own GC and a robust way
of passing data between processes?
Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"The day Microsoft makes something that doesn't suck is probably the
day they start making vacuum cleaners." -- Ernst Jan Plugge
Loup Vaillant
> Jon Harrop wrote:
>
> > I'm having a look at it now. I had thought that it was an experimental version
> > of OCaml that with a concurrent GC but that seems to be completely wrong.
> >
> > Will OCaml have a concurrent GC in the future?
>
> How much does a concurrent GC actually buy in comparison to
> multiple processes each with their own GC and a robust way
> of passing data between processes?
>
As far as I know, the developement team had made it quite clear that
there will be no concurent GC (not in the near future, at least).
Loup Vaillant
> Jon Harrop wrote:
>
> > I'm having a look at it now. I had thought that it was an experimental version
> > of OCaml that with a concurrent GC but that seems to be completely wrong.
> >
> > Will OCaml have a concurrent GC in the future?
>
> How much does a concurrent GC actually buy in comparison to
> multiple processes each with their own GC and a robust way
> of passing data between processes?
>
As far as I know, the developement team had made it quite clear that
there will be no concurent GC (not in the near future, at least). The
main reason is performance loss.
(Sorry for the double post)
Luc Maranget
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
>
> This seems like an easy way to get concurrency in OCaml...
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> OCaml for Scientists
> http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
This is what we did for a a few examples of using JoCaml,
the soon-to-be-released extension of OCaml for concurrent programming.
Fork/Exec is an easy way to get simultaneous execution.
JoCaml is not released yet, (I am writting the doc
and web site at the moment).
The much incomplete web site is at
<http://jocaml.inria.fr>
One example of fork under jocaml control
<http://jocaml.inria.fr/manual/concurrent.html#htoc25>
The example may not meet all your concerns (speed I guess),
but you can replace the shell in the example by somme
C or Ocaml program that computes something and refine the control
to collect results.
Hope it helps.
--
Luc Maranget
Jon Harrop
> As far as I know, the developement team had made it quite clear that
> there will be no concurent GC (not in the near future, at least). The
> main reason is performance loss.
Might be interesting to compare the performance of some languages using my ray
tracer:
C++: 3.67s
OCaml: 3.97s
F#: 5.26s
Lisp: 6.04s
Scheme: 6.29s
Java: 6.53s
F# is ~30% slower than OCaml but can be made almost twice as fast on my dual
core machine by tracing concurrently. However, Java is also a concurrent
static language and it is much slower. Maybe this reflects more effort having
gone into the .NET GC.
I should also note that the F# and Scheme are both 32-bit. I wonder how well
F# would do if it were 64-bit... :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Jon Harrop
> How much does a concurrent GC actually buy in comparison to
> multiple processes each with their own GC and a robust way
> of passing data between processes?
1. Shared memory and locks should be much faster for synchronization than
marshalling between processes.
2. Forking results in multiple GCs redundantly traversing the same heap and,
worst case, it may end up copying the entire heap in the child process in
order to deallocate it.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Erik de Castro Lopo
> This is what we did for a a few examples of using JoCaml,
> the soon-to-be-released extension of OCaml for concurrent programming.
>
> Fork/Exec is an easy way to get simultaneous execution.
>
> JoCaml is not released yet, (I am writting the doc
> and web site at the moment).
>
> The much incomplete web site is at
> <http://jocaml.inria.fr>
Now that *really* *does* look interesting!
Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"It has been discovered that C++ provides a remarkable facility
for concealing the trival details of a program -- such as where
its bugs are." -- David Keppel
Joel Reymont
On May 30, 2007, at 9:40 AM, Luc Maranget wrote:
> This is what we did for a a few examples of using JoCaml,
> the soon-to-be-released extension of OCaml for concurrent programming.
Tell me, please tell me, it does not require me to install another
OCaml compiler source tree!
I'm yearning for a concurrent OCaml extension that uses Camlp4 and
generates plain OCaml code. Is there such a thing?
Thanks, Joel
--
http://topdog.cc - EasyLanguage to C# compiler
http://wagerlabs.com - Blog
Erik de Castro Lopo
> > The much incomplete web site is at
> > <http://jocaml.inria.fr>
>
> Now that *really* *does* look interesting!
I tried to grab the source tarball, but got a 404 not found :-(.
Patience Erik, patience!
Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
Diana West for President of the United States
http://www.washtimes.com/op-ed/20060817-091447-7758r.htm
http://www.washtimes.com/op-ed/20060824-084015-5082r.htm
Jon Harrop
> Erik de Castro Lopo wrote:
> > > The much incomplete web site is at
> > > <http://jocaml.inria.fr>
> >
> > Now that *really* *does* look interesting!
>
> I tried to grab the source tarball, but got a 404 not found :-(.
>
> Patience Erik, patience!
This is outrageous. We could have had JoCaml by now if Luc hadn't been posting
on mailing lists. I'm shocked and appalled...
By the way, apologies to the ten people who downloaded my original bytecode
tarball of Smoke that had dependencies on other code that wasn't there. It
should all be fixed now. Why does nobody ever tell me whether or not my demos
work?! :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Joel Reymont
On May 30, 2007, at 10:25 AM, Jon Harrop wrote:
> Why does nobody ever tell me whether or not my demos work?! :-)
This off-topic but it must be basic human psychology or something.
The same thing happens with my translator.
Joel
--
http://topdog.cc - EasyLanguage to C# translator
http://wagerlabs.com - Blog
Benedikt Grundmann
I'm also doing an OSP project on concurrency. In my case there will
actually be a new api which will offer erlang style concurrency (e.g.
asynchroneous messages). (Also implemented using UNIX & TCP sockets).
Cheers,
Bene
PS: I already have some code that does the local message passing, but
it is all in a flux and I consider that a prototype, so hold your
breath until August.
2007/5/30, Jonathan Bryant <jtbr...@valdosta.edu>:
--
Calvin: I try to make everyone's day a little more
surreal.
(From Calvin & Hobbes)
Thomas Fischbacher
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
>
> This seems like an easy way to get concurrency in OCaml...
That is indeed an exercise I like to pose to my PhD students.
(Of course, the question whether this really makes that much
sense is a different issue...)
Here is my own suggestion how to do it:
let compute_uniform_workload_forked
?(bailout=
(fun str ->
let () = Printf.fprintf stderr "AIEE! %s\n%!" str in
exit 1))
~fun_combine
v_work =
let bailout s dummy = let _ = bailout s in dummy in
(* Note that we use the "bailout" function in two different places
where it expects
different return types. Hence, we have to bend over backwards to
get the type
system to accept what we actually want to do...
*)
let nr_processes = Array.length v_work in
let rec setup_childs nr_process child_info =
if nr_process = nr_processes
then List.rev child_info (* This ensures we get the data in proper
order. *)
else
let (fd_read,fd_write) = Unix.socketpair Unix.PF_UNIX
Unix.SOCK_STREAM 0 in
let pid = Unix.fork () in
if pid == (-1) (* fork failure *)
then
bailout "fork() failure!" child_info
else
if pid == 0 (* We are the child - compute our share and exit *)
then
let () = Unix.close fd_read in
let s_write = Unix.out_channel_of_descr fd_write in
let result = v_work.(nr_process) () in
let () = Marshal.to_channel s_write result [] in
exit 0
else
(* We are the parent *)
let () = Unix.close fd_write in
let s_read = Unix.in_channel_of_descr fd_read in
setup_childs (1+nr_process) ((s_read,pid)::child_info)
in
let all_childs_info = setup_childs 1 [] in
(* Note that it is important that we start counting at 1 here, as
the parent will do
chunk #0!
*)
let result_chunk0 = v_work.(0) () in
(* Note that we just do assume that all pieces of the computation
take the same time.
We are not trying to be overly sophisticated, fetching data from
the fastest
child first. Also, if we wanted a more powerful tool to compute
with forked processes,
we might want to divide the big task in a more fine-grained way
and hand out sub-tasks
to processes through a scheduler that takes care of when which
process finishes
which sub-task. For now, this is overkill.
*)
let rec collect_child_results have child_info_todo =
match child_info_todo with
| [] -> have
| ((s_read,pid)::child_info_todo_next) ->
let contrib = Marshal.from_channel s_read in
let (returned_pid,status) = Unix.waitpid [] pid in
if status <> Unix.WEXITED 0
then
bailout "Child failure!\n%!" have
else
collect_child_results
(fun_combine contrib have)
child_info_todo_next
in collect_child_results result_chunk0 all_childs_info
;;
(* ---
(* === Example === *)
let sum_of_inverse_squares =
compute_uniform_workload_forked
~fun_combine:(fun a b -> a+.b)
(let nr_processes=4 in
let ranges=split_range nr_processes 1 100000 in
let work subrange_start subrange_end =
let () = Printf.printf "PID: %d SUB-RANGE %d - %d\n%!"
(Unix.getpid()) subrange_start subrange_end
in
let rec walk n sum =
if n = subrange_end then sum
else walk (1+n) (let fn = float_of_int n in sum +. 1.0/.(fn*.fn))
in walk subrange_start 0.0
in
(Array.init nr_processes
(fun n ->
let (r_s,r_e) = ranges.(n) in
fun () -> work r_s r_e)))
;;
(* This gives: 1.64492406679822967
The full sum would be pi^2/6 = 1.64493406684822641
*)
--- *)
--
best regards,
Thomas Fischbacher
t...@functionality.de
Mattias Engdegård
>> multiple processes each with their own GC and a robust way
>> of passing data between processes?
>
>1. Shared memory and locks should be much faster for synchronization than
>marshalling between processes.
>
>2. Forking results in multiple GCs redundantly traversing the same heap and,
>worst case, it may end up copying the entire heap in the child process in
>order to deallocate it.
3. Cores on the same chip often share at least one cache level,
and the same is trivially true for threads in the same core.
In software-speak, this means that processes should share the read-only
part of their working set as much as possible.
Gerd Stolpmann
> Jon Harrop schrieb:
> > Has anyone implemented a parallel map function in OCaml using Unix forks,
> > pipes and maybe marshalling?
>
> I've been toying with something like
>
> module type MR =
> functor (D1: DICT_TYPE) ->
> functor (D2: DICT_TYPE) ->
> sig
> val mapreduce :
> (D1.key -> D1.value -> (D2.key * 'a) list) ->
> ( D2.key -> 'a list -> D2.value option) ->
> D1.t ->
> D2.t
> end
Interesting example... We are going to implement a distributed mapreduce
on a cluster using ocamlnet (and its components rpc and netplex).
Netplex is a framework to listen to a number of sockets and to
start/manage processes dealing with the TCP connections (using a
generalized pre-fork model). We are already using it for our distributed
web crawler.
Gerd
> and have one implementation that forks a set of worker processes
> and then marshalls data of types
> type 'a command = Quit | Execute of 'a
> type ('a, 'b) response = Result of 'a | Error of 'b
> through a pipe.
>
> Not very robust right now, but it seems to work if none of the
> workers dies prematurely...
>
> Yours Florian.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany
ge...@gerd-stolpmann.de http://www.gerd-stolpmann.de
Phone: +49-6151-153855 Fax: +49-6151-997714
------------------------------------------------------------
Richard Jones
>
> pipes and maybe marshalling?
>
> This seems like an easy way to get concurrency in OCaml...
Don't particularly have any code to show but kind of: at Merjis we did
something like this using both MPI and the Ancient module. (Not at
the same time).
MPI was used to parallelise a simple log parsing job across a cluster
of machines. This wasn't very successful as it turned out because I
got bitten by Amdahl's law - the thing that was taking the time was
the serial parsing part of the job.
Second approach was to parse the logfiles overnight into a file-backed
memory heap using Ancient. Then we used several processes to do the
analysis. The processes were forked, but accessed the file-backed
shared memory directly (so no pipes).
Rich.
--
Richard Jones
Red Hat
Richard Jones
> F# is ~30% slower than OCaml but can be made almost twice as fast on my dual
> core machine by tracing concurrently. However, Java is also a concurrent
> static language and it is much slower. Maybe this reflects more effort having
> gone into the .NET GC.
Jon,
We've had this discussion before. Summary: yes, SMP is suddenly
popular. If we keep doubling the number of cores available every 18
months though, then soon we'll have dozens-hundreds of cores, and
there's no chance at all that these will have uniform memory access.
Once you have NUMA, threads and concurrent GC don't help.
Intel 80 core processor:
http://www.reghardware.co.uk/2006/09/26/intel_teraflop_processor/ ,
and it's very very NUMA - each core has 20 MB of RAM strapped to it.
>From the article: "[The chip] also features a network processing unit
on each core to control core-to-core communication. [...] Once Intel
boffins have worked out the best way to interconnect cores, memory [...]"
Rich.
--
Richard Jones
Red Hat
_______________________________________________
Richard Jones
> On Wednesday 30 May 2007 09:13:00 Erik de Castro Lopo wrote:
> > How much does a concurrent GC actually buy in comparison to
> > multiple processes each with their own GC and a robust way
> > of passing data between processes?
>
> 1. Shared memory and locks should be much faster for synchronization than
> marshalling between processes.
>
> 2. Forking results in multiple GCs redundantly traversing the same heap and,
> worst case, it may end up copying the entire heap in the child process in
> order to deallocate it.
Fixed: http://merjis.com/developers/ancient
Rich.
--
Richard Jones
Red Hat
_______________________________________________
Granicz Adam
wrote:
>
> Has anyone implemented a parallel map function in OCaml using Unix forks,
> pipes and maybe marshalling?
>
> This seems like an easy way to get concurrency in OCaml...
>
I am swamped with emails so this may have come up already in this thread,
but Tomas has a nice parallel list implementation at
http://tomasp.net/blog/fsparallelops.aspx
Cheers,
Adam.
Pablo Polvorin
> for synchronization than marshalling between processes.
as long as i don't have to use ugly locks in my code, that will be ok.
But I think that the Erlang approach is simpler and more elegant than
the use of locks - critical regions. Also, as already mentioned, it
offers an easy transition from multicore to distributed computing,
where shared memory isn't available.
2007/5/30, Jon Harrop <j...@ffconsultancy.com>:
> On Wednesday 30 May 2007 09:13:00 Erik de Castro Lopo wrote:
> > How much does a concurrent GC actually buy in comparison to
> > multiple processes each with their own GC and a robust way
> > of passing data between processes?
>
>
> 2. Forking results in multiple GCs redundantly traversing the same heap and,
> worst case, it may end up copying the entire heap in the child process in
> order to deallocate it.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> OCaml for Scientists
> http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
Pablo Polvorin
David Teller
Yeah !
Happiness and tears of joy !
David,
who will now stop spamming people with Erlang and return to advocating
JoCaml.
On Wed, 2007-05-30 at 10:40 +0200, Luc Maranget wrote:
> JoCaml is not released yet, (I am writting the doc
> and web site at the moment).
>
> The much incomplete web site is at
> <http://jocaml.inria.fr>
>
> One example of fork under jocaml control
> <http://jocaml.inria.fr/manual/concurrent.html#htoc25>
>
> The example may not meet all your concerns (speed I guess),
> but you can replace the shell in the example by somme
> C or Ocaml program that computes something and refine the control
> to collect results.
>
>
> Hope it helps.
>
_______________________________________________