[Caml-list] Regarding regular expressions

[Caml-list] Regarding regular expressions

[John Skaller]

Below is some analysis of use of backreferences in Perl, done by
Eric Niebler <ericne#micorosft.com> for the C++ committee.
This post is stolen from the library subgroup committee reflector.
The C++ committee is looking at which kind of regular expresssions
to provide as standard in the C++ Standard Library. Thought I'd post
it here in case it's useful to the Ocaml team which is also looking
at RE libraries.

------------------------------------------------------------------------

OK, I have some numbers.  As a refresher, POSIX-extended doesn't do
backreferences, but guarantees complexity O(SN) where S is the number of
states in the NFA, and N is the number of characters in the input
string.  ECMAScript does backreferences, but worst-case complexity is
O(2^N).

For a language where backreferences are available, I thought it would be
interesting to see how often people make use of this feature.  So I
downloaded the CPAN archive and analyzed the perl scripts there.  Here
is what I found:

     - I found 165228 perl scripts/modules in CPAN [1].
     - Of those, 68501 use regular expressions [2].
     - Of those, 32359 (or 47 percent) use backreferences [3].

So, nearly half of all perl scripts on CPAN that use regular expressions
make use of the backreference feature.  IMO this argues strongly in
favor of supporting backreferences in C++.  (Backreferences can only be
handled by a backtracking NFA engine, IIRC.)

There are other features besides backreferences that can only be
provided by a backtracking NFA.  These features include non-greedy
quantification, positive and negative look-ahead and look-behind
assertions, independent sub-expressions, conditional sub-expressions,
and backreferences within the pattern itself.  I did a separate analysis
to see how often these features were used.  Here's what I found:

     - Of the 68501 scripts that use regular expressions, 12199 (or 18
percent) use at least one of the features listed above [4].

If I count the files that use either backreferences or one of these
other features, I find that:

     - 33881 files, or 49.5 percent, use some feature that requires a
backtracking NFA engine.

To get some idea of how many false-positives were turning up in my
tests, I ran the same search against the files which do not use regular
expressions at all.  I found that of the 96727 scripts that do *not* use
regular expressions [2], 2300 tested positive for a backtracking regex
feature.  That amounts to a 2% false positive rate.  So it would be fair
to knock 2% off the percentages quoted above.

Eric



