compiler/utils/dedupe_set-inl.h

/*
 * 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_