Optimize FetchAndCacheResolvedClassesAndMethods

Moved FetchAndCacheResolvedClassesAndMethods to use a newly added
memory efficient DexReferenceCollection. This reduces RAM by
6+ bytes per sampled method during the process.

Changed profile logic to use bulk adding for each dex file instead
of looping through all of the ids and doing a string map comparison
for each one.

Also moved the vectors to use arena allocators to make sure the
pages get released after sampling is done.

Time in FetchAndCacheResolvedClassesAndMethods for Maps goes from
90.4ms to 47ms (average of 5 samples).

The motivation is to improve this call since it will be called more
often for sampling post startup methods.

Test: test-art-host
Test: manually look at -verbose:profiler output

Bug: 36457259

Change-Id: I3ed647ae15900c96d2180eb5c799f45393794dda

5 files changed, 245 insertions, 64 deletions

diff --git a/runtime/dex_reference_collection.h b/runtime/dex_reference_collection.h
new file mode 100644
index 0000000000..76355d6335
--- /dev/null
+++ b/runtime/dex_reference_collection.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_DEX_REFERENCE_COLLECTION_H_
+#define ART_RUNTIME_DEX_REFERENCE_COLLECTION_H_
+
+#include "base/macros.h"
+
+#include <vector>
+#include <map>
+
+namespace art {
+
+class DexFile;
+
+// Collection of dex references that is more memory efficient than a vector of <dex, index> pairs.
+// Also allows quick lookups of all of the references for a single dex.
+template <class IndexType, template<typename Type> class Allocator>
+class DexReferenceCollection {
+ public:
+  using VectorAllocator = Allocator<IndexType>;
+  using IndexVector = std::vector<IndexType, VectorAllocator>;
+  using MapAllocator = Allocator<std::pair<const DexFile*, IndexVector>>;
+  using DexFileMap = std::map<
+      const DexFile*,
+      IndexVector,
+      std::less<const DexFile*>,
+      Allocator<std::pair<const DexFile* const, IndexVector>>>;
+
+  DexReferenceCollection(const MapAllocator& map_allocator = MapAllocator(),
+                         const VectorAllocator& vector_allocator = VectorAllocator())
+      : map_(map_allocator),
+        vector_allocator_(vector_allocator) {}
+
+  void AddReference(const DexFile* dex, IndexType index) {
+    GetOrInsertVector(dex)->push_back(index);
+  }
+
+  DexFileMap& GetMap() {
+    return map_;
+  }
+
+  size_t NumReferences() const {
+    size_t ret = 0;
+    for (auto&& pair : map_) {
+      ret += pair.second.size();
+    }
+    return ret;
+  }
+
+ private:
+  DexFileMap map_;
+  // Optimize for adding to same vector in succession.
+  const DexFile* current_dex_file_ = nullptr;
+  IndexVector* current_vector_ = nullptr;
+  VectorAllocator vector_allocator_;
+
+  ALWAYS_INLINE IndexVector* GetOrInsertVector(const DexFile* dex) {
+    if (UNLIKELY(current_dex_file_ != dex)) {
+      // There is an assumption that constructing an empty vector wont do any allocations. If this
+      // incorrect, this might leak for the arena case.
+      current_vector_ = &map_.emplace(dex, IndexVector(vector_allocator_)).first->second;
+      current_dex_file_ = dex;
+    }
+    return current_vector_;
+  }
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_DEX_REFERENCE_COLLECTION_H_
diff --git a/runtime/jit/profile_compilation_info-inl.h b/runtime/jit/profile_compilation_info-inl.h
new file mode 100644
index 0000000000..8a067a5870
--- /dev/null
+++ b/runtime/jit/profile_compilation_info-inl.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_JIT_PROFILE_COMPILATION_INFO_INL_H_
+#define ART_RUNTIME_JIT_PROFILE_COMPILATION_INFO_INL_H_
+
+#include "profile_compilation_info.h"
+
+namespace art {
+
+template <class Iterator>
+inline bool ProfileCompilationInfo::AddSampledMethodsForDex(bool startup,
+                                                            const DexFile* dex_file,
+                                                            Iterator index_begin,
+                                                            Iterator index_end) {
+  DexFileData* data = GetOrAddDexFileData(dex_file);
+  if (data == nullptr) {
+    return false;
+  }
+  for (auto it = index_begin; it != index_end; ++it) {
+    DCHECK_LT(*it, data->num_method_ids);
+    data->AddSampledMethod(startup, *it);
+  }
+  return true;
+}
+
+template <class Iterator>
+inline bool ProfileCompilationInfo::AddHotMethodsForDex(const DexFile* dex_file,
+                                                        Iterator index_begin,
+                                                        Iterator index_end) {
+  DexFileData* data = GetOrAddDexFileData(dex_file);
+  if (data == nullptr) {
+    return false;
+  }
+  for (auto it = index_begin; it != index_end; ++it) {
+    DCHECK_LT(*it, data->num_method_ids);
+    data->FindOrAddMethod(*it);
+  }
+  return true;
+}
+
+template <class Iterator>
+inline bool ProfileCompilationInfo::AddClassesForDex(const DexFile* dex_file,
+                                                     Iterator index_begin,
+                                                     Iterator index_end) {
+  DexFileData* data = GetOrAddDexFileData(dex_file);
+  if (data == nullptr) {
+    return false;
+  }
+  data->class_set.insert(index_begin, index_end);
+  return true;
+}
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_JIT_PROFILE_COMPILATION_INFO_INL_H_
diff --git a/runtime/jit/profile_compilation_info.cc b/runtime/jit/profile_compilation_info.cc
index 3852a5bc53..ea27d3b300 100644
--- a/runtime/jit/profile_compilation_info.cc
+++ b/runtime/jit/profile_compilation_info.cc
@@ -147,18 +147,6 @@ bool ProfileCompilationInfo::AddSampledMethod(bool startup,
   return true;
 }
 
-bool ProfileCompilationInfo::AddSampledMethods(bool startup,
-                                               std::vector<MethodReference>& methods) {
-  for (const MethodReference& ref : methods) {
-    DexFileData* data = GetOrAddDexFileData(ref.dex_file);
-    if (data == nullptr) {
-      return false;
-    }
-    data->AddSampledMethod(startup, ref.dex_method_index);
-  }
-  return true;
-}
-
 bool ProfileCompilationInfo::AddMethodsAndClasses(
     const std::vector<ProfileMethodInfo>& methods,
     const std::set<DexCacheResolvedClasses>& resolved_classes) {
diff --git a/runtime/jit/profile_compilation_info.h b/runtime/jit/profile_compilation_info.h
index a9f2fb6dd8..bd1b9d651f 100644
--- a/runtime/jit/profile_compilation_info.h
+++ b/runtime/jit/profile_compilation_info.h
@@ -197,6 +197,10 @@ class ProfileCompilationInfo {
   bool AddMethodsAndClasses(const std::vector<ProfileMethodInfo>& methods,
                             const std::set<DexCacheResolvedClasses>& resolved_classes);
 
+  // Iterator is type for ids not class defs.
+  template <class Iterator>
+  bool AddClassesForDex(const DexFile* dex_file, Iterator index_begin, Iterator index_end);
+
   // Add a method index to the profile (without inline caches).
   bool AddMethodIndex(const std::string& dex_location,
                       uint32_t checksum,
@@ -207,13 +211,24 @@ class ProfileCompilationInfo {
   bool AddMethod(const ProfileMethodInfo& pmi);
 
   // Add methods that have samples but are are not necessarily hot. These are partitioned into two
-  // possibly interesecting sets startup and post startup.
-  bool AddSampledMethods(bool startup, std::vector<MethodReference>& methods);
+  // possibly intersecting sets startup and post startup.
   bool AddSampledMethod(bool startup,
                         const std::string& dex_location,
                         uint32_t checksum,
                         uint16_t method_idx,
                         uint32_t num_method_ids);
+  // Bulk add sampled methods for a single dex, fast since it only has one GetOrAddDexFileData call.
+  template <class Iterator>
+  bool AddSampledMethodsForDex(bool startup,
+                               const DexFile* dex_file,
+                               Iterator index_begin,
+                               Iterator index_end);
+
+  // Bulk add hot methods for a single dex, fast since it only has one GetOrAddDexFileData call.
+  template <class Iterator>
+  bool AddHotMethodsForDex(const DexFile* dex_file,
+                           Iterator index_begin,
+                           Iterator index_end);
 
   // Load profile information from the given file descriptor.
   // If the current profile is non-empty the load will fail.
diff --git a/runtime/jit/profile_saver.cc b/runtime/jit/profile_saver.cc
index 2a191f2962..68f33bde03 100644
--- a/runtime/jit/profile_saver.cc
+++ b/runtime/jit/profile_saver.cc
@@ -25,13 +25,16 @@
 
 #include "art_method-inl.h"
 #include "base/enums.h"
+#include "base/scoped_arena_containers.h"
 #include "base/stl_util.h"
 #include "base/systrace.h"
 #include "base/time_utils.h"
 #include "compiler_filter.h"
+#include "dex_reference_collection.h"
 #include "gc/collector_type.h"
 #include "gc/gc_cause.h"
 #include "gc/scoped_gc_critical_section.h"
+#include "jit/profile_compilation_info-inl.h"
 #include "oat_file_manager.h"
 #include "scoped_thread_state_change-inl.h"
 
@@ -180,33 +183,45 @@ void ProfileSaver::NotifyJitActivityInternal() {
   }
 }
 
+using MethodReferenceCollection = DexReferenceCollection<uint16_t, ScopedArenaAllocatorAdapter>;
+using TypeReferenceCollection = DexReferenceCollection<dex::TypeIndex,
+                                                       ScopedArenaAllocatorAdapter>;
+
 // Get resolved methods that have a profile info or more than kStartupMethodSamples samples.
 // Excludes native methods and classes in the boot image.
-class GetMethodsVisitor : public ClassVisitor {
+class GetClassesAndMethodsVisitor : public ClassVisitor {
  public:
-  GetMethodsVisitor(std::vector<MethodReference>* hot_methods,
-                    std::vector<MethodReference>* sampled_methods,
-                    uint32_t hot_method_sample_threshold)
+  GetClassesAndMethodsVisitor(MethodReferenceCollection* hot_methods,
+                              MethodReferenceCollection* sampled_methods,
+                              TypeReferenceCollection* resolved_classes,
+                              uint32_t hot_method_sample_threshold)
     : hot_methods_(hot_methods),
       sampled_methods_(sampled_methods),
+      resolved_classes_(resolved_classes),
       hot_method_sample_threshold_(hot_method_sample_threshold) {}
 
   virtual bool operator()(ObjPtr<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_) {
-    if (Runtime::Current()->GetHeap()->ObjectIsInBootImageSpace(klass)) {
+    if (klass->IsProxyClass() ||
+        klass->IsArrayClass() ||
+        !klass->IsResolved() ||
+        klass->IsErroneousResolved() ||
+        klass->GetClassLoader() == nullptr) {
       return true;
     }
+    DCHECK(klass->GetDexCache() != nullptr) << klass->PrettyClass();
+    resolved_classes_->AddReference(&klass->GetDexFile(), klass->GetDexTypeIndex());
     for (ArtMethod& method : klass->GetMethods(kRuntimePointerSize)) {
-      if (!method.IsNative() && !method.IsProxyMethod()) {
+      if (!method.IsNative()) {
+        DCHECK(!method.IsProxyMethod());
         const uint16_t counter = method.GetCounter();
-        MethodReference ref(method.GetDexFile(), method.GetDexMethodIndex());
         // Mark startup methods as hot if they have more than hot_method_sample_threshold_ samples.
         // This means they will get compiled by the compiler driver.
         if (method.GetProfilingInfo(kRuntimePointerSize) != nullptr ||
             (method.GetAccessFlags() & kAccPreviouslyWarm) != 0 ||
             counter >= hot_method_sample_threshold_) {
-          hot_methods_->push_back(ref);
+          hot_methods_->AddReference(method.GetDexFile(), method.GetDexMethodIndex());
         } else if (counter != 0) {
-          sampled_methods_->push_back(ref);
+          sampled_methods_->AddReference(method.GetDexFile(), method.GetDexMethodIndex());
         }
       } else {
         CHECK_EQ(method.GetCounter(), 0u);
@@ -216,85 +231,95 @@ class GetMethodsVisitor : public ClassVisitor {
   }
 
  private:
-  std::vector<MethodReference>* const hot_methods_;
-  std::vector<MethodReference>* const sampled_methods_;
+  MethodReferenceCollection* const hot_methods_;
+  MethodReferenceCollection* const sampled_methods_;
+  TypeReferenceCollection* const resolved_classes_;
   uint32_t hot_method_sample_threshold_;
 };
 
 void ProfileSaver::FetchAndCacheResolvedClassesAndMethods() {
   ScopedTrace trace(__PRETTY_FUNCTION__);
+  const uint64_t start_time = NanoTime();
 
   // Resolve any new registered locations.
   ResolveTrackedLocations();
 
   Thread* const self = Thread::Current();
-  std::vector<MethodReference> hot_methods;
-  std::vector<MethodReference> startup_methods;
-  std::set<DexCacheResolvedClasses> resolved_classes;
+  Runtime* const runtime = Runtime::Current();
+  ArenaStack stack(runtime->GetArenaPool());
+  ScopedArenaAllocator allocator(&stack);
+  MethodReferenceCollection hot_methods(allocator.Adapter(), allocator.Adapter());
+  MethodReferenceCollection startup_methods(allocator.Adapter(), allocator.Adapter());
+  TypeReferenceCollection resolved_classes(allocator.Adapter(), allocator.Adapter());
+  const size_t hot_threshold = options_.GetHotStartupMethodSamples();
   {
     ScopedObjectAccess soa(self);
     gc::ScopedGCCriticalSection sgcs(self,
                                      gc::kGcCauseProfileSaver,
                                      gc::kCollectorTypeCriticalSection);
-
-    ClassLinker* const class_linker = Runtime::Current()->GetClassLinker();
-    resolved_classes = class_linker->GetResolvedClasses(/*ignore boot classes*/ true);
-
     {
       ScopedTrace trace2("Get hot methods");
-      GetMethodsVisitor visitor(&hot_methods,
-                                &startup_methods,
-                                options_.GetHotStartupMethodSamples());
-      class_linker->VisitClasses(&visitor);
-      VLOG(profiler) << "Profile saver recorded " << hot_methods.size() << " hot methods and "
-                     << startup_methods.size() << " startup methods with threshold "
-                     << options_.GetHotStartupMethodSamples();
+      GetClassesAndMethodsVisitor visitor(&hot_methods,
+                                          &startup_methods,
+                                          &resolved_classes,
+                                          hot_threshold);
+      runtime->GetClassLinker()->VisitClasses(&visitor);
     }
   }
+
   MutexLock mu(self, *Locks::profiler_lock_);
   uint64_t total_number_of_profile_entries_cached = 0;
 
   for (const auto& it : tracked_dex_base_locations_) {
     std::set<DexCacheResolvedClasses> resolved_classes_for_location;
     const std::string& filename = it.first;
+    auto info_it = profile_cache_.Put(
+        filename,
+        new ProfileCompilationInfo(Runtime::Current()->GetArenaPool()));
+    ProfileCompilationInfo* cached_info = info_it->second;
+
     const std::set<std::string>& locations = it.second;
-    std::vector<ProfileMethodInfo> profile_methods_for_location;
-    std::vector<MethodReference> startup_methods_for_locations;
-    for (const MethodReference& ref : hot_methods) {
-      if (locations.find(ref.dex_file->GetBaseLocation()) != locations.end()) {
-        profile_methods_for_location.emplace_back(ref.dex_file, ref.dex_method_index);
-        // Hot methods are also startup methods since this function is only invoked during startup.
-        startup_methods_for_locations.push_back(ref);
+    for (const auto& pair : hot_methods.GetMap()) {
+      const DexFile* const dex_file = pair.first;
+      if (locations.find(dex_file->GetBaseLocation()) != locations.end()) {
+        cached_info->AddSampledMethodsForDex(/*startup*/ true,
+                                             dex_file,
+                                             pair.second.begin(),
+                                             pair.second.end());
+        // Adding hot methods is a bit slow, TODO: optimize.
+        cached_info->AddHotMethodsForDex(dex_file, pair.second.begin(), pair.second.end());
       }
     }
-    for (const MethodReference& ref : startup_methods) {
-      if (locations.find(ref.dex_file->GetBaseLocation()) != locations.end()) {
-        startup_methods_for_locations.push_back(ref);
+    for (const auto& pair : startup_methods.GetMap()) {
+      const DexFile* const dex_file = pair.first;
+      if (locations.find(dex_file->GetBaseLocation()) != locations.end()) {
+        cached_info->AddSampledMethodsForDex(/*startup*/ true,
+                                             dex_file,
+                                             pair.second.begin(),
+                                             pair.second.end());
       }
     }
-
-    for (const DexCacheResolvedClasses& classes : resolved_classes) {
-      if (locations.find(classes.GetBaseLocation()) != locations.end()) {
-        VLOG(profiler) << "Added " << classes.GetClasses().size() << " classes for location "
-                       << classes.GetBaseLocation() << " (" << classes.GetDexLocation() << ")";
-        resolved_classes_for_location.insert(classes);
+    for (const auto& pair : resolved_classes.GetMap()) {
+      const DexFile* const dex_file = pair.first;
+      if (locations.find(dex_file->GetBaseLocation()) != locations.end()) {
+        const TypeReferenceCollection::IndexVector& classes = pair.second;
+        VLOG(profiler) << "Added " << classes.size() << " classes for location "
+                       << dex_file->GetBaseLocation()
+                       << " (" << dex_file->GetLocation() << ")";
+        cached_info->AddClassesForDex(dex_file, classes.begin(), classes.end());
       } else {
-        VLOG(profiler) << "Location not found " << classes.GetBaseLocation()
-                       << " (" << classes.GetDexLocation() << ")";
+        VLOG(profiler) << "Location not found " << dex_file->GetBaseLocation()
+                       << " (" << dex_file->GetLocation() << ")";
       }
     }
-    auto info_it = profile_cache_.Put(
-        filename,
-        new ProfileCompilationInfo(Runtime::Current()->GetArenaPool()));
-
-    ProfileCompilationInfo* cached_info = info_it->second;
-    cached_info->AddMethodsAndClasses(profile_methods_for_location, resolved_classes_for_location);
-    cached_info->AddSampledMethods(/*startup*/ true, startup_methods_for_locations);
     total_number_of_profile_entries_cached += resolved_classes_for_location.size();
   }
   max_number_of_profile_entries_cached_ = std::max(
       max_number_of_profile_entries_cached_,
       total_number_of_profile_entries_cached);
+  VLOG(profiler) << "Profile saver recorded " << hot_methods.NumReferences() << " hot methods and "
+                 << startup_methods.NumReferences() << " startup methods with threshold "
+                 << hot_threshold << " in " << PrettyDuration(NanoTime() - start_time);
 }
 
 bool ProfileSaver::ProcessProfilingInfo(bool force_save, /*out*/uint16_t* number_of_new_methods) {