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)
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index fecea89..fb90b91 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -147,15 +147,6 @@
VlogClassInitializationFailure(klass);
}
-static size_t Hash(const char* s) {
- // This is the java.lang.String hashcode for convenience, not interoperability.
- size_t hash = 0;
- for (; *s != '\0'; ++s) {
- hash = hash * 31 + *s;
- }
- return hash;
-}
-
// Gap between two fields in object layout.
struct FieldGap {
uint32_t start_offset; // The offset from the start of the object.
@@ -2010,7 +2001,8 @@
}
CHECK(h_class->IsRetired());
// Get the updated class from class table.
- klass = LookupClass(self, descriptor, h_class.Get()->GetClassLoader());
+ klass = LookupClass(self, descriptor, ComputeModifiedUtf8Hash(descriptor),
+ h_class.Get()->GetClassLoader());
}
// Wait for the class if it has not already been linked.
@@ -2043,22 +2035,20 @@
typedef std::pair<const DexFile*, const DexFile::ClassDef*> ClassPathEntry;
// Search a collection of DexFiles for a descriptor
-static ClassPathEntry FindInClassPath(const char* descriptor,
- const std::vector<const DexFile*>& class_path) {
- for (size_t i = 0; i != class_path.size(); ++i) {
- const DexFile* dex_file = class_path[i];
- const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor);
+ClassPathEntry FindInClassPath(const char* descriptor,
+ size_t hash, const std::vector<const DexFile*>& class_path) {
+ for (const DexFile* dex_file : class_path) {
+ const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor, hash);
if (dex_class_def != nullptr) {
return ClassPathEntry(dex_file, dex_class_def);
}
}
- // TODO: remove reinterpret_cast when issue with -std=gnu++0x host issue resolved
- return ClassPathEntry(static_cast<const DexFile*>(nullptr),
- static_cast<const DexFile::ClassDef*>(nullptr));
+ return ClassPathEntry(nullptr, nullptr);
}
mirror::Class* ClassLinker::FindClassInPathClassLoader(ScopedObjectAccessAlreadyRunnable& soa,
Thread* self, const char* descriptor,
+ size_t hash,
Handle<mirror::ClassLoader> class_loader) {
if (class_loader->GetClass() !=
soa.Decode<mirror::Class*>(WellKnownClasses::dalvik_system_PathClassLoader) ||
@@ -2066,14 +2056,14 @@
soa.Decode<mirror::Class*>(WellKnownClasses::java_lang_BootClassLoader)) {
return nullptr;
}
- ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+ ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
// Check if this would be found in the parent boot class loader.
if (pair.second != nullptr) {
- mirror::Class* klass = LookupClass(self, descriptor, nullptr);
+ mirror::Class* klass = LookupClass(self, descriptor, hash, nullptr);
if (klass != nullptr) {
return EnsureResolved(self, descriptor, klass);
}
- klass = DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+ klass = DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
*pair.second);
if (klass != nullptr) {
return klass;
@@ -2121,11 +2111,11 @@
break;
}
for (const DexFile* cp_dex_file : *dex_files) {
- const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor);
+ const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor, hash);
if (dex_class_def != nullptr) {
RegisterDexFile(*cp_dex_file);
- mirror::Class* klass =
- DefineClass(self, descriptor, class_loader, *cp_dex_file, *dex_class_def);
+ mirror::Class* klass = DefineClass(self, descriptor, hash, class_loader,
+ *cp_dex_file, *dex_class_def);
if (klass == nullptr) {
CHECK(self->IsExceptionPending()) << descriptor;
self->ClearException();
@@ -2152,19 +2142,20 @@
// for primitive classes that aren't backed by dex files.
return FindPrimitiveClass(descriptor[0]);
}
+ const size_t hash = ComputeModifiedUtf8Hash(descriptor);
// Find the class in the loaded classes table.
- mirror::Class* klass = LookupClass(self, descriptor, class_loader.Get());
+ mirror::Class* klass = LookupClass(self, descriptor, hash, class_loader.Get());
if (klass != nullptr) {
return EnsureResolved(self, descriptor, klass);
}
// Class is not yet loaded.
if (descriptor[0] == '[') {
- return CreateArrayClass(self, descriptor, class_loader);
+ return CreateArrayClass(self, descriptor, hash, class_loader);
} else if (class_loader.Get() == nullptr) {
// The boot class loader, search the boot class path.
- ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+ ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
if (pair.second != nullptr) {
- return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+ return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
*pair.second);
} else {
// The boot class loader is searched ahead of the application class loader, failures are
@@ -2177,16 +2168,16 @@
} else if (Runtime::Current()->UseCompileTimeClassPath()) {
// First try with the bootstrap class loader.
if (class_loader.Get() != nullptr) {
- klass = LookupClass(self, descriptor, nullptr);
+ klass = LookupClass(self, descriptor, hash, nullptr);
if (klass != nullptr) {
return EnsureResolved(self, descriptor, klass);
}
}
// If the lookup failed search the boot class path. We don't perform a recursive call to avoid
// a NoClassDefFoundError being allocated.
- ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+ ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
if (pair.second != nullptr) {
- return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+ return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
*pair.second);
}
// Next try the compile time class path.
@@ -2197,9 +2188,9 @@
soa.AddLocalReference<jobject>(class_loader.Get()));
class_path = &Runtime::Current()->GetCompileTimeClassPath(jclass_loader.get());
}
- pair = FindInClassPath(descriptor, *class_path);
+ pair = FindInClassPath(descriptor, hash, *class_path);
if (pair.second != nullptr) {
- return DefineClass(self, descriptor, class_loader, *pair.first, *pair.second);
+ return DefineClass(self, descriptor, hash, class_loader, *pair.first, *pair.second);
} else {
// Use the pre-allocated NCDFE at compile time to avoid wasting time constructing exceptions.
mirror::Throwable* pre_allocated = Runtime::Current()->GetPreAllocatedNoClassDefFoundError();
@@ -2208,7 +2199,8 @@
}
} else {
ScopedObjectAccessUnchecked soa(self);
- mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, class_loader);
+ mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, hash,
+ class_loader);
if (cp_klass != nullptr) {
return cp_klass;
}
@@ -2245,13 +2237,12 @@
UNREACHABLE();
}
-mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, size_t hash,
Handle<mirror::ClassLoader> class_loader,
const DexFile& dex_file,
const DexFile::ClassDef& dex_class_def) {
StackHandleScope<3> hs(self);
auto klass = hs.NewHandle<mirror::Class>(nullptr);
- bool should_allocate = false;
// Load the class from the dex file.
if (UNLIKELY(!init_done_)) {
@@ -2270,14 +2261,10 @@
klass.Assign(GetClassRoot(kJavaLangReflectArtField));
} else if (strcmp(descriptor, "Ljava/lang/reflect/ArtMethod;") == 0) {
klass.Assign(GetClassRoot(kJavaLangReflectArtMethod));
- } else {
- should_allocate = true;
}
- } else {
- should_allocate = true;
}
- if (should_allocate) {
+ if (klass.Get() == nullptr) {
// Allocate a class with the status of not ready.
// Interface object should get the right size here. Regular class will
// figure out the right size later and be replaced with one of the right
@@ -2302,7 +2289,7 @@
klass->SetClinitThreadId(self->GetTid());
// Add the newly loaded class to the loaded classes table.
- mirror::Class* existing = InsertClass(descriptor, klass.Get(), Hash(descriptor));
+ mirror::Class* existing = InsertClass(descriptor, klass.Get(), hash);
if (existing != nullptr) {
// We failed to insert because we raced with another thread. Calling EnsureResolved may cause
// this thread to block.
@@ -3106,7 +3093,8 @@
primitive_class->SetPrimitiveType(type);
primitive_class->SetStatus(mirror::Class::kStatusInitialized, self);
const char* descriptor = Primitive::Descriptor(type);
- mirror::Class* existing = InsertClass(descriptor, primitive_class, Hash(descriptor));
+ mirror::Class* existing = InsertClass(descriptor, primitive_class,
+ ComputeModifiedUtf8Hash(descriptor));
CHECK(existing == nullptr) << "InitPrimitiveClass(" << type << ") failed";
return primitive_class;
}
@@ -3124,7 +3112,7 @@
// array class; that always comes from the base element class.
//
// Returns nullptr with an exception raised on failure.
-mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor, size_t hash,
Handle<mirror::ClassLoader> class_loader) {
// Identify the underlying component type
CHECK_EQ('[', descriptor[0]);
@@ -3134,7 +3122,8 @@
if (component_type.Get() == nullptr) {
DCHECK(self->IsExceptionPending());
// We need to accept erroneous classes as component types.
- component_type.Assign(LookupClass(self, descriptor + 1, class_loader.Get()));
+ const size_t component_hash = ComputeModifiedUtf8Hash(descriptor + 1);
+ component_type.Assign(LookupClass(self, descriptor + 1, component_hash, class_loader.Get()));
if (component_type.Get() == nullptr) {
DCHECK(self->IsExceptionPending());
return nullptr;
@@ -3164,7 +3153,7 @@
// class to the hash table --- necessary because of possible races with
// other threads.)
if (class_loader.Get() != component_type->GetClassLoader()) {
- mirror::Class* new_class = LookupClass(self, descriptor, component_type->GetClassLoader());
+ mirror::Class* new_class = LookupClass(self, descriptor, hash, component_type->GetClassLoader());
if (new_class != nullptr) {
return new_class;
}
@@ -3253,7 +3242,7 @@
new_class->SetAccessFlags(access_flags);
- mirror::Class* existing = InsertClass(descriptor, new_class.Get(), Hash(descriptor));
+ mirror::Class* existing = InsertClass(descriptor, new_class.Get(), hash);
if (existing == nullptr) {
return new_class.Get();
}
@@ -3330,21 +3319,18 @@
mirror::Class* ClassLinker::UpdateClass(const char* descriptor, mirror::Class* klass,
size_t hash) {
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- mirror::Class* existing =
- LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
-
- if (existing == nullptr) {
+ auto existing_it = class_table_.FindWithHash(std::make_pair(descriptor, klass->GetClassLoader()),
+ hash);
+ if (existing_it == class_table_.end()) {
CHECK(klass->IsProxyClass());
return nullptr;
}
+ mirror::Class* existing = existing_it->Read();
CHECK_NE(existing, klass) << descriptor;
CHECK(!existing->IsResolved()) << descriptor;
CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor;
- auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash);
- CHECK(it != class_table_.end());
-
CHECK(!klass->IsTemp()) << descriptor;
if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
dex_cache_image_class_lookup_required_) {
@@ -3358,7 +3344,7 @@
VerifyObject(klass);
// Update the element in the hash set.
- *it = GcRoot<mirror::Class>(klass);
+ *existing_it = GcRoot<mirror::Class>(klass);
if (log_new_class_table_roots_) {
new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
}
@@ -3382,9 +3368,8 @@
return false;
}
-mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor, size_t hash,
mirror::ClassLoader* class_loader) {
- size_t hash = Hash(descriptor);
{
ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
mirror::Class* result = LookupClassFromTableLocked(descriptor, class_loader, hash);
@@ -3451,7 +3436,7 @@
if (klass != nullptr) {
DCHECK(klass->GetClassLoader() == nullptr);
const char* descriptor = klass->GetDescriptor(&temp);
- size_t hash = Hash(descriptor);
+ size_t hash = ComputeModifiedUtf8Hash(descriptor);
mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash);
if (existing != nullptr) {
CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != "
@@ -3952,7 +3937,8 @@
CHECK_EQ(klass.Get()->GetThrows(),
soa.Decode<mirror::ObjectArray<mirror::ObjectArray<mirror::Class>>*>(throws));
}
- mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(), Hash(descriptor.c_str()));
+ mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(),
+ ComputeModifiedUtf8Hash(descriptor.c_str()));
CHECK(existing == nullptr);
return klass.Get();
}
@@ -4499,7 +4485,8 @@
FixupTemporaryDeclaringClass(klass.Get(), new_class_h.Get());
- mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(), Hash(descriptor));
+ mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(),
+ ComputeModifiedUtf8Hash(descriptor));
CHECK(existing == nullptr || existing == klass.Get());
// This will notify waiters on temp class that saw the not yet resolved class in the
@@ -4695,7 +4682,7 @@
void Add(uint32_t virtual_method_index) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
mirror::ArtMethod* local_method = klass_->GetVirtualMethodDuringLinking(virtual_method_index);
const char* name = local_method->GetName();
- uint32_t hash = Hash(name);
+ uint32_t hash = ComputeModifiedUtf8Hash(name);
uint32_t index = hash % hash_size_;
// Linear probe until we have an empty slot.
while (hash_table_[index] != invalid_index_) {
@@ -4708,7 +4695,7 @@
uint32_t FindAndRemove(MethodNameAndSignatureComparator* comparator)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
const char* name = comparator->GetName();
- uint32_t hash = Hash(name);
+ uint32_t hash = ComputeModifiedUtf8Hash(name);
size_t index = hash % hash_size_;
while (true) {
const uint32_t value = hash_table_[index];
@@ -5888,7 +5875,7 @@
std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root)
const {
std::string temp;
- return Hash(root.Read()->GetDescriptor(&temp));
+ return ComputeModifiedUtf8Hash(root.Read()->GetDescriptor(&temp));
}
bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
@@ -5902,7 +5889,7 @@
std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(
const std::pair<const char*, mirror::ClassLoader*>& element) const {
- return Hash(element.first);
+ return ComputeModifiedUtf8Hash(element.first);
}
bool ClassLinker::ClassDescriptorHashEquals::operator()(
@@ -5919,7 +5906,7 @@
}
std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const {
- return Hash(descriptor);
+ return ComputeModifiedUtf8Hash(descriptor);
}
} // namespace art