From: Thomas Hurst <tom.hurst@...>
Date: 2002-10-07T21:25:32+09:00
Subject: Re: regex speed

* David Garamond (davegaramond@icqmail.com) wrote:

> i am noticing ruby is much slower than perl when matching patterns
> with two or more quantifier (+ or *). consider this string:
>
>  $ ruby -0 -ne 'print "A"*3,"\n"*10000,"B"*10,"\n"*10000' > str

Um, this hangs on my machine.  Fine when I execute it from a file
though.

> and matching this string:
>
>  $ perl -0 -ne'print 1 if /A.+\n+B/s' str   # 0m1.682s

5.005:   Real: 0:01.82 CPU: 99.4% (0.007/1.816) Mem: 712
5.6.1:   Real: 0:01.85 CPU: 100.0% (0.000/1.850) Mem: 642

>  $ ruby -0 -ne'print 1 if /A.+\n+B/m' str   # 0m12.468s

Normal:     Real: 0:15.35 CPU: 99.6% (0.023/15.272) Mem: 1298
Oni Guruma: Real: 0:15.54 CPU: 99.6% (0.007/15.485) Mem: 1172

>  $ perl -0 -ne'print 1 if /A.+\n.+\nB/s' str   # 0m1.368s

5.005:   Real: 0:12.75 CPU: 99.2% (0.023/12.645) Mem: 642
5.6.1:   Real: 0:13.46 CPU: 99.0% (0.023/13.313) Mem: 712

>  $ ruby -0 -ne'print 1 if /A.+\n.+\nB/m' str   # 0m11.427s

Normal:     Real: 0:15.74 CPU: 99.6% (0.039/15.651) Mem: 1298
Oni Guruma: Real: 0:09.83 CPU: 99.3% (0.015/9.760) Mem: 1172

-% perl -v
This is perl, v5.6.1 built for i386-freebsd

-% /usr/bin/perl5.00503 -v
This is perl, version 5.005_03 built for i386-freebsd

-% ruby -v
ruby 1.6.7 (2002-09-12) [i386-freebsd4]

Interesting that perl 5.005 is actually faster than 5.6.1 on these
matches.  I'd also imagine you're using 5.8 given how quick your version
of perl performed the second match.

> i even have one case where perl takes less than a second and ruby
> takes more than five minutes (i don't know for sure, i interrupted the
> process so ruby never finished).

Yes; regexp engines can encounter cases where they take a very long time
(easily measured in days) to perform a match.  Perl has gone to great
lengths to avoid these situations, but they're still there.

> note that i'm not implying anything though, because i understand
> perl's regex engine has undergone a long period of tweaking and
> optimization.

And ruby's has undergone a rewrite :)

-- 
Thomas 'Freaky' Hurst  -  freaky@aagh.net  -  http://www.aagh.net/
-
Maj. Bloodnok:  Seagoon, you're a coward!
Seagoon:        Only in the holiday season.
Maj. Bloodnok:  Ah, another Noel Coward!