Strange performances

Strange performances

[Benjamin Canou]

  Hi,

The code following my message is way faster in bytecode than in native
code. Is there a good reason for that or is it a bug ?
Note : It is a (way too, I know) naive implementation of the well known
string suite 1, 11, 21, 1211, 111221, ...

  Benjamin Canou.

=== code ===

let list_of_string s =
  let rec list_of_string s i =
    try s.[i] :: list_of_string s (succ i)
    with _ -> []
  in list_of_string s 0

let rec trans = function
  | '1' :: '1' :: '1' :: tl -> "31" ^ trans tl
  | '1' :: '1' :: tl -> "21" ^ trans tl
  | '1' :: tl -> "11" ^ trans tl
  | '2' :: '2' :: '2' :: tl -> "32" ^ trans tl
  | '2' :: '2' :: tl -> "22" ^ trans tl
  | '2' :: tl -> "12" ^ trans tl
  | '3' :: '3' :: '3' :: tl -> "33" ^ trans tl
  | '3' :: '3' :: tl -> "23" ^ trans tl
  | '3' :: tl -> "13" ^ trans tl
  | [] -> ""
  | _ -> failwith "bad input"

let rec print n s =
  print_endline s ;
  if n > 0 then print (pred n) (trans (list_of_string s))
    
let _ = print 30 "1"

=== perfs ===

benjamin@benjamin-laptop:~/Work/Stuff$ ocamlopt 123.ml -o 123
benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
[...]
real    0m5.245s
user    0m4.944s
sys     0m0.016s
benjamin@benjamin-laptop:~/Work/Stuff$ ocamlc 123.ml -o 123
benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
[...]
real    0m1.097s
user    0m0.840s
sys     0m0.008s
benjamin@benjamin-laptop:~/Work/Stuff$ ocaml -version
The Objective Caml toplevel, version 3.09.2

Re: [Caml-list] Strange performances

[Jacques Garrigue]

The problem seems to be in list_of_string.
If I write:

let list_of_string s =
  let rec list_of_string s i =
    if i < String.length s then s.[i] :: list_of_string s (succ i) else []
  in list_of_string s 0

I get a 10 time increase in speed for bytecode, and 5 times better for
native code, as one would expect. Out-of-bounds exceptions are
intended as fatal errors, do not try to catch them...

By the way, on my machine your version doesn't even work in native
code, I only get segfaults. This is allowed behaviour for
out-of-bounds access.

Jacques Garrigue

From: Benjamin Canou <benjamin.canou@gmail.com>
>   Hi,
> 
> The code following my message is way faster in bytecode than in native
> code. Is there a good reason for that or is it a bug ?
> Note : It is a (way too, I know) naive implementation of the well known
> string suite 1, 11, 21, 1211, 111221, ...
> 
>   Benjamin Canou.
> 
> === code ===
> 
> let list_of_string s =
>   let rec list_of_string s i =
>     try s.[i] :: list_of_string s (succ i)
>     with _ -> []
>   in list_of_string s 0
> 
> let rec trans = function
>   | '1' :: '1' :: '1' :: tl -> "31" ^ trans tl
>   | '1' :: '1' :: tl -> "21" ^ trans tl
>   | '1' :: tl -> "11" ^ trans tl
>   | '2' :: '2' :: '2' :: tl -> "32" ^ trans tl
>   | '2' :: '2' :: tl -> "22" ^ trans tl
>   | '2' :: tl -> "12" ^ trans tl
>   | '3' :: '3' :: '3' :: tl -> "33" ^ trans tl
>   | '3' :: '3' :: tl -> "23" ^ trans tl
>   | '3' :: tl -> "13" ^ trans tl
>   | [] -> ""
>   | _ -> failwith "bad input"
> 
> let rec print n s =
>   print_endline s ;
>   if n > 0 then print (pred n) (trans (list_of_string s))
>     
> let _ = print 30 "1"
> 
> === perfs ===
> 
> benjamin@benjamin-laptop:~/Work/Stuff$ ocamlopt 123.ml -o 123
> benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> [...]
> real    0m5.245s
> user    0m4.944s
> sys     0m0.016s
> benjamin@benjamin-laptop:~/Work/Stuff$ ocamlc 123.ml -o 123
> benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> [...]
> real    0m1.097s
> user    0m0.840s
> sys     0m0.008s
> benjamin@benjamin-laptop:~/Work/Stuff$ ocaml -version
> The Objective Caml toplevel, version 3.09.2

