flee@cs.psu.edu (Felix Lee) (03/29/91)
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.eduworley@compass.com (Dale Worley) (04/02/91)
X-Name: Felix Lee
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.
Well, here's the original loop:
while (! $done) {
&begin();
&eat() if /$cookie/;
&run() if /$monster/;
&end();
}
The usual solution runs along the lines:
$cookie = ...;
$monster = ...;
eval "sub cookie { &eat() if /$cookie/o; }";
eval "sub monster { &run() if /$monster/o; }";
while (! $done) {
&begin();
&cookie;
&monster;
&end();
}
Now, anytime $cookie is changed, reexecute the first eval, and anytime
$monster is changed, reexecute the second eval.
If there was only one pattern searched for in the loop, you could
exploit the fact that // reuses the previous pattern.
Dale
Dale Worley Compass, Inc. worley@compass.com
--
Heard on "The Daily Feed", a syndicated political satire radio
program:
Saddam Hussein is not Hitler; if he were, France would have surrendered
by now.flee@cs.psu.edu (Felix Lee) (04/05/91)
> eval "sub cookie { &eat() if /$cookie/o; }"; > eval "sub monster { &run() if /$monster/o; }"; > while (! $done) { > &begin(); > &cookie; > &monster; > &end(); > } Okay. Now how do you make it recursive? sub ctw { local($cookie, $monster) = @_; while (! $done) { &eat() if /$cookie/; &run() if /$monster/; } } $cookie and $monster change infrequently, but they may change in either &eat or &run. Either &eat or &run may call &ctw recursively with random parameters. It doesn't look very hard to change Perl so it does a cheap string compare before it recompiles run-time patterns. -- Felix Lee flee@cs.psu.edu
worley@compass.com (Dale Worley) (04/06/91)
From: flee@cs.psu.edu (Felix Lee)
Okay. Now how do you make it recursive?
sub ctw {
local($cookie, $monster) = @_;
while (! $done) {
&eat() if /$cookie/;
&run() if /$monster/;
}
}
$cookie and $monster change infrequently, but they may change in
either &eat or &run. Either &eat or &run may call &ctw recursively
with random parameters.
The following code comes to mind, although I don't know if it is correct:
$old_cookie = $old_monster = 'something invalid';
sub ctw {
local($cookie, $monster) = @_;
local($old_cookie, $old_monster);
local(*cookie, *monster);
while (! $done) {
eval "sub cookie { &eat() if /$cookie/o; }"
if $cookie ne $old_cookie;
&eat() if /$cookie/;
eval "sub monster { &run() if /$monster/o; }"
if $monster ne $old_monster;
&run() if /$monster/;
}
}
When a recursive call of ctw occurs, &cookie and &monster are saved,
along with $old_cookie and $old_monster.
Dale
Dale Worley Compass, Inc. worley@compass.com
--
He divines remedies against injuries; he knows how to turn serious accidents
to his own advantage; whatever does not kill him makes him stronger.
-- Friedrich Nietzscheflee@cs.psu.edu (Felix Lee) (04/07/91)
> local(*cookie, *monster); [...] > eval "sub cookie { &eat() if /$cookie/o; }" > if $cookie ne $old_cookie; Yes, I thought about something like that, but using local to create local versions of subroutines is somewhat frightening. Perl has a nasty habit of dumping core when you play games with references. Someday, I have to try building higher-order functions in Perl. *sin2 = &compose(*sin, *sqr); print &sin2($pi/4); -- Felix Lee flee@cs.psu.edu