[apparmor] [RFC/patch] parser: reduce virtual_cast<> calls when normalizing tree

[John Johansen]

On 04/05/2011 05:36 PM, Steve Beattie wrote:
> With the prior patch set fixing how the parser is built so that gprof
> profiling could work, I went ahead and did a few experiments with it.
> One of the surprising results (to me, anyway) was that in synthetic
> sample workloads, the parser was spending fully 40% of its time in
> dynamic_cast<> calls in the dfa library.
>
Its actually worse than that some times, profile it with the 1000
hat work load

 
> The attached patch I'm submitting for comment and consideration,
> particularly by jjohansen, as it is a start in a direction of trying
> to reduce the amount of usage of dynamic_cast<>s by pushing recursive
> or iterative function logic into the Node classes themselves,
> so as to eliminate a number of the type tests (which is what the
> dynamic_cast<> calls are doing). Is it both an acceptable direction to
> take structurally and stylistically? I don't want to continue down this
> path if it hampers jjohansen's understanding of the data structures.
> 
> In non-rigorous benchmarking, again with synthetic workloads
> (generated by the parser stress test), I see roughly 10-15% overall
> reduction in the amount of time to parse, generate, and compress a
> given profile set.
> 

NAK,

This is the direction is right, but I am going to NAK it.  Basically it
collides with the rewrite of this section, which I am about 10 patches into
(otherwise it would have been an ACK).

It does do a similar things but the whole structure of the code is being
reworked.  The recursive + iterative normalize and factorize until the
tree is stable is horribly inefficient (as seen in the 1000 hat work load).

Instead we are moving to an algorithm where every alt subtree is flattened,
sorted, merged and then factored.  This moves the similar item search to
O(nlog(n)) instead of O^2, and also removes the need handle the alternate
direction at the end of the tree search.

Bringing in the full character to character class merging will also let
us drop the number of nodes in the nodesets used to construct the dfa,
which will speed the construction up and reduce memory usage at the same
time.

I guess /me should start pushing some of these changes/cleanups out
for review.  I'll see if I can't get the first few patches cleaned up
and pushed out tonight.