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

 using namespace std;

@@ -402,13 +403,28 @@ string atvar_op::sym_name ()
 }


+struct str_pair_hash {
+    template <class T1, class T2>
+    std::size_t operator () (const std::pair<T1,T2> &p) const {
+        auto h1 = std::hash<T1>{}(p.first);
+        auto h2 = std::hash<T2>{}(p.second);
+
+        // Mainly for demonstration purposes, i.e. works but is overly simple
+        // In the real world, use sth. like boost.hash_combine
+        return h1 ^ h2;
+    }
+};
+
+
 // Substring operations like interned_string.find() are repeated a
 // surprising number of times (with nested / widely used tapset emb-C
 // functions), and need to be efficient.  We memoize the search
 // results.
 bool memo_tagged_p (const interned_string& haystack, const string& needle)
 {
-  static map <pair<interned_string,string>,bool> string_find_memoized;
+  static std::unordered_map <pair<interned_string,string>,bool,str_pair_hash>
+    string_find_memoized;
+
   auto key = make_pair(haystack,needle);

   auto it = string_find_memoized.find(key);
@@ -417,7 +433,7 @@ bool memo_tagged_p (const interned_string& haystack, const string& needle)

   auto findres = haystack.find(needle);
   bool res = (findres != interned_string::npos);
-  string_find_memoized.insert(make_pair(key,res));
+  string_find_memoized[key] = res;

   return res;
 }