[Caml-list] Loop times

[Caml-list] Loop times

[Daniel M. Albro]

	OK, I just did a test of the three methods.  Here's the code:

Exception Version:
-------------------------------------------------
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 = 1 to 10 do
          if ary.(j) = 5 then
            raise Break
        done
      with Break -> ()
    done

real    0m30.569s
user    0m30.250s
sys     0m0.140s
------------------------------------------------------

Straight imperative version:
------------------------------------------------------
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;
        incr j
      done
    done

real    0m40.498s
user    0m39.980s
sys     0m0.260s
------------------------------------------------------

Tail recursive version:
------------------------------------------------------
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 1
    done

real    0m22.571s
user    0m22.360s
sys     0m0.080s
-------------------------------------------------------

	So may I should just be quiet and use
recursion :).

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

Re: [Caml-list] Loop times

[Fabrice Le Fessant]

>  
>  	OK, I just did a test of the three methods.  Here's the code:
>  
>  Exception Version:
>  -------------------------------------------------
>  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 = 1 to 10 do
>            if ary.(j) = 5 then
>              raise Break
>          done
>        with Break -> ()
>      done
>  
>  real    0m30.569s
>  user    0m30.250s
>  sys     0m0.140s
>  ------------------------------------------------------

For the fun, could you try this one ? It does not allocate the
exception in the loop but outside.

  -------------------------------------------------
 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 = 1 to 10 do
           if ary.(j) = 5 then
             raise exn
         done
       with Break -> ()
     done 
 ------------------------------------------------------
 


- Fabrice

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

Re: [Caml-list] Loop times

[Daniel M. Albro]

OK, I did this test, but first after making the thing
compatible with the other tests I did.  (That is, the
j loop should be 0 to 9 (or some other number less than
12 and greater than 4).  The first version (once
again, after changing the j loop to 0 to 9) takes

real    0m34.033s
user    0m34.030s
sys     0m0.000s

and Fabrice's version (with 0 to 9) takes

real    0m28.086s
user    0m28.080s
sys     0m0.000s

so it is definitely a win.

					- Dan

Fabrice Le Fessant wrote:
>> 
>> 	OK, I just did a test of the three methods.  Here's the code:
>> 
>> Exception Version:
>> -------------------------------------------------
>> 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 = 1 to 10 do
>>           if ary.(j) = 5 then
>>             raise Break
>>         done
>>       with Break -> ()
>>     done
>> 
>> real    0m30.569s
>> user    0m30.250s
>> sys     0m0.140s
>> ------------------------------------------------------
> 
> 
> For the fun, could you try this one ? It does not allocate the
> exception in the loop but outside.
> 
>   -------------------------------------------------
>  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 = 1 to 10 do
>            if ary.(j) = 5 then
>              raise exn
>          done
>        with Break -> ()
>      done 
>  ------------------------------------------------------
>  
> 
> 
> - Fabrice
> 


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

Re: [Caml-list] Loop times

[Daniel M. Albro]

	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.  The
fastest loop routine overall was the tail recursive loop,
i.e. the functional/recursive.  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.

					- Dan


Oliver Bandel wrote:
> On Mon, Mar 17, 2003 at 10:59:27AM -0800, Daniel M. Albro wrote:
> [...]
> 
>>so it is definitely a win.
> 
> 
> What is a win?
> 
> So much different versions, spread over several mails...
> 
> Is functional/recursive a win over imperative?
> Or vice versa? Or what?
> 
> 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

Re: [Caml-list] Loop times

[Oliver Bandel]

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.  The
> fastest loop routine overall was the tail recursive loop,
> i.e. the functional/recursive.  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.


Well, I recently found an older article on tail-recursion
and try-with statements: It's from John prevost, from April 24th,
2002.

He said there, that exception handling blocks tail-calls,
and that this means, to avoid try-with around tail-calls.

So, confusion takes over control.....

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

Re: [Caml-list] Loop times

[Daniel M. Albro]

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

Re: [Caml-list] Loop times

[Noel Welsh]

--- Oliver Bandel <oliver@first.in-berlin.de> wrote:
> Well... I may re-read all the mails and put them
> together to
> one mail or may produce a little paper on that
> topic?

If you do this it would be interesting to include
standard deviations in your results.  Without the
standard deviations the statistical significance of
the results cannot be calculated.

Noel

__________________________________________________
Do you Yahoo!?
Yahoo! Platinum - Watch CBS' NCAA March Madness, live on your desktop!
http://platinum.yahoo.com

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

Re: [Caml-list] Loop times

[Florian Hars]

Oliver Bandel wrote:
> What does this mean for such a version of reading a file
> linewise into a list of strings?

Nothing. I/O usually isn't CPU-bound.

You may argue that this idiom looks ugly nonetheless, but this is why 
you stow it away in some utility functions, called Textfile.iter and 
Textfile.fold (anyone round here who has not writeen these?).

So your code looks something like

let input_lines chan =
    List.rev (Textfile.fold (::) chan [])

or so, depending on how you order the arguments.

Yours, Florian.

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

Re: [Caml-list] Loop times

[Oliver Bandel]

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