Re: [Caml-list] Strange performances

[Jacques Garrigue]

Sorry, my explanation was wrong.
Actually, your error was much worse.
You apparently assumed that s.[i] :: list_of_string s (succ i)
would be evaluated from left to write, raising an exception
as soon as i gets out of s. But this is not the case!
It is evaluated from right to left, first looping until the stack
overflows, then raising exceptions on all the way back. No surprise
that this was incredibly slow. And my segmentation fault was just
caused by the stack overflow. Otherwise, out-of-bound accesses are
correctly reported.

Jacques Garrigue

From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
> The problem seems to be in list_of_string.
> If I write:
> 
> let list_of_string s =
>   let rec list_of_string s i =
>     if i < String.length s then s.[i] :: list_of_string s (succ i) else []
>   in list_of_string s 0
> 
> I get a 10 time increase in speed for bytecode, and 5 times better for
> native code, as one would expect. Out-of-bounds exceptions are
> intended as fatal errors, do not try to catch them...
> 
> By the way, on my machine your version doesn't even work in native
> code, I only get segfaults. This is allowed behaviour for
> out-of-bounds access.
> 
> Jacques Garrigue
> 
> From: Benjamin Canou <benjamin.canou@gmail.com>
> >   Hi,
> > 
> > The code following my message is way faster in bytecode than in native
> > code. Is there a good reason for that or is it a bug ?
> > Note : It is a (way too, I know) naive implementation of the well known
> > string suite 1, 11, 21, 1211, 111221, ...
> > 
> >   Benjamin Canou.
> > 
> > === code ===
> > 
> > let list_of_string s =
> >   let rec list_of_string s i =
> >     try s.[i] :: list_of_string s (succ i)
> >     with _ -> []
> >   in list_of_string s 0
> > 
> > let rec trans = function
> >   | '1' :: '1' :: '1' :: tl -> "31" ^ trans tl
> >   | '1' :: '1' :: tl -> "21" ^ trans tl
> >   | '1' :: tl -> "11" ^ trans tl
> >   | '2' :: '2' :: '2' :: tl -> "32" ^ trans tl
> >   | '2' :: '2' :: tl -> "22" ^ trans tl
> >   | '2' :: tl -> "12" ^ trans tl
> >   | '3' :: '3' :: '3' :: tl -> "33" ^ trans tl
> >   | '3' :: '3' :: tl -> "23" ^ trans tl
> >   | '3' :: tl -> "13" ^ trans tl
> >   | [] -> ""
> >   | _ -> failwith "bad input"
> > 
> > let rec print n s =
> >   print_endline s ;
> >   if n > 0 then print (pred n) (trans (list_of_string s))
> >     
> > let _ = print 30 "1"
> > 
> > === perfs ===
> > 
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocamlopt 123.ml -o 123
> > benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> > [...]
> > real    0m5.245s
> > user    0m4.944s
> > sys     0m0.016s
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocamlc 123.ml -o 123
> > benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> > [...]
> > real    0m1.097s
> > user    0m0.840s
> > sys     0m0.008s
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocaml -version
> > The Objective Caml toplevel, version 3.09.2
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Strange performances

[Till Varoquaux]

On Jan 18, 2008 2:15 AM, Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> wrote:
...
> By the way, on my machine your version doesn't even work in native
> code, I only get segfaults. This is allowed behaviour for
> out-of-bounds access.

Could you please clarify? This seems a little scary to me, I thought
segfaults where acceptable only when you used unsafe features (or ran
out of stack).

