junrushao1994 commented on a change in pull request #5740:
URL: https://github.com/apache/incubator-tvm/pull/5740#discussion_r442488594
##########
File path: include/tvm/node/container.h
##########
@@ -43,51 +44,1188 @@ using runtime::Downcast;
using runtime::IterAdapter;
using runtime::make_object;
using runtime::Object;
+using runtime::ObjectEqual;
+using runtime::ObjectHash;
using runtime::ObjectPtr;
using runtime::ObjectPtrEqual;
using runtime::ObjectPtrHash;
using runtime::ObjectRef;
using runtime::String;
using runtime::StringObj;
-/*! \brief String-aware ObjectRef hash functor */
-struct ObjectHash {
- size_t operator()(const ObjectRef& a) const {
- if (const auto* str = a.as<StringObj>()) {
- return String::HashBytes(str->data, str->size);
- }
- return ObjectPtrHash()(a);
+#if (TVM_USE_STL_MAP != 0)
+
+/*! \brief Shared content of all specializations of hash map */
+class MapNode : public Object {
+ public:
+ /*! \brief Type of the keys in the hash map */
+ using key_type = ObjectRef;
+ /*! \brief Type of the values in the hash map */
+ using mapped_type = ObjectRef;
+ /*! \brief Type of the actual underlying container */
+ using ContainerType = std::unordered_map<ObjectRef, ObjectRef, ObjectHash,
ObjectEqual>;
+ /*! \brief Iterator class */
+ using iterator = ContainerType::iterator;
+ /*! \brief Iterator class */
+ using const_iterator = ContainerType::const_iterator;
+ /*! \brief Type of value stored in the hash map */
+ using KVType = ContainerType::value_type;
+
+ static_assert(std::is_standard_layout<KVType>::value, "KVType is not
standard layout");
+ static_assert(sizeof(KVType) == 16 || sizeof(KVType) == 8, "sizeof(KVType)
incorrect");
+
+ static constexpr const uint32_t _type_index =
runtime::TypeIndex::kRuntimeMap;
+ static constexpr const char* _type_key = "Map";
+ TVM_DECLARE_FINAL_OBJECT_INFO(MapNode, Object);
+
+ /*!
+ * \brief Number of elements in the SmallMapNode
+ * \return The result
+ */
+ size_t size() const { return data_.size(); }
+ /*!
+ * \brief Count the number of times a key exists in the hash map
+ * \param key The indexing key
+ * \return The result, 0 or 1
+ */
+ size_t count(const key_type& key) const { return data_.count(key); }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The const reference to the value
+ */
+ const mapped_type& at(const key_type& key) const { return data_.at(key); }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The mutable reference to the value
+ */
+ mapped_type& at(const key_type& key) { return data_.at(key); }
+ /*! \return begin iterator */
+ iterator begin() { return data_.begin(); }
+ /*! \return const begin iterator */
+ const_iterator begin() const { return data_.begin(); }
+ /*! \return end iterator */
+ iterator end() { return data_.end(); }
+ /*! \return end iterator */
+ const_iterator end() const { return data_.end(); }
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ const_iterator find(const key_type& key) const { return data_.find(key); }
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ iterator find(const key_type& key) { return data_.find(key); }
+ /*!
+ * \brief Erase the entry associated with the iterator
+ * \param position The iterator
+ */
+ void erase(const iterator& position) { data_.erase(position); }
+ /*!
+ * \brief Erase the entry associated with the key, do nothing if not exists
+ * \param key The indexing key
+ */
+ void erase(const key_type& key) { data_.erase(key); }
+
+ protected:
+ /*!
+ * \brief Create an empty container
+ * \return The object created
+ */
+ static ObjectPtr<MapNode> Empty() { return make_object<MapNode>(); }
+ /*!
+ * \brief Create the map using contents from the given iterators.
+ * \param first Begin of iterator
+ * \param last End of iterator
+ * \tparam IterType The type of iterator
+ * \return ObjectPtr to the map created
+ */
+ template <typename IterType>
+ static ObjectPtr<Object> CreateFromRange(IterType first, IterType last) {
+ ObjectPtr<MapNode> p = make_object<MapNode>();
+ p->data_ = std::unordered_map<ObjectRef, ObjectRef, ObjectHash,
ObjectEqual>(first, last);
+ return p;
+ }
+ /*!
+ * \brief InsertMaybeReHash an entry into the given hash map
+ * \param kv The entry to be inserted
+ * \param map The pointer to the map, can be changed if re-hashing happens
+ */
+ static void InsertMaybeReHash(const KVType& kv, ObjectPtr<Object>* map) {
+ MapNode* m = static_cast<MapNode*>(map->get());
+ m->data_[kv.first] = kv.second;
}
+ /*!
+ * \brief Create an empty container with elements copying from another
MapNode
+ * \param m The source container
+ * \return The object created
+ */
+ static ObjectPtr<MapNode> CopyFrom(MapNode* m) {
+ ObjectPtr<MapNode> p = make_object<MapNode>();
+ p->data_ = std::unordered_map<ObjectRef, ObjectRef, ObjectHash,
ObjectEqual>(m->data_.begin(),
+
m->data_.end());
+ return p;
+ }
+ /*! \brief The real container storing data */
+ ContainerType data_;
+ template <typename, typename, typename, typename>
+ friend class Map;
};
-/*! \brief String-aware ObjectRef equal functor */
-struct ObjectEqual {
- bool operator()(const ObjectRef& a, const ObjectRef& b) const {
- if (a.same_as(b)) {
- return true;
+#else
+
+/*! \brief Shared content of all specializations of hash map */
+class MapNode : public Object {
+ public:
+ /*! \brief Type of the keys in the hash map */
+ using key_type = ObjectRef;
+ /*! \brief Type of the values in the hash map */
+ using mapped_type = ObjectRef;
+ /*! \brief Type of value stored in the hash map */
+ using KVType = std::pair<ObjectRef, ObjectRef>;
+ /*! \brief Iterator class */
+ class iterator;
+
+ static_assert(std::is_standard_layout<KVType>::value, "KVType is not
standard layout");
+ static_assert(sizeof(KVType) == 16 || sizeof(KVType) == 8, "sizeof(KVType)
incorrect");
+
+ static constexpr const uint32_t _type_index =
runtime::TypeIndex::kRuntimeMap;
+ static constexpr const char* _type_key = "Map";
+ TVM_DECLARE_FINAL_OBJECT_INFO(MapNode, Object);
+
+ /*!
+ * \brief Number of elements in the SmallMapNode
+ * \return The result
+ */
+ size_t size() const { return size_; }
+ /*!
+ * \brief Count the number of times a key exists in the hash map
+ * \param key The indexing key
+ * \return The result, 0 or 1
+ */
+ size_t count(const key_type& key) const;
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The const reference to the value
+ */
+ const mapped_type& at(const key_type& key) const;
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The mutable reference to the value
+ */
+ mapped_type& at(const key_type& key);
+ /*! \return begin iterator */
+ iterator begin() const;
+ /*! \return end iterator */
+ iterator end() const;
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ iterator find(const key_type& key) const;
+ /*!
+ * \brief Erase the entry associated with the iterator
+ * \param position The iterator
+ */
+ void erase(const iterator& position);
+ /*!
+ * \brief Erase the entry associated with the key, do nothing if not exists
+ * \param key The indexing key
+ */
+ void erase(const key_type& key) { erase(find(key)); }
+
+ class iterator {
+ public:
+ using iterator_category = std::forward_iterator_tag;
+ using difference_type = int64_t;
+ using value_type = KVType;
+ using pointer = KVType*;
+ using reference = KVType&;
+ /*! \brief Default constructor */
+ iterator() : i(0), self(nullptr) {}
+ /*! \brief Compare iterators */
+ bool operator==(const iterator& other) const { return i == other.i && self
== other.self; }
+ /*! \brief Compare iterators */
+ bool operator!=(const iterator& other) const { return !(*this == other); }
+ /*! \brief De-reference iterators */
+ pointer operator->() const;
+ /*! \brief De-reference iterators */
+ reference operator*() const { return *((*this).operator->()); }
+ /*! \brief Prefix self increment, e.g. ++iter */
+ iterator& operator++();
+ /*! \brief Prefix self decrement, e.g. --iter */
+ iterator& operator--();
+ /*! \brief Suffix self increment */
+ iterator operator++(int) {
+ iterator copy = *this;
+ ++(*this);
+ return copy;
}
- if (const auto* str_a = a.as<StringObj>()) {
- if (const auto* str_b = b.as<StringObj>()) {
- return String::memncmp(str_a->data, str_b->data, str_a->size,
str_b->size) == 0;
+ /*! \brief Suffix self decrement */
+ iterator operator--(int) {
+ iterator copy = *this;
+ --(*this);
+ return copy;
+ }
+
+ protected:
+ /*! \brief Construct by value */
+ iterator(uint64_t i, const MapNode* self) : i(i), self(self) {}
+ /*! \brief The position on the array */
+ uint64_t i;
+ /*! \brief The container it points to */
+ const MapNode* self;
+
+ friend class DenseMapNode;
+ friend class SmallMapNode;
+ };
+
+ protected:
+ /*!
+ * \brief Create an empty container
+ * \return The object created
+ */
+ static ObjectPtr<MapNode> Empty();
+ /*!
+ * \brief Create the map using contents from the given iterators.
+ * \param first Begin of iterator
+ * \param last End of iterator
+ * \tparam IterType The type of iterator
+ * \return ObjectPtr to the map created
+ */
+ template <typename IterType>
+ static ObjectPtr<Object> CreateFromRange(IterType first, IterType last);
+ /*!
+ * \brief InsertMaybeReHash an entry into the given hash map
+ * \param kv The entry to be inserted
+ * \param map The pointer to the map, can be changed if re-hashing happens
+ */
+ static void InsertMaybeReHash(const KVType& kv, ObjectPtr<Object>* map);
+ /*!
+ * \brief Create an empty container with elements copying from another
SmallMapNode
+ * \param m The source container
+ * \return The object created
+ */
+ static ObjectPtr<MapNode> CopyFrom(MapNode* m);
+ /*! \brief number of slots minus 1 */
+ uint64_t slots_;
+ /*! \brief number of entries in the container */
+ uint64_t size_;
+ // Reference class
+ template <typename, typename, typename, typename>
+ friend class Map;
+};
+
+/*! \brief A specialization of small-sized hash map */
+class SmallMapNode : public MapNode,
+ public runtime::InplaceArrayBase<SmallMapNode,
MapNode::KVType> {
+ private:
+ static constexpr uint64_t kInitSize = 2;
+ static constexpr uint64_t kMaxSize = 4;
+
+ public:
+ using MapNode::iterator;
+ using MapNode::KVType;
+
+ /*! \brief Defaults to the destructor of InplaceArrayBase */
+ ~SmallMapNode() = default;
+ /*!
+ * \brief Count the number of times a key exists in the SmallMapNode
+ * \param key The indexing key
+ * \return The result, 0 or 1
+ */
+ size_t count(const key_type& key) const { return find(key).i < size_; }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The const reference to the value
+ */
+ const mapped_type& at(const key_type& key) const {
+ iterator itr = find(key);
+ CHECK(itr.i < size_) << "IndexError: key is not in Map";
+ return itr->second;
+ }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The mutable reference to the value
+ */
+ mapped_type& at(const key_type& key) {
+ iterator itr = find(key);
+ CHECK(itr.i < size_) << "IndexError: key is not in Map";
+ return itr->second;
+ }
+ /*! \return begin iterator */
+ iterator begin() const { return iterator(0, this); }
+ /*! \return end iterator */
+ iterator end() const { return iterator(size_, this); }
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ iterator find(const key_type& key) const {
+ KVType* ptr = static_cast<KVType*>(AddressOf(0));
+ for (uint64_t i = 0; i < size_; ++i, ++ptr) {
+ if (ObjectEqual()(ptr->first, key)) {
+ return iterator(i, this);
}
}
- return false;
+ return iterator(size_, this);
+ }
+ /*!
+ * \brief Erase the entry associated with the iterator
+ * \param position The iterator
+ */
+ void erase(const iterator& position) { Erase(position.i); }
+
+ private:
+ /*!
+ * \brief Remove a position in SmallMapNode
+ * \param i The position to be removed
+ */
+ void Erase(const uint64_t i) {
+ if (i >= size_) {
+ return;
+ }
+ KVType* begin = static_cast<KVType*>(AddressOf(0));
+ KVType* last = begin + (size_ - 1);
+ if (i + 1 == size_) {
+ last->first.ObjectRef::~ObjectRef();
+ last->second.ObjectRef::~ObjectRef();
+ } else {
+ *(begin + i) = std::move(*last);
+ }
+ size_ -= 1;
+ }
+ /*!
+ * \brief Create an empty container
+ * \param n Number of empty slots
+ * \return The object created
+ */
+ static ObjectPtr<SmallMapNode> Empty(uint64_t n = kInitSize) {
+ using ::tvm::runtime::make_inplace_array_object;
+ ObjectPtr<SmallMapNode> p = make_inplace_array_object<SmallMapNode,
KVType>(n);
+ p->size_ = 0;
+ p->slots_ = n;
+ return p;
+ }
+ /*!
+ * \brief Create an empty container initialized with a given range
+ * \param n Number of empty slots
+ * \param first begin of iterator
+ * \param last end of iterator
+ * \tparam IterType The type of iterator
+ * \return The object created
+ */
+ template <typename IterType>
+ static ObjectPtr<SmallMapNode> CreateFromRange(uint64_t n, IterType first,
IterType last) {
+ ObjectPtr<SmallMapNode> p = Empty(n);
+ KVType* ptr = static_cast<KVType*>(p->AddressOf(0));
+ for (; first != last; ++first, ++p->size_) {
+ new (ptr++) KVType(*first);
+ }
+ return p;
+ }
+ /*!
+ * \brief Create an empty container with elements copying from another
SmallMapNode
+ * \param m The source container
+ * \return The object created
+ */
+ static ObjectPtr<SmallMapNode> CopyFrom(SmallMapNode* m) {
+ KVType* first = static_cast<KVType*>(m->AddressOf(0));
+ KVType* last = first + m->size_;
+ return CreateFromRange(m->size_, first, last);
+ }
+ /*!
+ * \brief InsertMaybeReHash an entry into the given hash map
+ * \param kv The entry to be inserted
+ * \param map The pointer to the map, can be changed if re-hashing happens
+ */
+ static void InsertMaybeReHash(const KVType& kv, ObjectPtr<Object>* map) {
+ SmallMapNode* m = static_cast<SmallMapNode*>(map->get());
+ iterator itr = m->find(kv.first);
+ if (itr.i < m->size_) {
+ itr->second = kv.second;
+ return;
+ }
+ if (m->size_ < m->slots_) {
+ KVType* ptr = static_cast<KVType*>(m->AddressOf(m->size_));
+ new (ptr) KVType(kv);
+ ++m->size_;
+ return;
+ }
+ uint64_t next_size = std::max(m->slots_ * 2, uint64_t(kInitSize));
+ next_size = std::min(next_size, uint64_t(kMaxSize));
+ CHECK_GT(next_size, m->slots_);
+ ObjectPtr<Object> n = CreateFromRange(next_size, m->begin(), m->end());
+ InsertMaybeReHash(kv, &n);
+ *map = std::move(n);
}
+ /*!
+ * \brief Increment the pointer
+ * \param i The pointer to be incremented
+ * \return The increased pointer
+ */
+ uint64_t IncItr(uint64_t i) const { return i + 1 < size_ ? i + 1 : size_; }
+ /*!
+ * \brief Decrement the pointer
+ * \param i The pointer to be decremented
+ * \return The decreased pointer
+ */
+ uint64_t DecItr(uint64_t i) const { return i > 0 ? i - 1 : size_; }
+ /*!
+ * \brief De-reference the pointer
+ * \param i The pointer to be dereferenced
+ * \return The result
+ */
+ KVType* DeRefItr(uint64_t i) const { return
static_cast<KVType*>(AddressOf(i)); }
+ /*! \brief A size function used by InplaceArrayBase */
+ uint64_t GetSize() const { return size_; }
+
+ protected:
+ friend class MapNode;
+ friend class DenseMapNode;
+ friend ObjectPtr<MapNode> runtime::make_object<>();
+ friend class runtime::InplaceArrayBase<SmallMapNode, MapNode::KVType>;
};
-/*! \brief map node content */
-class MapNode : public Object {
+/*! \brief A specialization of hash map that implements the idea of
array-based hash map.
+ * Another reference implementation can be found [1].
+ *
+ * A. Overview
+ *
+ * DenseMapNode did several improvements over traditional separate chaining
hash,
+ * in terms of cache locality, memory footprints and data organization.
+ *
+ * A1. Implicit linked list. For better cache locality, instead of using
linked list
+ * explicitly for each bucket, we store list data into a single array that
spans contiguously
+ * in memory, and then carefully design access patterns to make sure most of
them fall into
+ * a single cache line.
+ *
+ * A2. 1-byte metadata. There is only 1 byte overhead for each slot in the
array to indexing and
+ * traversal. This can be divided in 3 parts.
+ * 1) Reserved code: (0b11111111)_2 indicates a slot is empty; (0b11111110)_2
indicates protected,
+ * which means the slot is empty but not allowed to be written.
+ * 2) If not empty or protected, the highest bit is used to indicate whether
data in the slot is
+ * head of a linked list.
+ * 3) The rest 7 bits are used as the "next pointer" (i.e. pointer to the next
element). On 64-bit
+ * architecture, an ordinary pointer can take up to 8 bytes, which is not
acceptable overhead when
+ * dealing with 16-byte ObjectRef pairs. Based on a commonly noticed fact that
the lists are
+ * relatively short (length <= 3) in hash maps, we follow [1]'s idea that only
allows the pointer to
+ * be one of the 126 possible values, i.e. if the next element of i-th slot is
(i + x)-th element,
+ * then x must be one of the 126 pre-defined values.
+ *
+ * A3. Data blocking. We organize the array in the way that every 16 elements
forms a data block.
+ * The 16-byte metadata of those 16 elements are stored together, followed by
the real data, i.e.
+ * 16 key-value pairs.
+ *
+ * B. Implementation details
+ *
+ * B1. Power-of-2 table size and Fibonacci Hashing. We use power-of-two as
table size to avoid
+ * modulo for more efficient arithmetics. To make the hash-to-slot mapping
distribute more evenly,
+ * we use the Fibonacci Hashing [2] trick.
+ *
+ * B2. Traverse a linked list in the array.
+ * 1) List head. Assume Fibonacci Hashing maps a given key to slot i, if
metadata at slot i
+ * indicates that it is list head, then we found the head; otherwise the list
is empty. No probing
+ * is done in this procedure. 2) Next element. To find the next element of a
non-empty slot i, we
+ * look at the last 7 bits of the metadata at slot i. If they are all zeros,
then it is the end of
+ * list; otherwise, we know that the next element is (i +
candidates[the-last-7-bits]).
+ *
+ * B3. InsertMaybeReHash an element. Following B2, we first traverse the
linked list to see if this
+ * element is in the linked list, and if not, we put it at the end by probing
the next empty
+ * position in one of the 126 candidate positions. If the linked list does not
even exist, but the
+ * slot for list head has been occupied by another linked list, we should find
this intruder another
+ * place.
+ *
+ * B4. Quadratic probing with triangle numbers. In open address hashing, it is
provable that probing
+ * with triangle numbers can traverse power-of-2-sized table [3]. In our
algorithm, we follow the
+ * suggestion in [1] that also use triangle numbers for "next pointer" as well
as sparing for list
+ * head.
+ *
+ * [1] https://github.com/skarupke/flat_hash_map
+ * [2] https://programmingpraxis.com/2018/06/19/fibonacci-hash/
+ * [3] https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
+ */
+class DenseMapNode : public MapNode {
+ private:
+ /*! \brief The number of elements in a memory block */
+ static constexpr int kBlockCap = 16;
+ /*! \brief Maximum load factor of the hash map */
+ static constexpr double kMaxLoadFactor = 0.99;
+ /*! \brief Binary representation of the metadata of an empty slot */
+ static constexpr uint8_t kEmptySlot = uint8_t(0b11111111);
+ /*! \brief Binary representation of the metadata of a protected slot */
+ static constexpr uint8_t kProtectedSlot = uint8_t(0b11111110);
+ /*! \brief Number of probing choices available */
+ static constexpr int kNumJumpDists = 126;
+ /*! \brief Head of the implicit linked list */
+ struct ListNode;
+ /*! \brief POD type of a block of memory */
+ struct Block {
+ uint8_t b[kBlockCap + kBlockCap * sizeof(KVType)];
+ };
+ static_assert(sizeof(Block) == kBlockCap * (sizeof(KVType) + 1),
"sizeof(Block) incorrect");
+ static_assert(std::is_standard_layout<Block>::value, "Block is not standard
layout");
+
public:
- /*! \brief The corresponding conatiner type */
- using ContainerType = std::unordered_map<ObjectRef, ObjectRef, ObjectHash,
ObjectEqual>;
+ using MapNode::iterator;
- /*! \brief the data content */
- ContainerType data;
+ /*!
+ * \brief Destroy the DenseMapNode
+ */
+ ~DenseMapNode() { this->Reset(); }
+ /*! \return The number of elements of the key */
+ size_t count(const key_type& key) const { return !Search(key).IsNone(); }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The const reference to the value
+ */
+ const mapped_type& at(const key_type& key) const { return At(key); }
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The mutable reference to the value
+ */
+ mapped_type& at(const key_type& key) { return At(key); }
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ iterator find(const key_type& key) const {
+ ListNode n = Search(key);
+ return n.IsNone() ? end() : iterator(n.index, this);
+ }
+ /*!
+ * \brief Erase the entry associated with the iterator
+ * \param position The iterator
+ */
+ void erase(const iterator& position) {
+ uint64_t i = position.i;
+ if (position.self != nullptr && i <= this->slots_) {
+ Erase(ListNode(i, this));
+ }
+ }
+ /*! \return begin iterator */
+ iterator begin() const {
+ if (slots_ == 0) {
+ return iterator(0, this);
+ }
+ for (uint64_t i = 0; i <= slots_; ++i) {
+ if (!ListNode(i, this).IsEmpty()) {
+ return iterator(i, this);
+ }
+ }
+ return iterator(slots_ + 1, this);
+ }
+ /*! \return end iterator */
+ iterator end() const { return slots_ == 0 ? iterator(0, this) :
iterator(slots_ + 1, this); }
- static constexpr const char* _type_key = "Map";
- TVM_DECLARE_FINAL_OBJECT_INFO(MapNode, Object);
+ private:
+ /*!
+ * \brief Search for the given key
+ * \param key The key
+ * \return ListNode that associated with the key
+ */
+ ListNode Search(const key_type& key) const {
+ if (this->size_ == 0) {
+ return ListNode();
+ }
+ for (ListNode n = GetListHead(ObjectHash()(key)); !n.IsNone();
n.MoveToNext(this)) {
+ if (ObjectEqual()(key, n.Key())) {
+ return n;
+ }
+ }
+ return ListNode();
+ }
+ /*!
+ * \brief Search for the given key, throw exception if not exists
+ * \param key The key
+ * \return ListNode that associated with the key
+ */
+ mapped_type& At(const key_type& key) const {
+ ListNode n = Search(key);
+ CHECK(!n.IsNone()) << "IndexError: key is not in Map";
+ return n.Val();
+ }
+ /*!
+ * \brief Try to insert a key, or do nothing if already exists
+ * \param key The indexing key
+ * \param result The linked-list entry found or just constructed
+ * \return A boolean, indicating if actual insertion happens
+ */
+ bool TryInsert(const key_type& key, ListNode* result) {
+ if (slots_ == 0) {
+ return false;
+ }
+ // required that `m` to be the head of a linked list through which we can
iterator
+ ListNode m = IndexFromhash(ObjectHash()(key));
+ // `m` can be: 1) empty; 2) body of an irrelevant list; 3) head of the
relevant list
+ // Case 1: empty
+ if (m.IsEmpty()) {
+ m.NewHead(KVType(key, ObjectRef(nullptr)));
+ this->size_ += 1;
+ *result = m;
+ return true;
+ }
+ // Case 2: body of an irrelevant list
+ if (!m.IsHead()) {
+ // we move the elements around and construct the single-element linked
list
+ return IsFull() ? false : TrySpareListHead(m, key, result);
+ }
+ // Case 3: head of the relevant list
+ // we iterate through the linked list until the end
+ ListNode n = m;
+ do {
+ // find equal item, do not insert
+ if (ObjectEqual()(key, n.Key())) {
+ *result = n;
+ return true;
+ }
+ // make sure `m` is the previous element of `n`
+ m = n;
+ } while (n.MoveToNext(this));
+ // `m` is the tail of the linked list
+ // always check capacity before insertion
+ if (IsFull()) {
+ return false;
+ }
+ // find the next empty slot
+ uint8_t jump;
+ if (!m.GetNextEmpty(this, &jump, result)) {
+ return false;
+ }
+ result->NewTail(KVType(key, ObjectRef(nullptr)));
+ // link `n` to `empty`, and move forward
+ m.SetJump(jump);
+ this->size_ += 1;
+ return true;
+ }
+ /*!
+ * \brief Spare an entry to be the head of a linked list.
+ * As described in B3, during insertion, it is possible that the entire
linked list does not
+ * exist, but the slot of its head has been occupied by other linked lists.
In this case, we need
+ * to spare the slot by moving away the elements to another valid empty one
to make insertion
+ * possible. \param n The given entry to be spared \param key The indexing
key \param result The
+ * linked-list entry constructed as the head \return A boolean, if actual
insertion happens
+ */
+ bool TrySpareListHead(ListNode n, const key_type& key, ListNode* result) {
+ // `n` is not the head of the linked list
+ // move the original item of `n` (if any)
+ // and construct new item on the position `n`
+ // To make `n` empty, we
+ // 1) find `w` the previous element of `n` in the linked list
+ // 2) copy the linked list starting from `r = n`
+ // 3) paste them after `w`
+ // read from the linked list after `r`
+ ListNode r = n;
+ // write to the tail of `w`
+ ListNode w = n.GetPrev(this);
+ // after `n` is moved, we disallow writing to the slot
+ bool is_first = true;
+ uint8_t r_meta, jump;
+ ListNode empty;
+ do {
+ // `jump` describes how `w` is jumped to `empty`
+ // rehash if there is no empty space after `w`
+ if (!w.GetNextEmpty(this, &jump, &empty)) {
+ return false;
+ }
+ // move `r` to `empty`
+ empty.NewTail(std::move(r.Data()));
+ // clear the metadata of `r`
+ r_meta = r.Meta();
+ if (is_first) {
+ is_first = false;
+ r.SetProtected();
+ } else {
+ r.SetEmpty();
+ }
+ // link `w` to `empty`, and move forward
+ w.SetJump(jump);
+ w = empty;
+ // move `r` forward as well
+ } while (r.MoveToNext(this, r_meta));
+ // finally we have done moving the linked list
+ // fill data_ into `n`
+ n.NewHead(KVType(key, ObjectRef(nullptr)));
+ this->size_ += 1;
+ *result = n;
+ return true;
+ }
+ /*!
+ * \brief Remove a ListNode
+ * \param n The node to be removed
+ */
+ void Erase(const ListNode& n) {
+ this->size_ -= 1;
+ if (!n.HasNext()) {
+ // `n` is the last
+ if (!n.IsHead()) {
+ // cut the link if there is any
+ n.GetPrev(this).SetJump(0);
+ }
+ n.Data().KVType::~KVType();
+ n.SetEmpty();
+ } else {
+ ListNode last = n, prev = n;
+ for (last.MoveToNext(this); last.HasNext(); prev = last,
last.MoveToNext(this)) {
+ }
+ n.Data() = std::move(last.Data());
+ last.SetEmpty();
+ prev.SetJump(0);
+ }
+ }
+ /*! \brief Clear the container to empty, release all entries and memory
acquired */
+ void Reset() {
+ uint64_t n_blocks = CalcNumBlocks(this->slots_);
+ DenseMapNode* m = this;
+ for (uint64_t bi = 0; bi < n_blocks; ++bi) {
+ uint8_t* m_m = m->data_[bi].b;
+ KVType* m_d = reinterpret_cast<KVType*>(m->data_[bi].b + kBlockCap);
+ for (int j = 0; j < kBlockCap; ++j, ++m_m, ++m_d) {
+ uint8_t& meta = *m_m;
+ if (meta != uint8_t(kProtectedSlot) && meta != uint8_t(kEmptySlot)) {
+ meta = uint8_t(kEmptySlot);
+ m_d->KVType::~KVType();
+ }
+ }
+ }
+ delete[] data_;
+ data_ = nullptr;
+ slots_ = 0;
+ size_ = 0;
+ fib_shift_ = 63;
+ }
+ /*!
+ * \brief Create an empty container
+ * \param fib_shift The fib shift provided
+ * \param n_slots Number of slots required, should be power-of-two
+ * \return The object created
+ */
+ static ObjectPtr<DenseMapNode> Empty(uint32_t fib_shift, uint64_t n_slots) {
+ CHECK_GT(n_slots, uint64_t(SmallMapNode::kMaxSize));
+ CHECK_EQ((n_slots & -n_slots), n_slots);
+ ObjectPtr<DenseMapNode> p = make_object<DenseMapNode>();
+ uint64_t n_blocks = CalcNumBlocks(n_slots - 1);
+ Block* block = p->data_ = new Block[n_blocks];
+ p->slots_ = n_slots - 1;
+ p->size_ = 0;
+ p->fib_shift_ = fib_shift;
+ for (uint64_t i = 0; i < n_blocks; ++i, ++block) {
+ std::fill(block->b, block->b + kBlockCap, uint8_t(kEmptySlot));
+ }
+ return p;
+ }
+ /*!
+ * \brief Create an empty container with elements copying from another
DenseMapNode
+ * \param m The source container
+ * \return The object created
+ */
+ static ObjectPtr<DenseMapNode> CopyFrom(DenseMapNode* m) {
+ ObjectPtr<DenseMapNode> p = make_object<DenseMapNode>();
+ uint64_t n_blocks = CalcNumBlocks(m->slots_);
+ p->data_ = new Block[n_blocks];
+ p->slots_ = m->slots_;
+ p->size_ = m->size_;
+ p->fib_shift_ = m->fib_shift_;
+ for (uint64_t bi = 0; bi < n_blocks; ++bi) {
+ uint8_t* m_m = m->data_[bi].b;
+ uint8_t* p_m = p->data_[bi].b;
+ KVType* m_d = reinterpret_cast<KVType*>(m->data_[bi].b + kBlockCap);
+ KVType* p_d = reinterpret_cast<KVType*>(p->data_[bi].b + kBlockCap);
+ for (int j = 0; j < kBlockCap; ++j, ++m_m, ++m_d, ++p_m, ++p_d) {
+ uint8_t& meta = *p_m = *m_m;
+ CHECK(meta != kProtectedSlot);
+ if (meta != uint8_t(kEmptySlot)) {
+ new (p_d) KVType(*m_d);
+ }
+ }
+ }
+ return p;
+ }
+ /*!
+ * \brief InsertMaybeReHash an entry into the given hash map
+ * \param kv The entry to be inserted
+ * \param map The pointer to the map, can be changed if re-hashing happens
+ */
+ static void InsertMaybeReHash(const KVType& kv, ObjectPtr<Object>* map) {
+ DenseMapNode* m = static_cast<DenseMapNode*>(map->get());
+ ListNode n;
+ if (m->TryInsert(kv.first, &n)) {
+ n.Val() = kv.second;
+ return;
+ }
+ CHECK_GT(m->slots_, uint64_t(SmallMapNode::kMaxSize));
+ ObjectPtr<Object> p = Empty(m->fib_shift_ - 1, m->slots_ * 2 + 2);
+ InsertMaybeReHash(kv, &p);
+ uint64_t n_blocks = CalcNumBlocks(m->slots_);
+ for (uint64_t bi = 0; bi < n_blocks; ++bi) {
+ uint8_t* m_m = m->data_[bi].b;
+ KVType* m_d = reinterpret_cast<KVType*>(m->data_[bi].b + kBlockCap);
+ for (int j = 0; j < kBlockCap; ++j, ++m_m, ++m_d) {
+ uint8_t& meta = *m_m;
+ if (meta != uint8_t(kProtectedSlot) && meta != uint8_t(kEmptySlot)) {
+ meta = uint8_t(kEmptySlot);
+ KVType kv = std::move(*m_d);
+ InsertMaybeReHash(kv, &p);
+ }
+ }
+ }
+ delete[] m->data_;
+ CHECK((static_cast<DenseMapNode*>(p.get()))->size_ == m->size_ + 1);
+ m->data_ = nullptr;
+ m->slots_ = 0;
+ m->size_ = 0;
+ m->fib_shift_ = 63;
+ *map = p;
+ }
+ /*!
+ * \brief Check whether the hash table is full
+ * \return A boolean indicating whether hash table is full
+ */
+ bool IsFull() const { return size_ + 1 > (slots_ + 1) * kMaxLoadFactor; }
+ /*!
+ * \brief Increment the pointer
+ * \param i The pointer to be incremented
+ * \return The increased pointer
+ */
+ uint64_t IncItr(uint64_t i) const {
+ for (++i; i <= slots_; ++i) {
+ if (!ListNode(i, this).IsEmpty()) {
+ return i;
+ }
+ }
+ return slots_ + 1;
+ }
+ /*!
+ * \brief Decrement the pointer
+ * \param i The pointer to be decremented
+ * \return The decreased pointer
+ */
+ uint64_t DecItr(uint64_t i) const {
+ while (i-- != 0) {
+ if (!ListNode(i, this).IsEmpty()) {
+ return i;
+ }
+ }
+ return slots_ + 1;
+ }
+ /*!
+ * \brief De-reference the pointer
+ * \param i The pointer to be dereferenced
+ * \return The result
+ */
+ KVType* DeRefItr(uint64_t i) const { return &ListNode(i, this).Data(); }
+ /*! \brief Construct from hash code */
+ ListNode IndexFromhash(uint64_t hash_value) const {
+ return ListNode(FibHash(hash_value, fib_shift_), this);
+ }
+ /*! \brief Construct from hash code if the position is head of list */
+ ListNode GetListHead(uint64_t hash_value) const {
+ ListNode n = IndexFromhash(hash_value);
+ return n.IsHead() ? n : ListNode();
+ }
+ /*! \brief Construct the number of blocks in the hash table */
+ static uint64_t CalcNumBlocks(uint64_t n_slots_m1) {
+ uint64_t n_slots = n_slots_m1 > 0 ? n_slots_m1 + 1 : 0;
+ return (n_slots + kBlockCap - 1) / kBlockCap;
+ }
+ /*! \brief Calculate the power-of-2 table size given the lower-bound of
required capacity. */
+ static void CalcTableSize(uint64_t cap, uint32_t* fib_shift, uint64_t*
n_slots) {
+ uint32_t shift = 64;
+ uint64_t slots = 1;
+ for (uint64_t c = cap; c; c >>= 1) {
+ shift -= 1;
+ slots <<= 1;
+ }
+ CHECK_GT(slots, cap);
+ if (slots < cap * 2) {
+ *fib_shift = shift - 1;
+ *n_slots = slots << 1;
+ } else {
+ *fib_shift = shift;
+ *n_slots = slots;
+ }
+ }
+ /*! \brief Fibonacci Hashing, maps a hash code to an index in a
power-of-2-sized table. */
+ static uint64_t FibHash(uint64_t hash_value, uint32_t fib_shift) {
+ // See also: https://programmingpraxis.com/2018/06/19/fibonacci-hash/
+ constexpr uint64_t coeff = 11400714819323198485ull;
+ return (coeff * hash_value) >> fib_shift;
+ }
+ /*! \brief The implicit in-place linked list used to index a chain */
+ struct ListNode {
+ /*! \brief Construct None */
+ ListNode() : index(0), block(nullptr) {}
+ /*! \brief Construct from position */
+ ListNode(uint64_t i, const DenseMapNode* self)
+ : index(i), block(self->data_ + (i / kBlockCap)) {}
+ /*! \brief Metadata on the entry */
+ uint8_t& Meta() const { return *(block->b + index % kBlockCap); }
+ /*! \brief Data on the entry */
+ KVType& Data() const {
+ return *(
+ reinterpret_cast<KVType*>(block->b + kBlockCap + (index % kBlockCap)
* sizeof(KVType)));
+ }
+ /*! \brief Key on the entry */
+ key_type& Key() const { return Data().first; }
+ /*! \brief Value on the entry */
+ mapped_type& Val() const { return Data().second; }
+ /*! \brief If the entry is head of linked list */
+ bool IsHead() const { return (Meta() & 0b10000000) == 0b00000000; }
+ /*! \brief If the entry is none */
+ bool IsNone() const { return block == nullptr; }
+ /*! \brief If the entry is empty slot */
+ bool IsEmpty() const { return Meta() == uint8_t(kEmptySlot); }
+ /*! \brief If the entry is protected slot */
+ bool IsProtected() const { return Meta() == uint8_t(kProtectedSlot); }
+ /*! \brief Set the entry to be empty */
+ void SetEmpty() const { Meta() = uint8_t(kEmptySlot); }
+ /*! \brief Set the entry to be protected */
+ void SetProtected() const { Meta() = uint8_t(kProtectedSlot); }
+ /*! \brief Set the entry's jump to its next entry */
+ void SetJump(uint8_t jump) const { (Meta() &= 0b10000000) |= jump; }
+ /*! \brief Construct a head of linked list in-place */
+ void NewHead(KVType v) const {
+ Meta() = 0b00000000;
+ new (&Data()) KVType(std::move(v));
+ }
+ /*! \brief Construct a tail of linked list in-place */
+ void NewTail(KVType v) const {
+ Meta() = 0b10000000;
+ new (&Data()) KVType(std::move(v));
+ }
+ /*! \brief If the entry has next entry on the linked list */
+ bool HasNext() const { return kNextProbeLocation[Meta() & 0b01111111] !=
0; }
+ /*! \brief Move the entry to the next entry on the linked list */
+ bool MoveToNext(const DenseMapNode* self, uint8_t meta) {
+ uint64_t d = kNextProbeLocation[meta & 0b01111111];
+ if (d == 0) {
+ index = 0;
+ block = nullptr;
+ return false;
+ }
+ index = (index + d) & (self->slots_);
+ block = self->data_ + (index / kBlockCap);
+ return true;
+ }
+ /*! \brief Move the entry to the next entry on the linked list */
+ bool MoveToNext(const DenseMapNode* self) { return MoveToNext(self,
Meta()); }
+ /*! \brief Get the previous entry on the linked list */
+ ListNode GetPrev(const DenseMapNode* self) const {
+ // start from the head of the linked list, which must exist
+ ListNode n = self->IndexFromhash(ObjectHash()(Key()));
+ // `m` is always the previous item of `n`
+ ListNode m = n;
+ for (n.MoveToNext(self); index != n.index; m = n, n.MoveToNext(self)) {
+ }
+ return m;
+ }
+ /*! \brief Get the next empty jump */
+ bool GetNextEmpty(const DenseMapNode* self, uint8_t* jump, ListNode*
result) const {
+ for (uint8_t idx = 1; idx < kNumJumpDists; ++idx) {
+ ListNode n((index + kNextProbeLocation[idx]) & (self->slots_), self);
+ if (n.IsEmpty()) {
+ *jump = idx;
+ *result = n;
+ return true;
+ }
+ }
+ return false;
+ }
+ /*! \brief Index on the real array */
+ uint64_t index;
+ /*! \brief Pointer to the actual block */
+ Block* block;
+ };
+
+ protected:
+ /*! \brief fib shift in Fibonacci Hashing */
+ uint32_t fib_shift_;
+ /*! \brief array of data blocks */
+ Block* data_;
+ /* clang-format off */
+ /*! \brief Candidates of probing distance */
+ TVM_DLL static constexpr uint64_t kNextProbeLocation[kNumJumpDists] {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
+ // Quadratic probing with triangle numbers. See also:
+ // 1) https://en.wikipedia.org/wiki/Quadratic_probing
+ // 2) https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
+ // 3) https://github.com/skarupke/flat_hash_map
+ 21, 28, 36, 45, 55, 66, 78, 91, 105, 120,
+ 136, 153, 171, 190, 210, 231, 253, 276, 300, 325,
+ 351, 378, 406, 435, 465, 496, 528, 561, 595, 630,
+ 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035,
+ 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540,
+ 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145,
+ 2211, 2278, 2346, 2415, 2485, 2556, 2628,
+ // larger triangle numbers
+ 8515, 19110, 42778, 96141, 216153,
+ 486591, 1092981, 2458653, 5532801, 12442566,
+ 27993903, 62983476, 141717030, 318844378, 717352503,
+ 1614057336, 3631522476, 8170957530, 18384510628, 41364789378,
+ 93070452520, 209408356380, 471168559170, 1060128894105, 2385289465695,
+ 5366898840628, 12075518705635, 27169915244790, 61132312065111,
137547689707000,
+ 309482283181501, 696335127828753, 1566753995631385, 3525196511162271,
7931691992677701,
+ 17846306936293605, 40154190677507445, 90346928918121501,
203280589587557251, 457381325854679626,
+ 1029107982097042876, 2315492959180353330, 5209859154120846435,
+ };
+ /* clang-format on */
+ friend class MapNode;
};
+#define _TVM_DISPATCH_MAP(base, var, body) \
+ { \
+ using TSmall = SmallMapNode*; \
+ using TDense = DenseMapNode*; \
+ uint64_t slots = base->slots_; \
+ if (slots <= SmallMapNode::kMaxSize) { \
+ TSmall var = static_cast<TSmall>(base); \
+ body; \
+ } else { \
+ TDense var = static_cast<TDense>(base); \
+ body; \
+ } \
+ }
+
+#define _TVM_DISPATCH_MAP_CONST(base, var, body) \
+ { \
+ using TSmall = const SmallMapNode*; \
+ using TDense = const DenseMapNode*; \
+ uint64_t slots = base->slots_; \
+ if (slots <= SmallMapNode::kMaxSize) { \
+ TSmall var = static_cast<TSmall>(base); \
+ body; \
+ } else { \
+ TDense var = static_cast<TDense>(base); \
+ body; \
+ } \
+ }
+
+inline MapNode::iterator::pointer MapNode::iterator::operator->() const {
+ _TVM_DISPATCH_MAP_CONST(self, p, { return p->DeRefItr(i); });
+}
+
+inline MapNode::iterator& MapNode::iterator::operator++() {
+ _TVM_DISPATCH_MAP_CONST(self, p, {
+ i = p->IncItr(i);
+ return *this;
+ });
+}
+
+inline MapNode::iterator& MapNode::iterator::operator--() {
+ _TVM_DISPATCH_MAP_CONST(self, p, {
+ i = p->IncItr(i);
+ return *this;
+ });
+}
+
+inline size_t MapNode::count(const key_type& key) const {
+ _TVM_DISPATCH_MAP_CONST(this, p, { return p->count(key); });
+}
+
+inline const MapNode::mapped_type& MapNode::at(const MapNode::key_type& key)
const {
+ _TVM_DISPATCH_MAP_CONST(this, p, { return p->at(key); });
+}
+
+inline MapNode::mapped_type& MapNode::at(const MapNode::key_type& key) {
+ _TVM_DISPATCH_MAP(this, p, { return p->at(key); });
+}
+
+inline MapNode::iterator MapNode::begin() const {
+ _TVM_DISPATCH_MAP_CONST(this, p, { return p->begin(); });
+}
+
+inline MapNode::iterator MapNode::end() const {
+ _TVM_DISPATCH_MAP_CONST(this, p, { return p->end(); });
+}
+
+inline MapNode::iterator MapNode::find(const MapNode::key_type& key) const {
+ _TVM_DISPATCH_MAP_CONST(this, p, { return p->find(key); });
+}
+
+inline void MapNode::erase(const MapNode::iterator& position) {
+ _TVM_DISPATCH_MAP(this, p, { return p->erase(position); });
+}
+
+#undef _TVM_DISPATCH_MAP
+#undef _TVM_DISPATCH_MAP_CONST
+
+inline ObjectPtr<MapNode> MapNode::Empty() { return SmallMapNode::Empty(); }
+
+inline ObjectPtr<MapNode> MapNode::CopyFrom(MapNode* m) {
+ if (m->slots_ <= SmallMapNode::kMaxSize) {
+ return SmallMapNode::CopyFrom(static_cast<SmallMapNode*>(m));
+ } else {
+ return DenseMapNode::CopyFrom(static_cast<DenseMapNode*>(m));
+ }
+}
+
+template <typename IterType>
+inline ObjectPtr<Object> MapNode::CreateFromRange(IterType first, IterType
last) {
+ int64_t _cap = std::distance(first, last);
+ if (_cap < 0) {
+ return SmallMapNode::Empty();
+ }
+ uint64_t cap = static_cast<uint64_t>(_cap);
+ if (cap < SmallMapNode::kMaxSize) {
+ return SmallMapNode::CreateFromRange(cap, first, last);
+ }
+ uint32_t fib_shift;
+ uint64_t n_slots;
+ DenseMapNode::CalcTableSize(cap, &fib_shift, &n_slots);
+ ObjectPtr<Object> n = DenseMapNode::Empty(fib_shift, n_slots);
+ for (; first != last; ++first) {
+ KVType kv(*first);
+ DenseMapNode::InsertMaybeReHash(kv, &n);
+ }
+ return n;
+}
+
+inline void MapNode::InsertMaybeReHash(const KVType& kv, ObjectPtr<Object>*
map) {
+ constexpr uint64_t kMaxSize = SmallMapNode::kMaxSize;
+ MapNode* base = static_cast<MapNode*>(map->get());
+ if (base->slots_ < kMaxSize) {
+ SmallMapNode::InsertMaybeReHash(kv, map);
+ CHECK_LE(static_cast<MapNode*>(map->get())->slots_, kMaxSize);
+ } else if (base->slots_ == kMaxSize) {
+ if (base->size_ < base->slots_) {
+ SmallMapNode::InsertMaybeReHash(kv, map);
+ CHECK_LE(static_cast<MapNode*>(map->get())->slots_, kMaxSize);
+ } else {
+ ObjectPtr<Object> new_map = MapNode::CreateFromRange(base->begin(),
base->end());
+ CHECK_GT(static_cast<MapNode*>(new_map.get())->slots_, kMaxSize);
+ DenseMapNode::InsertMaybeReHash(kv, &new_map);
+ *map = std::move(new_map);
+ CHECK_GT(static_cast<MapNode*>(map->get())->slots_, kMaxSize);
+ }
+ } else {
+ DenseMapNode::InsertMaybeReHash(kv, map);
+ CHECK_GT(static_cast<MapNode*>(map->get())->slots_, kMaxSize);
+ }
+}
+
+namespace runtime {
+template <>
+inline ObjectPtr<MapNode> make_object<>() {
+ return SmallMapNode::Empty();
Review comment:
Okay, here is what I am going to do:
* Mark make_object as deleted.
* Expose MapNode::Empty instead
Does it look good?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
