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