STXXL
1.4-dev
|
Parallelized External Memory Priority Queue.
ValueType | Type of the contained objects (POD with no references to internal memory). |
CompareType | The comparator type used to determine whether one element is smaller than another element. |
DefaultMemSize | Maximum memory consumption by the queue. Can be overwritten by the constructor. Default = 1 GiB. |
MaxItems | Maximum number of elements the queue contains at one time. Default = 0 = unlimited. This is no hard limit and only used for optimization. Can be overwritten by the constructor. |
BlockSize | External block size. Default = STXXL_DEFAULT_BLOCK_SIZE(ValueType). |
AllocStrategy | Allocation strategy for the external memory. Default = STXXL_DEFAULT_ALLOC_STRATEGY. |
Definition at line 1867 of file parallel_priority_queue.h.
Classes | |
struct | empty_external_array_eraser |
Unary operator which returns true if the external array has run empty. More... | |
struct | empty_internal_array_eraser |
Unary operator which returns true if the internal array has run empty. More... | |
struct | external_min_comparator |
Compares the largest accessible value of two external arrays. More... | |
struct | hint_comparator |
Compares the largest value of the block hinted the latest of two external arrays. More... | |
struct | inv_compare_type |
Inverse comparison functor. More... | |
struct | ProcessorData |
A struct containing the local insertion heap and other information local to a processor. More... | |
struct | s_min_tree_comparator |
struct | stats_type |
Struct of all statistical counters and timers. Turn on/off statistics using the stats_counter and stats_timer typedefs. More... | |
Public Member Functions | |
void | flush_ia_ea_until_memory_free (internal_size_type mem_free) |
Free up memory by flushing internal arrays and combining external arrays until enough bytes are free. More... | |
void | hint_external_arrays () |
Hints EA blocks which will be needed soon. Hints at most m_num_prefetchers blocks globally. More... | |
void | merge_external_arrays () |
Merges all external arrays and all internal arrays into one external array. More... | |
void | print_stats () const |
Print statistics. More... | |
void | rebuild_hint_tree () |
Rebuild hint tree completely as the hint sequence may have changed, and re-hint the correct block sequence. More... | |
void | resize_read_pool () |
Automatically resize the read/prefetch buffer pool depending on number of external arrays. More... | |
void | update_external_min_tree (size_t ea_index) |
Updates the external min tree afer a remove() or a wait_next_blocks() call. More... | |
void | update_hint_tree (size_t ea_index) |
Updates the prefetch prediction tree afer a remove_items(), which frees up blocks. More... | |
Bulk Operations | |
void | bulk_push_begin (size_type bulk_size) |
Start a sequence of push operations. More... | |
void | bulk_push (const value_type &element, const unsigned_type p) |
Push an element inside a sequence of pushes. More... | |
void | bulk_push (const value_type &element) |
Push an element inside a bulk sequence of pushes. More... | |
void | bulk_push_end () |
Ends a sequence of push operations. More... | |
void | bulk_pop (std::vector< value_type > &out, size_t max_size) |
Extract up to max_size values at once. More... | |
bool | bulk_pop_limit (std::vector< value_type > &out, const value_type &limit, size_t max_size=std::numeric_limits< size_t >::max()) |
Extracts all elements which are greater or equal to a given limit. More... | |
Aggregation Operations | |
void | aggregate_push (const value_type &element) |
Aggregate pushes. More... | |
std::priority_queue compliant operations | |
void | push (const value_type &element, unsigned_type p=0) |
Insert new element. More... | |
const value_type & | top () |
Access the minimum element. More... | |
void | pop () |
Remove the minimum element. More... | |
Protected Member Functions | |
void | add_as_internal_array (std::vector< value_type > &values, unsigned_type used=0, unsigned_type level=0) |
Add new internal array, which requires that values are sorted! automatically decreases m_mem_left! also merges internal arrays if there are too many internal arrays on the same level. More... | |
void | advance_arrays (std::vector< iterator_pair_type > &sequences, std::vector< size_type > &sizes, size_t eas, size_t ias) |
size_t | calculate_merge_sequences (std::vector< size_type > &sizes, std::vector< iterator_pair_type > &sequences, bool reuse_previous_lower_bounds=false) |
Calculates the sequences vector needed by the multiway merger, considering inaccessible data from external arrays. The sizes vector stores the size of each sequence. More... | |
void | check_external_level (unsigned_type level, bool force_merge_all=false) |
Merges external arrays if there are too many external arrays on the same level. More... | |
void | cleanup_external_arrays () |
Clean up empty external arrays, free their memory and capacity. More... | |
void | cleanup_internal_arrays () |
Clean up empty internal arrays, free their memory and capacity. More... | |
void | convert_eb_into_ia (bool do_not_flush=false) |
Convert extract buffer into a new internal array. More... | |
void | flush_array_internal (std::vector< value_type > &values) |
Sorts the values from values and writes them into an internal array. More... | |
void | flush_insertion_heap (unsigned_type p) |
Flushes the insertions heap p into an internal array. More... | |
void | flush_insertion_heaps () |
Flushes all insertions heaps into an internal array. More... | |
void | flush_insertion_heaps_with_limit (const value_type &limit) |
Flushes all elements of the insertion heaps which are greater or equal to a given limit. More... | |
void | flush_internal_arrays () |
Flushes the internal arrays into an external array. More... | |
void | refill_extract_buffer (size_t minimum_size=0, size_t maximum_size=0) |
Refills the extract buffer from the external arrays. More... | |
void | wait_next_ea_blocks (unsigned_type ea_index) |
Requests more EM data from a given EA and updates the winner trees and hints accordingly. More... | |
Static Protected Member Functions | |
template<typename RandomAccessIterator , typename HeapCompareType > | |
static unsigned_type | push_heap (RandomAccessIterator first, RandomAccessIterator last, HeapCompareType comp) |
SiftUp a new element from the last position in the heap, reestablishing the heap invariant. More... | |
Protected Attributes | |
unsigned_type | m_bulk_first_delayed_external_array |
First index in m_external_arrays that was not re-hinted during a bulk_push sequence. More... | |
size_type | m_extract_buffer_index |
Index of the currently smallest element in the extract buffer. More... | |
bool | m_in_bulk_push |
Flag if inside a bulk_push sequence. More... | |
bool | m_is_very_large_bulk |
If the bulk currently being inserted is very large, this boolean is set and bulk_push just accumulate the elements for eventual sorting. More... | |
stats_type | m_stats |
Number of elements currently in the data structures | |
size_type | m_heaps_size |
Number of elements int the insertion heaps. More... | |
size_type | m_extract_buffer_size |
Number of elements in the extract buffer. More... | |
size_type | m_internal_size |
Number of elements in the internal arrays. More... | |
size_type | m_external_size |
Number of elements in the external arrays. More... | |
Static Protected Attributes | |
Compile-Time Parameters | |
static const bool | c_merge_sorted_heaps = true |
Merge sorted heaps when flushing into an internal array. Pro: Reduces the risk of a large winner tree Con: Flush insertion heaps becomes slower. More... | |
static const unsigned | c_num_write_buffer_blocks = 14 |
Default number of write buffer block for a new external array being filled. More... | |
static const unsigned | c_num_reserved_external_arrays = 10 |
Defines for how much external arrays memory should be reserved in the constructor. More... | |
static const size_type | c_default_single_heap_ram = 1L * 1024L * 1024L |
Size of a single insertion heap in Byte, if not defined otherwise in the constructor. Default: 1 MiB. More... | |
static const double | c_default_extract_buffer_ram_part = 0.05 |
Default limit of the extract buffer ram consumption as share of total ram. More... | |
static const bool | c_limit_extract_buffer = true |
Limit the size of the extract buffer to an absolute value. More... | |
static const unsigned | c_single_insert_limit = 100 |
For bulks of size up to c_single_insert_limit sequential single insert is faster than bulk_push. More... | |
Parameters and Sizes for Memory Allocation Policy | |
const long | m_num_insertion_heaps |
Number of insertion heaps. Usually equal to the number of CPUs. More... | |
const unsigned | m_insertion_heap_capacity |
Capacity of one inserion heap. More... | |
const size_type | m_mem_total |
Total amount of internal memory. More... | |
size_type | m_extract_buffer_limit |
Maximum size of extract buffer in number of elements Only relevant if c_limit_extract_buffer==true. More... | |
const size_type | m_mem_for_heaps |
Size of all insertion heaps together in bytes. More... | |
const float | m_num_read_blocks_per_ea |
Number of read/prefetch blocks per external array. More... | |
unsigned_type | m_num_read_blocks |
Total number of read/prefetch buffer blocks. More... | |
unsigned_type | m_num_hinted_blocks |
number of currently hinted prefetch blocks More... | |
unsigned_type | m_num_used_read_blocks |
number of currently loaded blocks More... | |
size_type | m_mem_left |
Free memory in bytes. More... | |
size_type | insertion_heap_int_memory () const |
Return size of insertion heap reservation in bytes. More... | |
Data Holding Structures | |
typedef std::vector < ProcessorData * > | proc_vector_type |
proc_vector_type | m_proc |
Array of processor local data structures, including the insertion heaps. More... | |
pool_type | m_pool |
Prefetch and write buffer pool for external arrays (has to be in front of m_external_arrays) More... | |
std::vector< value_type > | m_extract_buffer |
The extract buffer where external (and internal) arrays are merged into for extracting. More... | |
internal_arrays_type | m_internal_arrays |
The sorted arrays in internal memory. More... | |
external_arrays_type | m_external_arrays |
The sorted arrays in external memory. More... | |
std::vector< value_type > | m_aggregated_pushes |
The aggregated pushes. They cannot be extracted yet. More... | |
unsigned_type | m_internal_levels [c_max_internal_levels] |
The number of internal arrays on each level, we use plain array. More... | |
unsigned_type | m_external_levels [c_max_external_levels] |
The number of external arrays on each level, we use plain array. More... | |
minima_type | m_minima |
The winner tree containing the smallest values of all sources where the globally smallest element could come from. More... | |
struct stxxl::parallel_priority_queue::external_min_comparator | m_external_min_comparator |
winner_tree < external_min_comparator > | m_external_min_tree |
Tracks the largest accessible values of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used in calculate_merge_sequences. More... | |
struct stxxl::parallel_priority_queue::hint_comparator | m_hint_comparator |
winner_tree< hint_comparator > | m_hint_tree |
Tracks the largest values of the block hinted the latest of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used for prefetch hints. More... | |
random_number32_r | m_rng |
Random number generator for randomly selecting a heap in sequential push() More... | |
static const unsigned_type | c_max_internal_levels = 8 |
The maximum number of internal array levels. More... | |
static const unsigned_type | c_max_external_levels = 8 |
The maximum number of external array levels. More... | |
Initialization | |
void | check_invariants () const |
Assert many invariants of the data structures. More... | |
parallel_priority_queue (const compare_type &compare=compare_type(), size_type total_ram=DefaultMemSize, float num_read_blocks_per_ea=1.5f, unsigned_type num_write_buffer_blocks=c_num_write_buffer_blocks, unsigned_type num_insertion_heaps=0, size_type single_heap_ram=c_default_single_heap_ram, size_type extract_buffer_ram=0) | |
Constructor. More... | |
~parallel_priority_queue () | |
Destructor. More... | |
Properties | |
bool | extract_buffer_empty () const |
Returns if the extract buffer is empty. More... | |
size_type | size () const |
The number of elements in the queue. More... | |
bool | empty () const |
Returns if the queue is empty. More... | |
size_type | memory_consumption () const |
The memory consumption in Bytes. More... | |
Bulk-Limit Operations | |
value_type | m_limit_element |
current limit element More... | |
bool | m_limit_extract |
flag if inside a bulk limit extract session More... | |
bool | m_limit_has_full_range |
flag if the extract buffer contains the full limit range More... | |
void | limit_begin (const value_type &limit, size_type bulk_size) |
Begin bulk-limit extraction session with limit element. More... | |
void | limit_push (const value_type &element, const unsigned_type p=0) |
Push new item >= bulk-limit element into insertion heap p. More... | |
const value_type & | limit_top () |
Access the minimum element, which can only be in the extract buffer. More... | |
void | limit_pop () |
Remove the minimum element, only works correctly while elements < L. More... | |
void | limit_end () |
Finish bulk-limit extraction session. More... | |
Additional Inherited Members | |
Private Member Functions inherited from stxxl::noncopyable | |
noncopyable () | |
typedef AllocStrategy stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::alloc_strategy |
Definition at line 1875 of file parallel_priority_queue.h.
typedef std::vector<BID<block_size> > stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bid_vector |
Definition at line 1880 of file parallel_priority_queue.h.
typedef bid_vector stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bids_container_type |
Definition at line 1881 of file parallel_priority_queue.h.
typedef typed_block<block_size, value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::block_type |
Definition at line 1879 of file parallel_priority_queue.h.
typedef CompareType stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::compare_type |
Definition at line 1874 of file parallel_priority_queue.h.
typedef ppq_local::external_array<value_type, block_size, AllocStrategy> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::external_array_type |
Definition at line 1884 of file parallel_priority_queue.h.
typedef external_array_type::writer_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::external_array_writer_type |
Definition at line 1885 of file parallel_priority_queue.h.
|
protected |
type of external arrays vector
Definition at line 1905 of file parallel_priority_queue.h.
|
protected |
type of insertion heap itself
Definition at line 1900 of file parallel_priority_queue.h.
typedef ppq_local::internal_array<value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::internal_array_type |
Definition at line 1883 of file parallel_priority_queue.h.
|
protected |
type of internal arrays vector
Definition at line 1903 of file parallel_priority_queue.h.
typedef internal_array_type::iterator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::iterator |
Definition at line 1887 of file parallel_priority_queue.h.
typedef std::pair<iterator, iterator> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::iterator_pair_type |
Definition at line 1888 of file parallel_priority_queue.h.
|
protected |
type of minima tree combining the structures
Definition at line 1909 of file parallel_priority_queue.h.
typedef read_write_pool<block_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::pool_type |
Definition at line 1882 of file parallel_priority_queue.h.
|
protected |
Definition at line 2079 of file parallel_priority_queue.h.
typedef uint64 stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::size_type |
Definition at line 1877 of file parallel_priority_queue.h.
|
protected |
Defines if statistics are gathered: dummy_custom_stats_counter or custom_stats_counter.
Definition at line 1938 of file parallel_priority_queue.h.
|
protected |
Defines if statistics are gathered: fake_timer or timer.
Definition at line 1941 of file parallel_priority_queue.h.
typedef std::vector<value_type>::iterator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::value_iterator |
Definition at line 1886 of file parallel_priority_queue.h.
typedef ValueType stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::value_type |
Definition at line 1873 of file parallel_priority_queue.h.
|
inline |
Constructor.
compare | Comparator for priority queue, which is a Max-PQ. |
total_ram | Maximum RAM usage. 0 = Default = Use the template value DefaultMemSize. |
num_read_blocks_per_ea | Number of read blocks per external array. Default = 1.5f |
num_write_buffer_blocks | Number of write buffer blocks for a new external array being filled. 0 = Default = c_num_write_buffer_blocks |
num_insertion_heaps | Number of insertion heaps. 0 = Default = Determine by omp_get_max_threads(). |
single_heap_ram | Memory usage for a single insertion heap. Default = c_single_heap_ram. |
extract_buffer_ram | Memory usage for the extract buffer. Only relevant if c_limit_extract_buffer==true. 0 = Default = total_ram * c_default_extract_buffer_ram_part. |
Definition at line 2325 of file parallel_priority_queue.h.
References stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::ProcessorData::insertion_heap, and STXXL_ERRMSG.
|
inline |
Destructor.
Definition at line 2447 of file parallel_priority_queue.h.
|
inlineprotected |
Add new internal array, which requires that values are sorted! automatically decreases m_mem_left! also merges internal arrays if there are too many internal arrays on the same level.
Definition at line 4403 of file parallel_priority_queue.h.
References stxxl::ppq_local::internal_array< ValueType >::int_memory(), stxxl::potentially_parallel::multiway_merge(), STXXL_ASSERT, STXXL_CHECK, and STXXL_DEBUG.
|
inlineprotected |
Definition at line 3868 of file parallel_priority_queue.h.
|
inline |
Aggregate pushes.
Use flush_aggregated_pushes() to finally push them. extract_min is allowed is allowed in between the aggregation of pushes if you can assure, that the extracted value is smaller than all of the aggregated values.
element | The element to push. |
Definition at line 2984 of file parallel_priority_queue.h.
|
inline |
Extract up to max_size values at once.
Definition at line 2812 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inline |
Extracts all elements which are greater or equal to a given limit.
out | result vector |
limit | limit value |
max_size | maximum number of items to extract |
Definition at line 2842 of file parallel_priority_queue.h.
References stxxl::potentially_parallel::multiway_merge(), STXXL_ASSERT, and STXXL_DEBUG.
|
inline |
Push an element inside a sequence of pushes.
Run bulk_push_begin() before using this method.
element | The element to push. |
p | The id of the insertion heap to use (usually the thread id). |
Definition at line 2634 of file parallel_priority_queue.h.
References UNLIKELY.
|
inline |
Push an element inside a bulk sequence of pushes.
Run bulk_push_begin() before using this method. This function uses the insertion heap id = omp_get_thread_num().
element | The element to push. |
Definition at line 2708 of file parallel_priority_queue.h.
|
inline |
Start a sequence of push operations.
bulk_size | Exact number of elements to push before the next pop. |
Definition at line 2599 of file parallel_priority_queue.h.
|
inline |
Ends a sequence of push operations.
Run bulk_push_begin() and some bulk_push() before this.
Definition at line 2722 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inlineprotected |
Calculates the sequences vector needed by the multiway merger, considering inaccessible data from external arrays. The sizes vector stores the size of each sequence.
reuse_previous_lower_bounds | Reuse upper bounds from previous runs. sequences[i].second must be valid upper bound iterator from a previous run! |
Definition at line 3598 of file parallel_priority_queue.h.
References STXXL_ASSERT, and STXXL_DEBUG.
|
inlineprotected |
Merges external arrays if there are too many external arrays on the same level.
Definition at line 4165 of file parallel_priority_queue.h.
References stxxl::winner_tree< Comparator >::activate_without_replay(), stxxl::ppq_local::external_array_writer< ExternalArrayType >::begin(), stxxl::winner_tree< Comparator >::deactivate_player(), stxxl::winner_tree< Comparator >::deactivate_without_replay(), stxxl::potentially_parallel::multiway_merge(), stxxl::winner_tree< Comparator >::rebuild(), stxxl::winner_tree< Comparator >::replay_on_change(), STXXL_ASSERT, STXXL_DEBUG, STXXL_DEBUG0, and stxxl::winner_tree< Comparator >::top().
|
inlineprotected |
Assert many invariants of the data structures.
Definition at line 2459 of file parallel_priority_queue.h.
References stxxl::is_heap(), STXXL_CHECK, and STXXL_CHECK_EQUAL.
|
inlineprotected |
Clean up empty external arrays, free their memory and capacity.
Definition at line 2207 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inlineprotected |
Clean up empty internal arrays, free their memory and capacity.
Definition at line 2184 of file parallel_priority_queue.h.
References STXXL_DEBUG0, and stxxl::swap_remove_if().
|
inlineprotected |
Convert extract buffer into a new internal array.
Definition at line 3716 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inline |
Returns if the queue is empty.
Definition at line 2570 of file parallel_priority_queue.h.
|
inlineprotected |
Returns if the extract buffer is empty.
Definition at line 2584 of file parallel_priority_queue.h.
|
inlineprotected |
Sorts the values from values and writes them into an internal array.
Don't use the value vector afterwards!
values | the vector to sort and store |
Definition at line 4498 of file parallel_priority_queue.h.
References stxxl::sort().
|
inline |
Free up memory by flushing internal arrays and combining external arrays until enough bytes are free.
Definition at line 3377 of file parallel_priority_queue.h.
|
inlineprotected |
Flushes the insertions heap p into an internal array.
Definition at line 3914 of file parallel_priority_queue.h.
References stxxl::sort(), and STXXL_DEBUG0.
|
inlineprotected |
Flushes all insertions heaps into an internal array.
Definition at line 3965 of file parallel_priority_queue.h.
References stxxl::potentially_parallel::multiway_merge(), and stxxl::sort().
|
inlineprotected |
Flushes all elements of the insertion heaps which are greater or equal to a given limit.
limit | limit value |
Definition at line 3279 of file parallel_priority_queue.h.
References stxxl::sort(), and STXXL_DEBUG.
|
inlineprotected |
Flushes the internal arrays into an external array.
Definition at line 4048 of file parallel_priority_queue.h.
References stxxl::ppq_local::external_array_writer< ExternalArrayType >::begin(), stxxl::potentially_parallel::multiway_merge(), and STXXL_DEBUG.
|
inline |
Hints EA blocks which will be needed soon. Hints at most m_num_prefetchers blocks globally.
Definition at line 3534 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inlineprotected |
Return size of insertion heap reservation in bytes.
Definition at line 2003 of file parallel_priority_queue.h.
|
inline |
Begin bulk-limit extraction session with limit element.
Definition at line 3175 of file parallel_priority_queue.h.
|
inline |
Finish bulk-limit extraction session.
Definition at line 3264 of file parallel_priority_queue.h.
|
inline |
Remove the minimum element, only works correctly while elements < L.
Definition at line 3236 of file parallel_priority_queue.h.
|
inline |
Push new item >= bulk-limit element into insertion heap p.
Definition at line 3196 of file parallel_priority_queue.h.
|
inline |
Access the minimum element, which can only be in the extract buffer.
Definition at line 3205 of file parallel_priority_queue.h.
|
inline |
The memory consumption in Bytes.
Definition at line 2576 of file parallel_priority_queue.h.
|
inline |
Merges all external arrays and all internal arrays into one external array.
Public for benchmark purposes.
Definition at line 3357 of file parallel_priority_queue.h.
References STXXL_DEBUG, and STXXL_ERRMSG.
|
inline |
Remove the minimum element.
Definition at line 3084 of file parallel_priority_queue.h.
References min(), and STXXL_ERRMSG.
|
inline |
Print statistics.
Definition at line 3563 of file parallel_priority_queue.h.
References STXXL_MEMDUMP, STXXL_MSG, and STXXL_VARDUMP.
|
inline |
Insert new element.
element | the element to insert. |
p | number of insertion heap to insert item into |
Definition at line 3025 of file parallel_priority_queue.h.
|
inlinestaticprotected |
SiftUp a new element from the last position in the heap, reestablishing the heap invariant.
This is identical to std::push_heap, except that it returns the last element modified by siftUp. Thus we can identify if the minimum may have changed.
Definition at line 2275 of file parallel_priority_queue.h.
References STXXL_MOVE.
|
inline |
Rebuild hint tree completely as the hint sequence may have changed, and re-hint the correct block sequence.
Definition at line 3445 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inlineprotected |
Refills the extract buffer from the external arrays.
minimum_size | requested minimum size of the resulting extract buffer. Prints a warning if there is not enough data to reach this size. |
maximum_size | maximum size of the extract buffer. Using m_extract_buffer_limit if set to 0. |
Definition at line 3751 of file parallel_priority_queue.h.
References stxxl::potentially_parallel::multiway_merge(), STXXL_DEBUG, and STXXL_MSG.
|
inline |
Automatically resize the read/prefetch buffer pool depending on number of external arrays.
Definition at line 3393 of file parallel_priority_queue.h.
References STXXL_ASSERT, STXXL_DEBUG, and STXXL_ERRMSG.
|
inline |
The number of elements in the queue.
Definition at line 2564 of file parallel_priority_queue.h.
|
inline |
Access the minimum element.
Definition at line 3046 of file parallel_priority_queue.h.
References min(), STXXL_DEBUG, and STXXL_ERRMSG.
|
inline |
Updates the external min tree afer a remove() or a wait_next_blocks() call.
ea_index | index of the external array in question |
Definition at line 3522 of file parallel_priority_queue.h.
|
inline |
Updates the prefetch prediction tree afer a remove_items(), which frees up blocks.
ea_index | index of the external array in question |
Definition at line 3507 of file parallel_priority_queue.h.
|
inlineprotected |
Requests more EM data from a given EA and updates the winner trees and hints accordingly.
Definition at line 3856 of file parallel_priority_queue.h.
|
static |
Definition at line 1876 of file parallel_priority_queue.h.
|
staticprotected |
Default limit of the extract buffer ram consumption as share of total ram.
Definition at line 1970 of file parallel_priority_queue.h.
|
staticprotected |
Size of a single insertion heap in Byte, if not defined otherwise in the constructor. Default: 1 MiB.
Definition at line 1963 of file parallel_priority_queue.h.
|
staticprotected |
Limit the size of the extract buffer to an absolute value.
The actual size can be set using the extract_buffer_ram parameter of the constructor. If this parameter is not set, the value is calculated by (total_ram*c_default_extract_buffer_ram_part)
If c_limit_extract_buffer==false, the memory consumption of the extract buffer is only limited by the number of external and internal arrays. This is considered in memory management using the ram_per_external_array and ram_per_internal_array values. Attention: Each internal array reserves space for the extract buffer in the size of all heaps together.
Definition at line 1986 of file parallel_priority_queue.h.
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_external_level_size |
currently global public tuning parameter:
Definition at line 1896 of file parallel_priority_queue.h.
|
staticprotected |
The maximum number of external array levels.
Definition at line 2108 of file parallel_priority_queue.h.
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_internal_level_size |
currently global public tuning parameter:
Definition at line 1893 of file parallel_priority_queue.h.
|
staticprotected |
The maximum number of internal array levels.
Definition at line 2102 of file parallel_priority_queue.h.
|
staticprotected |
Merge sorted heaps when flushing into an internal array. Pro: Reduces the risk of a large winner tree Con: Flush insertion heaps becomes slower.
Definition at line 1951 of file parallel_priority_queue.h.
|
staticprotected |
Defines for how much external arrays memory should be reserved in the constructor.
Definition at line 1959 of file parallel_priority_queue.h.
|
staticprotected |
Default number of write buffer block for a new external array being filled.
Definition at line 1955 of file parallel_priority_queue.h.
|
staticprotected |
For bulks of size up to c_single_insert_limit sequential single insert is faster than bulk_push.
Definition at line 1990 of file parallel_priority_queue.h.
|
static |
Definition at line 1890 of file parallel_priority_queue.h.
|
protected |
The aggregated pushes. They cannot be extracted yet.
Definition at line 2099 of file parallel_priority_queue.h.
|
protected |
First index in m_external_arrays that was not re-hinted during a bulk_push sequence.
Definition at line 2042 of file parallel_priority_queue.h.
|
protected |
<-Comparator for value_type
Definition at line 1931 of file parallel_priority_queue.h.
|
protected |
The sorted arrays in external memory.
Definition at line 2096 of file parallel_priority_queue.h.
|
protected |
The number of external arrays on each level, we use plain array.
Definition at line 2111 of file parallel_priority_queue.h.
|
protected |
|
protected |
Tracks the largest accessible values of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used in calculate_merge_sequences.
Definition at line 2136 of file parallel_priority_queue.h.
|
protected |
Number of elements in the external arrays.
Definition at line 2060 of file parallel_priority_queue.h.
|
protected |
The extract buffer where external (and internal) arrays are merged into for extracting.
Definition at line 2090 of file parallel_priority_queue.h.
|
protected |
Index of the currently smallest element in the extract buffer.
Definition at line 2045 of file parallel_priority_queue.h.
|
protected |
Maximum size of extract buffer in number of elements Only relevant if c_limit_extract_buffer==true.
Definition at line 2013 of file parallel_priority_queue.h.
|
protected |
Number of elements in the extract buffer.
Definition at line 2054 of file parallel_priority_queue.h.
|
protected |
Number of elements int the insertion heaps.
Definition at line 2051 of file parallel_priority_queue.h.
|
protected |
|
protected |
Tracks the largest values of the block hinted the latest of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used for prefetch hints.
Definition at line 2159 of file parallel_priority_queue.h.
|
protected |
Flag if inside a bulk_push sequence.
Definition at line 2034 of file parallel_priority_queue.h.
|
protected |
Capacity of one inserion heap.
Definition at line 2000 of file parallel_priority_queue.h.
|
protected |
The sorted arrays in internal memory.
Definition at line 2093 of file parallel_priority_queue.h.
|
protected |
The number of internal arrays on each level, we use plain array.
Definition at line 2105 of file parallel_priority_queue.h.
|
protected |
Number of elements in the internal arrays.
Definition at line 2057 of file parallel_priority_queue.h.
|
protected |
>-Comparator for value_type
Definition at line 1934 of file parallel_priority_queue.h.
|
protected |
If the bulk currently being inserted is very large, this boolean is set and bulk_push just accumulate the elements for eventual sorting.
Definition at line 2038 of file parallel_priority_queue.h.
|
protected |
current limit element
Definition at line 3165 of file parallel_priority_queue.h.
|
protected |
flag if inside a bulk limit extract session
Definition at line 3168 of file parallel_priority_queue.h.
|
protected |
flag if the extract buffer contains the full limit range
Definition at line 3171 of file parallel_priority_queue.h.
|
protected |
Size of all insertion heaps together in bytes.
Definition at line 2016 of file parallel_priority_queue.h.
|
protected |
Free memory in bytes.
Definition at line 2029 of file parallel_priority_queue.h.
|
protected |
Total amount of internal memory.
Definition at line 2009 of file parallel_priority_queue.h.
|
protected |
The winner tree containing the smallest values of all sources where the globally smallest element could come from.
Definition at line 2115 of file parallel_priority_queue.h.
|
protected |
number of currently hinted prefetch blocks
Definition at line 2024 of file parallel_priority_queue.h.
|
protected |
Number of insertion heaps. Usually equal to the number of CPUs.
Definition at line 1997 of file parallel_priority_queue.h.
|
protected |
Total number of read/prefetch buffer blocks.
Definition at line 2022 of file parallel_priority_queue.h.
|
protected |
Number of read/prefetch blocks per external array.
Definition at line 2019 of file parallel_priority_queue.h.
|
protected |
number of currently loaded blocks
Definition at line 2026 of file parallel_priority_queue.h.
|
protected |
Prefetch and write buffer pool for external arrays (has to be in front of m_external_arrays)
Definition at line 2086 of file parallel_priority_queue.h.
|
protected |
Array of processor local data structures, including the insertion heaps.
Definition at line 2082 of file parallel_priority_queue.h.
|
protected |
Random number generator for randomly selecting a heap in sequential push()
Definition at line 2163 of file parallel_priority_queue.h.
|
protected |
Definition at line 4658 of file parallel_priority_queue.h.