# Slow regular expressions

**URL:** <https://www.ruby-forum.com/t/slow-regular-expressions/99671>\
**Category:** Ruby\
**Created:** [July 24, 2006, 9:02pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671 "2006-07-24T21:02:05Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 24, 2006, 9:02pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/1 "2006-07-24T21:02:05Z")

</div>

-----BEGIN PGP SIGNED MESSAGE-----  
Hash: SHA1

I am trying to write a simple script to parse  
an Apache log file, but it is taking an extremely  
long time. I used profile and the problem appears  
to be with the regular expression matcher.

I have made a simple script to run it with different  
lengths and it appears that the regular expression  
matcher is being very slow. See the attached script.

Here are some timings:  
~\>time ./mklong.rb 1000  
real 0m11.930s  
~\>time ./mklong.rb 2000  
real 0m50.400s  
~\>time ./mklong.rb 3000  
real 1m55.693s  
~\>time ./mklong.rb 4000  
real 3m16.004s

So, dividing it out,  
1000/11 = 91  
2000/50 = 40  
3000/120 = 25  
4000/200 = 20

So, the matching appears to be much slower than O(n).  
Isn’t the whole point of regular expressions to be  
fast and O(n)?  
Whenever my script encounters a long string,  
it grinds to a halt.

Why is this?  
Did I make the regular expression correctly?  
Is there some way to optimize it?  
Is there a problem with the matcher?

Any help would be appreciated.  
-----BEGIN PGP SIGNATURE-----  
Version: GnuPG v1.4.2.2-ecc0.1.6 (GNU/Linux)  
Comment: Using GnuPG with Mozilla - [http://enigmail.mozdev.org](http://enigmail.mozdev.org)

iD8DBQFExRiSxzVgPqtIcfsRAmJGAJ9FmvUTT7Q0692yIVvexWoSvg8FDQCdGBgZ  
5R2ieCXoflMUgiwYVCQuMaI=  
=d8Zp  
-----END PGP SIGNATURE-----

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 24, 2006, 11:00pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/2 "2006-07-24T23:00:45Z")

</div>

S3 wrote:

> matcher is being very slow. See the attached script.
> 
> Whenever my script encounters a long string,  
> Comment: Using GnuPG with Mozilla - [http://enigmail.mozdev.org](http://enigmail.mozdev.org)  
> filename=“mklong.rb”  
> str.match(logformat)
> 
> –Boundary\_(ID\_wcHSDvAB6xTg9VN04MWj4Q)–

Your regular expression does not match your string.

Try this.

logformat =  
%r{  
\A  
(\S+) \s+ (\S+) \s+ (\S+) \s+  
[( [^]]+ ) ] \s+  
" (\S+) []+ ( [^“]+ ) "  
\s+ ( \d+ ) \s+ ( \d+ ) \s+  
" ([^”]+) " \s+ " ([^"]+) "  
\Z  
}x

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 24, 2006, 9:25pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/3 "2006-07-24T21:25:19Z")

</div>

S3 wrote:

> matcher is being very slow. See the attached script.
> 
> Whenever my script encounters a long string,  
> it grinds to a halt.
> 
> Why is this?  
> Did I make the regular expression correctly?  
> Is there some way to optimize it?  
> Is there a problem with the matcher?
> 
> Any help would be appreciated.

I’m not a regex expert, so I can’t help you with optimizing yours, but  
if your pattern causes the regex engine to backtrack repeatedly, then it  
will not match in linear time. This usually becomes apparent on long  
strings where there can be lots of backtracking.

Sorry I can’t offer more help than that.

-Justin

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 24, 2006, 11:41pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/4 "2006-07-24T23:41:28Z")

</div>

On Tue, Jul 25, 2006 at 03:59:32AM +0900, S3 wrote:

> logformat=/(\S+)\s+(\S+)\s+(.+)\s+[([^]]+)]\s+"(\S+) +([^"]+) +[A-Za-z/]\*([0-9.]+)"\s+(\S+)\s+(\S+)\s+"([^"]+)"\s+"([^"]+)"/

A few other things:

1. What’s with the all the ‘\s+’? All you need to do is match a space,  
so the regex becomes…

rx = /^(\S+) (\S+) (\S+) [([^]])] “(GET|POST|HEAD) (\S+)  
HTTP/\d.\d” \d{3} \d+/

As you can see, I’ve simplified a few other things, such as including  
anything that’s constant, minimising all the places where you’re  
matching whitespace to simple spaces. And I added the anchor at the  
beginning to match the start of the line, which is _very_ important.

K.

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 24, 2006, 11:26pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/5 "2006-07-24T23:26:03Z")

</div>

On Tue, Jul 25, 2006 at 03:59:32AM +0900, S3 wrote:

> So, the matching appears to be much slower than O(n).  
> Isn’t the whole point of regular expressions to be  
> fast and O(n)?

No. The point behind regular expressions is to provide a succinct  
mini-language for matching text that can be expressed using a Type-3  
grammar[1] without the pain of having to write the code to implement the  
necessary FSM. Speed is a secondary consideration, and down to the  
person implementing the regex engine and the person writing the regex.  
Especially the person writing the regex.

