ART: Switch to name-based IMT hashing
Use a hash scheme based on the name. This keeps IMT slots stable
when dex tables change.
This incurs a severe performance penalty for computing the slot.
Measurements on host degraded from 30ns to an average of 85mus.
However, calls in compiled code will not incur this overhead.
Added a test comparing similar interfaces in similar dex files.
Bug: 31594153
Test: test-art-host
Change-Id: Ibb86679ee94bec561984ea25826e56b1a7964cd0
diff --git a/runtime/imtable-inl.h b/runtime/imtable-inl.h
index 0cb9b5e..cb85fa6 100644
--- a/runtime/imtable-inl.h
+++ b/runtime/imtable-inl.h
@@ -20,15 +20,82 @@
#include "imtable.h"
#include "art_method-inl.h"
+#include "dex_file.h"
+#include "utf.h"
namespace art {
-inline uint32_t ImTable::GetBaseImtHash(ArtMethod* method) REQUIRES_SHARED(Locks::mutator_lock_) {
- return method->GetDexMethodIndex();
+static constexpr bool kImTableHashUseName = true;
+static constexpr bool kImTableHashUseCoefficients = true;
+
+// Magic configuration that minimizes some common runtime calls.
+static constexpr uint32_t kImTableHashCoefficientClass = 427;
+static constexpr uint32_t kImTableHashCoefficientName = 16;
+static constexpr uint32_t kImTableHashCoefficientSignature = 14;
+
+inline void ImTable::GetImtHashComponents(ArtMethod* method,
+ uint32_t* class_hash,
+ uint32_t* name_hash,
+ uint32_t* signature_hash) {
+ if (kImTableHashUseName) {
+ if (method->IsProxyMethod()) {
+ *class_hash = 0;
+ *name_hash = 0;
+ *signature_hash = 0;
+ return;
+ }
+
+ const DexFile* dex_file = method->GetDexFile();
+ const DexFile::MethodId& method_id = dex_file->GetMethodId(method->GetDexMethodIndex());
+
+ // Class descriptor for the class component.
+ *class_hash = ComputeModifiedUtf8Hash(dex_file->GetMethodDeclaringClassDescriptor(method_id));
+
+ // Method name for the method component.
+ *name_hash = ComputeModifiedUtf8Hash(dex_file->GetMethodName(method_id));
+
+ const DexFile::ProtoId& proto_id = dex_file->GetMethodPrototype(method_id);
+
+ // Read the proto for the signature component.
+ uint32_t tmp = ComputeModifiedUtf8Hash(
+ dex_file->GetTypeDescriptor(dex_file->GetTypeId(proto_id.return_type_idx_)));
+
+ // Mix in the argument types.
+ // Note: we could consider just using the shorty. This would be faster, at the price of
+ // potential collisions.
+ const DexFile::TypeList* param_types = dex_file->GetProtoParameters(proto_id);
+ if (param_types != nullptr) {
+ for (size_t i = 0; i != param_types->Size(); ++i) {
+ const DexFile::TypeItem& type = param_types->GetTypeItem(i);
+ tmp = 31 * tmp + ComputeModifiedUtf8Hash(
+ dex_file->GetTypeDescriptor(dex_file->GetTypeId(type.type_idx_)));
+ }
+ }
+
+ *signature_hash = tmp;
+ return;
+ } else {
+ *class_hash = method->GetDexMethodIndex();
+ *name_hash = 0;
+ *signature_hash = 0;
+ return;
+ }
}
inline uint32_t ImTable::GetImtIndex(ArtMethod* method) {
- return GetBaseImtHash(method) % ImTable::kSize;
+ uint32_t class_hash, name_hash, signature_hash;
+ GetImtHashComponents(method, &class_hash, &name_hash, &signature_hash);
+
+ uint32_t mixed_hash;
+ if (!kImTableHashUseCoefficients) {
+ mixed_hash = class_hash + name_hash + signature_hash;
+ } else {
+ mixed_hash = kImTableHashCoefficientClass * class_hash +
+ kImTableHashCoefficientName * name_hash +
+ kImTableHashCoefficientSignature * signature_hash;
+ }
+
+ return mixed_hash % ImTable::kSize;
}
} // namespace art