2008-10-01 Regexp Compilation Not An Issue

I was looking at an Oddmuse wiki with 3741 pages and ran time perl wiki.pl search=fnord raw=1 a few times. It took 1.502 seconds on the second run (the first one runs into disk caching issues). Then I rewrote the SearchString code to compile regular expressions and take it out of the loop. The second search took about 1.480 seconds. Talk about minimal gain!

This is disappointing. RadomirDopieralski pointed me to Regular Expression Matching Can Be Simple And Fast by Russ Cox. Maybe that explains why Daniel MacKay’s fix to Oddmuse search using grep as a filter is so much faster than the standard Oddmuse search.

sub SearchTitleAndBody {
  my ($query, $func, @args) = @_;
  # skip null entries, compile regular expressions
  my @regexps = map { qr/$_/i } grep /./, $query =~ /\"([^\"]+)\"|(\S+)/g;
  my @found;
  my $lang = GetParam('lang', '');
  foreach my $id (AllPagesList()) {
    my $name = NormalToFree($id);
    my ($text) = PageIsUploadedFile($id); # set to mime-type if this is an uploaded file
    if (not $text) { # not uploaded file, therefore allow searching of page body
      OpenPage($id); # this opens a page twice if it is not uploaded, but that's ok
      if ($lang) {
	my @languages = split(/,/, $Page{languages});
	next if (@languages and not grep(/$lang/, @languages));
      }
      $text = $Page{text};
    }
    if (SearchString($name . "\n" . $text, @regexps)) {
      push(@found, $id);
      &$func($id, @args) if $func;
    }
  }
  return @found;
}

sub SearchString {
  my $data = shift;
  foreach my $regexp (@_) {
    return 0 unless ($data =~ /$regexp/);
  }
  return 1;
}

I think Radomir is right when he says that Perl probably caches all the regular expressions anyway so there is very little time wasted in the original loop.

Then again, it seems that regular expressions are not the problem. I returned to the old code and tried index($data, $str) >= 0 instead of ($data =~ /$str/i) but got no gain at all. Gaah!

sub SearchTitleAndBody {
  my ($string, $func, @args) = @_;
  my @found;
  my $lang = GetParam('lang', '');
  foreach my $id (AllPagesList()) {
    my $name = NormalToFree($id);
    my ($text) = PageIsUploadedFile($id); # set to mime-type if this is an uploaded file
    if (not $text) { # not uploaded file, therefore allow searching of page body
      OpenPage($id); # this opens a page twice if it is not uploaded, but that's ok
      if ($lang) {
	my @languages = split(/,/, $Page{languages});
	next if (@languages and not grep(/$lang/, @languages));
      }
      $text = $Page{text};
    }
    if (SearchString(uc($string), uc($name . "\n" . $text))) {
      push(@found, $id);
      &$func($id, @args) if $func;
    }
  }
  return @found;
}

sub SearchString {
  my ($string, $data) = @_;
  my @strings = grep /./, $string =~ /\"([^\"]+)\"|(\S+)/g; # skip null entries
  foreach my $str (@strings) {
    return 0 unless index($data, $str) >= 0;
  }
  return 1;
}

I must therefore assume that for the simple regular expression I’m using the regular expression machinery is not the limiting factor. It must be page opening or page parsing or something like that.

I then tried to avoid parsing the page itself. OpenPage now takes an argument to shortcut:

sub OpenPage {      # Sets global variables
  my ($id, $raw) = shift;
  return if $OpenPageName eq $id;
  $OpenPageName = $id;
  if ($IndexHash{$id}) {
    my $data = ReadFileOrDie(GetPageFile($id));
    return $data if $raw; # must call ParseData later!
    %Page = ParseData($data);
  } else {
    %Page = ();
    $Page{ts} = $Now;
    $Page{revision} = 0;
    if ($id eq $HomePage and (open(F, $ReadMe) or open(F, 'README'))) {
      local $/ = undef;
      $Page{text} = <F>;
      close F;
    } elsif ($CommentsPrefix and $id =~ /^$CommentsPrefix(.*)/o) { # do nothing
    }
  }
}

And I use this in a version similar to the very first copy of the code except that I call SearchString twice:

    if (not $text) { # not uploaded file, therefore allow searching of page body
      my $data = OpenPage($id, 1); # this may open a page twice if not uploaded
      next unless SearchString($name . "\n" . $data, @regexps); # shortcut
      %Page = ParseData($data); # avoid parsing page data
      if ($lang) {
	my @languages = split(/,/, $Page{languages});
	next if (@languages and not grep(/$lang/, @languages));
      }
      $text = $Page{text};
    }
    if (SearchString($name . "\n" . $text, @regexps)) {
      push(@found, $id);
      &$func($id, @args) if $func;
    }

This reduced the time used by a bit more than 2%. How disappointing.

Tags:

Comments

wow, thanks for doing those tests and posting the results, Alex — maybe the current search code is “close enough” to optimal that we shouldn’t worry about tuning it any more ...

Mark Zimmermann 2008-10-02 01:43 UTC


Well, the only strange thing is that if you run perl -d:DProf wiki.pl search=fnord raw=1; dprofpp you’ll see that around a third of the time is spent in ParsePage. There must still be ways to gain a significant advantage.

AlexSchroeder 2008-10-02 04:49 UTC


Based on an old idea by Daniel MacKay I tried the following:

<   foreach my $id (AllPagesList()) {
---
>   foreach my $id (GrepFiltered($string, AllPagesList())) {

and

sub GrepFiltered { # grep is so much faster!!
  my ($string, @pages) = @_;
  return @pages unless $UseGrep;
  my @result;
  my $regexp = quotemeta join '|', map { index($_,'|') == -1 ? $_ : "($_)" }
    grep /./, $string =~ /\"([^\"]+)\"|(\S+)/g; # this acts as OR
  open(F,"grep -l -i $regexp $PageDir/*/*.pg|");
  while (<F>) {
    if (m/.*\/(.*)\.pg/) {
      push(@result, $1);
    }
  }
  close(F);
  return @result;
}

And guess what? time perl wiki.pl search=fnord raw=1 runs in 0.375 secs. That’s about ¼ of the original running time!

Grep does in fact rule over Perl.

AlexSchroeder 2008-10-02 22:17 UTC


wow, Alex! — a factor of 4 is huge ... hmmm ... I must study the above code ... any chance it could sneak into some future Oddmuse version? (I’m still running 1.835 — apologies, I know I need to update it!)

Mark Zimmermann 2008-10-05 11:41 UTC


I immediately added it to the latest and greatest version of Oddmuse. :D

AlexSchroeder 2008-10-05 13:34 UTC


Please make sure you contribute only your own work, or work licensed under the GNU Free Documentation License. Note: in order to facilitate peer review and fight vandalism, we will store your IP number for a number of days. See Privacy Policy for more information. See Info for text formatting rules. You can edit the comment page if you need to fix typos. You can subscribe to new comments by email without leaving a comment.

To save this page you must answer this question:

Please say HELLO.