Add hash map, reduce excessive hashing

Changed the class def index to use a HashMap instead of unordered_map
so that we can use FindWithHash to reduce how often we need to compute
hashes.

Fixed a bug in ClassLinker::UpdateClass where we didn't properly
handle classes with the same descriptor but different class loaders.
Introduced by previous CL.

Before (fb launch):
1.74% art::ComputeModifiedUtf8Hash(char const*)

After:
0.95% art::ComputeModifiedUtf8Hash(char const*)

Bug: 18054905
Bug: 16828525

Change-Id: Iba2ee37c9837289e0ea187800ba4af322225a994

(cherry picked from commit 564ff985184737977aa26c485d0c1a413e530705)

1 files changed, 19 insertions, 4 deletions

diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index 8ced664633..a71ca429cb 100644
--- a/runtime/dex_file.h
+++ b/runtime/dex_file.h
@@ -22,6 +22,7 @@
 #include <unordered_map>
 #include <vector>
 
+#include "base/hash_map.h"
 #include "base/logging.h"
 #include "base/mutex.h"  // For Locks::mutator_lock_.
 #include "base/value_object.h"
@@ -649,8 +650,9 @@ class DexFile {
     return StringByTypeIdx(class_def.class_idx_);
   }
 
-  // Looks up a class definition by its class descriptor.
-  const ClassDef* FindClassDef(const char* descriptor) const;
+  // Looks up a class definition by its class descriptor. Hash must be
+  // ComputeModifiedUtf8Hash(descriptor).
+  const ClassDef* FindClassDef(const char* descriptor, size_t hash) const;
 
   // Looks up a class definition by its type index.
   const ClassDef* FindClassDef(uint16_t type_idx) const;
@@ -986,17 +988,30 @@ class DexFile {
   // Number of misses finding a class def from a descriptor.
   mutable Atomic<uint32_t> find_class_def_misses_;
 
+  struct UTF16EmptyFn {
+    void MakeEmpty(std::pair<const char*, const ClassDef*>& pair) const {
+      pair.first = nullptr;
+      pair.second = nullptr;
+    }
+    bool IsEmpty(const std::pair<const char*, const ClassDef*>& pair) const {
+      if (pair.first == nullptr) {
+        DCHECK(pair.second == nullptr);
+        return true;
+      }
+      return false;
+    }
+  };
   struct UTF16HashCmp {
     // Hash function.
     size_t operator()(const char* key) const {
-      return ComputeUtf8Hash(key);
+      return ComputeModifiedUtf8Hash(key);
     }
     // std::equal function.
     bool operator()(const char* a, const char* b) const {
       return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0;
     }
   };
-  typedef std::unordered_map<const char*, const ClassDef*, UTF16HashCmp, UTF16HashCmp> Index;
+  typedef HashMap<const char*, const ClassDef*, UTF16EmptyFn, UTF16HashCmp, UTF16HashCmp> Index;
   mutable Atomic<Index*> class_def_index_;
 };
 std::ostream& operator<<(std::ostream& os, const DexFile& dex_file);