Cheers,
Till
>
> Jacques Garrigue
>
> From: Benjamin Canou <benjamin.canou@gmail.com>
>
> >   Hi,
> >
> > The code following my message is way faster in bytecode than in native
> > code. Is there a good reason for that or is it a bug ?
> > Note : It is a (way too, I know) naive implementation of the well known
> > string suite 1, 11, 21, 1211, 111221, ...
> >
> >   Benjamin Canou.
> >
> > === code ===
> >
> > let list_of_string s =
> >   let rec list_of_string s i =
> >     try s.[i] :: list_of_string s (succ i)
> >     with _ -> []
> >   in list_of_string s 0
> >
> > let rec trans = function
> >   | '1' :: '1' :: '1' :: tl -> "31" ^ trans tl
> >   | '1' :: '1' :: tl -> "21" ^ trans tl
> >   | '1' :: tl -> "11" ^ trans tl
> >   | '2' :: '2' :: '2' :: tl -> "32" ^ trans tl
> >   | '2' :: '2' :: tl -> "22" ^ trans tl
> >   | '2' :: tl -> "12" ^ trans tl
> >   | '3' :: '3' :: '3' :: tl -> "33" ^ trans tl
> >   | '3' :: '3' :: tl -> "23" ^ trans tl
> >   | '3' :: tl -> "13" ^ trans tl
> >   | [] -> ""
> >   | _ -> failwith "bad input"
> >
> > let rec print n s =
> >   print_endline s ;
> >   if n > 0 then print (pred n) (trans (list_of_string s))
> >
> > let _ = print 30 "1"
> >
> > === perfs ===
> >
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocamlopt 123.ml -o 123
> > benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> > [...]
> > real    0m5.245s
> > user    0m4.944s
> > sys     0m0.016s
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocamlc 123.ml -o 123
> > benjamin@benjamin-laptop:~/Work/Stuff$ time ./123
> > [...]
> > real    0m1.097s
> > user    0m0.840s
> > sys     0m0.008s
> > benjamin@benjamin-laptop:~/Work/Stuff$ ocaml -version
> > The Objective Caml toplevel, version 3.09.2
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
http://till-varoquaux.blogspot.com/

Re: [Caml-list] Strange performances

[Jacques Garrigue]

From: "Till Varoquaux" <till.varoquaux@gmail.com>
> On Jan 18, 2008 2:15 AM, Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> wrote:
> ...
> > By the way, on my machine your version doesn't even work in native
> > code, I only get segfaults. This is allowed behaviour for
> > out-of-bounds access.
> 
> Could you please clarify? This seems a little scary to me, I thought
> segfaults where acceptable only when you used unsafe features (or ran
> out of stack).

This is why I sent an erratum. The cause for the segfault was not the
array access, but the stack overflow, which occured due to ocaml's
peculiar evaluation order.
Still, I maintain that intentionally raising and catching out-of-bound
accesses is not good programming style...

Jacques Garrigue

Re: [Caml-list] Strange performances

[Benjamin Canou]

  Hi,

Indeed, using runtime exceptions catching as a programming style may
lead to strange behaviours, but I think using the any pattern in the try
with construct was the real mistake.

So basically, to those who did not understand the problem :
This code works perfectly :

let list_of_string s =
  let rec list_of_string s i =
    try let e = s.[i] in e :: list_of_string s (succ i)
    with Invalid_argument "index out of bounds" -> []
  in list_of_string s 0

And if I had used a correct matching of exceptions in my original code :

let list_of_string s =
  let rec list_of_string s i =
    try s.[i] :: list_of_string s (succ i)
    with Invalid_argument "index out of bounds" -> []
  in list_of_string s 0

I would have noticed that the bug came from my carelessness about the
evaluation order (btw, thank you Jacques) :

Fatal error: exception Stack_overflow

In fact, the function calls itself recursively to construct the right
hand side of the list constructor until the stack is full.

With the any (_) pattern, the function returns [] for each call from the
one corresponding to the end of the string to the one causing the
overflow. So the result is correct, but it takes a time proportional to
the maximum size of the stack...
With a pattern matching the out of bounds exception, the stack overflow
is not caught and the programs exits abnormally right after the
overflow.

Jacques, if I remember well, the ocaml runtime is not able to detect
stack overflows in native code on all platforms, that's why you get a
segfault instead of a Stack overflow exception.

  Benjamin Canou.

