Re: [Caml-list] Performance problem

[Xavier Leroy <xleroy@pauillac.inria.fr>]

> > >that occur to me are an output buffering problem or some delay in
> > >interacting with the X display, but I'm not sure how to solve either of
> > >those. And maybe it's something else entirely. Can anyone explain my
> > >terrible results?
> > 
> > My guess (without profiling) is that most of the time is being spent 
> > doing regular expression matching.

Profiling (ocamlopt -p) confirms this guess: 99.9% of the time is
spent in the regexp matching engine...

> > Regular expressions can be much slower than you might expect for 
> > non-trivial cases.  The expression in your program looks particularly 
> > nasty, since there are a lot of ambiguous cases (whether '-' should 
> > match '.*' or '-' depends on everything that follows).

Indeed.  This kind of regexp is among the worst cases for a greedy
backtracking regexp matcher like that of Str.  As someone else
suggested, making the regexp deterministic (replace .*- with [^-]*-)
helps immensely.

> > 1) you regexp string is not properly escaped, all the "\(" and "\)"
> >    should be "\\(" and "\\)".
> 
> Okay, I've run into that with other languages. But I didn't know you had
> to do that in OCaml. Is that documented anywhere?

In the syntax for strings, yes: a literal \ should be written \\,
hence the \( regexp construct should be written \\( in a string literal.
Perhaps this should be recalled in the docs for Str.regexp.  At any rate,
the compiler will nicely warn you.

> By the way, why doesn't the compiler just reject regexes with single
> backslashes? What is the point of issuing warnings and then accepting
> the incorrect syntax?

Backward compatibility, mostly.  But this is the kind of warning that
might become an error at some point in the future.  

> > 2) there are no problems using bytecode :
> >      0.3s using bytecode
> >      23s  using native

This I doubt very much, and indeed a quick test shows that bytecode
and native take exactly the same time.  This isn't surprising:
since 99% of the time is spent is the regexp engine, and this engine
is in C, it runs at the same speed in bytecode and in native-code.

- Xavier Leroy

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