Use HashMap for DexFileVerifier
Before:
2.51% std::map<unsigned int, unsigned short>::insert(...
0.72% malloc
After:
0.73% art::HashSet<std::__1::pair<unsigned int, unsigned short>::Insert(...
0.57% malloc
The allocation from HashSet is only 0.71% of the remaining 0.57% malloc time.
0.71% art::DexFileVerifier::CheckIntraSectionIterate(unsigned long, unsigned int, unsigned short)
Bug: 10921004
Change-Id: I85c60bf27fb2d9976b944fc15d8401904432dc22
diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h
index ad255b8..969f5b9 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -22,6 +22,7 @@
#include <unordered_map>
#include "atomic.h"
+#include "base/hash_map.h"
#include "base/macros.h"
#include "base/mutex.h"
#include "base/type_static_if.h"
@@ -170,6 +171,14 @@
using AllocationTrackingUnorderedMap = std::unordered_map<
Key, T, Hash, Pred, TrackingAllocator<std::pair<const Key, T>, kTag>>;
+template<class Key,
+ class T,
+ class EmptyFn,
+ AllocatorTag kTag,
+ class Hash = std::hash<Key>,
+ class Pred = std::equal_to<Key>>
+using AllocationTrackingHashMap = HashMap<
+ Key, T, EmptyFn, Hash, Pred, TrackingAllocator<std::pair<Key, T>, kTag>>;
} // namespace art
#endif // ART_RUNTIME_BASE_ALLOCATOR_H_
diff --git a/runtime/dex_file_verifier.cc b/runtime/dex_file_verifier.cc
index a5f9d09..440d696 100644
--- a/runtime/dex_file_verifier.cc
+++ b/runtime/dex_file_verifier.cc
@@ -1416,7 +1416,12 @@
}
if (IsDataSectionType(type)) {
- offset_to_type_map_.Put(aligned_offset, type);
+ if (aligned_offset == 0u) {
+ ErrorStringPrintf("Item %d offset is 0", i);
+ return false;
+ }
+ DCHECK(offset_to_type_map_.Find(aligned_offset) == offset_to_type_map_.end());
+ offset_to_type_map_.Insert(std::pair<uint32_t, uint16_t>(aligned_offset, type));
}
aligned_offset = ptr_ - begin_;
@@ -1589,7 +1594,8 @@
}
bool DexFileVerifier::CheckOffsetToTypeMap(size_t offset, uint16_t type) {
- auto it = offset_to_type_map_.find(offset);
+ DCHECK_NE(offset, 0u);
+ auto it = offset_to_type_map_.Find(offset);
if (UNLIKELY(it == offset_to_type_map_.end())) {
ErrorStringPrintf("No data map entry found @ %zx; expected %x", offset, type);
return false;
diff --git a/runtime/dex_file_verifier.h b/runtime/dex_file_verifier.h
index 4f15357..6c63749 100644
--- a/runtime/dex_file_verifier.h
+++ b/runtime/dex_file_verifier.h
@@ -175,7 +175,35 @@
const char* const location_;
const DexFile::Header* const header_;
- AllocationTrackingSafeMap<uint32_t, uint16_t, kAllocatorTagDexFileVerifier> offset_to_type_map_;
+ struct OffsetTypeMapEmptyFn {
+ // Make a hash map slot empty by making the offset 0. Offset 0 is a valid dex file offset that
+ // is in the offset of the dex file header. However, we only store data section items in the
+ // map, and these are after the header.
+ void MakeEmpty(std::pair<uint32_t, uint16_t>& pair) const {
+ pair.first = 0u;
+ }
+ // Check if a hash map slot is empty.
+ bool IsEmpty(const std::pair<uint32_t, uint16_t>& pair) const {
+ return pair.first == 0;
+ }
+ };
+ struct OffsetTypeMapHashCompareFn {
+ // Hash function for offset.
+ size_t operator()(const uint32_t key) const {
+ return key;
+ }
+ // std::equal function for offset.
+ bool operator()(const uint32_t a, const uint32_t b) const {
+ return a == b;
+ }
+ };
+ // Map from offset to dex file type, HashMap for performance reasons.
+ AllocationTrackingHashMap<uint32_t,
+ uint16_t,
+ OffsetTypeMapEmptyFn,
+ kAllocatorTagDexFileVerifier,
+ OffsetTypeMapHashCompareFn,
+ OffsetTypeMapHashCompareFn> offset_to_type_map_;
const uint8_t* ptr_;
const void* previous_item_;