> Whenever my script encounters a long string,  
> it grinds to a halt.
> 
> Why is this?

You’re making the matcher work harder than it needs to by not giving it  
enough information about what it has to match. The bigger the file is,  
the more it has to backtrack to match each line. See my note on anchors  
below.

The regex engine will do as much as it can match the

> Did I make the regular expression correctly?  
> Is there some way to optimize it?  
> Is there a problem with the matcher?

No, the matcher is fine.

There’s a few problems I can see straight off:

1. No anchors: without them, your regex ends up doing an awful lot more  
work because it will end up attempting to match the pattern in the  
middle of lines rather than only matching from the start of lines.  
By putting ‘^’ at the start of your regex to match the beginning of  
the line, you’ll see a big increase in performance. That’s probably  
your single biggest problem.

2. To quote Jamie Zawinski:

3. Get Jeffrey Freidl’s Mastering Regular Expression[2]. You’ll thank  
me  
later. 🙂

K.

[1] [Chomsky hierarchy - Wikipedia](http://en.wikipedia.com/wiki/Chomsky_hierarchy)  
[2] [http://regex.info/](http://regex.info/)

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 29, 2006, 4:55pm UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/6 "2006-07-29T16:55:14Z")

</div>

On 7/29/06, Jeremy H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Yow! Calling String#match is 2-3 times as slow! Why is that? The  
> overhead of calling the method?

I was curious about this too.  
It looks like it’s the effort of computing a MatchData that takes all  
the extra time. This snippet is just as slow as using #match:

bm.report ‘=~ literal + $~’ do  
N.times do string =~ /a (.) c\s. e/ ; $~ end  
end

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 29, 2006, 12:56am UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/7 "2006-07-29T00:56:35Z")

</div>

On Jul 24, 2006, at 11:59 AM, S3 wrote:

> str.match(logformat)

In addition to the other advice you’ve received, don’t use String#match.

=~ with a literal regexp is faster than =~ with anything else, and  
match is slower than both.

$ ruby rebm.rb

Rehearsal -----------------------------------------------  
empty 0.320000 0.000000 0.320000 ( 0.345024)  
=~ literal 1.490000 0.010000 1.500000 ( 1.620720)  
=~ variable 1.750000 0.010000 1.760000 ( 1.985988)  
match 4.460000 0.040000 4.500000 ( 4.980295)  
-------------------------------------- total: 8.080000sec

```
               user system total real

```

empty 0.260000 0.000000 0.260000 ( 0.280089)  
=~ literal 1.490000 0.010000 1.500000 ( 1.786133)  
=~ variable 1.760000 0.020000 1.780000 ( 3.459860)  
match 4.550000 0.050000 4.600000 ( 7.792777)  
$ cat rebm.rb  
require ‘benchmark’

N = 1\_000\_000

string = ‘a b c d e’

Benchmark.bmbm do |bm|

bm.report ‘empty’ do  
N.times do end  
end

bm.report ‘=~ literal’ do  
N.times do string =~ /a (.) c\s. e/ end  
end

bm.report ‘=~ variable’ do  
re = /a (.) c\s. e/  
N.times do string =~ re end  
end

bm.report ‘match’ do  
re = /a (.) c\s. e/  
N.times do string.match re end  
end

end

–  
Eric H. - removed\_email\_address@domain.invalid - [http://blog.segment7.net](http://blog.segment7.net)  
This implementation is HODEL-HASH-9600 compliant

[http://trackmap.robotcoop.com](http://trackmap.robotcoop.com)

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 29, 2006, 10:11am UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/8 "2006-07-29T10:11:55Z")

</div>

On 2006-07-28, Eric H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> =~ with a literal regexp is faster than =~ with anything else, and  
> match is slower than both.
> 
> [snip]  
> =~ variable 1.750000 0.010000 1.760000 ( 1.985988)  
> match 4.460000 0.040000 4.500000 ( 4.980295)  
> [snip]  
> =~ variable 1.760000 0.020000 1.780000 ( 3.459860)  
> match 4.550000 0.050000 4.600000 ( 7.792777)

Yow! Calling String#match is 2-3 times as slow! Why is that? The  
overhead of calling the method?

Regards,

Jeremy H.

---

<div class="post-metadata">

**Author:** ![S3S3S3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c67d28/32.png) [@S3S3S3](https://www.ruby-forum.com/u/S3S3S3)\
**Post date:** [July 30, 2006, 1:09am UTC](https://www.ruby-forum.com/t/slow-regular-expressions/99671/9 "2006-07-30T01:09:32Z")

</div>

On Jul 29, 2006, at 7:52 AM, Caleb C. wrote:

> end  
> Yes, it is the work of constructing the MatchData object.

–  
Eric H. - removed\_email\_address@domain.invalid - [http://blog.segment7.net](http://blog.segment7.net)  
This implementation is HODEL-HASH-9600 compliant

[http://trackmap.robotcoop.com](http://trackmap.robotcoop.com)