Faster hashing in `ClassLinker::LinkVirtualMethods()`.
Measurement shows that `ComputeModifiedUtf8Hash()` is faster
when iterating over `std::string_view` than `const char*`.
However, getting the length of the string with `strlen()`
would outweigh the benefits, so we shall only use the new
`ComputeModifiedUtf8Hash(std::string_view)` overload when
we can avoid (or usually avoid) the `strlen()` call.
In `ClassLinker::LinkVirtualMethods()`, method names come
from the dex file and we can avoid the `strlen()` call as
long as they are ASCII which is usually the case (at least
for boot class path methods; proguarded apps sometimes use
non-ASCII method names), so use `std::string_view` there.
Also simplify the code a bit, avoiding the UTF16 length
comparison. This has some trade-offs as we delay the length
comparison until we know the length in chars (and compare
that length instead) but we also replace `strcmp()` with a
faster `memcmp()`.
The changes to the Modified UTF-8 hashing API also prepare
for future work such as calculating array class descriptor
hash without a string allocation for the full descriptor.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 181943478
Change-Id: I6d45f738903000c55d401b776906dac83fca1a19
diff --git a/libdexfile/dex/utf.cc b/libdexfile/dex/utf.cc
index 3eb80b1..bfc704d 100644
--- a/libdexfile/dex/utf.cc
+++ b/libdexfile/dex/utf.cc
@@ -192,14 +192,18 @@
}
uint32_t ComputeModifiedUtf8Hash(const char* chars) {
- uint32_t hash = 0;
+ uint32_t hash = StartModifiedUtf8Hash();
while (*chars != '\0') {
- hash = hash * 31 + static_cast<uint8_t>(*chars);
+ hash = UpdateModifiedUtf8Hash(hash, *chars);
++chars;
}
return hash;
}
+uint32_t ComputeModifiedUtf8Hash(std::string_view chars) {
+ return UpdateModifiedUtf8Hash(StartModifiedUtf8Hash(), chars);
+}
+
int CompareModifiedUtf8ToUtf16AsCodePointValues(const char* utf8, const uint16_t* utf16,
size_t utf16_length) {
for (;;) {
diff --git a/libdexfile/dex/utf.h b/libdexfile/dex/utf.h
index c86b389..e3dc7f9 100644
--- a/libdexfile/dex/utf.h
+++ b/libdexfile/dex/utf.h
@@ -23,6 +23,7 @@
#include <stdint.h>
#include <string>
+#include <string_view>
/*
* All UTF-8 in art is actually modified UTF-8. Mostly, this distinction
@@ -90,6 +91,27 @@
// Compute a hash code of a modified UTF-8 string. Not the standard java hash since it returns a
// uint32_t and hashes individual chars instead of codepoint words.
uint32_t ComputeModifiedUtf8Hash(const char* chars);
+uint32_t ComputeModifiedUtf8Hash(std::string_view chars);
+
+// The starting value of a modified UTF-8 hash.
+constexpr uint32_t StartModifiedUtf8Hash() {
+ return 0u;
+}
+
+// Update a modified UTF-8 hash with one character.
+ALWAYS_INLINE
+inline uint32_t UpdateModifiedUtf8Hash(uint32_t hash, char c) {
+ return hash * 31u + static_cast<uint8_t>(c);
+}
+
+// Update a modified UTF-8 hash with characters of a `std::string_view`.
+ALWAYS_INLINE
+inline uint32_t UpdateModifiedUtf8Hash(uint32_t hash, std::string_view chars) {
+ for (char c : chars) {
+ hash = UpdateModifiedUtf8Hash(hash, c);
+ }
+ return hash;
+}
/*
* Retrieve the next UTF-16 character or surrogate pair from a UTF-8 string.
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index bfad3a9..f3f7afd 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1139,7 +1139,7 @@
ArraySlice<ArtMethod> virtual_methods = java_lang_Object->GetVirtualMethods(pointer_size);
DCHECK_EQ(virtual_method_hashes.size(), virtual_methods.size());
for (size_t i = 0; i != virtual_method_hashes.size(); ++i) {
- const char* name = virtual_methods[i].GetName();
+ std::string_view name = virtual_methods[i].GetNameView();
virtual_method_hashes[i] = ComputeModifiedUtf8Hash(name);
}
}
@@ -6344,15 +6344,15 @@
explicit MethodNameAndSignatureComparator(ArtMethod* method)
REQUIRES_SHARED(Locks::mutator_lock_) :
dex_file_(method->GetDexFile()), mid_(&dex_file_->GetMethodId(method->GetDexMethodIndex())),
- name_(nullptr), name_len_(0) {
+ name_view_() {
DCHECK(!method->IsProxyMethod()) << method->PrettyMethod();
}
- const char* GetName() {
- if (name_ == nullptr) {
- name_ = dex_file_->StringDataAndUtf16LengthByIdx(mid_->name_idx_, &name_len_);
+ ALWAYS_INLINE std::string_view GetNameView() {
+ if (name_view_.empty()) {
+ name_view_ = dex_file_->StringViewByIdx(mid_->name_idx_);
}
- return name_;
+ return name_view_;
}
bool HasSameNameAndSignature(ArtMethod* other)
@@ -6363,14 +6363,8 @@
if (dex_file_ == other_dex_file) {
return mid_->name_idx_ == other_mid.name_idx_ && mid_->proto_idx_ == other_mid.proto_idx_;
}
- GetName(); // Only used to make sure its calculated.
- uint32_t other_name_len;
- const char* other_name = other_dex_file->StringDataAndUtf16LengthByIdx(other_mid.name_idx_,
- &other_name_len);
- if (name_len_ != other_name_len || strcmp(name_, other_name) != 0) {
- return false;
- }
- return dex_file_->GetMethodSignature(*mid_) == other_dex_file->GetMethodSignature(other_mid);
+ return GetNameView() == other_dex_file->StringViewByIdx(other_mid.name_idx_) &&
+ dex_file_->GetMethodSignature(*mid_) == other_dex_file->GetMethodSignature(other_mid);
}
private:
@@ -6379,9 +6373,7 @@
// MethodId for the method to compare against.
const dex::MethodId* const mid_;
// Lazily computed name from the dex file's strings.
- const char* name_;
- // Lazily computed name length.
- uint32_t name_len_;
+ std::string_view name_view_;
};
class LinkVirtualHashTable {
@@ -6400,8 +6392,9 @@
void Add(uint32_t virtual_method_index) REQUIRES_SHARED(Locks::mutator_lock_) {
ArtMethod* local_method = klass_->GetVirtualMethodDuringLinking(
virtual_method_index, image_pointer_size_);
- const char* name = local_method->GetInterfaceMethodIfProxy(image_pointer_size_)->GetName();
- uint32_t hash = ComputeModifiedUtf8Hash(name);
+ std::string_view name_view =
+ local_method->GetInterfaceMethodIfProxy(image_pointer_size_)->GetNameView();
+ uint32_t hash = ComputeModifiedUtf8Hash(name_view);
uint32_t index = hash % hash_size_;
// Linear probe until we have an empty slot.
while (hash_table_[index] != invalid_index_) {
@@ -6414,7 +6407,7 @@
uint32_t FindAndRemove(MethodNameAndSignatureComparator* comparator, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) {
- DCHECK_EQ(hash, ComputeModifiedUtf8Hash(comparator->GetName()));
+ DCHECK_EQ(hash, ComputeModifiedUtf8Hash(comparator->GetNameView()));
size_t index = hash % hash_size_;
while (true) {
const uint32_t value = hash_table_[index];
@@ -6586,7 +6579,7 @@
// smaller as we go on.
uint32_t hash = (j < mirror::Object::kVTableLength)
? object_virtual_method_hashes_[j]
- : ComputeModifiedUtf8Hash(super_method_name_comparator.GetName());
+ : ComputeModifiedUtf8Hash(super_method_name_comparator.GetNameView());
uint32_t hash_index = hash_table.FindAndRemove(&super_method_name_comparator, hash);
if (hash_index != hash_table.GetNotFoundIndex()) {
ArtMethod* virtual_method = klass->GetVirtualMethodDuringLinking(