Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement)

[Oleg <oleg_inconnu@myrealbox.com>]

On Wednesday 10 July 2002 06:02 am, sebastien FURIC wrote:

<snip>

> </caml>
>
> real    11m9.021s
> user    0m0.020s
> sys     0m0.030s
>
>  Sebastien.

I guess this is an example of when very idiomatic C++ shines:

    1   #include <iostream>
    2   #include <vector>
    3
    4   typedef std::vector<int> 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