|
STXXL
1.4-dev
|
|
STXXL
1.4-dev
|
External array stores a sorted sequence of values on the hard disk and allows access to the first block (containing the smallest values).
The class uses buffering and prefetching in order to improve the performance.
| ValueType | Type of the contained objects (POD with no references to internal memory). |
| 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 442 of file parallel_priority_queue.h.
Inheritance diagram for stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >: Collaboration diagram for stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >:Public Types | |
| enum | { block_size = BlockSize, block_items = BlockSize / sizeof(value_type) } |
| The number of elements fitting into one block. More... | |
| typedef bid_vector::iterator | bid_iterator |
| typedef std::vector< BID < BlockSize > > | bid_vector |
| typedef iterator::block_pointers_type | block_pointers_type |
| typedef typed_block< BlockSize, value_type > | block_type |
| typedef std::vector< block_type * > | block_vector |
| typedef ppq_iterator< value_type > | iterator |
| typedef std::vector< value_type > | minima_vector |
| typedef read_write_pool < block_type > | pool_type |
| typedef std::vector< request_ptr > | request_vector |
| typedef external_array < value_type, BlockSize, AllocStrategy > | self_type |
| typedef ValueType | value_type |
| typedef external_array_writer < self_type > | writer_type |
Public Member Functions | |
| external_array (external_size_type size, pool_type *pool, unsigned_type level=0) | |
| Constructs an external array. More... | |
| external_array () | |
| Default constructor. Don't use this directy. Needed for regrowing in surrounding vector. More... | |
| ~external_array () | |
| Destructor. More... | |
| iterator | begin () const |
| Returns a random-access iterator to the begin of the data in internal memory. More... | |
| size_t | buffer_size () const |
| Returns the number elements available in internal memory. More... | |
| size_t | capacity () const |
| Returns the capacity in items. More... | |
| bool | empty () const |
| Returns true if the array is empty. More... | |
| iterator | end () const |
| Returns a random-access iterator 1 behind the end of the data in internal memory. More... | |
| unsigned_type | get_current_block_index () const |
| Returns the block in which m_index is located. More... | |
| unsigned_type | get_end_block_index () const |
| Returns the block beyond the block in which *(m_end_index-1) is located. More... | |
| const value_type & | get_min () |
| Returns the smallest element in the array. More... | |
| const value_type & | get_next_block_min () const |
| Returns the smallest element of the first block NOT in internal memory (or at least requested to be in internal memory) More... | |
| bool | has_em_data () const |
| Returns if there is data in EM, that's not randomly accessible. More... | |
| size_t | int_memory () const |
| Return the amount of internal memory used by the EA. More... | |
| unsigned_type | level () const |
| Returns the level (group number) of the array. More... | |
| size_t | num_blocks () const |
| Return the number of blocks. More... | |
| value_type & | operator[] (size_t i) const |
| Random access operator for data in internal memory You should call wait() once after fetching data from EM. More... | |
| size_t | size () const |
| Returns the current size in items. More... | |
| void | swap (external_array &o) |
| Swap external_array with another one. More... | |
| bool | valid () const |
| Returns if the data requested to be in internal memory is completely fetched. True if wait() has been called before. More... | |
Prefetching Hints | |
| void | hint_next_block () |
| Prefetch the next unhinted block, requires one free read block from the global pool. More... | |
| bool | has_unhinted_em_data () const |
| Returns if there is data in EM, that's not already hinted to the prefetcher. More... | |
| const value_type & | get_next_hintable_min () const |
| Returns the smallest element of the next hint candidate (the block after the last hinted one). More... | |
| size_t | num_hinted_blocks () const |
| Returns the number of hinted blocks. More... | |
| void | rebuild_hints_prepare () |
| This method prepares rebuilding the hints (this is done after creating a new EA in order to always have globally the n blocks hinted which will be fetched first). Resets m_unhinted_block to the first block not in RAM. Thereafter prehint_next_block() is used to advance this index. finish_rebuilding_hints() should be called after placing all hints in order to clean up the prefetch pool. More... | |
| void | rebuild_hints_prehint_next_block () |
| Advance m_unhinted_block index without actually prefetching. More... | |
| void | rebuild_hints_cancel () |
| Cancel hints which aren't needed anymore from the prefetcher and fixes it's size. prepare_rebuilding_hints() must be called before! More... | |
| void | rebuild_hints_finish () |
| Perform real-hinting of pre-hinted blocks, since now canceled blocks are available. More... | |
Waiting and Removal | |
| unsigned_type | wait_next_blocks () |
| Waits until the next prefetched block is read into RAM, then polls for any further blocks that are done as well. Returns how many blocks were successfully read. More... | |
| unsigned_type | wait_all_hinted_blocks () |
| Waits until all hinted blocks are read into RAM. Returns how many blocks were successfully read. More... | |
| size_t | num_used_blocks () const |
| Returns the number of blocks loaded in RAM. More... | |
| unsigned_type | remove_items (size_t n) |
| Removes the first n elements from the array. Returns the number of blocks released into the block pool. More... | |
Static Public Member Functions | |
| static size_t | int_memory (size_t capacity) |
| Returns memory usage of EA with given capacity, excluding blocks loaded in RAM. Blocks belong to prefetch pool. More... | |
| static void | prepare_write_pool (pool_type &pool, unsigned_type num_threads) |
| prepare the pool for writing external arrays with given number of threads More... | |
Static Public Attributes | |
| static const bool | debug = false |
Protected Member Functions | |
| bool | block_valid (size_t block_index) const |
| Returns if the block with the given index is completely fetched. More... | |
| void | finish_write () |
| finish the writing phase after multiway_merge() filled the vector. this method is called by the external_array_writer's destructor.. More... | |
| size_t | last_block_items () |
| void | prepare_write (unsigned_type num_threads) |
| prepare the external_array for writing using multiway_merge() with num_threads. this method is called by the external_array_writer's constructor. More... | |
| void | read_block (size_t block_index) |
| Called by the external_array_writer to read a block from disk into m_blocks[]. If the block is marked as uninitialized, then no read is performed. This is the usual case, and in theory, no block ever has be re-read from disk, since all can be written fully. However, we do support re-reading blocks for debugging purposes inside multiway_merge(), in a full performance build re-reading never occurs. More... | |
| void | update_block_pointers (size_t block_index) |
| Updates the m_block_pointers vector. Should be called after any steal() or read() operation. This is necessary for the iterators to work properly. More... | |
| void | write_block (size_t block_index) |
| Called by the external_array_writer to write a block from m_blocks[] to disk. Prior to writing and releasing the memory, extra information is preserved. More... | |
Protected Attributes | |
| bid_vector | m_bids |
| The IDs of each block in external memory. More... | |
| block_pointers_type | m_block_pointers |
| Begin and end pointers for each block, used for merging with ppq_iterator. More... | |
| block_vector | m_blocks |
| A vector of size m_num_blocks with block_type pointers, some of them will be filled while writing, but most are NULL. More... | |
| external_size_type | m_capacity |
| The total size of the external array in items. Cannot be changed after construction. More... | |
| external_size_type | m_end_index |
| The index behind the last element that is located in RAM (or is at least requested to be so) More... | |
| external_size_type | m_index |
| The read position in the array. More... | |
| unsigned_type | m_level |
| Level of external array (Sander's PQ: group number) More... | |
| minima_vector | m_minima |
| stores the minimum value of each block More... | |
| unsigned_type | m_num_blocks |
| Number of blocks, again: calculated at construction time. More... | |
| unsigned_type | m_old_unhinted_block |
| The first unhinted block index as it was before the prepare_rebuilding_hints() call. Used for removal of hints which aren't needed anymore. More... | |
| pool_type * | m_pool |
| Common prefetch and write buffer pool. More... | |
| request_vector | m_requests |
| The read request pointers are used to wait until the block has been completely fetched. More... | |
| external_size_type | m_size |
| The total number of elements minus the number of extracted values. More... | |
| unsigned_type | m_unhinted_block |
| The first unhinted block index. More... | |
| bool | m_write_phase |
| Is array in write phase? True = write phase, false = read phase. More... | |
Friends | |
| void | swap (external_array &a, external_array &b) |
| Swap external_array with another one. More... | |
Additional Inherited Members | |
| Private Member Functions inherited from stxxl::noncopyable | |
| noncopyable () | |
| typedef bid_vector::iterator stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::bid_iterator |
Definition at line 452 of file parallel_priority_queue.h.
| typedef std::vector<BID<BlockSize> > stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::bid_vector |
Definition at line 451 of file parallel_priority_queue.h.
| typedef iterator::block_pointers_type stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::block_pointers_type |
Definition at line 456 of file parallel_priority_queue.h.
| typedef typed_block<BlockSize, value_type> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::block_type |
Definition at line 449 of file parallel_priority_queue.h.
| typedef std::vector<block_type*> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::block_vector |
Definition at line 453 of file parallel_priority_queue.h.
| typedef ppq_iterator<value_type> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::iterator |
Definition at line 446 of file parallel_priority_queue.h.
| typedef std::vector<value_type> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::minima_vector |
Definition at line 455 of file parallel_priority_queue.h.
| typedef read_write_pool<block_type> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::pool_type |
Definition at line 450 of file parallel_priority_queue.h.
| typedef std::vector<request_ptr> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::request_vector |
Definition at line 454 of file parallel_priority_queue.h.
| typedef external_array<value_type, BlockSize, AllocStrategy> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::self_type |
Definition at line 448 of file parallel_priority_queue.h.
| typedef ValueType stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::value_type |
Definition at line 445 of file parallel_priority_queue.h.
| typedef external_array_writer<self_type> stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::writer_type |
Definition at line 457 of file parallel_priority_queue.h.
| anonymous enum |
The number of elements fitting into one block.
| Enumerator | |
|---|---|
| block_size | |
| block_items | |
Definition at line 460 of file parallel_priority_queue.h.
|
inline |
Constructs an external array.
| size | The total number of elements. Cannot be changed after construction. |
| num_prefetch_blocks | Number of blocks to prefetch from hard disk |
| num_write_buffer_blocks | Size of the write buffer in number of blocks |
Definition at line 535 of file parallel_priority_queue.h.
References stxxl::block_manager::new_blocks().
|
inline |
Default constructor. Don't use this directy. Needed for regrowing in surrounding vector.
Definition at line 567 of file parallel_priority_queue.h.
|
inline |
Destructor.
Definition at line 628 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::add_prefetch(), and STXXL_DEBUG.
|
inline |
Returns a random-access iterator to the begin of the data in internal memory.
Definition at line 743 of file parallel_priority_queue.h.
|
inlineprotected |
Returns if the block with the given index is completely fetched.
Definition at line 1164 of file parallel_priority_queue.h.
|
inline |
Returns the number elements available in internal memory.
Definition at line 718 of file parallel_priority_queue.h.
|
inline |
Returns the capacity in items.
Definition at line 668 of file parallel_priority_queue.h.
|
inline |
Returns true if the array is empty.
Definition at line 680 of file parallel_priority_queue.h.
|
inline |
Returns a random-access iterator 1 behind the end of the data in internal memory.
Definition at line 751 of file parallel_priority_queue.h.
|
inlineprotected |
finish the writing phase after multiway_merge() filled the vector. this method is called by the external_array_writer's destructor..
Definition at line 838 of file parallel_priority_queue.h.
|
inline |
Returns the block in which m_index is located.
Definition at line 736 of file parallel_priority_queue.h.
|
inline |
Returns the block beyond the block in which *(m_end_index-1) is located.
Definition at line 724 of file parallel_priority_queue.h.
|
inline |
Returns the smallest element in the array.
Definition at line 758 of file parallel_priority_queue.h.
|
inline |
Returns the smallest element of the first block NOT in internal memory (or at least requested to be in internal memory)
Definition at line 771 of file parallel_priority_queue.h.
|
inline |
Returns the smallest element of the next hint candidate (the block after the last hinted one).
Definition at line 957 of file parallel_priority_queue.h.
|
inline |
Returns if there is data in EM, that's not randomly accessible.
Definition at line 764 of file parallel_priority_queue.h.
|
inline |
Returns if there is data in EM, that's not already hinted to the prefetcher.
Definition at line 950 of file parallel_priority_queue.h.
|
inline |
Prefetch the next unhinted block, requires one free read block from the global pool.
Definition at line 930 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::read(), stxxl::read_write_pool< BlockType >::size_write(), stxxl::read_write_pool< BlockType >::steal_prefetch(), and STXXL_DEBUG.
|
inlinestatic |
Returns memory usage of EA with given capacity, excluding blocks loaded in RAM. Blocks belong to prefetch pool.
Definition at line 699 of file parallel_priority_queue.h.
References stxxl::div_ceil().
|
inline |
Return the amount of internal memory used by the EA.
Definition at line 712 of file parallel_priority_queue.h.
|
inlineprotected |
Definition at line 1194 of file parallel_priority_queue.h.
|
inline |
Returns the level (group number) of the array.
Definition at line 686 of file parallel_priority_queue.h.
|
inline |
Return the number of blocks.
Definition at line 692 of file parallel_priority_queue.h.
|
inline |
Returns the number of hinted blocks.
Definition at line 964 of file parallel_priority_queue.h.
|
inline |
Returns the number of blocks loaded in RAM.
Definition at line 1100 of file parallel_priority_queue.h.
|
inline |
Random access operator for data in internal memory You should call wait() once after fetching data from EM.
Definition at line 792 of file parallel_priority_queue.h.
|
inlineprotected |
prepare the external_array for writing using multiway_merge() with num_threads. this method is called by the external_array_writer's constructor.
Definition at line 831 of file parallel_priority_queue.h.
|
inlinestatic |
prepare the pool for writing external arrays with given number of threads
Definition at line 805 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::resize_write(), stxxl::read_write_pool< BlockType >::size_write(), and STXXL_ERRMSG.
|
inlineprotected |
Called by the external_array_writer to read a block from disk into m_blocks[]. If the block is marked as uninitialized, then no read is performed. This is the usual case, and in theory, no block ever has be re-read from disk, since all can be written fully. However, we do support re-reading blocks for debugging purposes inside multiway_merge(), in a full performance build re-reading never occurs.
Definition at line 859 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::read(), stxxl::read_write_pool< BlockType >::steal(), STXXL_DEBUG, and STXXL_ERRMSG.
|
inline |
Cancel hints which aren't needed anymore from the prefetcher and fixes it's size. prepare_rebuilding_hints() must be called before!
Definition at line 998 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::add_prefetch(), and STXXL_DEBUG.
|
inline |
Perform real-hinting of pre-hinted blocks, since now canceled blocks are available.
Definition at line 1015 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::read(), stxxl::read_write_pool< BlockType >::size_write(), stxxl::read_write_pool< BlockType >::steal_prefetch(), and STXXL_DEBUG.
|
inline |
Advance m_unhinted_block index without actually prefetching.
Definition at line 984 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inline |
This method prepares rebuilding the hints (this is done after creating a new EA in order to always have globally the n blocks hinted which will be fetched first). Resets m_unhinted_block to the first block not in RAM. Thereafter prehint_next_block() is used to advance this index. finish_rebuilding_hints() should be called after placing all hints in order to clean up the prefetch pool.
Definition at line 976 of file parallel_priority_queue.h.
|
inline |
Removes the first n elements from the array. Returns the number of blocks released into the block pool.
Definition at line 1107 of file parallel_priority_queue.h.
References stxxl::read_write_pool< BlockType >::add_prefetch(), and STXXL_DEBUG.
|
inline |
Returns the current size in items.
Definition at line 674 of file parallel_priority_queue.h.
|
inline |
Swap external_array with another one.
Definition at line 593 of file parallel_priority_queue.h.
References stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_bids, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_block_pointers, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_blocks, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_capacity, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_end_index, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_index, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_level, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_minima, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_num_blocks, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_old_unhinted_block, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_pool, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_requests, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_size, stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_unhinted_block, and stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::m_write_phase.
|
inlineprotected |
Updates the m_block_pointers vector. Should be called after any steal() or read() operation. This is necessary for the iterators to work properly.
Definition at line 1178 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inline |
Returns if the data requested to be in internal memory is completely fetched. True if wait() has been called before.
Definition at line 779 of file parallel_priority_queue.h.
|
inline |
Waits until all hinted blocks are read into RAM. Returns how many blocks were successfully read.
Definition at line 1081 of file parallel_priority_queue.h.
References min(), and STXXL_DEBUG.
|
inline |
Waits until the next prefetched block is read into RAM, then polls for any further blocks that are done as well. Returns how many blocks were successfully read.
Definition at line 1038 of file parallel_priority_queue.h.
References min(), and STXXL_DEBUG.
|
inlineprotected |
Called by the external_array_writer to write a block from m_blocks[] to disk. Prior to writing and releasing the memory, extra information is preserved.
Definition at line 900 of file parallel_priority_queue.h.
References STXXL_DEBUG, and stxxl::read_write_pool< BlockType >::write().
|
friend |
Swap external_array with another one.
Definition at line 622 of file parallel_priority_queue.h.
|
static |
Definition at line 465 of file parallel_priority_queue.h.
|
protected |
The IDs of each block in external memory.
Definition at line 482 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
Begin and end pointers for each block, used for merging with ppq_iterator.
Definition at line 490 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
A vector of size m_num_blocks with block_type pointers, some of them will be filled while writing, but most are NULL.
Definition at line 486 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The total size of the external array in items. Cannot be changed after construction.
Definition at line 470 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The index behind the last element that is located in RAM (or is at least requested to be so)
Definition at line 510 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The read position in the array.
Definition at line 506 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
Level of external array (Sander's PQ: group number)
Definition at line 476 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
stores the minimum value of each block
Definition at line 497 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
Number of blocks, again: calculated at construction time.
Definition at line 473 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The first unhinted block index as it was before the prepare_rebuilding_hints() call. Used for removal of hints which aren't needed anymore.
Definition at line 518 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
Common prefetch and write buffer pool.
Definition at line 479 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The read request pointers are used to wait until the block has been completely fetched.
Definition at line 494 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The total number of elements minus the number of extracted values.
Definition at line 503 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
The first unhinted block index.
Definition at line 513 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
|
protected |
Is array in write phase? True = write phase, false = read phase.
Definition at line 500 of file parallel_priority_queue.h.
Referenced by stxxl::ppq_local::external_array< ValueType, BlockSize, AllocStrategy >::swap().
1.8.5 
