[apparmor] [PATCH 02/11] Speed up dfa generation by using hashing in set comparison

[Steve Beattie]

On Mon, Oct 18, 2010 at 05:20:34PM -0700, John Johansen wrote:
> Convert Nodemap comparision to use a hash value.  This uses a little more
> memory than just using the NodeSet size to short circuit comparison but it
> improves on the case where compared sets have the same size.  It is possible
> that this will slow down small dfa generation slightly but the trade off for
> large dfa's (which are the slow ones to generate) is worth it.
> 
> This results in another performance bump over using the NodeSize is NodeSet
> comparison, and the amount of improvement increases with larger dfas

> @@ -1490,7 +1502,8 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
>  		/* check the default transition first */
>  		if (cases.otherwise) {
>  			State *target;
> -			update_for_nodes(cases.otherwise, target);
> +			pair <unsigned long, NodeSet *> index = make_pair (hash_NodeSet(cases.otherwise), cases.otherwise);
> +			update_for_nodes(index, target);
>  			from->cases.otherwise = target;
>  		}
>  
> @@ -1500,7 +1513,8 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
>  		for (NodeCases::iterator j = cases.begin(); j != cases.end();
>  		     j++) {
>  			State *target;
> -			update_for_nodes(j->second, target);
> +			pair <unsigned long, NodeSet *> index = make_pair(hash_NodeSet(j->second), j->second);
> +			update_for_nodes(index, target);
>  			/* Don't insert transition that the default transition
>  			 * already covers
>  			 */

ACK, though would it make sense to lift the index generation into the
update_for_nodes() macro definition?

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
Url : https://lists.ubuntu.com/archives/apparmor/attachments/20101021/9b218705/attachment.pgp