Thrill  0.1
SortNode< ValueType, CompareFunction, SortAlgorithm, Stable > Class Template Referencefinal

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
ValueTypeType of DIA elements
CompareFunctionType of the compare function
SortAlgorithmType of the local sort function
StableWhether 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...
 
Contextcontext ()
 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::Managermem_manager ()
 Return the Context's memory manager. More...
 
DIABaseoperator= (const DIABase &)=delete
 non-copyable: delete assignment operator More...
 
DIABaseoperator= (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...
 
ReferenceCounteroperator= (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::Filefiles_
 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< SampleIndexPairsamples_
 Sample vector: pairs of (sample,local index) More...
 
common::ReservoirSamplingGrow< SampleIndexPairres_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< Childchildren_
 Callback functions from the child nodes. More...
 
- Protected Attributes inherited from DIABase
Contextcontext_
 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< DIABasePtrparents_
 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

Timer or FakeTimer.

Definition at line 75 of file sort.hpp.

◆ TranmissionStreamPtr

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

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

◆ 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

◆ LessSampleIndex()

◆ MainOp()

◆ OnPreOpFile()

◆ PartialMultiwayMerge()

◆ PreOp()

◆ PushData()

◆ 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()

◆ 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()

◆ StartPreOp()

◆ StopPreOp()

◆ TransmitItems()

◆ wanted_sample_size()

Member Data Documentation

◆ compare_function_

◆ 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_

◆ local_items_

◆ 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

◆ res_sampler_

◆ samples_

std::vector<SampleIndexPair> samples_
private

◆ sort_algorithm_

SortAlgorithm sort_algorithm_
private

◆ 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_

◆ unsorted_writer_

◆ 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: