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

[John Johansen]

On 10/21/2010 10:48 PM, Steve Beattie wrote:
> 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?
> 
yep, I'll do that thanks