Detailed Description

template<typename TableItem, typename Key, typename Value, typename KeyExtractor, typename ReduceFunction, typename Emitter, const bool VolatileKey, typename ReduceConfig_, typename IndexFunction, typename KeyEqualFunction = std::equal_to<Key>>
class thrill::core::ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >

A data structure which takes an arbitrary value and extracts a key using a key extractor function from that value.

A key may also be provided initially as part of a key/value pair, not requiring to extract a key.

Afterwards, the key is hashed and the hash is used to assign that key/value pair to some slot.

In case a slot already has a key/value pair and the key of that value and the key of the value to be inserted are them same, the values are reduced according to some reduce function. No key/value is added to the data structure.

If the keys are different, the next slot (moving to the right) is considered. If the slot is occupied, the same procedure happens again (know as linear probing.)

Finally, the key/value pair to be inserted may either:

1.) Be reduced with some other key/value pair, sharing the same key. 2.) Inserted at a free slot. 3.) Trigger a resize of the data structure in case there are no more free slots in the data structure.

The following illustrations shows the general structure of the data structure. The set of slots is divided into 1..n partitions. Each key is hashed into exactly one partition.

Partition 0 Partition 1 Partition 2 Partition 3 Partition 4
P00 P01 P02 P10 P11 P12 P20 P21 P22 P30 P31 P32 P40 P41 P42

+—+—+—+—+—+—+—+—+—+—+—+—+—+—+—+ || | | || | | || | | || | | || | | || +—+—+—+—+—+—+—+—+—+—+—+—+—+—+—+ <- LI -> LI..Local Index <- GI -> GI..Global Index PI 0 PI 1 PI 2 PI 3 PI 4 PI..Partition ID

Definition at line 77 of file reduce_probing_hash_table.hpp.

Inheritance diagram for ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >:

Collaboration diagram for ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >:

#include <reduce_probing_hash_table.hpp>

Public Types
using	ReduceConfig = ReduceConfig_

Public Types inherited from ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >
using	MakeTableItem = ReduceMakeTableItem< Value, TableItem, VolatileKey >

using	ReduceConfig = ReduceConfig_

using	TableItem = typename std::conditional< VolatileKey, std::pair< Key, Value >, Value >::type

Public Member Functions
	ReduceProbingHashTable (Context &ctx, size_t dia_id, const KeyExtractor &key_extractor, const ReduceFunction &reduce_function, Emitter &emitter, size_t num_partitions, const ReduceConfig &config=ReduceConfig(), bool immediate_flush=false, const IndexFunction &index_function=IndexFunction(), const KeyEqualFunction &key_equal_function=KeyEqualFunction())

	~ReduceProbingHashTable ()

void	Dispose ()
	Deallocate items and memory. More...

void	GrowAndRehash (size_t partition_id)

void	GrowPartition (size_t partition_id)
	Grow a partition after a spill or flush (if possible) More...

void	Initialize (size_t limit_memory_bytes)

bool	Insert (const TableItem &kv)
	Inserts a value into the table, potentially reducing it in case both the key of the value already in the table and the key of the value to be inserted are the same. More...

Spilling Mechanisms to External Memory Files
void	SpillPartition (size_t partition_id)
	Spill all items of a partition into an external memory File. More...

void	SpillAnyPartition ()
	Spill all items of an arbitrary partition into an external memory File. More...

void	SpillLargestPartition ()
	Spill all items of the largest partition into an external memory File. More...

Flushing Mechanisms to Next Stage or Phase
template<typename Emit >
void	FlushPartitionEmit (size_t partition_id, bool consume, bool grow, Emit emit)

void	FlushPartition (size_t partition_id, bool consume, bool grow)

void	FlushAll ()

Public Member Functions inherited from ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >
	ReduceTable (Context &ctx, size_t dia_id, const KeyExtractor &key_extractor, const ReduceFunction &reduce_function, Emitter &emitter, size_t num_partitions, const ReduceConfig &config, bool immediate_flush, const IndexFunction &index_function, const KeyEqualFunction &key_equal_function)

	ReduceTable (const ReduceTable &)=delete
	non-copyable: delete copy-constructor More...

void	Dispose ()
	Deallocate memory. More...

void	InitializeSkip ()
	Initialize table for SkipPreReducePhase. More...

ReduceTable &	operator= (const ReduceTable &)=delete
	non-copyable: delete assignment operator More...

Context &	ctx () const
	Returns the context. More...

size_t	dia_id () const
	Returns dia_id_. More...

const KeyExtractor &	key_extractor () const
	Returns the key_extractor. More...

const ReduceFunction &	reduce_function () const
	Returns the reduce_function. More...

const Emitter &	emitter () const
	Returns emitter_. More...

const IndexFunction &	index_function () const
	Returns index_function_. More...

IndexFunction &	index_function ()
	Returns index_function_ (mutable) More...

const KeyEqualFunction &	key_equal_function () const
	Returns key_equal_function_. More...

std::vector< data::File > &	partition_files ()
	Returns the vector of partition files. More...

size_t	num_partitions ()
	Returns the number of partitions. More...

size_t	num_buckets () const
	Returns num_buckets_. More...

size_t	num_buckets_per_partition () const
	Returns num_buckets_per_partition_. More...

size_t	limit_memory_bytes () const
	Returns limit_memory_bytes_. More...

size_t	limit_items_per_partition () const
	Returns limit_items_per_partition_. More...

size_t	items_per_partition (size_t id) const
	Returns items_per_partition_. More...

size_t	num_items () const
	Returns the total num of items in the table. More...

size_t	num_items_calc () const
	Returns the total num of items in the table. More...

