From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA17562; Wed, 10 Jul 2002 22:14:27 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA17558 for ; Wed, 10 Jul 2002 22:14:26 +0200 (MET DST) Received: from dewberry.cc.columbia.edu (dewberry.cc.columbia.edu [128.59.59.68]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g6AKEPn09615 for ; Wed, 10 Jul 2002 22:14:25 +0200 (MET DST) Received: from there (tw304h3.cpmc.columbia.edu [156.111.84.180]) by dewberry.cc.columbia.edu (8.9.3/8.9.3) with SMTP id QAA14544; Wed, 10 Jul 2002 16:14:18 -0400 (EDT) Message-Id: <200207102014.QAA14544@dewberry.cc.columbia.edu> Content-Type: text/plain; charset="iso-8859-1" From: Oleg To: "sebastien FURIC" , Shannon --jj Behrens Subject: Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement) Date: Wed, 10 Jul 2002 16:15:33 -0400 X-Mailer: KMail [version 1.3.2] Cc: caml-list@inria.fr References: <20020709182022.69599.qmail@web10706.mail.yahoo.com> <3D2C063E.25EA1D8D@tni.fr> In-Reply-To: <3D2C063E.25EA1D8D@tni.fr> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wednesday 10 July 2002 06:02 am, sebastien FURIC wrote: > > > real 11m9.021s > user 0m0.020s > sys 0m0.030s > > Sebastien. I guess this is an example of when very idiomatic C++ shines: 1 #include 2 #include 3 4 typedef std::vector vec; 5 6 void next_prime_candidate(int c, vec& v) { 7 for(int i = 0; i < v.size(); ++i) 8 if(c % v[i] == 0) return; 9 v.push_back(c); 10 } 11 12 void print_vec(vec& v) { 13 for(int i = 0; i < v.size(); ++i) 14 std::cout << ' ' << v[i]; 15 } 16 17 int main() { 18 vec v; v.push_back(2); 19 for(int i = 3; v.size() < 10000; ++i) 20 next_prime_candidate(i, v); 21 print_vec(v); 22 } Compiled with g++-3.0 -O2 on my aging AMD K6-2 550 MHz, I get real 0m4.632s user 0m3.290s sys 0m0.260s while for Sebastien's findprimes_simple.ml, compiled with ocamlopt, I get real 0m43.809s user 0m41.590s sys 0m0.040s C++ version does not get faster if I add v.reserve(10000) in the beginning, so its bottleneck is probably not in memory allocation. Perhaps O'Caml version can be made faster: here's my shot at it: 1 let next_prime_candidate c v = 2 let _ = try 3 Array.iter (fun x -> if c mod x = 0 then failwith "not a prime") !v; 4 v := Array.append !v [| c |]; 5 with Failure "not a prime" -> () in ();; 6 7 let print_array v = 8 Array.iter (fun i -> print_char ' '; print_int i) v;; 9 10 let v = ref [| 2 |] in 11 let i = ref 2 in 12 let _ = 13 while Array.length !v < 10000 do 14 i := !i + 1; 15 next_prime_candidate !i v 16 done in 17 print_array !v;; Timing: real 0m11.645s user 0m11.370s sys 0m0.010s Still 3-4 times slower. Is it because exceptions are used instead of [non-existent ?] early function return or loop break? A version of the last program with Lists instead of Arrays is 7-8 times slower than the Array version. Oleg ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners