diff --git a/runtime/interpreter/interpreter_common.cc b/runtime/interpreter/interpreter_common.cc
index 68d56f5..5fbd687 100644
--- a/runtime/interpreter/interpreter_common.cc
+++ b/runtime/interpreter/interpreter_common.cc
@@ -709,7 +709,11 @@
       SafeMap<uint32_t, std::set<uint32_t>> string_init_map =
           verifier::MethodVerifier::FindStringInitMap(method);
       MutexLock mu(self, *Locks::interpreter_string_init_map_lock_);
-      auto it = method_to_string_init_map.Overwrite(method_ref, string_init_map);
+      auto it = method_to_string_init_map.lower_bound(method_ref);
+      if (it == method_to_string_init_map.end() ||
+          method_to_string_init_map.key_comp()(method_ref, it->first)) {
+        it = method_to_string_init_map.PutBefore(it, method_ref, std::move(string_init_map));
+      }
       string_init_map_ptr = &it->second;
     }
     if (string_init_map_ptr->size() != 0) {
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index 04549c7..7ac17b6 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -92,6 +92,11 @@
     DCHECK(result.second);  // Check we didn't accidentally overwrite an existing value.
     return result.first;
   }
+  iterator Put(const K& k, const V&& v) {
+    std::pair<iterator, bool> result = map_.emplace(k, std::move(v));
+    DCHECK(result.second);  // Check we didn't accidentally overwrite an existing value.
+    return result.first;
+  }
 
   // Used to insert a new mapping at a known position for better performance.
   iterator PutBefore(iterator pos, const K& k, const V& v) {
@@ -100,10 +105,16 @@
     DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
     return map_.emplace_hint(pos, k, v);
   }
+  iterator PutBefore(iterator pos, const K& k, const V&& v) {
+    // Check that we're using the correct position and the key is not in the map.
+    DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
+    DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
+    return map_.emplace_hint(pos, k, std::move(v));
+  }
 
   // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type
   // of this container is a pointer, any overwritten pointer will be lost and if this container
-  // was the owner, you have a leak.
+  // was the owner, you have a leak. Returns iterator pointing to the new or overwritten entry.
   iterator Overwrite(const K& k, const V& v) {
     std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v));
     if (!result.second) {
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index 3d4f04c..9938e90 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -548,7 +548,8 @@
   MethodVerifier verifier(self, m->GetDexFile(), dex_cache, class_loader, &m->GetClassDef(),
                           m->GetCodeItem(), m->GetDexMethodIndex(), m, m->GetAccessFlags(),
                           true, true, false, true);
-  return verifier.FindStringInitMap();
+  // Avoid copying: The map is moved out of the verifier before the verifier is destroyed.
+  return std::move(verifier.FindStringInitMap());
 }
 
 SafeMap<uint32_t, std::set<uint32_t>>& MethodVerifier::FindStringInitMap() {