Version française
Home     About     Download     Resources     Contact us    
Browse thread
More efficient implementation of intersection of sets?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Frédéric_Gava <gava@u...>
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?
Dear John, Sasha and Caml-list

> Not likely. OCaml's implementation is already vastly more efficient than any 
> other language I have ever seen (e.g. C++). Your next best bet is probably to 
> parallelize the algorithm to improve the performance but that is extremely 
> difficult to do without a concurrent GC. Frederic Gava did some work on this 
> in OCaml. I am working on the same problem in F#.

You can have parallel sets without a concurrent GC : each processor has 
a subset of your initial set and you can distribute the elements using a 
hash function from element to the number of processor "p" (there is so 
"p" ocaml programs that runs and thus "p" GC). A random function can be 
used in general and generate a quick good load balancing.

You can have more information here :
http://lacl.univ-paris12.fr//gava/papers/gava_ppl_2008.pdf

Note, that I used our "under development library" but this work can be 
done using OCaml-MPI


Frédéric G.