Use binary search for FindDeclaredInstance/StaticField
Before:
real 1m18.157s
user 1m8.167s
sys 0m8.071s
After:
real 1m12.943s
user 1m3.223s
sys 0m7.881s
Perf results:
FindDeclaredStaticField: 1.78% -> 0.11%
__GI___strncmp_ssse3: 2.45% -> 0.87%
Bug: 10921004
Change-Id: Ice7d3ce2635d6cd2de5574055375d9e20712d241
diff --git a/runtime/base/stringpiece.h b/runtime/base/stringpiece.h
index d793bb6..9c83cf5 100644
--- a/runtime/base/stringpiece.h
+++ b/runtime/base/stringpiece.h
@@ -148,6 +148,19 @@
StringPiece substr(size_type pos, size_type n = npos) const;
+ int Compare(const StringPiece& rhs) const {
+ const int r = memcmp(data(), rhs.data(), std::min(size(), rhs.size()));
+ if (r != 0) {
+ return r;
+ }
+ if (size() < rhs.size()) {
+ return -1;
+ } else if (size() > rhs.size()) {
+ return 1;
+ }
+ return 0;
+ }
+
private:
// Pointer to char data, not necessarily zero terminated.
const char* ptr_;
@@ -201,9 +214,7 @@
}
inline bool operator<(const StringPiece& x, const StringPiece& y) {
- const int r = memcmp(x.data(), y.data(),
- std::min(x.size(), y.size()));
- return ((r < 0) || ((r == 0) && (x.size() < y.size())));
+ return x.Compare(y) < 0;
}
inline bool operator>(const StringPiece& x, const StringPiece& y) {
diff --git a/runtime/mirror/class.cc b/runtime/mirror/class.cc
index 2ac44fc..53fedab 100644
--- a/runtime/mirror/class.cc
+++ b/runtime/mirror/class.cc
@@ -565,24 +565,58 @@
return nullptr;
}
-ArtField* Class::FindDeclaredInstanceField(const StringPiece& name, const StringPiece& type) {
- // Is the field in this class?
- // Interfaces are not relevant because they can't contain instance fields.
- for (size_t i = 0; i < NumInstanceFields(); ++i) {
- ArtField* f = GetInstanceField(i);
- if (name == f->GetName() && type == f->GetTypeDescriptor()) {
- return f;
+// Custom binary search to avoid double comparisons from std::binary_search.
+static ArtField* FindFieldByNameAndType(LengthPrefixedArray<ArtField>* fields,
+ const StringPiece& name,
+ const StringPiece& type)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
+ if (fields == nullptr) {
+ return nullptr;
+ }
+ size_t low = 0;
+ size_t high = fields->Length();
+ ArtField* ret = nullptr;
+ while (low < high) {
+ size_t mid = (low + high) / 2;
+ ArtField& field = fields->At(mid);
+ // Fields are sorted by class, then name, then type descriptor. This is verified in dex file
+ // verifier. There can be multiple fields with the same in the same class name due to proguard.
+ int result = StringPiece(field.GetName()).Compare(name);
+ if (result == 0) {
+ result = StringPiece(field.GetTypeDescriptor()).Compare(type);
+ }
+ if (result < 0) {
+ low = mid + 1;
+ } else if (result > 0) {
+ high = mid;
+ } else {
+ ret = &field;
+ break;
}
}
- return nullptr;
+ if (kIsDebugBuild) {
+ ArtField* found = nullptr;
+ for (ArtField& field : MakeIterationRangeFromLengthPrefixedArray(fields)) {
+ if (name == field.GetName() && type == field.GetTypeDescriptor()) {
+ found = &field;
+ break;
+ }
+ }
+ CHECK_EQ(found, ret) << "Found " << PrettyField(found) << " vs " << PrettyField(ret);
+ }
+ return ret;
+}
+
+ArtField* Class::FindDeclaredInstanceField(const StringPiece& name, const StringPiece& type) {
+ // Binary search by name. Interfaces are not relevant because they can't contain instance fields.
+ return FindFieldByNameAndType(GetIFieldsPtr(), name, type);
}
ArtField* Class::FindDeclaredInstanceField(const DexCache* dex_cache, uint32_t dex_field_idx) {
if (GetDexCache() == dex_cache) {
- for (size_t i = 0; i < NumInstanceFields(); ++i) {
- ArtField* f = GetInstanceField(i);
- if (f->GetDexFieldIndex() == dex_field_idx) {
- return f;
+ for (ArtField& field : GetIFields()) {
+ if (field.GetDexFieldIndex() == dex_field_idx) {
+ return &field;
}
}
}
@@ -615,21 +649,14 @@
ArtField* Class::FindDeclaredStaticField(const StringPiece& name, const StringPiece& type) {
DCHECK(type != nullptr);
- for (size_t i = 0; i < NumStaticFields(); ++i) {
- ArtField* f = GetStaticField(i);
- if (name == f->GetName() && type == f->GetTypeDescriptor()) {
- return f;
- }
- }
- return nullptr;
+ return FindFieldByNameAndType(GetSFieldsPtr(), name, type);
}
ArtField* Class::FindDeclaredStaticField(const DexCache* dex_cache, uint32_t dex_field_idx) {
if (dex_cache == GetDexCache()) {
- for (size_t i = 0; i < NumStaticFields(); ++i) {
- ArtField* f = GetStaticField(i);
- if (f->GetDexFieldIndex() == dex_field_idx) {
- return f;
+ for (ArtField& field : GetSFields()) {
+ if (field.GetDexFieldIndex() == dex_field_idx) {
+ return &field;
}
}
}
