Merge "Faster deduplication in OatWriter."
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index e1b6992..4b6d501 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -354,12 +354,12 @@
bool deduped = false;
// Deduplicate code arrays.
- auto code_iter = dedupe_map_.find(compiled_method);
- if (code_iter != dedupe_map_.end()) {
- quick_code_offset = code_iter->second;
+ auto lb = dedupe_map_.lower_bound(compiled_method);
+ if (lb != dedupe_map_.end() && !dedupe_map_.key_comp()(compiled_method, lb->first)) {
+ quick_code_offset = lb->second;
deduped = true;
} else {
- dedupe_map_.Put(compiled_method, quick_code_offset);
+ dedupe_map_.PutBefore(lb, compiled_method, quick_code_offset);
}
// Update quick method header.
@@ -386,7 +386,7 @@
code_size);
// Update checksum if this wasn't a duplicate.
- if (code_iter == dedupe_map_.end()) {
+ if (!deduped) {
writer_->oat_header_->UpdateChecksum(method_header, sizeof(*method_header));
offset_ += sizeof(*method_header); // Method header is prepended before code.
writer_->oat_header_->UpdateChecksum(&(*quick_code)[0], code_size);
@@ -485,12 +485,12 @@
const std::vector<uint8_t>* map = DataAccess::GetData(compiled_method);
uint32_t map_size = map->size() * sizeof((*map)[0]);
if (map_size != 0u) {
- auto it = dedupe_map_.find(map);
- if (it != dedupe_map_.end()) {
- DataAccess::SetOffset(oat_class, method_offsets_index_, it->second);
+ auto lb = dedupe_map_.lower_bound(map);
+ if (lb != dedupe_map_.end() && !dedupe_map_.key_comp()(map, lb->first)) {
+ DataAccess::SetOffset(oat_class, method_offsets_index_, lb->second);
} else {
DataAccess::SetOffset(oat_class, method_offsets_index_, offset_);
- dedupe_map_.Put(map, offset_);
+ dedupe_map_.PutBefore(lb, map, offset_);
offset_ += map_size;
writer_->oat_header_->UpdateChecksum(&(*map)[0], map_size);
}
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index bf3a15e..941fd0e 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -34,10 +34,12 @@
public:
typedef typename ::std::map<K, V, Comparator, Allocator>::key_compare key_compare;
+ typedef typename ::std::map<K, V, Comparator, Allocator>::value_compare value_compare;
typedef typename ::std::map<K, V, Comparator, Allocator>::allocator_type allocator_type;
typedef typename ::std::map<K, V, Comparator, Allocator>::iterator iterator;
typedef typename ::std::map<K, V, Comparator, Allocator>::const_iterator const_iterator;
typedef typename ::std::map<K, V, Comparator, Allocator>::size_type size_type;
+ typedef typename ::std::map<K, V, Comparator, Allocator>::key_type key_type;
typedef typename ::std::map<K, V, Comparator, Allocator>::value_type value_type;
SafeMap() = default;
@@ -50,6 +52,9 @@
return *this;
}
+ key_compare key_comp() const { return map_.key_comp(); }
+ value_compare value_comp() const { return map_.value_comp(); }
+
iterator begin() { return map_.begin(); }
const_iterator begin() const { return map_.begin(); }
iterator end() { return map_.end(); }
@@ -58,8 +63,9 @@
bool empty() const { return map_.empty(); }
size_type size() const { return map_.size(); }
+ void swap(Self& other) { map_.swap(other.map_); }
void clear() { map_.clear(); }
- void erase(iterator it) { map_.erase(it); }
+ iterator erase(iterator it) { return map_.erase(it); }
size_type erase(const K& k) { return map_.erase(k); }
iterator find(const K& k) { return map_.find(k); }
@@ -78,9 +84,18 @@
}
// Used to insert a new mapping.
- void Put(const K& k, const V& v) {
- std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v));
+ iterator Put(const K& k, const V& v) {
+ std::pair<iterator, bool> result = map_.emplace(k, v);
DCHECK(result.second); // Check we didn't accidentally overwrite an existing value.
+ return result.first;
+ }
+
+ // Used to insert a new mapping at a known position for better performance.
+ iterator PutBefore(iterator pos, const K& k, const V& v) {
+ // Check that we're using the correct position and the key is not in the map.
+ DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
+ DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
+ return map_.emplace_hint(pos, k, v);
}
// Used to insert a new mapping or overwrite an existing mapping. Note that if the value type
@@ -102,13 +117,15 @@
::std::map<K, V, Comparator, Allocator> map_;
};
-template <typename K, typename V, typename Comparator>
-bool operator==(const SafeMap<K, V, Comparator>& lhs, const SafeMap<K, V, Comparator>& rhs) {
+template <typename K, typename V, typename Comparator, typename Allocator>
+bool operator==(const SafeMap<K, V, Comparator, Allocator>& lhs,
+ const SafeMap<K, V, Comparator, Allocator>& rhs) {
return lhs.Equals(rhs);
}
-template <typename K, typename V, typename Comparator>
-bool operator!=(const SafeMap<K, V, Comparator>& lhs, const SafeMap<K, V, Comparator>& rhs) {
+template <typename K, typename V, typename Comparator, typename Allocator>
+bool operator!=(const SafeMap<K, V, Comparator, Allocator>& lhs,
+ const SafeMap<K, V, Comparator, Allocator>& rhs) {
return !(lhs == rhs);
}
