Speed improvements to SubstringSetMatcher

extensions/common/matcher/substring_set_matcher.h

Index: extensions/common/matcher/substring_set_matcher.h
diff --git a/extensions/common/matcher/substring_set_matcher.h b/extensions/common/matcher/substring_set_matcher.h
index 4ba8ec3acc364413a3f6dc16c25e9ed5db7f57b9..f4b9d2dd076c5bd26fc42a90538013dba874ceca 100644
--- a/extensions/common/matcher/substring_set_matcher.h
+++ b/extensions/common/matcher/substring_set_matcher.h
@@ -5,6 +5,7 @@
 #ifndef EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 #define EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 
+#include <limits>
 #include <map>
 #include <set>
 #include <string>
@@ -80,21 +81,22 @@ class SubstringSetMatcher {
   class AhoCorasickNode {
    public:
     // Key: label of the edge, value: node index in |tree_| of parent class.
-    typedef std::map<char, int> Edges;
+    typedef std::map<char, unsigned> Edges;
     typedef std::set<StringPattern::ID> Matches;
 
+    static const unsigned kNoSuchEdge = ~0;
+
     AhoCorasickNode();
     ~AhoCorasickNode();
     AhoCorasickNode(const AhoCorasickNode& other);
     AhoCorasickNode& operator=(const AhoCorasickNode& other);
 
-    bool HasEdge(char c) const;
-    int GetEdge(char c) const;
-    void SetEdge(char c, int node);
+    unsigned GetEdge(char c) const;
+    void SetEdge(char c, unsigned node);
     const Edges& edges() const { return edges_; }
 
-    int failure() const { return failure_; }
-    void set_failure(int failure) { failure_ = failure; }
+    unsigned failure() const { return failure_; }
+    void set_failure(unsigned failure) { failure_ = failure; }
 
     void AddMatch(StringPattern::ID id);
     void AddMatches(const Matches& matches);
@@ -105,12 +107,16 @@ class SubstringSetMatcher {
     Edges edges_;
 
     // Node index that failure edge leads to.
-    int failure_;
+    unsigned failure_;
 
     // Identifiers of matches.
     Matches matches_;
   };
 
+  typedef std::map<StringPattern::ID, const StringPattern*>
+      SubstringPatternSet;
+  typedef std::vector<const StringPattern*> SubstringPatternVector;

[vabr (Chromium), 2013/05/05 23:36:49]

While adding the new typedef I also moved this according to
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Declaration_Order

+
   void RebuildAhoCorasickTree();
 
   // Inserts a path for |pattern->pattern()| into the tree and adds
@@ -121,9 +127,9 @@ class SubstringSetMatcher {
 
   // Set of all registered StringPatterns. Used to regenerate the
   // Aho-Corasick tree in case patterns are registered or unregistered.
-  typedef std::map<StringPattern::ID, const StringPattern*>
-      SubstringPatternSet;
   SubstringPatternSet patterns_;
+  // Copy of |patterns_| sorted by the pattern string.
+  SubstringPatternVector sorted_patterns_;

[vabr (Chromium), 2013/05/05 23:36:49]

I guess once I create the vector, it might be easier to use it also for
iterating over all rules, where I don't need the map. I guess we could also get
rid of the map, re-creating it locally in the register&unregister method, but I
don't think this is performance relevant, rather for memory.

 
   // The nodes of a Aho-Corasick tree.
   std::vector<AhoCorasickNode> tree_;