Detailed Description

template<typename ValueType, typename CompareFunction, typename SortAlgorithm, bool Stable = false>
class thrill::api::SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >

A DIANode which performs a Sort operation.

Sort sorts a DIA according to a given compare function

Template Parameters

ValueType	Type of DIA elements
CompareFunction	Type of the compare function
SortAlgorithm	Type of the local sort function
Stable	Whether or not to use stable sorting mechanisms

Definition at line 64 of file sort.hpp.

Inheritance diagram for SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >:

Collaboration diagram for SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >:

#include <sort.hpp>

Classes
struct	MakeDefaultMultiwayMergeTree
	Multiway merge tree creation depends on Stable flag. More...

struct	MakeStableMultiwayMergeTree

class	TreeBuilder

Public Member Functions
template<typename ParentDIA >
	SortNode (const ParentDIA &parent, const CompareFunction &compare_function, const SortAlgorithm &sort_algorithm=SortAlgorithm())
	Constructor for a sort node. More...

void	Dispose () final
	Virtual clear method. Triggers actual disposing in sub-classes. More...

void	Execute () final
	Executes the sum operation. More...

DIAMemUse	ExecuteMemUse () final
	Amount of RAM used by Execute() More...

bool	OnPreOpFile (const data::File &file, size_t) final
	Receive a whole data::File of ValueType, but only if our stack is empty. More...

void	PreOp (const ValueType &input)

void	PushData (bool consume) final
	Virtual method for pushing data. Triggers actual pushing in sub-classes. More...

DIAMemUse	PushDataMemUse () final
	Amount of RAM used by PushData() More...

void	StartPreOp (size_t) final
	Virtual method for preparing start of PushData. More...

void	StopPreOp (size_t) final
	Virtual method for preparing end of PushData. More...

Public Member Functions inherited from DOpNode< ValueType >
	DOpNode (Context &ctx, const char *label, const std::initializer_list< size_t > &parent_ids, const std::initializer_list< DIABasePtr > &parents)
	Constructor for a DOpNode, which sets references to the parent nodes. More...

	DOpNode (Context &ctx, const char *label, std::vector< size_t > &&parent_ids, std::vector< DIABasePtr > &&parents)
	Constructor for a DOpNode, which sets references to the parent nodes. More...

Public Member Functions inherited from DIANode< ValueType >
	DIANode (Context &ctx, const char *label, const std::initializer_list< size_t > &parent_ids, const std::initializer_list< DIABasePtr > &parents)
	Constructor for a DIANode, which sets references to the parent nodes. More...

	DIANode (Context &ctx, const char *label, std::vector< size_t > &&parent_ids, std::vector< DIABasePtr > &&parents)
	Constructor for a DIANode, which sets references to the parent nodes. More...

virtual void	AddChild (DIABase *node, const Callback &callback=Callback(), size_t parent_index=0)
	Enables children to push their "folded" function chains to their parent. More...

std::vector< DIABase * >	children () const override
	Returns the children of this DIABase. More...

void	PushFile (data::File &file, bool consume) const

void	PushItem (const ValueType &item) const
	Method for derived classes to Push a single item to all children. More...

void	RemoveAllChildren () override

void	RemoveChild (DIABase *node) override

void	RunPushData () override

Public Member Functions inherited from DIABase
	DIABase (Context &ctx, const char *label, const std::initializer_list< size_t > &parent_ids, const std::initializer_list< DIABasePtr > &parents)
	The constructor for a DIABase. More...

	DIABase (Context &ctx, const char *label, std::vector< size_t > &&parent_ids, std::vector< DIABasePtr > &&parents)
	The constructor for a DIABase. More...

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

	DIABase (DIABase &&)=default
	move-constructor: default More...

virtual	~DIABase ()
	Virtual destructor for a DIABase. More...

virtual size_t	consume_counter () const
	Returns consume_counter_. More...

Context &	context ()
	Returns the api::Context of this DIABase. More...

virtual void	DecConsumeCounter (size_t counter)

const size_t &	dia_id () const
	return unique id of DIANode subclass as stored by StatsNode More...

virtual bool	ForwardDataOnly () const

virtual void	IncConsumeCounter (size_t counter)

const char *	label () const
	return label() of DIANode subclass as stored by StatsNode More...

mem::Manager &	mem_manager ()
	Return the Context's memory manager. More...

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

DIABase &	operator= (DIABase &&)=default
	move-assignment operator: default More...

std::vector< size_t >	parent_ids () const
	Returns the parents of this DIABase. More...

const std::vector< DIABasePtr > &	parents () const
	Returns the parents of this DIABase. More...

