diff --git a/staptree.cxx b/staptree.cxx
index cc2127207..e311e0173 100644
--- a/staptree.cxx
+++ b/staptree.cxx
@@ -21,6 +21,7 @@
 #include <vector>
 #include <algorithm>
 #include <cstring>
+#include <unordered_map>

 using namespace std;

@@ -423,46 +424,61 @@ bool memo_tagged_p (const interned_string& haystack, const string& needle)
 }


-
 bool
-embedded_expr::tagged_p (const char *tag) const
+embedded_expr::tagged_p (const char *tag)
 {
-  return memo_tagged_p (code, tag);
+  return tagged_p (string (tag));
 }


 bool
-embedded_expr::tagged_p (const string &tag) const
+embedded_expr::tagged_p (const string &tag)
 {
-  return memo_tagged_p (code, tag);
+  auto it = string_find_memoized.find(tag);
+  if (it != string_find_memoized.end())
+    return it->second;
+
+  auto findres = code.find(tag);
+  bool res = (findres != interned_string::npos);
+  string_find_memoized[tag] = res;
+
+  return res;
 }


 bool
-embedded_expr::tagged_p (const interned_string& tag) const
+embedded_expr::tagged_p (const interned_string& tag)
 {
-  return memo_tagged_p (code, tag);
+  return tagged_p (tag.to_string ());
 }


 bool
-embeddedcode::tagged_p (const char *tag) const
+embeddedcode::tagged_p (const char *tag)
 {
-  return memo_tagged_p (code, tag);
+  return tagged_p (string (tag));
 }


 bool
-embeddedcode::tagged_p (const string &tag) const
+embeddedcode::tagged_p (const string &tag)
 {
-  return memo_tagged_p (code, tag);
+  auto it = string_find_memoized.find(tag);
+  if (it != string_find_memoized.end())
+    return it->second;
+
+  auto findres = code.find(tag);
+  bool res = (findres != interned_string::npos);
+  string_find_memoized[tag] = res;
+
+  return res;
 }


 bool
-embeddedcode::tagged_p (const interned_string& tag) const
+embeddedcode::tagged_p (const interned_string& tag)
 {
-  return memo_tagged_p (code, tag);
+  return tagged_p (tag.to_string ());
 }


diff --git a/staptree.h b/staptree.h
index 177879647..efc06b265 100644
--- a/staptree.h
+++ b/staptree.h
@@ -20,6 +20,7 @@
 #include <stdexcept>
 #include <cassert>
 #include <typeinfo>
+#include <unordered_map>
 extern "C" {
 #include <stdint.h>
 }
@@ -184,9 +185,10 @@ struct literal_number: public literal
 struct embedded_expr: public expression
 {
   interned_string code;
-  bool tagged_p (const char *tag) const;
-  bool tagged_p (const std::string &tag) const;
-  bool tagged_p (const interned_string& tag) const;
+  std::unordered_map <std::string,bool> string_find_memoized;
+  bool tagged_p (const char *tag);
+  bool tagged_p (const std::string &tag);
+  bool tagged_p (const interned_string& tag);
   void print (std::ostream& o) const;
   void visit (visitor* u);
 };
@@ -717,9 +719,10 @@ std::ostream& operator << (std::ostream& o, const statement& k);
 struct embeddedcode: public statement
 {
   interned_string code;
-  bool tagged_p (const char *tag) const;
-  bool tagged_p (const std::string& tag) const;
-  bool tagged_p (const interned_string& tag) const;
+  std::unordered_map <std::string,bool> string_find_memoized;
+  bool tagged_p (const char *tag);
+  bool tagged_p (const std::string& tag);
+  bool tagged_p (const interned_string& tag);
   void print (std::ostream& o) const;
   void visit (visitor* u);
 };