common::Range	key_range (size_t partition_id)
	calculate key range for the given output partition More...

bool	has_spilled_data () const
	returns whether and partition has spilled data into external memory. More...

bool	has_spilled_data_on_partition (size_t partition_id)

Key	key (const TableItem &t) const

TableItem	reduce (const TableItem &a, const TableItem &b) const

IndexFunction::Result	calculate_index (const TableItem &kv) const

Private Types
using	Super = ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >

Private Attributes
TableItem *	items_ = nullptr
	Storing the actual hash table. More...

std::vector< size_t >	limit_items_per_partition_

std::vector< size_t >	partition_size_
	Current sizes of the partitions because the valid allocated areas grow. More...

size_t	sentinel_partition_ = invalid_partition_

Static Private Attributes
static constexpr bool	debug_items = false

static constexpr size_t	invalid_partition_ = size_t(-1)
	sentinel for invalid partition or no sentinel. More...

Additional Inherited Members
Static Public Attributes inherited from ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >
static constexpr bool	debug

Protected Attributes inherited from ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >
Context &	ctx_
	Context. More...

size_t	dia_id_
	Associated DIA id. More...

Emitter &	emitter_
	Emitter object to receive items outputted to next phase. More...

IndexFunction	index_function_
	Index Calculation functions: Hash or ByIndex. More...

KeyEqualFunction	key_equal_function_
	Comparator function for keys. More...

KeyExtractor	key_extractor_
	Key extractor function for extracting a key from a value. More...

std::vector< data::File >	partition_files_
	Store the files for partitions. More...

ReduceFunction	reduce_function_
	Reduce function for reducing two values. More...

const size_t	num_partitions_
	Number of partitions. More...

ReduceConfig	config_
	config of reduce table More...

size_t	num_buckets_

size_t	num_buckets_per_partition_
	Partition size, the number of buckets per partition. More...

size_t	limit_memory_bytes_
	Size of the table in bytes. More...

size_t	limit_items_per_partition_
	Number of items in a partition before the partition is spilled. More...

bool	immediate_flush_

size_t	num_items_
	Current number of items. More...

std::vector< size_t >	items_per_partition_
	Current number of items per partition. More...

Member Typedef Documentation

◆ ReduceConfig

using ReduceConfig = ReduceConfig_

Definition at line 91 of file reduce_probing_hash_table.hpp.

◆ Super

using Super = ReduceTable<TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction>

private

Definition at line 86 of file reduce_probing_hash_table.hpp.

Constructor & Destructor Documentation

◆ ReduceProbingHashTable()

ReduceProbingHashTable	(	Context &	ctx,
		size_t	dia_id,
		const KeyExtractor &	key_extractor,
		const ReduceFunction &	reduce_function,
		Emitter &	emitter,
		size_t	num_partitions,
		const ReduceConfig &	config = `ReduceConfig()`,
		bool	immediate_flush = `false`,
		const IndexFunction &	index_function = `IndexFunction()`,
		const KeyEqualFunction &	key_equal_function = `KeyEqualFunction()`
	)

inline

Definition at line 93 of file reduce_probing_hash_table.hpp.

◆ ~ReduceProbingHashTable()

~ReduceProbingHashTable ( )

inline

Definition at line 170 of file reduce_probing_hash_table.hpp.

References ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::Dispose(), and ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::items_.

Member Function Documentation

◆ Dispose()

void Dispose ( )

inline

Deallocate items and memory.

Definition at line 271 of file reduce_probing_hash_table.hpp.

Referenced by ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::~ReduceProbingHashTable().

◆ FlushAll()

void FlushAll ( )

inline

Definition at line 492 of file reduce_probing_hash_table.hpp.

◆ FlushPartition()

void FlushPartition	(	size_t	partition_id,
		bool	consume,
		bool	grow
	)

inline

Definition at line 484 of file reduce_probing_hash_table.hpp.

References ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::emitter_, and ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::FlushPartitionEmit().

Referenced by ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::FlushAll(), and ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::SpillPartition().

◆ FlushPartitionEmit()

void FlushPartitionEmit	(	size_t	partition_id,
		bool	consume,
		bool	grow,
		Emit	emit
	)

inline

Definition at line 444 of file reduce_probing_hash_table.hpp.

Referenced by ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::FlushPartition().

◆ GrowAndRehash()

void GrowAndRehash ( size_t partition_id )

inline

Definition at line 293 of file reduce_probing_hash_table.hpp.

Referenced by ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::Insert().

◆ GrowPartition()

void GrowPartition ( size_t partition_id )

inline

Grow a partition after a spill or flush (if possible)

Definition at line 336 of file reduce_probing_hash_table.hpp.

References ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::config_, ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::items_, ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::limit_items_per_partition_, thrill::mem::memory_exceeded, min(), ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::num_buckets_per_partition_, ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::partition_size_, sLOG, ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::SpillPartition(), and TLX_UNLIKELY.

Referenced by ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::FlushPartitionEmit(), and ReduceProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::GrowAndRehash().

◆ Initialize()

void Initialize ( size_t limit_memory_bytes )

inline

Construct the hash table itself. fill it with sentinels. have one extra cell beyond the end for reducing the sentinel itself.

Definition at line 111 of file reduce_probing_hash_table.hpp.

◆ Insert()

bool Insert ( const TableItem & kv )

inline

Inserts a value into the table, potentially reducing it in case both the key of the value already in the table and the key of the value to be inserted are the same.

An insert may trigger a partial flush of the partition with the most items if the maximal number of items in the table (max_num_items_table) is reached.

Alternatively, it may trigger a resize of the table in case the maximal fill ratio per partition is reached.

Parameters