diff options
Diffstat (limited to 'compiler/utils/dedupe_set-inl.h')
-rw-r--r-- | compiler/utils/dedupe_set-inl.h | 275 |
1 files changed, 0 insertions, 275 deletions
diff --git a/compiler/utils/dedupe_set-inl.h b/compiler/utils/dedupe_set-inl.h deleted file mode 100644 index db744c53f7..0000000000 --- a/compiler/utils/dedupe_set-inl.h +++ /dev/null @@ -1,275 +0,0 @@ -/* - * Copyright (C) 2015 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_INL_H_ -#define ART_COMPILER_UTILS_DEDUPE_SET_INL_H_ - -#include "dedupe_set.h" - -#include <inttypes.h> - -#include <algorithm> -#include <unordered_map> - -#include "android-base/stringprintf.h" - -#include "base/hash_set.h" -#include "base/macros.h" -#include "base/mutex.h" -#include "base/stl_util.h" -#include "base/time_utils.h" - -namespace art HIDDEN { - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -struct DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Stats { - size_t collision_sum = 0u; - size_t collision_max = 0u; - size_t total_probe_distance = 0u; - size_t total_size = 0u; -}; - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -class DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Shard { - public: - Shard(const Alloc& alloc, const std::string& lock_name) - : alloc_(alloc), - lock_name_(lock_name), - lock_(lock_name_.c_str()), - keys_() { - } - - ~Shard() { - for (const HashedKey<StoreKey>& key : keys_) { - DCHECK(key.Key() != nullptr); - alloc_.Destroy(key.Key()); - } - } - - const StoreKey* Add(Thread* self, size_t hash, const InKey& in_key) REQUIRES(!lock_) { - MutexLock lock(self, lock_); - HashedKey<InKey> hashed_in_key(hash, &in_key); - auto it = keys_.find(hashed_in_key); - if (it != keys_.end()) { - DCHECK(it->Key() != nullptr); - return it->Key(); - } - const StoreKey* store_key = alloc_.Copy(in_key); - keys_.insert(HashedKey<StoreKey> { hash, store_key }); - return store_key; - } - - size_t Size(Thread* self) { - MutexLock lock(self, lock_); - return keys_.size(); - } - - void UpdateStats(Thread* self, Stats* global_stats) REQUIRES(!lock_) { - // HashSet<> doesn't keep entries ordered by hash, so we actually allocate memory - // for bookkeeping while collecting the stats. - std::unordered_map<HashType, size_t> stats; - { - MutexLock lock(self, lock_); - // Note: The total_probe_distance will be updated with the current state. - // It may have been higher before a re-hash. - global_stats->total_probe_distance += keys_.TotalProbeDistance(); - global_stats->total_size += keys_.size(); - for (const HashedKey<StoreKey>& key : keys_) { - auto it = stats.find(key.Hash()); - if (it == stats.end()) { - stats.insert({key.Hash(), 1u}); - } else { - ++it->second; - } - } - } - for (const auto& entry : stats) { - size_t number_of_entries = entry.second; - if (number_of_entries > 1u) { - global_stats->collision_sum += number_of_entries - 1u; - global_stats->collision_max = std::max(global_stats->collision_max, number_of_entries); - } - } - } - - private: - template <typename T> - class HashedKey { - public: - HashedKey() : hash_(0u), key_(nullptr) { } - HashedKey(size_t hash, const T* key) : hash_(hash), key_(key) { } - - size_t Hash() const { - return hash_; - } - - const T* Key() const { - return key_; - } - - bool IsEmpty() const { - return Key() == nullptr; - } - - void MakeEmpty() { - key_ = nullptr; - } - - private: - size_t hash_; - const T* key_; - }; - - class ShardEmptyFn { - public: - bool IsEmpty(const HashedKey<StoreKey>& key) const { - return key.IsEmpty(); - } - - void MakeEmpty(HashedKey<StoreKey>& key) { - key.MakeEmpty(); - } - }; - - struct ShardHashFn { - template <typename T> - size_t operator()(const HashedKey<T>& key) const { - return key.Hash(); - } - }; - - struct ShardPred { - typename std::enable_if<!std::is_same<StoreKey, InKey>::value, bool>::type - operator()(const HashedKey<StoreKey>& lhs, const HashedKey<StoreKey>& rhs) const { - DCHECK(lhs.Key() != nullptr); - DCHECK(rhs.Key() != nullptr); - // Rehashing: stored keys are already deduplicated, so we can simply compare key pointers. - return lhs.Key() == rhs.Key(); - } - - template <typename LeftT, typename RightT> - bool operator()(const HashedKey<LeftT>& lhs, const HashedKey<RightT>& rhs) const { - DCHECK(lhs.Key() != nullptr); - DCHECK(rhs.Key() != nullptr); - return lhs.Hash() == rhs.Hash() && - lhs.Key()->size() == rhs.Key()->size() && - std::equal(lhs.Key()->begin(), lhs.Key()->end(), rhs.Key()->begin()); - } - }; - - Alloc alloc_; - const std::string lock_name_; - Mutex lock_; - HashSet<HashedKey<StoreKey>, ShardEmptyFn, ShardHashFn, ShardPred> keys_ GUARDED_BY(lock_); -}; - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -const StoreKey* DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::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; - return shards_[shard_bin]->Add(self, shard_hash, key); -} - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::DedupeSet(const char* set_name, - const Alloc& alloc) - : hash_time_(0) { - for (HashType i = 0; i < kShard; ++i) { - std::ostringstream oss; - oss << set_name << " lock " << i; - shards_[i].reset(new Shard(alloc, oss.str())); - } -} - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::~DedupeSet() { - // Everything done by member destructors. -} - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -size_t DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Size(Thread* self) const { - size_t result = 0u; - for (const auto& shard : shards_) { - result += shard->Size(self); - } - return result; -} - -template <typename InKey, - typename StoreKey, - typename Alloc, - typename HashType, - typename HashFunc, - HashType kShard> -std::string DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::DumpStats( - Thread* self) const { - Stats stats; - for (HashType shard = 0; shard < kShard; ++shard) { - shards_[shard]->UpdateStats(self, &stats); - } - return android::base::StringPrintf("%zu collisions, %zu max hash collisions, " - "%zu/%zu probe distance, %" PRIu64 " ns hash time", - stats.collision_sum, - stats.collision_max, - stats.total_probe_distance, - stats.total_size, - hash_time_); -} - - -} // namespace art - -#endif // ART_COMPILER_UTILS_DEDUPE_SET_INL_H_ |