Stan Hoeppner:
> So, the question is, which form of expression processes the "does not
> match" case faster? The fully qualified expression, or the simple
> expression? Noel mentioned that the fully qualified expressions will
> tend to process faster. Is this true? Is it true for both the
> "matches" and "does not match" case?
I would expect better performance when patterns only match the text
that needs to be matched.
If you must match a very large numbers of patterns, you need an
implementation that transforms N patterns into one deterministic
automaton. This can match 1 pattern in the same time as N patterns.
Once the automaton is built (which takes some time) it is blindingly
fast. An example of such an implementation is flex.
Similar optimizations are needed for large CIDR maps. Right now,
Postfix's linear search does 10^8 patterns/s. With this, postscreen
can search the largest ipdeny.com file in 1ms on a modern CPU,
which is sufficient for the moment. To make it fast, the CIDR
entries need to be arranged into a tree that can be traversed in
log(N) time.
Wietse
