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

Re: [Caml-list] Loop times
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-03-19 (06:49) From: Daniel M. Albro Subject: Re: [Caml-list] Loop times
```OK, as requested here's a summary email.  I think someone already
answered you about the input loop (recap -- Input-Output routines
are so slow that the speed of the loop around them fades into
insignificance by comparison).

I was trying to illustrate a point that a "break" statement
would be a nice addition to the language, but I got distracted a bit
into figuring out what is the fastest way to break out of a loop as
things stand now (as opposed to the best way, which might be different
from the fastest...).  I did 8 different timing tests, which I will
present from fastest to slowest:

(1) Tail-recursive function, top-level defined (slightly
faster than (2), possibly because the variable ary is
more local)
---------------------------------------------------
let rec loop ary j =
if j = 10 then
()
else if ary.(j) = 5 then
()
else
loop ary (j + 1)

let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
for i = 1 to 1_000_000_000 do
loop ary 0
done

real    0m26.787s
user    0m26.770s
sys     0m0.010s
---------------------------------------------

(2) Tail-recursive auxilliary function
---------------------------------------------
let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
let rec loop j =
if j = 10 then
()
else if ary.(j) = 5 then
()
else
loop (j + 1)
in
for i = 1 to 1_000_000_000 do
loop 0
done

real    0m26.823s
user    0m26.780s
sys     0m0.020s
-----------------------------------------------------

(3) For loop with exception pre-built:
-----------------------------------------------------
exception Break

let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
let exn = Break in
for i = 1 to 1_000_000_000 do
try
for j = 0 to 9 do
if ary.(j) = 5 then
raise exn
done
with Break -> ()
done

real    0m28.095s
user    0m28.070s
sys     0m0.030s
------------------------------------------------------

(4) Continuation-passing style
------------------------------------------------------
let _ =
let ary = [| 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12 |] in
let rec loop f j =
if j = 10 || ary.(j) = 5 then f ()
else loop f (j + 1)
in
let rec outer i =
if i <= 1_000_000_000 then
loop (fun _ -> outer (i + 1)) 0
in
outer 1

real    0m29.999s
user    0m29.890s
sys     0m0.010s
------------------------------------------------------------

(5) For loop with exception
------------------------------------------------------------
exception Break

let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
for i = 1 to 1_000_000_000 do
try
for j = 0 to 9 do
if ary.(j) = 5 then
raise Break
done
with Break -> ()
done

real    0m34.245s
user    0m34.080s
sys     0m0.010s
-----------------------------------------------------

(6) Tail recursive auxilliary function defined inside
the outer loop (sometimes, in more complicated cases,
this might be an option, I suppose, for example, if
the inner loop needs to be a separate function)
-----------------------------------------------------
let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
for i = 1 to 1_000_000_000 do
let rec loop j =
if j = 10 then
()
else if ary.(j) = 5 then
()
else
loop (j + 1)
in
loop 0
done

real    0m35.188s
user    0m35.140s
sys     0m0.040s
------------------------------------------------------

(7) while loop with references
------------------------------------------------------
let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
let j = ref 0 in
for i = 1 to 1_000_000_000 do
j := 0;
while !j < 10 do
if ary.(!j) = 5 then
j := 10
else
incr j
done
done

real    0m39.458s
user    0m39.440s
sys     0m0.000s
------------------------------------------------------

(8) "Higher order functions".  This style is nifty because
it's like a break statement that can return a value.
------------------------------------------------------
let escape body =
let module Fail = struct exception T end in
let datum = ref None in
let throw v =
begin
datum := Some v;
raise Fail.T
end
in
try
body throw
with
Fail.T -> (match !datum with Some v -> v | None -> assert false)

let _ =
let ary = [|1;2;3;4;5;6;7;8;9;10;11;12|] in
for i = 1 to 1_000_000_000 do
escape (fun exit ->
for j = 0 to 9 do
if ary.(j) = 5 then exit()
done)
done

real    1m49.178s
user    1m48.900s
sys     0m0.280s
------------------------------------------------------

The main surprise to me was that number (7) was so slow.  Anyway,
as matters currently stand it looks like tail recursive loops are
the way to go if you have to have a fast inner loop that can break
out early.  HOWEVER, I would like to argue that for cases where
you really want to optimize a loop like this (and where you can't
radically change the algorithm or data structures, of course), it
would be really great if the language added a genuine break
statement (plus some sort of step value for for loops).  As usual,
my argument is in terms of a timing test.  If you have an inner
loop that *doesn't* have to break out in the middle, the for loop
is much faster than a tail recursive loop.  Here are the
tests:

(1) for loop
------------------------------------
let _ =
let k = ref 0 in
for i = 1 to 1_000_000_000 do
k := 0;
for j = 1 to 10 do
incr k
done
done

real    0m22.867s
user    0m22.850s
sys     0m0.010s
------------------------------------

(2) tail recursive loop
------------------------------------
let _ =
let k = ref 0 in
let rec loop j =
incr k;
if j = 10 then () else loop (j + 1)
in
for i = 1 to 1_000_000_000 do
k := 0;
loop 1
done

real    0m37.105s
user    0m36.870s
sys     0m0.200s
------------------------------------

On Tue, 2003-03-18 at 00:52, Oliver Bandel wrote:
> On Mon, Mar 17, 2003 at 02:01:21PM -0800, Daniel M. Albro wrote:
> >
> > 	Sorry, I just meant that the version that puts the
> > exception into a variable outside of the loop is a win over
> > the one that creates the exception inside the loop.
>
> What does this mean for such a version of reading a file
> linewise into a list of strings?
>
>
> let input_lines chan =
>   let rec input_lines_helper res =
>     let sl =
>        try
>          Some (input_line chan)
>        with
>          End_of_file -> None in
>     match sl with
>        None -> List.rev res
>      | Some l -> input_lines_helper (l :: res) in
>   input_lines_helper []
>
> There is a try-with inside the reacursive function.
> But is there a way to avoid it?
>
>
> Well... I may re-read all the mails and put them together to
> one mail or may produce a little paper on that topic?
>
> I have to sort the many new things in FPL-programming
> for better understanding....
>
> Or maybe you are interested in collecting all results together
> into one conclusion-mail?
> (Would be nice. :))
>
>
> > The
> > fastest loop routine overall was the tail recursive loop,
> > i.e. the functional/recursive.
>
> BTW: This is new to me. Even OCaml-people told me, that
> the imperative version of loops will be faster than
> recursive/functional.
>
> That's good news for FP-programming, but that's also
> bad news for people, who want to optimize their
> functional programs in speed.
>
>
> > However, this latest
> > imperative version has timing that's very close -- the
> > imperative version that pre-builds the exception takes
> > just over 28 seconds, and the tail-recursive version
> > takes just under 27 seconds.
>
> OK.
>
> Can you give me a short advice on the recursive
> Input-function, mantioned above?
>
> Thanks.
>
>
> Ciao,
>    Oliver
>
> -------------------
> 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
--
Daniel M. Albro <albro@humnet.ucla.edu>

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

```