html2
Copyright (C) 2000-2012 |
Whole document tree html2
18. Performance considerations
The main design goal of
with the first three all being quite expensive and the last two being quite cheap. Note also that `unput()' is implemented as a routine call that potentially does quite a bit of work, while `yyless()' is a quite-cheap macro; so if just putting back some excess text you scanned, use `yyless()'.
Getting rid of backing up is messy and often may be an enormous amount of work for a complicated scanner. In principal, one begins by using the `-b' flag to generate a `lex.backup' file. For example, on the input
the file looks like:
The first few lines tell us that there's a scanner state in which it can make a transition on an 'o' but not on any other character, and that in that state the currently scanned text does not match any rule. The state occurs when trying to match the rules found at lines 2 and 3 in the input file. If the scanner is in that state and then reads something other than an 'o', it will have to back up to find a rule which is matched. With a bit of head-scratching one can see that this must be the state it's in when it has seen "fo". When this has happened, if anything other than another 'o' is seen, the scanner will have to back up to simply match the 'f' (by the default rule). The comment regarding State #8 indicates there's a problem when "foob" has been scanned. Indeed, on any character other than an 'a', the scanner will have to back up to accept "foo". Similarly, the comment for State #9 concerns when "fooba" has been scanned and an 'r' does not follow. The final comment reminds us that there's no point going to all the trouble of removing backing up from the rules unless we're using `-Cf' or `-CF', since there's no performance gain doing so with compressed scanners. The way to remove the backing up is to add "error" rules:
Eliminating backing up among a list of keywords can also be done using a "catch-all" rule:
This is usually the best solution when appropriate.
Backing up messages tend to cascade. With a complicated
set of rules it's not uncommon to get hundreds of
messages. If one can decipher them, though, it often only
takes a dozen or so rules to eliminate the backing up
(though it's easy to make a mistake and have an error rule
accidentally match a valid token. A possible future It's important to keep in mind that you gain the benefits of eliminating backing up only if you eliminate every instance of backing up. Leaving just one means you gain nothing.
Variable trailing context (where both the leading and
trailing parts do not have a fixed length) entails almost
the same performance loss as
is better written:
or as
Note that here the special '|' action does not provide any savings, and can even make things worse (see Deficiencies / Bugs below).
Another area where the user can increase a scanner's
performance (and one that's easier to implement) arises from
the fact that the longer the tokens matched, the faster
the scanner will run. This is because with long tokens
the processing of most input characters takes place in the
(short) inner scanning loop, and does not often have to go
through the additional work of setting up the scanning
environment (e.g.,
This could be sped up by writing it as:
Now instead of each newline requiring the processing of another action, recognizing the newlines is "distributed" over the other rules to keep the matched text as long as possible. Note that adding rules does not slow down the scanner! The speed of the scanner is independent of the number of rules or (modulo the considerations given at the beginning of this section) how complicated the rules are with regard to operators such as '*' and '|'. A final example in speeding up a scanner: suppose you want to scan through a file containing identifiers and keywords, one per line and with no other extraneous characters, and recognize all the keywords. A natural first approach is:
To eliminate the back-tracking, introduce a catch-all rule:
Now, if it's guaranteed that there's exactly one word per line, then we can reduce the total number of matches by a half by merging in the recognition of newlines with that of the other tokens:
One has to be careful here, as we have now reintroduced
backing up into the scanner. In particular, while we know
that there will never be any characters in the input
stream other than letters or newlines,
Compiled with `-Cf', this is about as fast as one can get a
A final note:
Another final note regarding performance: as mentioned
above in the section How the Input is Matched, dynamically
resizing
This document was generated by root on March, 17 2002 using texi2html |