Le vendredi 18 janvier 2008 à 18:12 +0900, Jacques Garrigue a écrit :
> From: "Till Varoquaux" <till.varoquaux@gmail.com>
> > On Jan 18, 2008 2:15 AM, Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> wrote:
> > ...
> > > By the way, on my machine your version doesn't even work in native
> > > code, I only get segfaults. This is allowed behaviour for
> > > out-of-bounds access.
> > 
> > Could you please clarify? This seems a little scary to me, I thought
> > segfaults where acceptable only when you used unsafe features (or ran
> > out of stack).
> 
> This is why I sent an erratum. The cause for the segfault was not the
> array access, but the stack overflow, which occured due to ocaml's
> peculiar evaluation order.
> Still, I maintain that intentionally raising and catching out-of-bound
> accesses is not good programming style...
> 
> Jacques Garrigue
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Strange performances

[Edgar Friendly]

Jacques Garrigue wrote:
> 
> This is why I sent an erratum. The cause for the segfault was not the
> array access, but the stack overflow, which occured due to ocaml's
> peculiar evaluation order.

Is there any case where ocaml's "peculiar evaluation order" results in
any benefit other than slightly simpler code at the compiler level?  I
understand that people shouldn't depend on evaluation order, but it
seems that people fall into this trap often.  And even extremely
experienced camlers (if you permit this characterization of you) forget
this behavior.

E.

Re: [Caml-list] Strange performances

[Olivier Andrieu]

Salut,

On Jan 18, 2008 5:55 PM, Benjamin Canou <benjamin.canou@gmail.com> wrote:
> This code works perfectly :
>
> let list_of_string s =
>   let rec list_of_string s i =
>     try let e = s.[i] in e :: list_of_string s (succ i)
>     with Invalid_argument "index out of bounds" -> []
>   in list_of_string s 0

well, until you compile with the -unsafe flag ....

> Jacques, if I remember well, the ocaml runtime is not able to detect
> stack overflows in native code on all platforms, that's why you get a
> segfault instead of a Stack overflow exception.

indeed, stack overflow of native code is not detected on all platforms.
Even on platforms where it is supported, you won't get an exception if
the overflow occurs in a function inside the C runtime.

-- 
  Olivier

Re: [Caml-list] Strange performances

[Jon Harrop]

On Friday 18 January 2008 17:05:20 Olivier Andrieu wrote:
> Salut,
>
> On Jan 18, 2008 5:55 PM, Benjamin Canou <benjamin.canou@gmail.com> wrote:
> > This code works perfectly :
> >
> > let list_of_string s =
> >   let rec list_of_string s i =
> >     try let e = s.[i] in e :: list_of_string s (succ i)
> >     with Invalid_argument "index out of bounds" -> []
> >   in list_of_string s 0
>
> well, until you compile with the -unsafe flag ....

That is an argument against the -unsafe flag rather than against the above 
code, IMHO. None of the operations used here were unsafe and, in an ideal 
world, OCaml would never segfault on this safe code.

I _really_ don't like the notion that OCaml can just screw up following out of 
bounds access because that is one of the main reasons I migrated to OCaml in 
the first place...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Strange performances

[Jon Harrop]

On Friday 18 January 2008 16:55:14 Benjamin Canou wrote:
> This code works perfectly :
>
> let list_of_string s =
>   let rec list_of_string s i =
>     try let e = s.[i] in e :: list_of_string s (succ i)
>     with Invalid_argument "index out of bounds" -> []
>   in list_of_string s 0

As an aside, I would recommend using an imperative style with mutable data 
structures like "string" are involved:

  let list_of_string string =
    let list = ref [] in
    for i = String.length string - 1 downto 0 do
      list := string.[i] :: !list
    done;
    !list;;

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Strange performances

[Kuba Ober]

On Friday 18 January 2008, Edgar Friendly wrote:
> Jacques Garrigue wrote:
> > This is why I sent an erratum. The cause for the segfault was not the
> > array access, but the stack overflow, which occured due to ocaml's
> > peculiar evaluation order.
>
> Is there any case where ocaml's "peculiar evaluation order" results in
> any benefit other than slightly simpler code at the compiler level?  I
> understand that people shouldn't depend on evaluation order, but it
> seems that people fall into this trap often.  And even extremely
> experienced camlers (if you permit this characterization of you) forget
> this behavior.

I think that if you apply principle of least astonishment, things should be 
evaluated left-to-right. Or at least with a consistent rule.

Cheers, Kuba

Re: [Caml-list] Strange performances

[Jon Harrop]