[1] - I was only looking at files with .pm and .pl extensions, after
extracting all archives with .tar.gz, .tgz, and .zip extensions.
[2] - A perl file was determined to use regular expressions if it
matched the pattern, "[=!]~ *[^ty ]".  That is, if it used the operators
=~ or !~ for matching or substituting (i.e. not character translation).
[3] - A file was determined to use backreferences if it contained the
pattern, "\$[1-9][^0-9]".
[4] - A file was included in this total if it matched one of the
following patterns:
         \(\?=                      // a positive look-ahead assertion
         \(\?!                      // a negative look-ahead assertion
         [0-9]\}\?                  // a non-greedy quantifier
         [+*]\?                     // also a non-greedy quantifier
         \(\?> // an independent sub-expression
         \(\?<=                     // a positive look-behind assertion
         \(\?<!                     // a negative look-behind assertion
         \(\?\(                     // a conditional sub-expression
         [=!]~.*\\[1-9][^0-9]       // a backreference used within a
pattern



-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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] Regarding regular expressions

[Jerome Vouillon]

> For a language where backreferences are available, I thought it would be
> interesting to see how often people make use of this feature.  So I
> downloaded the CPAN archive and analyzed the perl scripts there.  Here
> is what I found:
> 
>     - I found 165228 perl scripts/modules in CPAN [1].
>     - Of those, 68501 use regular expressions [2].
>     - Of those, 32359 (or 47 percent) use backreferences [3].
> 
> So, nearly half of all perl scripts on CPAN that use regular expressions
> make use of the backreference feature.  IMO this argues strongly in
> favor of supporting backreferences in C++.  (Backreferences can only be
> handled by a backtracking NFA engine, IIRC.)

What he means by backreference is a way to refer to a submatch.  For
instance, with the regular expression "^([^ ]*) *([^ ]*)", the
backreference "$1" will refer to the substring matched by the first
parenthesed subexpression "([^ ]*)".  As long as the references do not
occur in the regular expression itself, they can be handled perfectly
well with a DFA engine.  So, the numbers above do not prove anything.

> There are other features besides backreferences that can only be
> provided by a backtracking NFA.  These features include non-greedy
> quantification, positive and negative look-ahead and look-behind
> assertions, independent sub-expressions, conditional sub-expressions,
> and backreferences within the pattern itself.

I believe all these features but backreferences within a pattern can
be provided by a DFA engine (though my RE library only support one of
these features, non-greedy quantification, at the moment).

So, the real questions are:
- how often are backreferences used within a pattern?
- when they are used, is it just for convenience, or would it be hard
  to rewrite the pattern without using backreferences?

[Feel free to forward this mail back to the C++ commitee.]

-- Jerome
-------------------
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] Regarding regular expressions

[Pixel]

Jerome Vouillon <vouillon@pps.jussieu.fr> writes:

[...]

> > So, nearly half of all perl scripts on CPAN that use regular expressions
> > make use of the backreference feature.  IMO this argues strongly in
> > favor of supporting backreferences in C++.  (Backreferences can only be
> > handled by a backtracking NFA engine, IIRC.)
> 
> What he means by backreference is a way to refer to a submatch.  For
> instance, with the regular expression "^([^ ]*) *([^ ]*)", the
> backreference "$1" will refer to the substring matched by the first
> parenthesed subexpression "([^ ]*)".  As long as the references do not
> occur in the regular expression itself, they can be handled perfectly
> well with a DFA engine.  So, the numbers above do not prove anything.

agreed.

Here are the numbers I get (only scanning perl 5.8.0, not CPAN):

% cd /usr/lib/perl5/5.8.0
% find -name "*.p[lm]" | xargs perl -ne 'print "$ARGV: $_" if /[=!]~\s*[^ty ]/' | wc -l
   2640
% find -name "*.p[lm]" | xargs perl -ne 'print "$ARGV: $_" if /[=!]~\s*[^ty ]/' | perl -ne 'print if /\\[1-9]\D/' | wc -l
      3
% find -name "*.p[lm]" | xargs perl -ne 'print "$ARGV: $_" if /[=!]~\s*[^ty ]/' | perl -ne 'print if /\\[1-9]\D/'
./ExtUtils/MM_Win32.pm:      while ($libs =~ s/(?:^|\s)(("?)-L.+?\2)(?:\s|$)/ /) {
./Pod/Text/Overstrike.pm:     $text =~ s/(.)[\b]\1/$1/g;
./Test.pm:          (undef, $regex) = ($expected =~ m,^ m([^\w\s]) (.+) \1 $,sx)) {

> - how often are backreferences used within a pattern?

I get 3 / 2640 = 0.1%
-------------------
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

[Caml-list] Three way comparaisons

[Diego Olivier Fernandez Pons]

    Bonjour,

Dans une note d'Arno Andersson [signalée par Okasaki dans Oka98] est
présenté un algorithme de recherche dans un arbre en (log n + 1)
comparaisons :

au lieu de

let rec member x = function
  | Empty -> false
  | Node (a, y, b) ->
     match compare x y with
      | n when n < 0 -> member x a
      | n when n > 0 -> member x b
      | _ -> true

Arno propose un algorithme qui ne fait qu'une comparaison par noeud.
Il explique que "since most high-level languages do not supply three
way comparaisons the number of comparaisons used _de facto_ are
reduced by a factor of two"

Il ajoute en plus "However, so far the autor has never observed a
compiler which actually translate these two comparaisons into one
three-way comparaison"

- Qu'est exactement une comparaison à trois voies ? (est-ce une façon
d'exploiter que les processeurs en général lèvent des drapeaux de
signe ou de nullité pour leurs opérations ?)

- Le compilateur Caml effectue-t-il cette optimisation ?

- Le code proposé par Andersson sera-t-il vraiment plus efficace étant
donné que l'on est obligé de transmettre un paramètre de plus
(indépendamment du fait que l'arbre soit parcouru sur toute sa hauteur
dans la mesure où le truc peut toujours servir pour les insertions où
le parcours est toujours complet ?)

Code d'Andersson

(* y est le plus grand des minorants de x déjà rencontrés donc le
candidat idéal pour le test d'égalité *)

let rec member_some x y = function
  | Empty -> compare x y = 0
  | Node (a, z, b) ->
     compare x z with
       | n when n < 0 -> member_some x y a
       | _ -> member_some x z b

let rec member_none x = function
  | Empty -> false
  | Node (a, y, b) ->
      match compare x y with
        | n when n < 0 -> member_none x a
        | _ -> member_some x y b

let member x = function tree -> member_none x tree

        Diego Olivier

-------------------
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] Three way comparaisons

[Luc Maranget]

> 
>     Bonjour,
> 
Bonjour,

Un conseil : essayer les deux codes, plus une info perdue plus bas sur les
optimisations de ocamlopt.

> Dans une note d'Arno Andersson [signal=E9e par Okasaki dans Oka98] est
> pr=E9sent=E9 un algorithme de recherche dans un arbre en (log n + 1)
> comparaisons :
> 
> au lieu de
  code classique.

> Arno propose un algorithme qui ne fait qu'une comparaison par noeud.
> Il explique que "since most high-level languages do not supply three
> way comparaisons the number of comparaisons used _de facto_ are
> reduced by a factor of two"
> 

J'ai lu vite mais dans les deux cas le nombre d'appels a` compare me
semble identique. Si les clefs sont compliquées (des chaînes par ex)
c'est là l'essentiel.


Enuite ça va être plus serré. Il faut essayer...



> Il ajoute en plus "However, so far the autor has never observed a
> compiler which actually translate these two comparaisons into one
> three-way comparaison"
Mais y a-til des machines qui les réalisent ces fameuses comparaisons
trois voies ? C'est bien la question au final.

Avec un processeur muni de drapeaux d'états on peut imaginer
une comparaison suivie de deux sauts conditionnels.

Avec un Risc genre Mips, je vois pas trop.


> 
> - Qu'est exactement une comparaison =E0 trois voies ? (est-ce une fa=E7on
> d'exploiter que les processeurs en g=E9n=E9ral l=E8vent des drapeaux de
> signe ou de nullit=E9 pour leurs op=E9rations ?)
C'est un truc mysterieux pour moi. qui par magie envoie sur trois
choix possibles de façon « atomique » vu du processeur ça a peut être existé un
jour...
En gros ça correspond à un modèle du coût de la machine où ce choix
entre trois possibilités compte pour un..

En pratique et pour avoir essayé longtemps il est dur de relier les
modèles de coût basés sur le nombre de comparaisons élémentaires au
temps machine.  La raison est assez simple, les deux (trois ?) cas
possibles n'ont pas le même coût, car on a un dileme saut/pas saut et
le temps d'un saut est disons variable.


En pratique, les sauts pris sont souvent dominants dans le coût du
code natif, dès lors, le coût effectif dépend  des entrés et aie.

En bytecode c'est moins net.



> 
> - Le compilateur Caml effectue-t-il cette optimisation ?

Il en fait une de ce style.

Sur le pentium et pour un

match du style (type t = A | B | C)

match x with
| A -> ...
| B -> ...
| C -> ...

Alors le code produit aura une instruction de compraison 
et deux sauts conditionnels.
Savoir si l'on gagne beaucoup à ce jeu-là, on gagne sans doute un peu
et dans certains cas (une instruction compare en moins..).


De façon générale, il est assez dur de se faire une idée précise de
possibles différences d'efficacité entre ces deux codes, au seul vu du
source (comme souvent).

L'argument supplémentaire peut être un facteur de ralentissement, mais
pas forcément exagéré (passage en registres).

Comme déjà dit c'est pas facile de relier un match ou même un if à un
quelconque coût final. Ça va dépendre de l'allignement de l'addresse
du code cible, de l'état des caches de la prédiction des sauts, voire
de la phase de la lune...


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

-------------------
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] Three way comparaisons

[Diego Olivier Fernandez Pons]

    Bonjour,

> J'ai lu vite mais dans les deux cas le nombre d'appels a` compare me
> semble identique. Si les clefs sont compliquées (des chaînes par ex)
> c'est là l'essentiel.

On peut omettre dans un premier temps la nature de la clef

let rec member x = function
  | Empty -> false
  | Node (a, y, b) ->
	if x < y then member x a
        else if x > y then member x b
        else true

Il y a très approximativement 3/2 log n comparaisons par recherche
contre log n + 1 pour la version d'Andersson

Cela reste vrai si l'on mémorise auparavant le résultat de la
comparaison de clefs pour se ramener à une compairaison d'entiers

> Comme déjà dit c'est pas facile de relier un match ou même un if à un
> quelconque coût final. Ça va dépendre de l'allignement de l'addresse
> du code cible, de l'état des caches de la prédiction des sauts, voire
> de la phase de la lune...

Tout le monde se plaint de l'absence de prévisibilité des performances
des processeurs actuels. Matteo Frigo dans sa thèse conclut que la
seule solution reste en somme que le compilateur essaie différentes
possibilités et choisisse celle qui convient le mieux après test. 
Peut-être est-ce possible également en Caml (d'un autre côté Caml est
déjà très rapide alors quelques gains de performance ne sont pas une
priorité absolue il me semble). 

        Diego Olivier

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