Merge sorting consists of three phases. More...
#include <tpie/pipelining/merge_sorter.h>
Public Types | |
typedef std::shared_ptr < merge_sorter > | ptr |
typedef progress_types < UseProgress > | Progress |
Public Member Functions | |
merge_sorter (pred_t pred=pred_t(), store_t store=store_t()) | |
void | set_parameters (memory_size_type runLength, memory_size_type fanout) |
Enable setting run length and fanout manually (for testing purposes). More... | |
void | set_available_files (memory_size_type f) |
Calculate parameters from given amount of files. More... | |
void | set_available_files (memory_size_type f1, memory_size_type f2, memory_size_type f3) |
Calculate parameters from given amount of files. More... | |
void | set_available_memory (memory_size_type m) |
Calculate parameters from given memory amount. More... | |
void | set_available_memory (memory_size_type m1, memory_size_type m2, memory_size_type m3) |
Calculate parameters from given memory amount. More... | |
void | set_phase_1_files (memory_size_type f1) |
void | set_phase_2_files (memory_size_type f2) |
void | set_phase_3_files (memory_size_type f3) |
void | set_phase_1_memory (memory_size_type m1) |
void | set_phase_2_memory (memory_size_type m2) |
void | set_phase_3_memory (memory_size_type m3) |
void | begin () |
Initiate phase 1: Formation of input runs. More... | |
void | push (item_type &&item) |
Push item to merge sorter during phase 1. More... | |
void | push (const item_type &item) |
void | end () |
End phase 1. More... | |
bool | is_calc_free () const |
void | calc (typename Progress::base &pi) |
Perform phase 2: Performing all merges in the merge tree except the last one. More... | |
void | evacuate () |
void | evacuate_before_merging () |
void | evacuate_before_reporting () |
void | reinitialize_final_merger () |
bool | can_pull () |
In phase 3, return true if there are more items in the final merge phase. More... | |
item_type | pull () |
In phase 3, fetch next item in the final merge phase. More... | |
stream_size_type | item_count () |
memory_size_type | actual_memory_phase_3 () |
memory_size_type | evacuated_memory_usage () const |
void | set_items (stream_size_type n) |
Set upper bound on number of items pushed. More... | |
void | set_owner (tpie::pipelining::node *n) |
Static Public Member Functions | |
static memory_size_type | memory_usage_phase_1 (const sort_parameters ¶ms) |
static memory_size_type | minimum_memory_phase_1 () |
static memory_size_type | memory_usage_phase_2 (const sort_parameters ¶ms) |
static memory_size_type | minimum_memory_phase_2 () |
static memory_size_type | memory_usage_phase_3 (const sort_parameters ¶ms) |
static memory_size_type | minimum_memory_phase_3 () |
static memory_size_type | maximum_memory_phase_3 () |
Merge sorting consists of three phases.
If the number of elements received during phase 1 is less than the length of a single run, we are in "report internal" mode, meaning we do not write anything to disk. This causes phase 2 to be a no-op and phase 3 to be a simple array traversal.
Definition at line 150 of file merge_sorter.h.
|
inline |
Initiate phase 1: Formation of input runs.
Definition at line 288 of file merge_sorter.h.
References tpie::sort_parameters::fanout, tpie::log_debug(), tpie::array< T, Allocator >::resize(), tpie::sort_parameters::runLength, and tp_assert.
|
inline |
Perform phase 2: Performing all merges in the merge tree except the last one.
Definition at line 380 of file merge_sorter.h.
References tpie::progress_indicator_base::done(), tpie::progress_indicator_base::init(), tpie::progress_indicator_base::step(), and tp_assert.
|
inline |
In phase 3, return true if there are more items in the final merge phase.
Definition at line 585 of file merge_sorter.h.
References tp_assert.
Referenced by tpie::merge_sorter< T, UseProgress, pred_t, store_t >::pull().
|
inline |
End phase 1.
Definition at line 329 of file merge_sorter.h.
References tpie::get_memory_manager(), tpie::sort_parameters::internalReportThreshold, tpie::log_debug(), tpie::array< T, Allocator >::resize(), tpie::array< T, Allocator >::size(), tpie::array< T, Allocator >::swap(), and tp_assert.
|
inline |
In phase 3, fetch next item in the final merge phase.
Definition at line 597 of file merge_sorter.h.
References tpie::merge_sorter< T, UseProgress, pred_t, store_t >::can_pull(), tpie::bits::run_positions::close(), tpie::array< T, Allocator >::resize(), and tp_assert.
|
inline |
Push item to merge sorter during phase 1.
Definition at line 304 of file merge_sorter.h.
References tpie::sort_parameters::runLength, and tp_assert.
|
inline |
Calculate parameters from given amount of files.
f | Files available for phase 1, 2 and 3 |
Definition at line 206 of file merge_sorter.h.
References tpie::sort_parameters::filesPhase1, tpie::sort_parameters::filesPhase2, and tpie::sort_parameters::filesPhase3.
|
inline |
Calculate parameters from given amount of files.
f1 | Files available for phase 1 |
f2 | Files available for phase 2 |
f3 | Files available for phase 3 |
Definition at line 217 of file merge_sorter.h.
References tpie::sort_parameters::filesPhase1, tpie::sort_parameters::filesPhase2, and tpie::sort_parameters::filesPhase3.
|
inline |
Calculate parameters from given memory amount.
m | Memory available for phase 1, 2 and 3 |
Definition at line 228 of file merge_sorter.h.
References tpie::sort_parameters::memoryPhase1, tpie::sort_parameters::memoryPhase2, and tpie::sort_parameters::memoryPhase3.
|
inline |
Calculate parameters from given memory amount.
m1 | Memory available for phase 1 |
m2 | Memory available for phase 2 |
m3 | Memory available for phase 3 |
Definition at line 239 of file merge_sorter.h.
References tpie::sort_parameters::memoryPhase1, tpie::sort_parameters::memoryPhase2, and tpie::sort_parameters::memoryPhase3.
|
inline |
Set upper bound on number of items pushed.
If the number of items to push is less than the size of a single run, this method will decrease the run size to that. This may make it easier for the sorter to go into internal reporting mode.
Definition at line 814 of file merge_sorter.h.
References tpie::sort_parameters::internalReportThreshold, tpie::log_debug(), and tpie::sort_parameters::runLength.
|
inline |
Enable setting run length and fanout manually (for testing purposes).
Definition at line 192 of file merge_sorter.h.
References tpie::sort_parameters::fanout, tpie::sort_parameters::finalFanout, tpie::sort_parameters::internalReportThreshold, tpie::log_debug(), tpie::sort_parameters::runLength, and tp_assert.