ART: Change StringTable for RecentAllocations
Avoid the expensive std::distance call by caching the index inside
the set element. This requires a mutable field and a Finish call.
Effect on b/37620770 repro case: Dump time = ~ 12s -> 3.7s
Bug: 37620770
Test: m test-art-host
Change-Id: I6ab89e0e99994466183042bd59358439f98dde42
diff --git a/runtime/debugger.cc b/runtime/debugger.cc
index 4c67adc..f9828d6 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -4925,14 +4925,33 @@
}
class StringTable {
+ private:
+ struct Entry {
+ explicit Entry(const char* data_in) : data(data_in), index(0) {}
+ Entry(const Entry& entry) = default;
+ Entry(Entry&& entry) = default;
+
+ // Pointer to the actual string data.
+ const char* data;
+ // The index. This will be filled in on Finish and is not part of the ordering, so mark it
+ // mutable.
+ mutable uint32_t index;
+
+ bool operator<(const Entry& other) const {
+ return strcmp(data, other.data) < 0;
+ }
+ };
+
public:
- StringTable() {
+ StringTable() : finished_(false) {
}
void Add(const char* str, bool copy_string) {
+ DCHECK(!finished_);
if (UNLIKELY(copy_string)) {
// Check whether it's already there.
- if (table_.find(str) != table_.end()) {
+ Entry entry(str);
+ if (table_.find(entry) != table_.end()) {
return;
}
@@ -4943,15 +4962,33 @@
string_backup_.emplace_back(copy);
str = copy;
}
- table_.insert(str);
+ Entry entry(str);
+ table_.insert(entry);
+ }
+
+ // Update all entries and give them an index. Note that this is likely not the insertion order,
+ // as the set will with high likelihood reorder elements. Thus, Add must not be called after
+ // Finish, and Finish must be called before IndexOf. In that case, WriteTo will walk in
+ // the same order as Finish, and indices will agree. The order invariant, as well as indices,
+ // are enforced through debug checks.
+ void Finish() {
+ DCHECK(!finished_);
+ finished_ = true;
+ uint32_t index = 0;
+ for (auto& entry : table_) {
+ entry.index = index;
+ ++index;
+ }
}
size_t IndexOf(const char* s) const {
- auto it = table_.find(s);
+ DCHECK(finished_);
+ Entry entry(s);
+ auto it = table_.find(entry);
if (it == table_.end()) {
LOG(FATAL) << "IndexOf(\"" << s << "\") failed";
}
- return std::distance(table_.begin(), it);
+ return it->index;
}
size_t Size() const {
@@ -4959,23 +4996,24 @@
}
void WriteTo(std::vector<uint8_t>& bytes) const {
- for (const char* str : table_) {
- size_t s_len = CountModifiedUtf8Chars(str);
+ DCHECK(finished_);
+ uint32_t cur_index = 0;
+ for (const auto& entry : table_) {
+ DCHECK_EQ(cur_index++, entry.index);
+
+ size_t s_len = CountModifiedUtf8Chars(entry.data);
std::unique_ptr<uint16_t[]> s_utf16(new uint16_t[s_len]);
- ConvertModifiedUtf8ToUtf16(s_utf16.get(), str);
+ ConvertModifiedUtf8ToUtf16(s_utf16.get(), entry.data);
JDWP::AppendUtf16BE(bytes, s_utf16.get(), s_len);
}
}
private:
- struct ConstCharStarComparator {
- bool operator()(const char *s1, const char *s2) const {
- return strcmp(s1, s2) < 0;
- }
- };
-
- std::set<const char*, ConstCharStarComparator> table_;
+ std::set<Entry> table_;
std::vector<std::unique_ptr<char[]>> string_backup_;
+
+ bool finished_;
+
DISALLOW_COPY_AND_ASSIGN(StringTable);
};
@@ -5082,6 +5120,9 @@
alloc_byte_count += record->GetDepth() * (2u + 2u + 2u + 2u);
}
+ class_names.Finish();
+ method_names.Finish();
+ filenames.Finish();
VLOG(jdwp) << "Done collecting StringTables:" << std::endl
<< " ClassNames: " << class_names.Size() << std::endl
<< " MethodNames: " << method_names.Size() << std::endl