From c73743cfd9718a8e1eeb9c9220c182a475935a1c Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Wed, 3 Dec 2014 15:28:15 +0000 Subject: [PATCH] Rewrite ImageWriter's merging of String char[]s. Simply sort the Strings and then look at two consecutive Strings to find prefixes and duplicates. Avoid unnecessary memory allocations. Change-Id: I996306ed4b31e61f9f0def8f3bcce71eb01c9265 --- compiler/image_writer.cc | 130 ++++++++++++++++++++--------------------------- 1 file changed, 54 insertions(+), 76 deletions(-) diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc index ab5c6c77d..a50714d49 100644 --- a/compiler/image_writer.cc +++ b/compiler/image_writer.cc @@ -480,34 +480,29 @@ class StringCollector { }; // Compare strings based on length, used for sorting strings by length / reverse length. -class StringLengthComparator { +class LexicographicalStringComparator { public: - explicit StringLengthComparator(Handle> strings) - : strings_(strings) { + bool operator()(const mirror::HeapReference& lhs, + const mirror::HeapReference& rhs) const + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + mirror::String* lhs_s = lhs.AsMirrorPtr(); + mirror::String* rhs_s = rhs.AsMirrorPtr(); + uint16_t* lhs_begin = lhs_s->GetCharArray()->GetData() + lhs_s->GetOffset(); + uint16_t* rhs_begin = rhs_s->GetCharArray()->GetData() + rhs_s->GetOffset(); + return std::lexicographical_compare(lhs_begin, lhs_begin + lhs_s->GetLength(), + rhs_begin, rhs_begin + rhs_s->GetLength()); } - bool operator()(size_t a, size_t b) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { - return strings_->GetWithoutChecks(a)->GetLength() < strings_->GetWithoutChecks(b)->GetLength(); - } - - private: - Handle> strings_; }; -// Normal string < comparison through the chars_ array. -class SubstringComparator { - public: - explicit SubstringComparator(const std::vector* const chars) : chars_(chars) { - } - bool operator()(const std::pair& a, const std::pair& b) { - return std::lexicographical_compare(chars_->begin() + a.first, - chars_->begin() + a.first + a.second, - chars_->begin() + b.first, - chars_->begin() + b.first + b.second); +static bool IsPrefix(mirror::String* pref, mirror::String* full) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + if (pref->GetLength() > full->GetLength()) { + return false; } - - private: - const std::vector* const chars_; -}; + uint16_t* pref_begin = pref->GetCharArray()->GetData() + pref->GetOffset(); + uint16_t* full_begin = full->GetCharArray()->GetData() + full->GetOffset(); + return std::equal(pref_begin, pref_begin + pref->GetLength(), full_begin); +} void ImageWriter::ProcessStrings() { size_t total_strings = 0; @@ -529,67 +524,50 @@ void ImageWriter::ProcessStrings() { // Some strings could have gotten freed if AllocStringArray caused a GC. CHECK_LE(string_collector.GetIndex(), total_strings); total_strings = string_collector.GetIndex(); - size_t total_length = 0; - std::vector reverse_sorted_strings; - for (size_t i = 0; i < total_strings; ++i) { - mirror::String* s = strings->GetWithoutChecks(i); - // Look up the string in the array. - total_length += s->GetLength(); - reverse_sorted_strings.push_back(i); - } - // Sort by reverse length. - StringLengthComparator comparator(strings); - std::sort(reverse_sorted_strings.rbegin(), reverse_sorted_strings.rend(), comparator); - // Deduplicate prefixes and add strings to the char array. - std::vector combined_chars(total_length, 0U); - size_t num_chars = 0; + auto* strings_begin = reinterpret_cast*>( + strings->GetRawData(sizeof(mirror::HeapReference), 0)); + std::sort(strings_begin, strings_begin + total_strings, LexicographicalStringComparator()); // Characters of strings which are non equal prefix of another string (not the same string). // We don't count the savings from equal strings since these would get interned later anyways. size_t prefix_saved_chars = 0; - std::set, SubstringComparator> existing_strings(( - SubstringComparator(&combined_chars))); - for (size_t i = 0; i < total_strings; ++i) { - mirror::String* s = strings->GetWithoutChecks(reverse_sorted_strings[i]); - // Add the string to the end of the char array. + // Count characters needed for the strings. + size_t num_chars = 0u; + mirror::String* prev_s = nullptr; + for (size_t idx = 0; idx != total_strings; ++idx) { + mirror::String* s = strings->GetWithoutChecks(idx); size_t length = s->GetLength(); - for (size_t j = 0; j < length; ++j) { - combined_chars[num_chars++] = s->CharAt(j); - } - // Try to see if the string exists as a prefix of an existing string. - size_t new_offset = 0; - std::pair new_string(num_chars - length, length); - auto it = existing_strings.lower_bound(new_string); - bool is_prefix = false; - if (it != existing_strings.end()) { - CHECK_LE(length, it->second); - is_prefix = std::equal(combined_chars.begin() + new_string.first, - combined_chars.begin() + new_string.first + new_string.second, - combined_chars.begin() + it->first); - } - if (is_prefix) { - // Shares a prefix, set the offset to where the new offset will be. - new_offset = it->first; - // Remove the added chars. - num_chars -= length; - if (it->second != length) { - prefix_saved_chars += length; + num_chars += length; + if (prev_s != nullptr && IsPrefix(prev_s, s)) { + size_t prev_length = prev_s->GetLength(); + num_chars -= prev_length; + if (prev_length != length) { + prefix_saved_chars += prev_length; } - } else { - new_offset = new_string.first; - existing_strings.insert(new_string); } - s->SetOffset(new_offset); - } - // Allocate and update the char arrays. - auto* array = mirror::CharArray::Alloc(self, num_chars); - for (size_t i = 0; i < num_chars; ++i) { - array->SetWithoutChecks(i, combined_chars[i]); - } - for (size_t i = 0; i < total_strings; ++i) { - strings->GetWithoutChecks(i)->SetArray(array); + prev_s = s; + } + // Create character array, copy characters and point the strings there. + mirror::CharArray* array = mirror::CharArray::Alloc(self, num_chars); + uint16_t* array_data = array->GetData(); + size_t pos = 0u; + prev_s = nullptr; + for (size_t idx = 0; idx != total_strings; ++idx) { + mirror::String* s = strings->GetWithoutChecks(idx); + uint16_t* s_data = s->GetCharArray()->GetData(); + int32_t s_length = s->GetLength(); + int32_t prefix_length = 0u; + if (idx != 0u && IsPrefix(prev_s, s)) { + prefix_length = prev_s->GetLength(); + } + memcpy(array_data + pos, s_data + prefix_length, (s_length - prefix_length) * sizeof(*s_data)); + s->SetOffset(pos - prefix_length); + s->SetArray(array); + pos += s_length - prefix_length; + prev_s = s; } + LOG(INFO) << "Total # image strings=" << total_strings << " combined length=" - << total_length << " prefix saved chars=" << prefix_saved_chars; + << num_chars << " prefix saved chars=" << prefix_saved_chars; ComputeEagerResolvedStrings(); } -- 2.11.0