void	RemoveParent (DIABase *p)
	Remove a parent. More...

virtual bool	RequireParentPushData (size_t) const

void	RunScope ()

void	set_mem_limit (const DIAMemUse &mem_limit)

void	set_state (const DIAState &state)

virtual void	SetConsumeCounter (size_t counter)

DIAState	state () const

virtual DIAMemUse	PreOpMemUse ()
	Amount of RAM used by PreOp after StartPreOp() More...

Public Member Functions inherited from ReferenceCounter
	ReferenceCounter () noexcept
	new objects have zero reference count More...

	ReferenceCounter (const ReferenceCounter &) noexcept
	coping still creates a new object with zero reference count More...

	~ReferenceCounter ()

bool	dec_reference () const noexcept
	Call whenever resetting (i.e. More...

void	inc_reference () const noexcept
	Call whenever setting a pointer to the object. More...

ReferenceCounter &	operator= (const ReferenceCounter &) noexcept
	assignment operator, leaves pointers unchanged More...

size_t	reference_count () const noexcept
	Return the number of references to this object (for debugging) More...

bool	unique () const noexcept
	Test if the ReferenceCounter is referenced by only one CountingPtr. More...

Private Types
using	MakeMultiwayMergeTree = typename std::conditional< Stable, MakeStableMultiwayMergeTree, MakeDefaultMultiwayMergeTree >::type

using	RunTimer = common::RunTimer< Timer >
	RIAA class for running the timer. More...

using	SampleIndexPair = std::pair< ValueType, size_t >

using	Super = DOpNode< ValueType >

using	Timer = common::StatsTimerBaseStopped< stats_enabled >
	Timer or FakeTimer. More...

using	TranmissionStreamPtr = tlx::CountingPtr< TranmissionStreamType >

using	TranmissionStreamType = typename std::conditional< Stable, data::CatStream, data::MixStream >::type
	Stream type for item transmission depends on Stable flag. More...

Private Member Functions
bool	EqualSampleGreaterIndex (const SampleIndexPair &a, const SampleIndexPair &b)

void	FindAndSendSplitters (std::vector< SampleIndexPair > &splitters, size_t sample_size, data::MixStreamPtr &sample_stream, data::MixStream::Writers &sample_writers)

bool	LessSampleIndex (const SampleIndexPair &a, const SampleIndexPair &b)

void	MainOp ()

void	PartialMultiwayMerge (size_t merge_degree, size_t prefetch)

void	ReceiveItems (TranmissionStreamPtr &data_stream)

void	SortAndWriteToFile (std::vector< ValueType > &vec)

void	TransmitItems (const ValueType const tree, size_t k, size_t log_k, size_t actual_k, const SampleIndexPair const sorted_splitters, size_t prefix_items, TranmissionStreamPtr &data_stream)

Static Private Member Functions
template<typename Integral >
static size_t	RoundDown (Integral n, Integral k)
	round n down by k where k is a power of two. More...

Private Attributes
CompareFunction	compare_function_
	The comparison function which is applied to two elements. More...

const bool	parent_stack_empty_
	Whether the parent stack is empty. More...

SortAlgorithm	sort_algorithm_
	Sort function class. More...

MainOp and PushData
std::vector< data::File >	files_
	Local data files. More...

size_t	local_out_size_ = 0
	Total number of local elements after communication. More...

Statistics
Timer	timer_preop_
	time spent in PreOp (including preceding Node's computation) More...

Timer	timer_execute_
	time spent in Execute More...

Timer	timer_sort_
	time spent in sort() More...

Static Private Attributes
static constexpr bool	debug = false

static constexpr bool	stats_enabled = false
	Set this variable to true to enable generation and output of stats. More...

static const bool	use_background_thread_ = false

PreOp Phase
static constexpr double	desired_imbalance_ = 0.1
	epsilon More...

data::File	unsorted_file_ { context_.GetFile(this) }
	All local unsorted items before communication. More...

data::File::Writer	unsorted_writer_
	Writer for unsorted_file_. More...

size_t	local_items_ = 0
	Number of items on this worker. More...

std::vector< SampleIndexPair >	samples_
	Sample vector: pairs of (sample,local index) More...

common::ReservoirSamplingGrow< SampleIndexPair >	res_sampler_
	Reservoir sampler. More...

size_t	wanted_sample_size () const
	calculate currently desired number of samples More...

Additional Inherited Members
Public Types inherited from DOpNode< ValueType >
using	Super = DIANode< ValueType >

Public Types inherited from DIANode< ValueType >
using	Callback = tlx::delegate< void(const ValueType &)>

Public Types inherited from DIABase
using	DIABasePtr = tlx::CountingPtr< DIABase >

Public Attributes inherited from DIABase
common::JsonLogger	logger_

Static Public Attributes inherited from DIABase
static constexpr size_t	kNeverConsume = static_cast<size_t>(-1)
	Never full consume. More...

Protected Attributes inherited from DIANode< ValueType >
std::vector< Child >	children_
	Callback functions from the child nodes. More...

Protected Attributes inherited from DIABase
Context &	context_
	associated Context More...

const size_t	dia_id_
	DIA serial id. More...

const char *const	label_
	DOp node static label. More...

DIAState	state_ = DIAState::NEW
	State of the DIANode. State is NEW on creation. More...

std::vector< DIABasePtr >	parents_
	Parents of this DIABase. More...

DIAMemUse	mem_limit_ = 0

size_t	consume_counter_ = 1

Member Typedef Documentation

◆ MakeMultiwayMergeTree

using MakeMultiwayMergeTree = typename std::conditional< Stable, MakeStableMultiwayMergeTree, MakeDefaultMultiwayMergeTree>::type

private

Definition at line 114 of file sort.hpp.

◆ RunTimer

using RunTimer = common::RunTimer<Timer>

private

RIAA class for running the timer.

Definition at line 77 of file sort.hpp.

◆ SampleIndexPair

using SampleIndexPair = std::pair<ValueType, size_t>

private

Definition at line 79 of file sort.hpp.

◆ Super

using Super = DOpNode<ValueType>

private

Definition at line 71 of file sort.hpp.

◆ Timer

using Timer = common::StatsTimerBaseStopped<stats_enabled>

private

Timer or FakeTimer.

Definition at line 75 of file sort.hpp.

◆ TranmissionStreamPtr

using TranmissionStreamPtr = tlx::CountingPtr<TranmissionStreamType>

private

Definition at line 85 of file sort.hpp.

◆ TranmissionStreamType

using TranmissionStreamType = typename std::conditional< Stable, data::CatStream, data::MixStream>::type

private

Stream type for item transmission depends on Stable flag.

Definition at line 84 of file sort.hpp.

Constructor & Destructor Documentation

◆ SortNode()

SortNode	(	const ParentDIA &	parent,
		const CompareFunction &	compare_function,
		const SortAlgorithm &	sort_algorithm = `SortAlgorithm()`
	)

inline

Constructor for a sort node.

Definition at line 123 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::parent_stack_empty_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::sort_algorithm_.

Member Function Documentation

◆ Dispose()

void Dispose ( )

inlinefinalvirtual

Virtual clear method. Triggers actual disposing in sub-classes.

Reimplemented from DIABase.

Definition at line 273 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::files_.

◆ EqualSampleGreaterIndex()

bool EqualSampleGreaterIndex	(	const SampleIndexPair &	a,
		const SampleIndexPair &	b
	)

inlineprivate

Definition at line 424 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems().

◆ Execute()

void Execute ( )

inlinefinalvirtual

Executes the sum operation.

Implements DIABase.

Definition at line 197 of file sort.hpp.

References DIABase::context_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp(), Context::PrintCollectiveMeanStdev(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::timer_execute_.

◆ ExecuteMemUse()

DIAMemUse ExecuteMemUse ( )

inlinefinalvirtual

Amount of RAM used by Execute()

Reimplemented from DIABase.

Definition at line 192 of file sort.hpp.

References DIAMemUse::Max().

◆ FindAndSendSplitters()

void FindAndSendSplitters	(	std::vector< SampleIndexPair > &	splitters,
		size_t	sample_size,
		data::MixStreamPtr &	sample_stream,
		data::MixStream::Writers &	sample_writers
	)

inlineprivate

Definition at line 337 of file sort.hpp.

References DIABase::context_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::LessSampleIndex(), LOG, and Context::num_workers().

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp().

◆ LessSampleIndex()

bool LessSampleIndex	(	const SampleIndexPair &	a,
		const SampleIndexPair &	b
	)

inlineprivate

Definition at line 419 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::FindAndSendSplitters().

◆ MainOp()

void MainOp ( )

inlineprivate

Definition at line 537 of file sort.hpp.

References StreamData::Writers::Close(), DIABase::context_, thrill::common::CreateThread(), DIABase::dia_id(), FlowControlChannel::ExPrefixSumTotal(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::FindAndSendSplitters(), Context::GetNewMixStream(), MixBlockQueueReader::HasNext(), tlx::integer_log2_ceil(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_items_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_out_size_, Context::local_worker_id(), DIABase::logger_, Context::my_rank(), Context::net, Context::num_workers(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::ReceiveItems(), CountingPtr< Type, Deleter >::reset(), thrill::common::SetCpuAffinity(), sLOG, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems(), and tlx::vector_free().

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::Execute().

◆ OnPreOpFile()

bool OnPreOpFile	(	const data::File &	file,
		size_t
	)

inlinefinalvirtual

Receive a whole data::File of ValueType, but only if our stack is empty.

Reimplemented from DIABase.

Definition at line 151 of file sort.hpp.

References DIABase::context_, File::Copy(), thrill::common::g_debug_push_file, File::GetItemAt(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_items_, LOGC, min(), File::num_items(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::parent_stack_empty_, Context::rng_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::samples_, sLOG, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_file_, and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::wanted_sample_size().

◆ PartialMultiwayMerge()

void PartialMultiwayMerge	(	size_t	merge_degree,
		size_t	prefetch
	)

inlineprivate

Definition at line 744 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_, DIABase::context_, Context::GetFile(), sLOG1, thrill::data::StartPrefetch(), and tlx::swap().

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PushData().

◆ PreOp()

void PreOp ( const ValueType & input )

inline

Definition at line 144 of file sort.hpp.

References ReservoirSamplingGrow< Type, RNG >::add(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_items_, BlockWriter< BlockSink >::Put(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::res_sampler_, and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_writer_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortNode().

◆ PushData()

void PushData ( bool consume )

inlinefinalvirtual

Virtual method for pushing data. Triggers actual pushing in sub-classes.

Implements DIABase.

Definition at line 216 of file sort.hpp.

References Context::block_pool(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_, DIABase::context_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::files_, BlockPool::MaxMergeDegreePrefetch(), Context::my_rank(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PartialMultiwayMerge(), Context::PrintCollectiveMeanStdev(), DIANode< ValueType >::PushFile(), DIANode< ValueType >::PushItem(), sLOGC, and thrill::data::StartPrefetch().

◆ PushDataMemUse()

DIAMemUse PushDataMemUse ( )

inlinefinalvirtual

Amount of RAM used by PushData()

Reimplemented from DIABase.

Definition at line 205 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::files_, and DIAMemUse::Max().

◆ ReceiveItems()

void ReceiveItems ( TranmissionStreamPtr & data_stream )

inlineprivate

Definition at line 665 of file sort.hpp.

References DIABase::context_, LOG0, DIABase::mem_limit_, thrill::mem::memory_exceeded, Context::PrintCollectiveMeanStdev(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortAndWriteToFile().

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp().

◆ RoundDown()

static size_t RoundDown	(	Integral	n,
		Integral	k
	)

inlinestaticprivate

round n down by k where k is a power of two.

Definition at line 430 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems().

◆ SortAndWriteToFile()

void SortAndWriteToFile ( std::vector< ValueType > & vec )

inlineprivate

Definition at line 696 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_, DIABase::context_, die_unless, Context::GetFile(), LOG, LOG0, DIABase::logger_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::sort_algorithm_, and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::timer_sort_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::ReceiveItems().

◆ StartPreOp()

void StartPreOp ( size_t )

inlinefinalvirtual

Virtual method for preparing start of PushData.

Reimplemented from DIABase.

Definition at line 139 of file sort.hpp.

References File::GetWriter(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::timer_preop_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_file_, and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_writer_.

◆ StopPreOp()

void StopPreOp ( size_t )

inlinefinalvirtual

Virtual method for preparing end of PushData.

Reimplemented from DIABase.

Definition at line 177 of file sort.hpp.

References BlockWriter< BlockSink >::Close(), DIABase::context_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_items_, LOG0, Context::PrintCollectiveMeanStdev(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::samples_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::timer_preop_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_writer_, and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::wanted_sample_size().

◆ TransmitItems()

void TransmitItems	(	const ValueType *const	tree,
		size_t	k,
		size_t	log_k,
		size_t	actual_k,
		const SampleIndexPair *const	sorted_splitters,
		size_t	prefix_items,
		TranmissionStreamPtr &	data_stream
	)

inlineprivate

Definition at line 434 of file sort.hpp.

References SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::compare_function_, SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::EqualSampleGreaterIndex(), File::GetConsumeReader(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::local_items_, BlockReader< BlockSource >::Next(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::RoundDown(), tlx::swap(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::unsorted_file_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp().

◆ wanted_sample_size()

size_t wanted_sample_size ( ) const

inlineprivate

calculate currently desired number of samples

Definition at line 307 of file sort.hpp.

References ReservoirSamplingGrow< Type, RNG >::calc_sample_size(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::res_sampler_.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::OnPreOpFile(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StopPreOp().

Member Data Documentation

◆ compare_function_

CompareFunction compare_function_

private

The comparison function which is applied to two elements.

Definition at line 279 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::EqualSampleGreaterIndex(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::LessSampleIndex(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PartialMultiwayMerge(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PushData(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortAndWriteToFile(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortNode(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems().

◆ debug

constexpr bool debug = false

staticprivate

Definition at line 66 of file sort.hpp.

◆ desired_imbalance_

constexpr double desired_imbalance_ = 0.1

staticprivate

epsilon

Definition at line 298 of file sort.hpp.

◆ files_

std::vector<data::File> files_

private

Local data files.

Definition at line 317 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::Dispose(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PushData(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PushDataMemUse().

◆ local_items_

size_t local_items_ = 0

private

Number of items on this worker.

Definition at line 295 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::OnPreOpFile(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PreOp(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StopPreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems().

◆ local_out_size_

size_t local_out_size_ = 0

private

Total number of local elements after communication.

Definition at line 319 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::MainOp().

◆ parent_stack_empty_

const bool parent_stack_empty_

private

Whether the parent stack is empty.

Definition at line 285 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::OnPreOpFile(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortNode().

◆ res_sampler_

common::ReservoirSamplingGrow<SampleIndexPair> res_sampler_

private

Initial value:

{
        samples_, context_.rng_, desired_imbalance_
    }

Reservoir sampler.

Definition at line 303 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::wanted_sample_size().

◆ samples_

std::vector<SampleIndexPair> samples_

private

Sample vector: pairs of (sample,local index)

Definition at line 301 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::OnPreOpFile(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StopPreOp().

◆ sort_algorithm_

SortAlgorithm sort_algorithm_

private

Sort function class.

Definition at line 282 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortAndWriteToFile(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortNode().

◆ stats_enabled

constexpr bool stats_enabled = false

staticprivate

Set this variable to true to enable generation and output of stats.

Definition at line 69 of file sort.hpp.

◆ timer_execute_

Timer timer_execute_

private

time spent in Execute

Definition at line 330 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::Execute().

◆ timer_preop_

Timer timer_preop_

private

time spent in PreOp (including preceding Node's computation)

Definition at line 327 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StartPreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StopPreOp().

◆ timer_sort_

Timer timer_sort_

private

time spent in sort()

Definition at line 333 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::SortAndWriteToFile().

◆ unsorted_file_

data::File unsorted_file_ { context_.GetFile(this) }

private

All local unsorted items before communication.

Definition at line 291 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::OnPreOpFile(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StartPreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::TransmitItems().

◆ unsorted_writer_

data::File::Writer unsorted_writer_

private

Writer for unsorted_file_.

Definition at line 293 of file sort.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::PreOp(), SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StartPreOp(), and SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >::StopPreOp().

◆ use_background_thread_

const bool use_background_thread_ = false

staticprivate

Definition at line 116 of file sort.hpp.

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

thrill/api/sort.hpp

Detailed Description

template<typename ValueType, typename CompareFunction, typename SortAlgorithm, bool Stable = false> class thrill::api::SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

PreOp Phase

Additional Inherited Members

Member Typedef Documentation

◆ MakeMultiwayMergeTree

◆ RunTimer

◆ SampleIndexPair

◆ Super

◆ Timer

◆ TranmissionStreamPtr

◆ TranmissionStreamType

Constructor & Destructor Documentation

◆ SortNode()

Member Function Documentation

◆ Dispose()

◆ EqualSampleGreaterIndex()

◆ Execute()

◆ ExecuteMemUse()

◆ FindAndSendSplitters()

◆ LessSampleIndex()

◆ MainOp()

◆ OnPreOpFile()

◆ PartialMultiwayMerge()

◆ PreOp()

◆ PushData()

◆ PushDataMemUse()

◆ ReceiveItems()

◆ RoundDown()

◆ SortAndWriteToFile()

◆ StartPreOp()

◆ StopPreOp()

◆ TransmitItems()

◆ wanted_sample_size()

Member Data Documentation

◆ compare_function_

◆ debug

◆ desired_imbalance_

◆ files_

◆ local_items_

◆ local_out_size_

◆ parent_stack_empty_

◆ res_sampler_

◆ samples_

◆ sort_algorithm_

◆ stats_enabled

◆ timer_execute_

◆ timer_preop_

◆ timer_sort_

◆ unsorted_file_

◆ unsorted_writer_

◆ use_background_thread_

template<typename ValueType, typename CompareFunction, typename SortAlgorithm, bool Stable = false>
class thrill::api::SortNode< ValueType, CompareFunction, SortAlgorithm, Stable >