blob: 4e892f26164dacc516f266989f4fc532a48f6744 [file] [log] [blame]
/*
* 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/mutex.h"
#include "base/stl_util.h"
#include "base/time_utils.h"
namespace art {
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;
}
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>
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_