[interpreter] Use hashmap for ConstantArrayBuilder's constant map

src/inline-hash-map.h

+// Copyright 2016 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_ZONE_TEMPLATE_HASH_MAP_H_
+#define V8_ZONE_TEMPLATE_HASH_MAP_H_

[rmcilroy, 2016/09/12 14:17:31]

I wonder how much of this should really live in the header. I know hashmap.h
does, but maybe we could take this opportunity to move some of the
implementation in a cc file (presumably just the non-fast-path parts though). 

+
+#include "src/zone.h"
+
+namespace v8 {
+namespace internal {

[rmcilroy, 2016/09/12 14:17:31]

This should really be v8/base (and in the base directory)

+
+class DefaultAllocationPolicy {
+ public:
+  V8_INLINE void* New(size_t size) { return malloc(size); }
+  V8_INLINE static void Delete(void* p) { free(p); }
+};
+
+namespace detail {

[rmcilroy, 2016/09/12 14:17:31]

Typically we use annoymous namespaces for private details, but I realize that
doesn't work for headers (hence my comment above). Maybe you could make a
inline-hash-map.h file with the interface, and a inline-hash-map-inl.h header
with the implementation, which is in a namespace internal (and is included in
the main header)?

+
+template <typename Key, typename Value>
+class InlineHashMapEntry {
+ public:
+  InlineHashMapEntry(Key key, Value value, size_t hash)
+      : keyValue_(std::move(key), std::move(value)),
+        hash_(hash),
+        exists_(true) {}
+
+  const std::pair<const Key, Value>& keyValue() const { return keyValue_; }
+  std::pair<const Key, Value>& keyValue() { return keyValue_; }
+
+  size_t hash() const { return hash_; }
+
+  bool exists() const { return exists_; }
+
+  void clear() { exists_ = false; }
+
+  bool operator==(const InlineHashMapEntry& other) {
+    if (!exists()) {
+      return !other.exists();
+    }
+
+    if (!other.exists()) {
+      return false;
+    }
+
+    return keyValue() == other.keyValue();
+  }
+
+  bool operator!=(const InlineHashMapEntry& other) { return !(*this == other); }
+
+ private:
+  std::pair<const Key, Value> keyValue_;
+  size_t hash_;  // The full hash value for key
+  bool exists_;  // TODO(leszeks): this could be a tagged hash
+};
+
+// Specialize InlineHashMapEntry for pointer types
+template <typename Key, typename Value>
+class InlineHashMapEntry<Key*, Value> {
+ public:
+  InlineHashMapEntry(Key* key, Value value, size_t hash)
+      : keyValue_(std::move(key), std::move(value)), hash_(hash) {}
+
+  const std::pair<Key* const, Value>& keyValue() const { return keyValue_; }
+  std::pair<Key* const, Value>& keyValue() { return keyValue_; }
+
+  size_t hash() const { return hash_; }
+
+  bool exists() const { return keyValue_.first != nullptr; }
+
+  void clear() {
+    // Nasty const_cast to allow us to set the normally const key of the entry.
+    // Only valid because we absolutely promise that we're not using this object
+    // except for existence tests.
+    const_cast<Key*&>(keyValue_.first) = nullptr;
+  }
+
+  bool operator==(const InlineHashMapEntry& other) {
+    if (!exists()) {
+      return !other.exists();
+    }
+
+    if (!other.exists()) {
+      return false;
+    }
+
+    return keyValue() == other.keyValue();
+  }
+
+  bool operator!=(const InlineHashMapEntry& other) { return !(*this == other); }
+
+ private:
+  std::pair<Key* const, Value> keyValue_;
+  size_t hash_;  // The full hash value for key
+};
+}  // namespace detail
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy = DefaultAllocationPolicy>
+class InlineHashMap
+    : private AllocationPolicy /* for Empty Base Optimization */ {
+ public:
+  // The default capacity.  This is used by the call sites which want
+  // to pass in a non-default AllocationPolicy but want to use the
+  // default value of capacity specified by the implementation.
+  static const uint32_t kDefaultHashMapCapacity = 8;
+
+  // initial_capacity is the size of the initial hash map;
+  // it must be a power of 2 (and thus must not be 0).
+  explicit InlineHashMap(uint32_t capacity = kDefaultHashMapCapacity,
+                         AllocationPolicy allocator = AllocationPolicy());
+
+  ~InlineHashMap();
+
+  class Iterator;
+  typedef Iterator iterator;
+  typedef const Iterator const_iterator;
+
+  // If an entry with matching key is found, returns an iterator to that entry.
+  // Otherwise, the end() iterator is returned
+  iterator Find(const Key& key) const;
+
+  // Inserts the given key and value into the map, returning true if there was
+  // already another entry under that key
+  bool Insert(Key key, Value value);
+
+  // If an entry with matching key is found, returns the value of that entry.
+  // Otherwise, it creates the value using the given function, inserts it, and
+  // returns it
+  template <typename Func>
+  Value& LookupOrInsert(const Key& key, const Func& valueFunc);
+
+  // If an entry with matching key is found, returns the value of that entry.
+  // Otherwise, it creates the value with its default constructor, inserts it,
+  // and returns it
+  Value& LookupOrInsert(const Key& key);
+
+  Value& operator[](const Key& key);
+
+  iterator start();
+
+  iterator end();
+
+  // Removes the entry with matching key.
+  // Returns true if there was an entry.
+  bool Remove(const Key& key);
+
+  void Clear();
+
+  // The number of (non-empty) entries in the table.
+  uint32_t occupancy() const { return occupancy_; }
+
+  // The capacity of the table. The implementation
+  // makes sure that occupancy is at most 80% of
+  // the table capacity.
+  uint32_t capacity() const { return capacity_; }
+
+ private:
+  typedef detail::InlineHashMapEntry<Key, Value> Entry;
+
+  Entry* map_;
+  uint32_t capacity_;
+  uint32_t occupancy_;
+
+  Entry* map_end() const { return map_ + capacity_; }
+
+  void EnsureInitialized() const;
+  void Initialize(uint32_t capacity);
+
+  Entry* Probe(const Key& key, size_t hash) const;
+  Entry* FillProbe(Entry* entry, Key key, Value value, size_t hashval);
+  Entry* ResizeAndProbe(const Key& key, size_t hash);
+};
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::InlineHashMap(
+    uint32_t initial_capacity, AllocationPolicy allocator)
+    : AllocationPolicy(allocator),
+      map_(nullptr),

[rmcilroy, 2016/09/12 14:17:31]

As discussed offline, let's make this just eagerly initialized.

+      capacity_(initial_capacity),
+      occupancy_(0) {
+  // initialize lazily
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::~InlineHashMap() {
+  AllocationPolicy::Delete(map_);
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::iterator
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::Find(const Key& key) const {
+  Entry* p = Probe(key, Hash()(key));
+  return Iterator(p->exists() ? p : map_end(), map_end());
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+bool InlineHashMap<Key, Value, Hash, AllocationPolicy>::Insert(Key key,
+                                                               Value value) {
+  size_t hashval = Hash()(key);
+  Entry* p = Probe(key, hashval);
+  bool valueReplaced = p->exists();
+  p = FillProbe(p, key, Value(), hashval);
+  return valueReplaced;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+template <typename Func>
+Value& InlineHashMap<Key, Value, Hash, AllocationPolicy>::LookupOrInsert(
+    const Key& key, const Func& valueFunc) {
+  size_t hashval = Hash()(key);
+  Entry* p = Probe(key, hashval);
+  if (!p->exists()) {
+    p = FillProbe(p, key, valueFunc(), hashval);
+  }
+  return p->keyValue().second;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+Value& InlineHashMap<Key, Value, Hash, AllocationPolicy>::LookupOrInsert(
+    const Key& key) {
+  return LookupOrInsert(key, []() { return Value(); });
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+Value& InlineHashMap<Key, Value, Hash, AllocationPolicy>::operator[](
+    const Key& key) {
+  return LookupOrInsert(key);
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::iterator
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::start() {
+  if (map_ == nullptr) {
+    return Iterator(nullptr, nullptr);
+  }
+  // Increment from map_ - 1 to find the first entry that exists
+  return ++Iterator(map_ - 1, map_end());
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::iterator
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::end() {
+  if (map_ == nullptr) {
+    return Iterator(nullptr, nullptr);
+  }
+  return Iterator(map_end(), map_end());
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+void InlineHashMap<Key, Value, Hash, AllocationPolicy>::EnsureInitialized()
+    const {
+  if (map_ == nullptr) {
+    // Cast away the constness of "this", because this is a lazy
+    // initialization and "virtually" happens in the constructor
+    const_cast<InlineHashMap*>(this)->Initialize(capacity_);
+  }
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+void InlineHashMap<Key, Value, Hash, AllocationPolicy>::Initialize(
+    uint32_t capacity) {
+  DCHECK(base::bits::IsPowerOfTwo32(capacity));
+  map_ =
+      reinterpret_cast<Entry*>(AllocationPolicy::New(capacity * sizeof(Entry)));
+  if (map_ == nullptr) {
+    FATAL("Out of memory: HashMap::Initialize");
+    return;
+  }
+  capacity_ = capacity;
+  Clear();
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+bool InlineHashMap<Key, Value, Hash, AllocationPolicy>::Remove(const Key& key) {
+  if (map_ == nullptr) {
+    return false;
+  }
+
+  size_t hashval = Hash()(key);
+  // Lookup the entry for the key to remove.
+  Entry* p = Probe(key, hashval);
+  if (!p->exists()) {
+    // Key not found nothing to remove.
+    return false;
+  }
+
+  // To remove an entry we need to ensure that it does not create an empty
+  // entry that will cause the search for another entry to stop too soon. If all
+  // the entries between the entry to remove and the next empty slot have their
+  // initial position inside this interval, clearing the entry to remove will
+  // not break the search. If, while searching for the next empty entry, an
+  // entry is encountered which does not have its initial position between the
+  // entry to remove and the position looked at, then this entry can be moved to
+  // the place of the entry to remove without breaking the search for it. The
+  // entry made vacant by this move is now the entry to remove and the process
+  // starts over.
+  // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
+
+  // This guarantees loop termination as there is at least one empty entry so
+  // eventually the removed entry will have an empty entry after it.
+  DCHECK(occupancy_ < capacity_);
+
+  // p is the candidate entry to clear. q is used to scan forwards.
+  Entry* q = p;  // Start at the entry to remove.
+  while (true) {
+    // Move q to the next entry.
+    q = q + 1;
+    if (q == map_end()) {
+      q = map_;
+    }
+
+    // All entries between p and q have their initial position between p and q
+    // and the entry p can be cleared without breaking the search for these
+    // entries.
+    if (!q->exists()) {
+      break;
+    }
+
+    // Find the initial position for the entry at position q.
+    Entry* r = map_ + (q->hash & (capacity_ - 1));
+
+    // If the entry at position q has its initial position outside the range
+    // between p and q it can be moved forward to position p and will still be
+    // found. There is now a new candidate entry for clearing.
+    if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
+      *p = *q;
+      p = q;
+    }
+  }
+
+  // Clear the entry which is allowed to be emptied.
+  p->clear();
+  occupancy_--;
+  return true;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+void InlineHashMap<Key, Value, Hash, AllocationPolicy>::Clear() {
+  for (Entry* e = map_; e < map_end(); ++e) {
+    e->clear();
+  }
+  occupancy_ = 0;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::Entry*
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::Probe(const Key& key,
+                                                         size_t hash) const {
+  DCHECK(base::bits::IsPowerOfTwo32(capacity_));
+  EnsureInitialized();
+
+  Entry* p = map_ + (hash & (capacity_ - 1));
+  const Entry* end = map_end();
+  DCHECK(map_ <= p && p < end);
+
+  DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
+  while (p->exists() && (hash != p->hash() || key != p->keyValue().first)) {
+    p++;
+    if (p >= end) {
+      p = map_;
+    }
+  }
+
+  return p;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::Entry*
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::FillProbe(Entry* entry,
+                                                             Key key,
+                                                             Value value,
+                                                             size_t hashval) {
+  DCHECK(!entry->exists());
+
+  // No entry found; insert one.
+  new (entry) Entry(std::move(key), std::move(value), hashval);
+  occupancy_++;
+
+  // Grow the map if we reached >= 80% occupancy.
+  if (occupancy_ + occupancy_ / 4 >= capacity_) {
+    entry = ResizeAndProbe(key, hashval);
+  }
+
+  return entry;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+typename InlineHashMap<Key, Value, Hash, AllocationPolicy>::Entry*
+InlineHashMap<Key, Value, Hash, AllocationPolicy>::ResizeAndProbe(
+    const Key& recoveredKey, size_t recoveredHash) {
+  Entry* map = map_;
+  Entry* recoveredVal = nullptr;
+  uint32_t n = occupancy_;
+
+  // Allocate larger map.
+  Initialize(capacity_ * 2);
+
+  // Rehash all current entries.
+  for (Entry* p = map; n > 0; p++) {
+    if (p->exists()) {
+      Entry* new_p = Probe(p->keyValue().first, p->hash());
+      // Manually fill the probed entry to skip the occupancy check
+      DCHECK(!new_p->exists());
+      new (new_p) Entry(std::move(p->keyValue().first),
+                        std::move(p->keyValue().second), p->hash());
+      occupancy_++;
+      n--;
+
+      // If this entry is the one that caused the resize, save its new pointer
+      // This saves us doing another probe after the resize.
+      if (recoveredVal == nullptr && p->hash() == recoveredHash &&
+          p->keyValue().first == recoveredKey) {
+        recoveredVal = new_p;
+      }
+    }
+  }
+
+  // Delete previous map
+  AllocationPolicy::Delete(map);
+
+  DCHECK(recoveredVal != nullptr);
+  return recoveredVal;
+}
+
+template <typename Key, typename Value, typename Hash,
+          typename AllocationPolicy>
+class InlineHashMap<Key, Value, Hash, AllocationPolicy>::Iterator {
+ public:
+  Iterator() : entry_(nullptr), end_(nullptr) {}
+  Iterator(Entry* start, Entry* end) : entry_(start), end_(end) {}
+
+  std::pair<const Key, Value>& operator*() { return entry_->keyValue(); }
+  const std::pair<const Key, Value>& operator*() const {
+    return entry_->keyValue();
+  }
+
+  std::pair<const Key, Value>* operator->() { return &entry_->keyValue(); }
+  const std::pair<const Key, Value>* operator->() const {
+    return &entry_->keyValue();
+  }
+
+  Iterator operator++() {
+    ++entry_;
+    while (entry_ < end_ && !entry_->exists()) {
+      ++entry_;
+    }
+    return *this;
+  }
+
+  Iterator operator++(int) {
+    Iterator ret(*this);
+    this->operator++();
+    return ret;
+  }
+
+  bool operator==(const Iterator& other) const {
+    return entry_ == other.entry_;
+  }
+
+  bool operator!=(const Iterator& other) const { return entry_ != other.entry; }
+
+ private:
+  Entry* entry_;
+  Entry* end_;
+};
+
+template <typename Key, typename Value, typename Hash>
+class ZoneInlineHashMap
+    : public InlineHashMap<Key, Value, Hash, ZoneAllocationPolicy> {
+ public:
+  explicit ZoneInlineHashMap(
+      Zone* zone,
+      uint32_t capacity = InlineHashMap<
+          Key, Value, ZoneAllocationPolicy>::kDefaultHashMapCapacity)
+      : InlineHashMap<Key, Value, Hash, ZoneAllocationPolicy>(
+            capacity, ZoneAllocationPolicy(zone)) {}
+};
+
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_ZONE_TEMPLATE_HASH_MAP_H_