3 files changed, 62 insertions, 12 deletions

diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index e3dfdb3256..6a5e8b6d65 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1495,18 +1495,44 @@ void AppImageLoadingHelper::HandleAppImageStrings(gc::space::ImageSpace* space)
   intern_table->AddImageStringsToTable(space, [&](InternTable::UnorderedSet& interns)
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(Locks::intern_table_lock_) {
+    const size_t non_boot_image_strings = intern_table->CountInterns(
+        /*visit_boot_images=*/false,
+        /*visit_non_boot_images=*/true);
     VLOG(image) << "AppImage:stringsInInternTableSize = " << interns.size();
-    for (auto it = interns.begin(); it != interns.end(); ) {
-      ObjPtr<mirror::String> string = it->Read();
-      ObjPtr<mirror::String> existing = intern_table->LookupWeakLocked(string);
-      if (existing == nullptr) {
-        existing = intern_table->LookupStrongLocked(string);
-      }
-      if (existing != nullptr) {
-        intern_remap.Put(string.Ptr(), existing.Ptr());
-        it = interns.erase(it);
-      } else {
-        ++it;
+    VLOG(image) << "AppImage:nonBootImageInternStrings = " << non_boot_image_strings;
+    // Visit the smaller of the two sets to compute the intersection.
+    if (interns.size() < non_boot_image_strings) {
+      for (auto it = interns.begin(); it != interns.end(); ) {
+        ObjPtr<mirror::String> string = it->Read();
+        ObjPtr<mirror::String> existing = intern_table->LookupWeakLocked(string);
+        if (existing == nullptr) {
+          existing = intern_table->LookupStrongLocked(string);
+        }
+        if (existing != nullptr) {
+          intern_remap.Put(string.Ptr(), existing.Ptr());
+          it = interns.erase(it);
+        } else {
+          ++it;
+        }
+      }
+    } else {
+      intern_table->VisitInterns([&](const GcRoot<mirror::String>& root)
+          REQUIRES_SHARED(Locks::mutator_lock_)
+          REQUIRES(Locks::intern_table_lock_) {
+        auto it = interns.find(root);
+        if (it != interns.end()) {
+          ObjPtr<mirror::String> existing = root.Read();
+          intern_remap.Put(it->Read(), existing.Ptr());
+          it = interns.erase(it);
+        }
+      }, /*visit_boot_images=*/false, /*visit_non_boot_images=*/true);
+    }
+    // Sanity check to ensure correctness.
+    if (kIsDebugBuild) {
+      for (GcRoot<mirror::String>& root : interns) {
+        ObjPtr<mirror::String> string = root.Read();
+        CHECK(intern_table->LookupWeakLocked(string) == nullptr) << string->ToModifiedUtf8();
+        CHECK(intern_table->LookupStrongLocked(string) == nullptr) << string->ToModifiedUtf8();
       }
     }
   });
diff --git a/runtime/intern_table-inl.h b/runtime/intern_table-inl.h
index 3c7da09d5d..6fc53e9f20 100644
--- a/runtime/intern_table-inl.h
+++ b/runtime/intern_table-inl.h
@@ -77,7 +77,7 @@ inline void InternTable::VisitInterns(const Visitor& visitor,
                                       bool visit_boot_images,
                                       bool visit_non_boot_images) {
   auto visit_tables = [&](std::vector<Table::InternalTable>& tables)
-      REQUIRES_SHARED(Locks::mutator_lock_) {
+      NO_THREAD_SAFETY_ANALYSIS {
     for (Table::InternalTable& table : tables) {
       // Determine if we want to visit the table based on the flags..
       const bool visit =
@@ -94,6 +94,26 @@ inline void InternTable::VisitInterns(const Visitor& visitor,
   visit_tables(weak_interns_.tables_);
 }
 
+inline size_t InternTable::CountInterns(bool visit_boot_images,
+                                        bool visit_non_boot_images) const {
+  size_t ret = 0u;
+  auto visit_tables = [&](const std::vector<Table::InternalTable>& tables)
+      NO_THREAD_SAFETY_ANALYSIS {
+    for (const Table::InternalTable& table : tables) {
+      // Determine if we want to visit the table based on the flags..
+      const bool visit =
+          (visit_boot_images && table.IsBootImage()) ||
+          (visit_non_boot_images && !table.IsBootImage());
+      if (visit) {
+        ret += table.set_.size();
+      }
+    }
+  };
+  visit_tables(strong_interns_.tables_);
+  visit_tables(weak_interns_.tables_);
+  return ret;
+}
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_INTERN_TABLE_INL_H_
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index baeb1a9640..165d56cf66 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -174,6 +174,10 @@ class InternTable {
                     bool visit_non_boot_images)
       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
 
+  // Count the number of intern strings in the table.
+  size_t CountInterns(bool visit_boot_images, bool visit_non_boot_images) const
+      REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
+
   void DumpForSigQuit(std::ostream& os) const REQUIRES(!Locks::intern_table_lock_);
 
   void BroadcastForNewInterns();