A specialization of hash map that implements the idea of array-based hash map. Another reference implementation can be found [1]. More...

#include <map.h>

Inheritance diagram for tvm::runtime::DenseMapNode:

Collaboration diagram for tvm::runtime::DenseMapNode:

Public Member Functions
	~DenseMapNode ()
	Destroy the DenseMapNode. More...

size_t	count (const key_type &key) const

const mapped_type &	at (const key_type &key) const
	Index value associated with a key, throw exception if the key does not exist. More...

mapped_type &	at (const key_type &key)
	Index value associated with a key, throw exception if the key does not exist. More...

iterator	find (const key_type &key) const
	Index value associated with a key. More...

void	erase (const iterator &position)
	Erase the entry associated with the iterator. More...

iterator	begin () const

iterator	end () const

Public Member Functions inherited from tvm::runtime::MapNode
	TVM_DECLARE_FINAL_OBJECT_INFO (MapNode, Object)

size_t	size () const
	Number of elements in the SmallMapNode. More...

size_t	count (const key_type &key) const
	Count the number of times a key exists in the hash map. More...

const mapped_type &	at (const key_type &key) const
	Index value associated with a key, throw exception if the key does not exist. More...

mapped_type &	at (const key_type &key)
	Index value associated with a key, throw exception if the key does not exist. More...

iterator	begin () const

iterator	end () const

iterator	find (const key_type &key) const
	Index value associated with a key. More...

void	erase (const iterator &position)
	Erase the entry associated with the iterator. More...

void	erase (const key_type &key)
	Erase the entry associated with the key, do nothing if not exists. More...

Public Member Functions inherited from tvm::runtime::Object
uint32_t	type_index () const

std::string	GetTypeKey () const

size_t	GetTypeKeyHash () const

template<typename TargetType >
bool	IsInstance () const

bool	unique () const

	Object ()

	Object (const Object &other)

	Object (Object &&other)

Object &	operator= (const Object &other)

Object &	operator= (Object &&other)

Static Protected Member Functions
static uint64_t	NextProbeLocation (size_t index)

Static Protected Member Functions inherited from tvm::runtime::MapNode
template<typename IterType >
static ObjectPtr< Object >	CreateFromRange (IterType first, IterType last)
	Create the map using contents from the given iterators. More...

static void	InsertMaybeReHash (const KVType &kv, ObjectPtr< Object > *map)
	InsertMaybeReHash an entry into the given hash map. More...

static ObjectPtr< MapNode >	CopyFrom (MapNode *from)
	Create an empty container with elements copying from another SmallMapNode. More...

Static Protected Member Functions inherited from tvm::runtime::Object
static uint32_t	GetOrAllocRuntimeTypeIndex (const std::string &key, uint32_t static_tindex, uint32_t parent_tindex, uint32_t type_child_slots, bool type_child_slots_can_overflow)
	Get the type index using type key. More...

Protected Attributes
uint32_t	fib_shift_
	fib shift in Fibonacci Hashing More...

Block *	data_
	array of data blocks More...

Protected Attributes inherited from tvm::runtime::MapNode
uint64_t	slots_
	number of slots minus 1 More...

uint64_t	size_
	number of entries in the container More...

Protected Attributes inherited from tvm::runtime::Object
uint32_t	type_index_ {0}
	Type index(tag) that indicates the type of the object. More...

RefCounterType	ref_counter_ {0}
	The internal reference counter. More...

FDeleter	deleter_ = nullptr
	deleter of this object to enable customized allocation. If the deleter is nullptr, no deletion will be performed. The creator of the object must always set the deleter field properly. More...

Friends
class	MapNode

Additional Inherited Members
Public Types inherited from tvm::runtime::MapNode
using	key_type = ObjectRef
	Type of the keys in the hash map. More...

using	mapped_type = ObjectRef
	Type of the values in the hash map. More...

using	KVType = std::pair< ObjectRef, ObjectRef >
	Type of value stored in the hash map. More...

Public Types inherited from tvm::runtime::Object
typedef void(*	FDeleter) (Object *self)
	Object deleter. More...

