[apparmor] [PATCH 01/11] Speed up DFA creation by including setsize in comparison

[Seth Arnold]

Ha! Good idea.
-----Original Message-----
From: John Johansen <john.johansen at canonical.com>
Sender: apparmor-bounces at lists.ubuntu.com
Date: Mon, 18 Oct 2010 17:20:33 
To: <apparmor at lists.ubuntu.com>
Subject: [apparmor] [PATCH 01/11] Speed up DFA creation by including set
	size in comparison

Use set size as part of set comparison, short circuiting comparing sets
of pointers when it isn't necessary.  This results in a nice little
performance increase in dfa creation.
---
 parser/libapparmor_re/regexp.y |    9 +++++++--
 1 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/parser/libapparmor_re/regexp.y b/parser/libapparmor_re/regexp.y
index e1bbbfd..e19214d 100644
--- a/parser/libapparmor_re/regexp.y
+++ b/parser/libapparmor_re/regexp.y
@@ -1300,13 +1300,18 @@ void dump_syntax_tree(ostream& os, Node *node) {
 }
 
 /* Comparison operator for sets of <NodeSet *>.
- * Do compare pointer comparison on set of <Node *>, the pointer comparison
+ * Compare set sizes, and if the sets are the same size
+ * do compare pointer comparison on set of <Node *>, the pointer comparison
  * allows us to determine which Sets of <Node *> we have seen already from
  * new ones when constructing the DFA.
  */
 struct deref_less_than {
   bool operator()(NodeSet * const & lhs, NodeSet * const & rhs) const
-  { return *lhs < *rhs; }
+  { if (lhs->size() == rhs->size())
+      return *lhs < *rhs;
+    else
+      return lhs->size() < rhs->size();
+  }
 };
 
 class State;
-- 
1.7.1


-- 
AppArmor mailing list
AppArmor at lists.ubuntu.com
Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor