Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!psuvax1!news
From: flee@cs.psu.edu (Felix Lee)
Newsgroups: comp.lang.perl
Subject: Sluggish patterns.
Message-ID: <f2G_hkb1@cs.psu.edu>
Date: 29 Mar 91 03:39:24 GMT
Sender: news@cs.psu.edu (Usenet)
Organization: Penn State Computer Science
Lines: 67
Nntp-Posting-Host: guardian.cs.psu.edu

I have a pattern /$cookie/ that appears in an inner loop and gets
evaluated thousands of times.  Recompiling the pattern every time is
terribly inefficient, since $cookie almost never changes.

So add an //o modifier to the pattern, right?  Nope.  $cookie might
change a few times within the loop, depending upon input.  $cookie is
only constant 99.9% of the time.

So wrap the loop in an eval, and die whenever $cookie changes.  Well,
here's the original loop:
	while (! $done) {
		&begin();
		&eat() if /$cookie/;
		&run() if /$monster/;
		&end();
	}
And here's the loop using eval and die:
	while (! $done) {
		$Cookie = $cookie;
		$Monster = $monster;
		eval q#
		while (! $done) {
			&begin();
			&eat() if /# . $cookie . q#/;
			&run() if /# . $monster . q#/;
			&end();
			die if $cookie ne $Cookie || $monster ne $Monster;
		}#;
	}
The simple loop is beginning to get lost in the fog.

But wait!  There's more!  This eval+die loop above assumes that
$cookie and $monster can only change in &end.

What if $monster changes within &eat?  You have to put a check between
the &eat and &run clauses.  But after you die, how do you resume the
inner loop?  You have to keep restart state.  The inner loop will
probably get rewritten as a state machine.

The final version bears no resemblance to the original simple loop.
What went wrong?

This can be fixed in a number of ways.  Pick one:

1.  For every varying pattern, cache a copy of its value or its
variables.

2.  Keep pointers from variables to patterns they affect, so you can
mark a pattern dirty when the variable changes.

3.  Introduce a first-class pattern object.  Something like
	\pat = /$cookie/;
will store a (compiled) pattern in \pat, which can be applied any
place a // pattern can be applied.

4.  Introduce a first-class code object.  Something like
	:code = '/$cookie/ || /$monster/';
will store (compiled) Perl code in :code, which can be used in place
of any expression.

5.  Get out your handy-dandy optimizing Perl compiler, which will
infer that $cookie is a pattern object.  This is an invisible
implementation of numbers 3 and 4 above.

Number 1 seems simplest.
--
Felix Lee	flee@cs.psu.edu