1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_UTILS_DEDUPE_SET_INL_H_
18#define ART_COMPILER_UTILS_DEDUPE_SET_INL_H_
19
20#include "dedupe_set.h"
21
22#include <algorithm>
23#include <inttypes.h>
24#include <unordered_map>
25
26#include "base/mutex.h"
27#include "base/hash_set.h"
28#include "base/stl_util.h"
29#include "base/stringprintf.h"
30#include "base/time_utils.h"
31
32namespace art {
33
34template <typename InKey,
35          typename StoreKey,
36          typename Alloc,
37          typename HashType,
38          typename HashFunc,
39          HashType kShard>
40struct DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Stats {
41  size_t collision_sum = 0u;
42  size_t collision_max = 0u;
43  size_t total_probe_distance = 0u;
44  size_t total_size = 0u;
45};
46
47template <typename InKey,
48          typename StoreKey,
49          typename Alloc,
50          typename HashType,
51          typename HashFunc,
52          HashType kShard>
53class DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Shard {
54 public:
55  Shard(const Alloc& alloc, const std::string& lock_name)
56      : alloc_(alloc),
57        lock_name_(lock_name),
58        lock_(lock_name_.c_str()),
59        keys_() {
60  }
61
62  ~Shard() {
63    for (const HashedKey<StoreKey>& key : keys_) {
64      DCHECK(key.Key() != nullptr);
65      alloc_.Destroy(key.Key());
66    }
67  }
68
69  const StoreKey* Add(Thread* self, size_t hash, const InKey& in_key) REQUIRES(!lock_) {
70    MutexLock lock(self, lock_);
71    HashedKey<InKey> hashed_in_key(hash, &in_key);
72    auto it = keys_.Find(hashed_in_key);
73    if (it != keys_.end()) {
74      DCHECK(it->Key() != nullptr);
75      return it->Key();
76    }
77    const StoreKey* store_key = alloc_.Copy(in_key);
78    keys_.Insert(HashedKey<StoreKey> { hash, store_key });
79    return store_key;
80  }
81
82  void UpdateStats(Thread* self, Stats* global_stats) REQUIRES(!lock_) {
83    // HashSet<> doesn't keep entries ordered by hash, so we actually allocate memory
84    // for bookkeeping while collecting the stats.
85    std::unordered_map<HashType, size_t> stats;
86    {
87      MutexLock lock(self, lock_);
88      // Note: The total_probe_distance will be updated with the current state.
89      // It may have been higher before a re-hash.
90      global_stats->total_probe_distance += keys_.TotalProbeDistance();
91      global_stats->total_size += keys_.Size();
92      for (const HashedKey<StoreKey>& key : keys_) {
93        auto it = stats.find(key.Hash());
94        if (it == stats.end()) {
95          stats.insert({key.Hash(), 1u});
96        } else {
97          ++it->second;
98        }
99      }
100    }
101    for (const auto& entry : stats) {
102      size_t number_of_entries = entry.second;
103      if (number_of_entries > 1u) {
104        global_stats->collision_sum += number_of_entries - 1u;
105        global_stats->collision_max = std::max(global_stats->collision_max, number_of_entries);
106      }
107    }
108  }
109
110 private:
111  template <typename T>
112  class HashedKey {
113   public:
114    HashedKey() : hash_(0u), key_(nullptr) { }
115    HashedKey(size_t hash, const T* key) : hash_(hash), key_(key) { }
116
117    size_t Hash() const {
118      return hash_;
119    }
120
121    const T* Key() const {
122      return key_;
123    }
124
125    bool IsEmpty() const {
126      return Key() == nullptr;
127    }
128
129    void MakeEmpty() {
130      key_ = nullptr;
131    }
132
133   private:
134    size_t hash_;
135    const T* key_;
136  };
137
138  class ShardEmptyFn {
139   public:
140    bool IsEmpty(const HashedKey<StoreKey>& key) const {
141      return key.IsEmpty();
142    }
143
144    void MakeEmpty(HashedKey<StoreKey>& key) {
145      key.MakeEmpty();
146    }
147  };
148
149  struct ShardHashFn {
150    template <typename T>
151    size_t operator()(const HashedKey<T>& key) const {
152      return key.Hash();
153    }
154  };
155
156  struct ShardPred {
157    typename std::enable_if<!std::is_same<StoreKey, InKey>::value, bool>::type
158    operator()(const HashedKey<StoreKey>& lhs, const HashedKey<StoreKey>& rhs) const {
159      DCHECK(lhs.Key() != nullptr);
160      DCHECK(rhs.Key() != nullptr);
161      // Rehashing: stored keys are already deduplicated, so we can simply compare key pointers.
162      return lhs.Key() == rhs.Key();
163    }
164
165    template <typename LeftT, typename RightT>
166    bool operator()(const HashedKey<LeftT>& lhs, const HashedKey<RightT>& rhs) const {
167      DCHECK(lhs.Key() != nullptr);
168      DCHECK(rhs.Key() != nullptr);
169      return lhs.Hash() == rhs.Hash() &&
170          lhs.Key()->size() == rhs.Key()->size() &&
171          std::equal(lhs.Key()->begin(), lhs.Key()->end(), rhs.Key()->begin());
172    }
173  };
174
175  Alloc alloc_;
176  const std::string lock_name_;
177  Mutex lock_;
178  HashSet<HashedKey<StoreKey>, ShardEmptyFn, ShardHashFn, ShardPred> keys_ GUARDED_BY(lock_);
179};
180
181template <typename InKey,
182          typename StoreKey,
183          typename Alloc,
184          typename HashType,
185          typename HashFunc,
186          HashType kShard>
187const StoreKey* DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::Add(
188    Thread* self, const InKey& key) {
189  uint64_t hash_start;
190  if (kIsDebugBuild) {
191    hash_start = NanoTime();
192  }
193  HashType raw_hash = HashFunc()(key);
194  if (kIsDebugBuild) {
195    uint64_t hash_end = NanoTime();
196    hash_time_ += hash_end - hash_start;
197  }
198  HashType shard_hash = raw_hash / kShard;
199  HashType shard_bin = raw_hash % kShard;
200  return shards_[shard_bin]->Add(self, shard_hash, key);
201}
202
203template <typename InKey,
204          typename StoreKey,
205          typename Alloc,
206          typename HashType,
207          typename HashFunc,
208          HashType kShard>
209DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::DedupeSet(const char* set_name,
210                                                                         const Alloc& alloc)
211    : hash_time_(0) {
212  for (HashType i = 0; i < kShard; ++i) {
213    std::ostringstream oss;
214    oss << set_name << " lock " << i;
215    shards_[i].reset(new Shard(alloc, oss.str()));
216  }
217}
218
219template <typename InKey,
220          typename StoreKey,
221          typename Alloc,
222          typename HashType,
223          typename HashFunc,
224          HashType kShard>
225DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::~DedupeSet() {
226  // Everything done by member destructors.
227}
228
229template <typename InKey,
230          typename StoreKey,
231          typename Alloc,
232          typename HashType,
233          typename HashFunc,
234          HashType kShard>
235std::string DedupeSet<InKey, StoreKey, Alloc, HashType, HashFunc, kShard>::DumpStats(
236    Thread* self) const {
237  Stats stats;
238  for (HashType shard = 0; shard < kShard; ++shard) {
239    shards_[shard]->UpdateStats(self, &stats);
240  }
241  return StringPrintf("%zu collisions, %zu max hash collisions, "
242                      "%zu/%zu probe distance, %" PRIu64 " ns hash time",
243                      stats.collision_sum,
244                      stats.collision_max,
245                      stats.total_probe_distance,
246                      stats.total_size,
247                      hash_time_);
248}
249
250
251}  // namespace art
252
253#endif  // ART_COMPILER_UTILS_DEDUPE_SET_INL_H_
254