Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2953

Re: How can the speed of a scanner be independent of the number of rules?

Show all headers | View raw

I see that Kaz Kylheku has written a thought out and well-reasoned
response.  However, it isn't based upon actual analysis of data and
uses a strawman that I reject having done (while at Intel) such an
analysis while designing a register expression acceleration chip.

So, let me first deal with the strawman.

> None of these rules take precedence over the 10 rules, and so the input is handled by the same rules.

That assumption is not necessary.  Even if the input is distributed
over all 1000 rules, the performance will still be substantially the
same.  This is due to the use of a DFA.  In a DFA, the speed is
constant because the same code handles each state, roughly something
like this.

s := initial state;
forever() do {
   c := new character from input;
   s := new state[c];
   if (s == end of token) return token;
   token :+= c;
  }

On most modern computers, the cost is dominated by the cost to fetch
(via an indirect/indexed access) the next state.  Now, cache effects
can impact this, but most modern caches are large enough that this is
a negligible effect.  Moreover, it is possible to consider the case
where all cache probes are misses and it goes to memory.  Although,
that is significantly slower, it is still constant, and more
importantly the ratio of cache hits to misses is essentially also a
constant ratio.  Only if you are increasing the size of the DFA to the
point where it starts approaching (or exceeding) the cache size does
this become an issue.  That would be the "knee" Kaz mentioned. 1000
tokens is usually not sufficient to do that.

As I mentioned we measured this at Intel, not only for programming
lexers but also for Snort, where the number of regular expressions is
much larger.  We even looked at ClamAV where we considered making our
regular expression engine into a tool to calculate the "signatures"
(essentially performing a cryptographic hash).  Moreover, this goes to
the argument that hashing algorithms are essentially O(1).

Now, theory and practice don't always precisely line up, so in a real
application, one would benchmark to verify this, but over a large
range of regular expression sets, I have found it to hold, having done
that benchmarking.

This leads to another experiment we did at Intel as part of the
Hyperscan software effort.  Hyperscan is generally a Glushkov inspired
NFA engine, but when possible (i.e. the DFAs are small enough) it does
subset construction to turn them into DFAs.  However, when the DFAs
are too large, the construction fails and it falls back to the NFA
engine.  Because DFAs can be significantly faster than NFAs, we wanted
an algorithm that allowed us to split an NFA into a small set  of
parallel DFAs (8 or fewer).  To be practical though, we did not want
the overhead of threads running on multiple cores accessing the same
input data.  That would in many cases have completely eroded the DFA
performance boost.  So, I was tasked with finding a way of running 8
threads in one thread, by interleaving the code of them.   From the
above code and analysis, we know the issue is that next state fetch,
and dependencies of it on the statements before and after it.  Even
with a cache hit, this is longer than the instruction pipeline.  So,
the answer was to move the dependencies away from each other allowing
the fetch to occur and doing other work in the pipeline in the
meantime.  With the help of VTune this was achieved.  We got our 8
parallel DFAs to operate in the same time, it took to execute a single
DFA.  Note that this was achieved without the use of any assembly
language coding.  Our code was still portable C code with no compiler
specific features.

The last point I want to make in this regard is that in most cases,
regular expressions, tend to have a "bushy" part where the code fans
out to a variety of states, but much larger "skinny" parts, where
generally only a few (usually only 1, following a variation on Zipf's
distribution law) possible out going transitions.  This is
particularly easy to see if you are doing something like the
Aho-Corasick algorithm, where the fanout is usually concentrated in
the first few (often 2 or 3) states at the head of the algorithm, the
initial state and its successors.  The regular expression hardware we
built was actually optimized for this property, with a fast dispatch
for the head states and then threads for the tail states.  (If you can
read patent-ese language, you can tease out the details. I found that
challenging despite being the original author of the idea.)

--------

Now, having hopefully covered most of the reasons why with a DFA, the
worry is mostly unfounded.  I want to go over the other case.
Particularly as it applies to mistakes one can make.  This most often
occurs in hand-written parsers and or lexers.

First, I want to note that the LR(0) machine construction algorithm is
essentially a variation on the subset construction algorithm.  That
means that your LR machine essentially has a DFA inside it.  This is
scary to many people as they aren't used to reading state machines,
this is compounded when the tables are "compressed".  However, despite
that the same effect holds.  The running time of an LR parser is still
generally linear in the input length and each state transition is
O(1).

Aside: with GLR parsers and parse forests, this guarantee is somewhat
eroded, but it is usually still acceptable as it is often only eroded
over short ambiguous stretches.  And here is where my understanding of
the theory reaches its boundary.  I think in the worst case, it still
has O(n**3) complexity based upon a German theory paper I attempted
unsuccessfully to read completely.  Naively, it seems that the bound
should be n**2, but I cannot do the calculations to prove that and the
paper seemed to have good evidence for its bound, i.e. that the
forests could grow at n**2 at each new token, rather than just n.

So, how does a naive implementation break this?  Many recursive
descent parsers don't use a computed goto (case statement with an
integer selector) to do the dispatch.  Instead, they use a series of
if statements.  The result is that you have now linearized the lookup
and you need an average of n/2 comparisons to find the next state.
That means the next state lookup is no longer O(1), but O(n).

You sometimes also see this in keyword lookup.  They do so by
comparing the text to a sequence of strings to determine whether the
token is a keyword or not.  Again, you have introduced an O(n) factor
by serializing the comparison.  Now, if the list is not long, this
factor isn't sufficient to impact the total performance, but it is
performance left on-the-table.  The sequence of ifs may be easier to
read than a state machine, but that is their only advantage.  Thus, if
you want to speed your keyword lookup up, use a simple hashing
algorithm so that the hash cost is low, but then you have only a
limited number of keywords (in each bucket) to compare to.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How can the speed of a scanner be independent of the number of rules? Roger L Costello <costello@mitre.org> - 2022-03-23 18:49 +0000
  Re: How can the speed of a scanner be independent of the number of rules? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-03-23 21:27 +0000
    Re: How can the speed of a scanner be independent of the number of rules? gah4 <gah4@u.washington.edu> - 2022-03-23 19:57 -0700
    Re: How can the speed of a scanner be independent of the number of rules? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-24 13:12 +0200
    Re: How can the speed of a scanner be independent of the number of rules? Roger L Costello <costello@mitre.org> - 2022-03-24 11:53 +0000
      Re: How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 11:56 -0700
        Re: How can the speed of a scanner be independent of the number of rules? gah4 <gah4@u.washington.edu> - 2022-03-24 13:08 -0700
  Re: How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 02:01 -0700
    Re: Parallel scanning, was How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 11:18 -0700
      Parallel lexers by chunking the input Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-24 22:32 +0200
        Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-25 08:04 +0000
          Re: Parallel lexers by chunking the input gah4 <gah4@u.washington.edu> - 2022-03-25 07:58 -0700
          Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-25 17:47 +0000
            Parallel lexers by chunking the input. Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-26 00:36 +0200
            Parallel lexers by chunking the input Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-26 01:00 +0200
            Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-26 09:27 +0000

csiph-web