ART: Swap-space in the compiler
Introduce a swap-space and corresponding allocator to transparently
switch native allocations to memory backed by a file.
Bug: 18596910
(cherry picked from commit 62746d8d9c4400e4764f162b22bfb1a32be287a9)
Change-Id: I131448f3907115054a592af73db86d2b9257ea33
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
index 4c52174..b062a2a 100644
--- a/compiler/utils/dedupe_set.h
+++ b/compiler/utils/dedupe_set.h
@@ -17,50 +17,89 @@
#ifndef ART_COMPILER_UTILS_DEDUPE_SET_H_
#define ART_COMPILER_UTILS_DEDUPE_SET_H_
+#include <algorithm>
+#include <inttypes.h>
+#include <memory>
#include <set>
#include <string>
#include "base/mutex.h"
#include "base/stl_util.h"
#include "base/stringprintf.h"
+#include "utils/swap_space.h"
namespace art {
// A set of Keys that support a HashFunc returning HashType. Used to find duplicates of Key in the
// Add method. The data-structure is thread-safe through the use of internal locks, it also
// supports the lock being sharded.
-template <typename Key, typename HashType, typename HashFunc, HashType kShard = 1>
+template <typename InKey, typename StoreKey, typename HashType, typename HashFunc,
+ HashType kShard = 1>
class DedupeSet {
- typedef std::pair<HashType, Key*> HashedKey;
+ typedef std::pair<HashType, const InKey*> HashedInKey;
+ struct HashedKey {
+ StoreKey* store_ptr;
+ union {
+ HashType store_hash; // Valid if store_ptr != nullptr.
+ const HashedInKey* in_key; // Valid if store_ptr == nullptr.
+ };
+ };
class Comparator {
public:
bool operator()(const HashedKey& a, const HashedKey& b) const {
- if (a.first != b.first) {
- return a.first < b.first;
+ HashType a_hash = (a.store_ptr != nullptr) ? a.store_hash : a.in_key->first;
+ HashType b_hash = (b.store_ptr != nullptr) ? b.store_hash : b.in_key->first;
+ if (a_hash != b_hash) {
+ return a_hash < b_hash;
+ }
+ if (a.store_ptr != nullptr && b.store_ptr != nullptr) {
+ return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
+ b.store_ptr->begin(), b.store_ptr->end());
+ } else if (a.store_ptr != nullptr && b.store_ptr == nullptr) {
+ return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
+ b.in_key->second->begin(), b.in_key->second->end());
+ } else if (a.store_ptr == nullptr && b.store_ptr != nullptr) {
+ return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
+ b.store_ptr->begin(), b.store_ptr->end());
} else {
- return *a.second < *b.second;
+ return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
+ b.in_key->second->begin(), b.in_key->second->end());
}
}
};
public:
- Key* Add(Thread* self, const Key& key) {
+ StoreKey* Add(Thread* self, const InKey& key) {
+ uint64_t hash_start;
+ if (kIsDebugBuild) {
+ hash_start = NanoTime();
+ }
HashType raw_hash = HashFunc()(key);
+ if (kIsDebugBuild) {
+ uint64_t hash_end = NanoTime();
+ hash_time_ += hash_end - hash_start;
+ }
HashType shard_hash = raw_hash / kShard;
HashType shard_bin = raw_hash % kShard;
- HashedKey hashed_key(shard_hash, const_cast<Key*>(&key));
+ HashedInKey hashed_in_key(shard_hash, &key);
+ HashedKey hashed_key;
+ hashed_key.store_ptr = nullptr;
+ hashed_key.in_key = &hashed_in_key;
MutexLock lock(self, *lock_[shard_bin]);
auto it = keys_[shard_bin].find(hashed_key);
if (it != keys_[shard_bin].end()) {
- return it->second;
+ DCHECK(it->store_ptr != nullptr);
+ return it->store_ptr;
}
- hashed_key.second = new Key(key);
+ hashed_key.store_ptr = CreateStoreKey(key);
+ hashed_key.store_hash = shard_hash;
keys_[shard_bin].insert(hashed_key);
- return hashed_key.second;
+ return hashed_key.store_ptr;
}
- explicit DedupeSet(const char* set_name) {
+ explicit DedupeSet(const char* set_name, SwapAllocator<void>& alloc)
+ : allocator_(alloc), hash_time_(0) {
for (HashType i = 0; i < kShard; ++i) {
std::ostringstream oss;
oss << set_name << " lock " << i;
@@ -70,15 +109,59 @@
}
~DedupeSet() {
- for (HashType i = 0; i < kShard; ++i) {
- STLDeleteValues(&keys_[i]);
+ // Have to manually free all pointers.
+ for (auto& shard : keys_) {
+ for (const auto& hashed_key : shard) {
+ DCHECK(hashed_key.store_ptr != nullptr);
+ DeleteStoreKey(hashed_key.store_ptr);
+ }
}
}
+ std::string DumpStats() const {
+ size_t collision_sum = 0;
+ size_t collision_max = 0;
+ for (HashType shard = 0; shard < kShard; ++shard) {
+ HashType last_hash = 0;
+ size_t collision_cur_max = 0;
+ for (const HashedKey& key : keys_[shard]) {
+ DCHECK(key.store_ptr != nullptr);
+ if (key.store_hash == last_hash) {
+ collision_cur_max++;
+ if (collision_cur_max > 1) {
+ collision_sum++;
+ if (collision_cur_max > collision_max) {
+ collision_max = collision_cur_max;
+ }
+ }
+ } else {
+ collision_cur_max = 1;
+ last_hash = key.store_hash;
+ }
+ }
+ }
+ return StringPrintf("%zu collisions, %zu max bucket size, %" PRIu64 " ns hash time",
+ collision_sum, collision_max, hash_time_);
+ }
+
private:
+ StoreKey* CreateStoreKey(const InKey& key) {
+ StoreKey* ret = allocator_.allocate(1);
+ allocator_.construct(ret, key.begin(), key.end(), allocator_);
+ return ret;
+ }
+
+ void DeleteStoreKey(StoreKey* key) {
+ SwapAllocator<StoreKey> alloc(allocator_);
+ alloc.destroy(key);
+ alloc.deallocate(key, 1);
+ }
+
std::string lock_name_[kShard];
std::unique_ptr<Mutex> lock_[kShard];
std::set<HashedKey, Comparator> keys_[kShard];
+ SwapAllocator<StoreKey> allocator_;
+ uint64_t hash_time_;
DISALLOW_COPY_AND_ASSIGN(DedupeSet);
};