On Friday 18 January 2008 17:52:06 Kuba Ober wrote:
> On Friday 18 January 2008, Edgar Friendly wrote:
> > Jacques Garrigue wrote:
> > > This is why I sent an erratum. The cause for the segfault was not the
> > > array access, but the stack overflow, which occured due to ocaml's
> > > peculiar evaluation order.
> >
> > Is there any case where ocaml's "peculiar evaluation order" results in
> > any benefit other than slightly simpler code at the compiler level?  I
> > understand that people shouldn't depend on evaluation order, but it
> > seems that people fall into this trap often.  And even extremely
> > experienced camlers (if you permit this characterization of you) forget
> > this behavior.
>
> I think that if you apply principle of least astonishment, things should be
> evaluated left-to-right. Or at least with a consistent rule.

I believe this design was chosen to give the compiler more freedom for 
optimizing but I agree that left to right is preferable.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Strange performances

[Benjamin Canou]

Le vendredi 18 janvier 2008 à 17:43 +0000, Jon Harrop a écrit :
> As an aside, I would recommend using an imperative style with mutable data 
> structures like "string" are involved:
> 
>   let list_of_string string =
>     let list = ref [] in
>     for i = String.length string - 1 downto 0 do
>       list := string.[i] :: !list
>     done;
>     !list;;
> 

Actually, and as I said in my first message, it was a really naive
implementation, for which I used the more compact and quick to write
code.

Imho, I would not add references and write the function like this :

let list_of_string str =
  let rec aux i acc =
    if i < 0 then acc
    else aux (i - 1) (String.unsafe_get str i :: acc)
  in aux (String.length str - 1) []

But we are digressing...

  Benjamin.

Re: [Caml-list] Strange performances

[Jacques Garrigue]

From: Edgar Friendly <thelema314@gmail.com>
> Jacques Garrigue wrote:
> > 
> > This is why I sent an erratum. The cause for the segfault was not the
> > array access, but the stack overflow, which occured due to ocaml's
> > peculiar evaluation order.
> 
> Is there any case where ocaml's "peculiar evaluation order" results in
> any benefit other than slightly simpler code at the compiler level?  I
> understand that people shouldn't depend on evaluation order, but it
> seems that people fall into this trap often.  And even extremely
> experienced camlers (if you permit this characterization of you) forget
> this behavior.

Actually, the bytecode optimization is related to the evaluation order
of functions, not data structures. So it would be perfectly possible
to create blocks from left to right, without losing this optimization.
I thought about it once, since most errors seem actually related with
data construction rather than function calls. Such an order would even
generate slightly more compact code for modules (which clearly have
to be evaluated from left to right.)

The downside of such an approach would be different evaluation orders
for data constructors and functions. There is no theoretical problem
in it, since they form different syntactic classes in ocaml, but
people may not be completely aware of that.

Another unrelated problem seldom noted is that for records, the
evaluation order is that of the record definition, not that used when
creating it. And the same thing is true for labelled functions.
So you cannot expect the evaluation order to be exactly the one
appearing in the code.

Cheers,

        Jacques

Re: [Caml-list] Strange performances

[Christophe Raffalli]

> The downside of such an approach would be different evaluation orders
> for data constructors and functions. There is no theoretical problem
> in it, since they form different syntactic classes in ocaml, but
> people may not be completely aware of that.
>
>   
There is already a mixed evaluation order in OCaml :
"&&", "||", ";", ... are left to right (and the logical connective are 
lazy moreover)
So left to right everywhere except in function applications would be the 
simplest
deterministic strategy for OCaml ...

The current situation with OCaml unspecified evaluation order is really 
not satisfactory.
Let aside that it makes proving code more difficult (more cases to check).
But, even if you try to make your code independant from the evaluation 
order ...
how can you be sure ? This would require a random evaluation order to 
catch your potential bugs.
(like the old days Apple's SANE library with a random least significant 
bit to know how your
computation depends on rounding errors, I am missing that one ;-)
> Another unrelated problem seldom noted is that for records, the
> evaluation order is that of the record definition, not that used when
> creating it. And the same thing is true for labelled functions.
> So you cannot expect the evaluation order to be exactly the one
> appearing in the code.
>   
Argh ! Not nice that one ? For what reasons ?

Best regards,
Christophe