breaking up regular expressions

If you're like me, you probably have a line in your ubhrc like this:

OPT_X = stupid|boring|offensive

and if you're like me, it probably gets longer and longer and makes
inclusion/exclusion processing take a very long time.

It turns out that in Perl, splitting it up into three regular expressions
makes it a lot faster. ie.

if (/stupid/ || /boring/ || /offensive/) { ... }

runs over ten times faster than

if (/stupid|boring|offensive/) { ... }

and has the same result. To demonstrate this, I've attached a short benchmark
program. Run it with a UBH2 cache file as the command-line argument.

Here's my results:
Benchmark: timing 20 iterations of plain, split, splitstudy...
     plain: 25 wallclock secs (23.26 usr +  0.27 sys = 23.53 CPU) @  0.85/s (n=20)
     split:  2 wallclock secs ( 1.82 usr +  0.01 sys =  1.83 CPU) @ 10.93/s (n=20)
splitstudy:  4 wallclock secs ( 3.46 usr +  0.06 sys =  3.52 CPU) @  5.68/s (n=20)

I ran it with a cache file around 9M in size--if your cache file is a lot
smaller or bigger, you'll need to change the number of iterations.

You can of course modify this benchmark to use your actual OPT_X or OPT_I
regular expression so you can see how much breaking it up would benefit you.

The benchmark also tests the effect of using study(); I found it gave around
4% benefit for my own regular expression when broken up, but makes things a
lot slower when there's only a few strings to match.

The problem, of course, is that there's no way to specify a broken-up regular
expression in the config file. So I'm posting to gather some ideas before I go
ahead and hack up my own implementation.

Here are my ideas:

a) Automatically break regular expressions where we see a | that is not within
brackets. This would be easiest for users if it worked, but I think it would
go wrong a lot of the time.

OPT_X = stupid|boring|offensive

or b) Break regular expressions if the user puts || inside them. This would
mean existing config files would continue to work, but users could get a speed
boost by modifying the expression.

OPT_X = stupid||boring||offensive

The downside is that it's a totally non-standard syntax, and there's a small
chance an existing regular expression could contain something like
\|stupid\||\[dumb\] and break.

or c) Change the syntax to be a Perl expression rather than a regular
expression, ie.

OPT_X = /stupid/ || /boring/ || /offensive/

This would mean everyone who's using OPT_X or OPT_I would have to change their
config files. It's also a lot more typing than b). The benefit is that it
looks very familiar to people who know Perl, and you could even do things
other than regexps, eg.

OPT_X = /\"(.*\.mp3)/i && -e "group/$1"

or if you found your expression benefitted from study:

OPT_X = (study&&0) || /stupid/ || /boring/ || /offensive/ || ...


I initially favoured option b), but the more I think about it, the more I
prefer c), since UBH 3 means everyone has to change their config anyway.

Regardless of the config file format, the simplest implementation (avoiding
using eval every time), would be to replace

            if ((defined $opt{'I'} && $title !~ /$opt{'I'}/o) ||
	                    (defined $opt{'X'} && $title =~ /$opt{'X'}/o)) {
			    
with

if (should_be_excluded($title)) {

and then generate the function 'should_be_excluded' at runtime using eval. The
disadvantage is that the function call itself has significant overhead. The
alternative is to replace the entire surrounding loop with a function
generated at runtime. That would be a lot faster, but make the code
considerably more complex and hard to maintain.

Since some people have been talking about moving the regular expressions into
SQL, I investigated this too. I discovered:

1) MySQL regexps are really ugly. It took me about 10 minutes to rewrite my
OPT_X expression for MySQL.
2) They are around 4 times slower than Perl's (even when Perl is getting the
data to match from MySQL!)
3) MySQL executes:

select count(*) from headers where subject regexp binary 'stupid' or subject
regexp binary 'boring' or subject regexp binary 'offensive';

around 5 times quicker than:

select count(*) from headers where subject regexp binary 'stupid|boring|offensive';

Adam

-- 
Adam Rice -- [email protected] -- Blackburn, Lancashire, England

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Save up to 80% on top-quality inkjet cartridges and get your order fast!
FREE shipping on orders $50 or more to the US & Canada. Shop at Myinks.com!
http://www.c1tracking.com/l.asp?cid=5511
http://us.click.yahoo.com/v2G7ND/KfUGAA/ySSFAA/IHFolB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
[email protected]

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

#!/usr/local/bin/perl -w

use strict;
use Benchmark;

my(@subjects);

while (<>) {
    chomp;
    s/^.*\|//;
    push(@subjects, $_);
}

timethese(20, {
	      "plain" => mek(q{/stupid|boring|offensive/}),
	      "split" => mek(q{/stupid/ || /boring/ || /offensive/}),
	      "splitstudy" => mek(q{(study&&0)||/stupid/ || /boring/ || /offensive/}),
	     });

sub mek {
    my($code) = @_;
    return eval "sub { scalar(grep($code, \@subjects)) }";
}