Smarter set intersection between app image and non boot image strings

If there are fewer non boot image strings in the runtime, iterate
over those strings instead of the set being newly added.

On AOSP, nonBootImageInternStrings is around 500.

Test: test-art-host
Bug: 116059983
Change-Id: I76b49f2090971cf593ba487889b35dfc1fa8cf13

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();