Change safecast data from set to an ordered vector.

This saves memory and improves performance.

Bug: 12167380
Change-Id: Ica8d9291cdd515e8eab03814fb75a85d424eb629

2 files changed, 8 insertions, 4 deletions

diff --git a/compiler/dex/verified_methods_data.cc b/compiler/dex/verified_methods_data.cc
index 454b92cd85..b3ceefcb63 100644
--- a/compiler/dex/verified_methods_data.cc
+++ b/compiler/dex/verified_methods_data.cc
@@ -130,8 +130,8 @@ bool VerifiedMethodsData::IsSafeCast(MethodReference ref, uint32_t pc) {
   }
 
   // Look up the cast address in the set of safe casts
-  MethodSafeCastSet::const_iterator cast_it = it->second->find(pc);
-  return cast_it != it->second->end();
+  // Use binary_search for lookup in the sorted vector.
+  return std::binary_search(it->second->begin(), it->second->end(), pc);
 }
 
 void VerifiedMethodsData::AddRejectedClass(ClassReference ref) {
@@ -337,8 +337,10 @@ VerifiedMethodsData::MethodSafeCastSet* VerifiedMethodsData::GenerateSafeCastSet
       if (is_safe_cast) {
         if (mscs.get() == nullptr) {
           mscs.reset(new MethodSafeCastSet());
+        } else {
+          DCHECK_LT(mscs->back(), dex_pc);  // Verify ordering for push_back() to the sorted vector.
         }
-        mscs->insert(dex_pc);
+        mscs->push_back(dex_pc);
       }
     }
   }
diff --git a/compiler/dex/verified_methods_data.h b/compiler/dex/verified_methods_data.h
index 8d5058ab2f..d495dff7d9 100644
--- a/compiler/dex/verified_methods_data.h
+++ b/compiler/dex/verified_methods_data.h
@@ -83,7 +83,9 @@ class VerifiedMethodsData {
         LOCKS_EXCLUDED(dex_gc_maps_lock_);
 
     // Cast elision types.
-    typedef std::set<uint32_t> MethodSafeCastSet;
+    // Since we're adding the dex PCs to the set in increasing order, a sorted vector
+    // is better for performance (not just memory usage), especially for large sets.
+    typedef std::vector<uint32_t> MethodSafeCastSet;
     typedef SafeMap<MethodReference, const MethodSafeCastSet*,
         MethodReferenceComparator> SafeCastMap;
     MethodSafeCastSet* GenerateSafeCastSet(verifier::MethodVerifier* method_verifier)