Use `std::unordered_map<int, int>` for `StdIntMap`.
When using `std::map<int, int>`, profiling shows a hotspot in the
iteration in `PrefilterTree::PropagateMatch()`. Application-level
benchmarks indicate that changing maps produces a noticeable win.
Change-Id: I0a7c43de254642b8ccd188cc93eff4d08d3c10fd
Reviewed-on: https://code-review.googlesource.com/c/re2/+/59990
Reviewed-by: Perry Lorier <perryl@google.com>
Reviewed-by: Paul Wankadia <junyer@google.com>
diff --git a/re2/prefilter_tree.cc b/re2/prefilter_tree.cc
index fdf4e08..b483b2e 100644
--- a/re2/prefilter_tree.cc
+++ b/re2/prefilter_tree.cc
@@ -67,7 +67,6 @@
compiled_ = true;
- // TODO(junyer): Use std::unordered_set<Prefilter*> instead?
NodeMap nodes;
AssignUniqueIds(&nodes, atom_vec);
diff --git a/re2/prefilter_tree.h b/re2/prefilter_tree.h
index 5d73074..aa8f913 100644
--- a/re2/prefilter_tree.h
+++ b/re2/prefilter_tree.h
@@ -18,6 +18,7 @@
#include <map>
#include <string>
+#include <unordered_map>
#include <vector>
#include "util/util.h"
@@ -59,7 +60,9 @@
private:
typedef SparseArray<int> IntMap;
- typedef std::map<int, int> StdIntMap;
+ typedef std::unordered_map<int, int> StdIntMap;
+ // TODO(junyer): Use std::unordered_set<Prefilter*> instead?
+ // It should be trivial to get rid of the stringification...
typedef std::map<std::string, Prefilter*> NodeMap;
// Each unique node has a corresponding Entry that helps in