Change intern table to unordered set.
Intern table active used bytes goes from 430k to 317k on system
server. Similar %wise savings on other apps.
Bug: 16238192
(cherry picked from commit d910fcef539e12ab181e56ec80684f39c4e95733)
Change-Id: Ic70395124435c6f420a77e6d8639404a160f395a
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index aadd85a..c66f99e 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -22,7 +22,7 @@
#include "mirror/dex_cache.h"
#include "mirror/object_array-inl.h"
#include "mirror/object-inl.h"
-#include "mirror/string.h"
+#include "mirror/string-inl.h"
#include "thread.h"
#include "utf.h"
@@ -58,25 +58,23 @@
MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
if ((flags & kVisitRootFlagAllRoots) != 0) {
for (auto& strong_intern : strong_interns_) {
- strong_intern.second.VisitRoot(callback, arg, 0, kRootInternedString);
- DCHECK(!strong_intern.second.IsNull());
+ const_cast<GcRoot<mirror::String>&>(strong_intern).
+ VisitRoot(callback, arg, 0, kRootInternedString);
+ DCHECK(!strong_intern.IsNull());
}
} else if ((flags & kVisitRootFlagNewRoots) != 0) {
- for (auto& pair : new_strong_intern_roots_) {
- mirror::String* old_ref = pair.second.Read<kWithoutReadBarrier>();
- pair.second.VisitRoot(callback, arg, 0, kRootInternedString);
- mirror::String* new_ref = pair.second.Read<kWithoutReadBarrier>();
+ for (auto& root : new_strong_intern_roots_) {
+ mirror::String* old_ref = root.Read<kWithoutReadBarrier>();
+ root.VisitRoot(callback, arg, 0, kRootInternedString);
+ mirror::String* new_ref = root.Read<kWithoutReadBarrier>();
if (UNLIKELY(new_ref != old_ref)) {
- // Uh ohes, GC moved a root in the log. Need to search the strong interns and update the
+ // The GC moved a root in the log. Need to search the strong interns and update the
// corresponding object. This is slow, but luckily for us, this may only happen with a
// concurrent moving GC.
- for (auto it = strong_interns_.lower_bound(pair.first), end = strong_interns_.end();
- it != end && it->first == pair.first; ++it) {
- // If the class stored matches the old class, update it to the new value.
- if (old_ref == it->second.Read<kWithoutReadBarrier>()) {
- it->second = GcRoot<mirror::String>(new_ref);
- }
- }
+ auto it = strong_interns_.find(GcRoot<mirror::String>(old_ref));
+ DCHECK(it != strong_interns_.end());
+ strong_interns_.erase(it);
+ strong_interns_.insert(GcRoot<mirror::String>(new_ref));
}
}
}
@@ -92,87 +90,79 @@
// Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
}
-mirror::String* InternTable::LookupStrong(mirror::String* s, int32_t hash_code) {
- return Lookup(&strong_interns_, s, hash_code);
+mirror::String* InternTable::LookupStrong(mirror::String* s) {
+ return Lookup(&strong_interns_, s);
}
-mirror::String* InternTable::LookupWeak(mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::LookupWeak(mirror::String* s) {
// Weak interns need a read barrier because they are weak roots.
- return Lookup(&weak_interns_, s, hash_code);
+ return Lookup(&weak_interns_, s);
}
-mirror::String* InternTable::Lookup(Table* table, mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::Lookup(Table* table, mirror::String* s) {
Locks::intern_table_lock_->AssertHeld(Thread::Current());
- for (auto it = table->lower_bound(hash_code), end = table->end();
- it != end && it->first == hash_code; ++it) {
- mirror::String* existing_string = it->second.Read();
- if (existing_string->Equals(s)) {
- return existing_string;
- }
+ auto it = table->find(GcRoot<mirror::String>(s));
+ if (LIKELY(it != table->end())) {
+ return const_cast<GcRoot<mirror::String>&>(*it).Read<kWithReadBarrier>();
}
- return NULL;
+ return nullptr;
}
-mirror::String* InternTable::InsertStrong(mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::InsertStrong(mirror::String* s) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
- runtime->RecordStrongStringInsertion(s, hash_code);
+ runtime->RecordStrongStringInsertion(s);
}
if (log_new_roots_) {
- new_strong_intern_roots_.push_back(std::make_pair(hash_code, GcRoot<mirror::String>(s)));
+ new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
}
- strong_interns_.insert(std::make_pair(hash_code, GcRoot<mirror::String>(s)));
+ strong_interns_.insert(GcRoot<mirror::String>(s));
return s;
}
-mirror::String* InternTable::InsertWeak(mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::InsertWeak(mirror::String* s) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
- runtime->RecordWeakStringInsertion(s, hash_code);
+ runtime->RecordWeakStringInsertion(s);
}
- weak_interns_.insert(std::make_pair(hash_code, GcRoot<mirror::String>(s)));
+ weak_interns_.insert(GcRoot<mirror::String>(s));
return s;
}
-void InternTable::RemoveStrong(mirror::String* s, int32_t hash_code) {
- Remove(&strong_interns_, s, hash_code);
+void InternTable::RemoveStrong(mirror::String* s) {
+ Remove(&strong_interns_, s);
}
-void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) {
+void InternTable::RemoveWeak(mirror::String* s) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
- runtime->RecordWeakStringRemoval(s, hash_code);
+ runtime->RecordWeakStringRemoval(s);
}
- Remove(&weak_interns_, s, hash_code);
+ Remove(&weak_interns_, s);
}
-void InternTable::Remove(Table* table, mirror::String* s, int32_t hash_code) {
- for (auto it = table->lower_bound(hash_code), end = table->end();
- it != end && it->first == hash_code; ++it) {
- mirror::String* existing_string = it->second.Read();
- if (existing_string == s) {
- table->erase(it);
- return;
- }
- }
+void InternTable::Remove(Table* table, mirror::String* s) {
+ auto it = table->find(GcRoot<mirror::String>(s));
+ DCHECK(it != table->end());
+ table->erase(it);
}
// Insert/remove methods used to undo changes made during an aborted transaction.
-mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s) {
DCHECK(!Runtime::Current()->IsActiveTransaction());
- return InsertStrong(s, hash_code);
+ return InsertStrong(s);
}
-mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s, int32_t hash_code) {
+mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s) {
DCHECK(!Runtime::Current()->IsActiveTransaction());
- return InsertWeak(s, hash_code);
+ return InsertWeak(s);
}
-void InternTable::RemoveStrongFromTransaction(mirror::String* s, int32_t hash_code) {
+void InternTable::RemoveStrongFromTransaction(mirror::String* s) {
DCHECK(!Runtime::Current()->IsActiveTransaction());
- RemoveStrong(s, hash_code);
+ RemoveStrong(s);
}
-void InternTable::RemoveWeakFromTransaction(mirror::String* s, int32_t hash_code) {
+void InternTable::RemoveWeakFromTransaction(mirror::String* s) {
DCHECK(!Runtime::Current()->IsActiveTransaction());
- RemoveWeak(s, hash_code);
+ RemoveWeak(s);
}
static mirror::String* LookupStringFromImage(mirror::String* s)
@@ -218,7 +208,6 @@
MutexLock mu(self, *Locks::intern_table_lock_);
DCHECK(s != NULL);
- uint32_t hash_code = s->GetHashCode();
while (UNLIKELY(!allow_new_interns_)) {
new_intern_condition_.WaitHoldingLocks(self);
@@ -226,7 +215,7 @@
if (is_strong) {
// Check the strong table for a match.
- mirror::String* strong = LookupStrong(s, hash_code);
+ mirror::String* strong = LookupStrong(s);
if (strong != NULL) {
return strong;
}
@@ -234,39 +223,39 @@
// Check the image for a match.
mirror::String* image = LookupStringFromImage(s);
if (image != NULL) {
- return InsertStrong(image, hash_code);
+ return InsertStrong(image);
}
// There is no match in the strong table, check the weak table.
- mirror::String* weak = LookupWeak(s, hash_code);
+ mirror::String* weak = LookupWeak(s);
if (weak != NULL) {
// A match was found in the weak table. Promote to the strong table.
- RemoveWeak(weak, hash_code);
- return InsertStrong(weak, hash_code);
+ RemoveWeak(weak);
+ return InsertStrong(weak);
}
// No match in the strong table or the weak table. Insert into the strong
// table.
- return InsertStrong(s, hash_code);
+ return InsertStrong(s);
}
// Check the strong table for a match.
- mirror::String* strong = LookupStrong(s, hash_code);
+ mirror::String* strong = LookupStrong(s);
if (strong != NULL) {
return strong;
}
// Check the image for a match.
mirror::String* image = LookupStringFromImage(s);
if (image != NULL) {
- return InsertWeak(image, hash_code);
+ return InsertWeak(image);
}
// Check the weak table for a match.
- mirror::String* weak = LookupWeak(s, hash_code);
+ mirror::String* weak = LookupWeak(s);
if (weak != NULL) {
return weak;
}
// Insert into the weak table.
- return InsertWeak(s, hash_code);
+ return InsertWeak(s);
}
mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
@@ -296,7 +285,7 @@
bool InternTable::ContainsWeak(mirror::String* s) {
MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
- const mirror::String* found = LookupWeak(s, s->GetHashCode());
+ const mirror::String* found = LookupWeak(s);
return found == s;
}
@@ -304,16 +293,33 @@
MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
// This does not need a read barrier because this is called by GC.
- mirror::Object* object = it->second.Read<kWithoutReadBarrier>();
+ GcRoot<mirror::String>& root = const_cast<GcRoot<mirror::String>&>(*it);
+ mirror::Object* object = root.Read<kWithoutReadBarrier>();
mirror::Object* new_object = callback(object, arg);
if (new_object == nullptr) {
- // TODO: use it = weak_interns_.erase(it) when we get a c++11 stl.
- weak_interns_.erase(it++);
+ it = weak_interns_.erase(it);
} else {
- it->second = GcRoot<mirror::String>(down_cast<mirror::String*>(new_object));
+ root.Assign(down_cast<mirror::String*>(new_object));
++it;
}
}
}
+std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) {
+ if (kIsDebugBuild) {
+ Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
+ }
+ return static_cast<size_t>(
+ const_cast<GcRoot<mirror::String>&>(root).Read<kWithoutReadBarrier>()->GetHashCode());
+}
+
+bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
+ const GcRoot<mirror::String>& b) {
+ if (kIsDebugBuild) {
+ Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
+ }
+ return const_cast<GcRoot<mirror::String>&>(a).Read<kWithoutReadBarrier>()->Equals(
+ const_cast<GcRoot<mirror::String>&>(b).Read<kWithoutReadBarrier>());
+}
+
} // namespace art