Add hash map, reduce excessive hashing
Changed the class def index to use a HashMap instead of unordered_map
so that we can use FindWithHash to reduce how often we need to compute
hashes.
Fixed a bug in ClassLinker::UpdateClass where we didn't properly
handle classes with the same descriptor but different class loaders.
Introduced by previous CL.
Before (fb launch):
1.74% art::ComputeModifiedUtf8Hash(char const*)
After:
0.95% art::ComputeModifiedUtf8Hash(char const*)
Bug: 18054905
Bug: 16828525
Change-Id: Iba2ee37c9837289e0ea187800ba4af322225a994
(cherry picked from commit 564ff985184737977aa26c485d0c1a413e530705)
diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h
new file mode 100644
index 0000000..c0f903f
--- /dev/null
+++ b/runtime/base/hash_map.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_HASH_MAP_H_
+#define ART_RUNTIME_BASE_HASH_MAP_H_
+
+#include <utility>
+
+#include "hash_set.h"
+
+namespace art {
+
+template <typename Fn>
+class HashMapWrapper {
+ public:
+ // Hash function.
+ template <class Key, class Value>
+ size_t operator()(const std::pair<Key, Value>& pair) const {
+ return fn_(pair.first);
+ }
+ template <class Key>
+ size_t operator()(const Key& key) const {
+ return fn_(key);
+ }
+ template <class Key, class Value>
+ bool operator()(const std::pair<Key, Value>& a, const std::pair<Key, Value>& b) const {
+ return fn_(a.first, b.first);
+ }
+ template <class Key, class Value, class Element>
+ bool operator()(const std::pair<Key, Value>& a, const Element& element) const {
+ return fn_(a.first, element);
+ }
+
+ private:
+ Fn fn_;
+};
+
+template <class Key, class Value, class EmptyFn = DefaultEmptyFn<Key>,
+ class HashFn = std::hash<Key>, class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<Key, Value>>>
+class HashMap : public HashSet<std::pair<Key, Value>, EmptyFn, HashMapWrapper<HashFn>,
+ HashMapWrapper<Pred>, Alloc> {
+};
+
+} // namespace art
+
+#endif // ART_RUNTIME_BASE_HASH_MAP_H_
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
index 885fc06..5f498d9 100644
--- a/runtime/base/hash_set_test.cc
+++ b/runtime/base/hash_set_test.cc
@@ -22,12 +22,11 @@
#include <unordered_set>
#include "common_runtime_test.h"
-#include "utils.h"
+#include "hash_map.h"
namespace art {
-class IsEmptyFnString {
- public:
+struct IsEmptyFnString {
void MakeEmpty(std::string& item) const {
item.clear();
}
@@ -200,4 +199,25 @@
}
}
+struct IsEmptyStringPair {
+ void MakeEmpty(std::pair<std::string, int>& pair) const {
+ pair.first.clear();
+ }
+ bool IsEmpty(const std::pair<std::string, int>& pair) const {
+ return pair.first.empty();
+ }
+};
+
+TEST_F(HashSetTest, TestHashMap) {
+ HashMap<std::string, int, IsEmptyStringPair> hash_map;
+ hash_map.Insert(std::make_pair(std::string("abcd"), 123));
+ hash_map.Insert(std::make_pair(std::string("abcd"), 124));
+ hash_map.Insert(std::make_pair(std::string("bags"), 444));
+ auto it = hash_map.Find(std::string("abcd"));
+ ASSERT_EQ(it->second, 123);
+ hash_map.Erase(it);
+ it = hash_map.Find(std::string("abcd"));
+ ASSERT_EQ(it->second, 124);
+}
+
} // namespace art