using	RefCounterType = std::atomic< int32_t >

Static Public Member Functions inherited from tvm::runtime::MapNode
static ObjectPtr< MapNode >	Empty ()
	Create an empty container. More...

Static Public Member Functions inherited from tvm::runtime::Object
static std::string	TypeIndex2Key (uint32_t tindex)
	Get the type key of the corresponding index from runtime. More...

static size_t	TypeIndex2KeyHash (uint32_t tindex)
	Get the type key hash of the corresponding index from runtime. More...

static uint32_t	TypeKey2Index (const std::string &key)
	Get the type index of the corresponding key from runtime. More...

static uint32_t	_GetOrAllocRuntimeTypeIndex ()

static uint32_t	RuntimeTypeIndex ()

Static Public Attributes inherited from tvm::runtime::MapNode
static constexpr const uint32_t	_type_index = runtime::TypeIndex::kRuntimeMap

static constexpr const char *	_type_key = "Map"

Static Public Attributes inherited from tvm::runtime::Object
static constexpr const char *	_type_key = "runtime.Object"

static constexpr bool	_type_final = false

static constexpr uint32_t	_type_child_slots = 0

static constexpr bool	_type_child_slots_can_overflow = true

static constexpr bool	_type_has_method_visit_attrs = true

static constexpr bool	_type_has_method_sequal_reduce = false

static constexpr bool	_type_has_method_shash_reduce = false

static constexpr uint32_t	_type_index = TypeIndex::kDynamic

Protected Member Functions inherited from tvm::runtime::Object
void	IncRef ()
	developer function, increases reference counter. More...

void	DecRef ()
	developer function, decrease reference counter. More...

Detailed Description

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/

Constructor & Destructor Documentation

◆ ~DenseMapNode()

tvm::runtime::DenseMapNode::~DenseMapNode ( )

inline

Destroy the DenseMapNode.

Member Function Documentation

◆ at() [1/2]

mapped_type& tvm::runtime::DenseMapNode::at ( const key_type & key )

inline

Index value associated with a key, throw exception if the key does not exist.

Parameters

key	The indexing key

Returns: The mutable reference to the value

◆ at() [2/2]

const mapped_type& tvm::runtime::DenseMapNode::at ( const key_type & key ) const

inline

Index value associated with a key, throw exception if the key does not exist.

Parameters

key	The indexing key

Returns: The const reference to the value

◆ begin()

iterator tvm::runtime::DenseMapNode::begin ( ) const

inline

Returns: begin iterator

◆ count()

size_t tvm::runtime::DenseMapNode::count ( const key_type & key ) const

inline

Returns: The number of elements of the key

◆ end()

iterator tvm::runtime::DenseMapNode::end ( ) const

inline

Returns: end iterator

◆ erase()

void tvm::runtime::DenseMapNode::erase ( const iterator & position )

inline

Erase the entry associated with the iterator.

Parameters

position The iterator

◆ find()

iterator tvm::runtime::DenseMapNode::find ( const key_type & key ) const

inline

Index value associated with a key.

Parameters

key	The indexing key

Returns: The iterator of the entry associated with the key, end iterator if not exists

◆ NextProbeLocation()

static uint64_t tvm::runtime::DenseMapNode::NextProbeLocation ( size_t index )

inlinestaticprotected

Candidates of probing distance

Friends And Related Function Documentation

◆ MapNode

friend class MapNode

friend

Member Data Documentation

◆ data_

Block* tvm::runtime::DenseMapNode::data_

protected

array of data blocks

◆ fib_shift_

uint32_t tvm::runtime::DenseMapNode::fib_shift_

protected

fib shift in Fibonacci Hashing

The documentation for this class was generated from the following file:

include/tvm/runtime/container/map.h

Public Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ~DenseMapNode()

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ begin()

◆ count()

◆ end()

◆ erase()

◆ find()

◆ NextProbeLocation()

Friends And Related Function Documentation

◆ MapNode

Member Data Documentation

◆ data_

◆ fib_shift_