This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] productivity improvement
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2002-07-10 (20:35) From: William D. Neumann Subject: [Caml-list] Re: Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement)
```Gah!!! You guys are making me nuts!

Not because of this topic (I actually find this somewhat interesting --
even if I don't know why), but because every post on the subject has
ignored the two most basic optimizations that should be done for this
small prime generation:
Doing trial division only up to the square root of the candidate (and)
Incrementing your candidates by 2 rather than 1 (2 is the only even
prime -- don't waste your time on even numbers!)

Seriously, why pull out vector libraries, etc. while leaving these pigs in

For what it's worth, here is my naive 10 minute solution that takes about
0.2 seconds to generate the first 5000 primes on my 500MHz G4 (and no
fair laughing at my poor programming chops!):

(* ********************************** *)

type pState = {primes : int array;
mutable top : int;
mutable cur : int;
max : int};;

let print_prime op =
match op with
None -> ()
| Some p -> Printf.printf "%d\n" p;;

let next state = state.cur <- state.cur + 2;;
let update state =
begin
Array.set state.primes state.top state.cur;
state.top <- state.top + 1;
next state
end;;

let is_prime state=
let b = (int_of_float (sqrt (float_of_int state.cur))) and
index = ref 1 and
prime = ref true in
while ((state.primes.(!index) <= b) & !prime) do
if (state.cur mod state.primes.(!index) = 0)
then prime := false
else index := (!index + 1)
done;
!prime;;

let rec next_prime state =
if state.top >= state.max then
None
else
if is_prime state then
(update state; Some state.primes.(state.top - 1))
else
(next state; next_prime state);;

let main () =
let num_primes = (int_of_string Sys.argv.(1)) in
let state = {primes = Array.make num_primes 2;
top = 1;
cur = 3;
max = num_primes;} in
let p = ref (next_prime state) in
while (!p <> None) do
print_prime !p;
p := (next_prime state);
done;;

main ();;

(* ********************************** *)

William D. "Cranky or something" Neumann

On Wed, 10 Jul 2002, Oleg wrote:

> 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
>

---

"The magnum opus of rms and his Foundation is called 'GNU', a project to
completely rewrite the propritorially soiled Unix operating system.
(Apparently, 'GNU' stands for "Gnu's Not Unix", and is proudly held to be
the world's first 'recursive acronym'. Which, of course, proves that rms
didn't get out enough in his youth.)

-- Nick Roberts

-------------------
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

```