Multi threaded hashed deduplication during compilation.
Moved deduplication to be in the compiler driver instead of oat
writer. This enables deduplication to be performed on multiple
threads. Also added a hash function to avoid excessive comparison
of byte arrays.
Improvements:
Before (alloats host):
real 1m6.967s
user 4m22.940s
sys 1m22.610s
Thinkfree.apk (target mako):
0m23.74s real 0m50.95s user 0m9.50s system
0m24.62s real 0m50.61s user 0m10.07s system
0m24.22s real 0m51.44s user 0m10.09s system
0m23.70s real 0m51.05s user 0m9.97s system
0m23.50s real 0m50.74s user 0m10.63s system
After (alloats host):
real 1m5.705s
user 4m44.030s
sys 1m29.990s
Thinkfree.apk (target mako):
0m23.32s real 0m51.38s user 0m10.00s system
0m23.49s real 0m51.20s user 0m9.80s system
0m23.18s real 0m50.80s user 0m9.77s system
0m23.52s real 0m51.22s user 0m10.02s system
0m23.50s real 0m51.55s user 0m9.46s system
Bug: 10552630
Change-Id: Ia6d06a747b86b0bfc4473b3cd68f8ce1a1c7eb22
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
new file mode 100644
index 0000000..f3d35d7
--- /dev/null
+++ b/compiler/utils/dedupe_set.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2013 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_COMPILER_UTILS_DEDUPE_SET_H_
+#define ART_COMPILER_UTILS_DEDUPE_SET_H_
+
+#include <set>
+
+#include "base/mutex.h"
+#include "base/stl_util.h"
+
+namespace art {
+
+// A simple data structure to handle hashed deduplication. Add is thread safe.
+template <typename Key, typename HashType, typename HashFunc>
+class DedupeSet {
+ typedef std::pair<HashType, Key*> HashedKey;
+
+ class Comparator {
+ public:
+ bool operator()(const HashedKey& a, const HashedKey& b) const {
+ if (a.first < b.first) return true;
+ if (a.first > b.first) return true;
+ return *a.second < *b.second;
+ }
+ };
+
+ typedef std::set<HashedKey, Comparator> Keys;
+
+ public:
+ typedef typename Keys::iterator iterator;
+ typedef typename Keys::const_iterator const_iterator;
+ typedef typename Keys::size_type size_type;
+ typedef typename Keys::value_type value_type;
+
+ iterator begin() { return keys_.begin(); }
+ const_iterator begin() const { return keys_.begin(); }
+ iterator end() { return keys_.end(); }
+ const_iterator end() const { return keys_.end(); }
+
+ Key* Add(Thread* self, const Key& key) {
+ HashType hash = HashFunc()(key);
+ HashedKey hashed_key(hash, const_cast<Key*>(&key));
+ MutexLock lock(self, lock_);
+ auto it = keys_.find(hashed_key);
+ if (it != keys_.end()) {
+ return it->second;
+ }
+ hashed_key.second = new Key(key);
+ keys_.insert(hashed_key);
+ return hashed_key.second;
+ }
+
+ DedupeSet() : lock_("dedupe lock") {
+ }
+
+ ~DedupeSet() {
+ STLDeleteValues(&keys_);
+ }
+
+ private:
+ Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+ Keys keys_;
+ DISALLOW_COPY_AND_ASSIGN(DedupeSet);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_DEDUPE_SET_H_
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
new file mode 100644
index 0000000..9f5e292
--- /dev/null
+++ b/compiler/utils/dedupe_set_test.cc
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#include "common_test.h"
+#include "dedupe_set.h"
+
+namespace art {
+
+class DedupeSetTest : public testing::Test {
+ public:
+};
+
+class DedupeHashFunc {
+ public:
+ size_t operator()(const std::vector<uint8_t>& array) const {
+ size_t hash = 0;
+ for (uint8_t c : array) {
+ hash += c;
+ hash += hash << 10;
+ hash += hash >> 6;
+ }
+ return hash;
+ }
+};
+TEST_F(DedupeSetTest, Test) {
+ Thread* self = Thread::Current();
+ typedef std::vector<uint8_t> ByteArray;
+ DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator;
+ ByteArray* array1;
+ {
+ ByteArray test1;
+ test1.push_back(10);
+ test1.push_back(20);
+ test1.push_back(30);
+ test1.push_back(45);
+ array1 = deduplicator.Add(self, test1);
+ ASSERT_EQ(test1, *array1);
+ }
+
+ ByteArray* array2;
+ {
+ ByteArray test1;
+ test1.push_back(10);
+ test1.push_back(20);
+ test1.push_back(30);
+ test1.push_back(45);
+ array2 = deduplicator.Add(self, test1);
+ ASSERT_EQ(array2, array1);
+ ASSERT_EQ(test1, *array2);
+ }
+
+ ByteArray* array3;
+ {
+ ByteArray test1;
+ test1.push_back(10);
+ test1.push_back(22);
+ test1.push_back(30);
+ test1.push_back(47);
+ array3 = deduplicator.Add(self, test1);
+ ASSERT_NE(array3, &test1);
+ ASSERT_EQ(test1, *array3);
+ }
+}
+
+} // namespace art