STXXL
1.4-dev
|
An external_array can only be written using an external_array_writer object. The writer objects provides iterators which are designed to be used by stxxl::parallel::multiway_merge() to write the external memory blocks in parallel. Thus in the writer we coordinate thread-safe access to the blocks using reference counting.
An external_array_writer::iterator has two states: normal and "live". In normal mode, the iterator only has a valid index into the external array's items. In normal mode, only index calculations are possible. Once operator*() is called, the iterators goes into "live" mode by requesting access to the corresponding block. Using reference counting the blocks is written once all iterators are finished with the corresponding block. Since with operator*() we cannot know if the value is going to be written or read, when going to live mode, the block must be read from EM. This read overhead, however, is optimized by marking blocks as uninitialized in external_array, and skipping reads for then. In a full performance build, no block needs to be read from disk. Reads only occur in debug mode, when the results are verify.
The iterator's normal/live mode only stays active for the individual iterator object. When an iterator is copied/assigned/calculated with the mode is NOT inherited! The exception is prefix operator ++, which is used by multiway_merge() to fill an array. Thus the implementation of the iterator heavily depends on the behavior of multiway_merge() and is optimized for it.
Definition at line 421 of file parallel_priority_queue.h.
Classes | |
class | iterator |
Public Types | |
typedef ea_type::block_type | block_type |
typedef ExternalArrayType | ea_type |
typedef external_array_writer | self_type |
typedef ea_type::value_type | value_type |
Public Member Functions | |
external_array_writer (ea_type &ea, unsigned int num_threads=0) | |
~external_array_writer () | |
iterator | begin () |
iterator | end () |
Static Public Attributes | |
static const bool | debug = false |
scope based debug variable More... | |
Protected Member Functions | |
void | free_block_ref (size_t block_index) |
decrease reference count on the block, and possibly write it to disk (called when an iterator releases live mode). More... | |
block_type * | get_block_ref (size_t block_index) |
read block into memory and increase reference count (called when an iterator goes live on the block). More... | |
Protected Member Functions inherited from stxxl::noncopyable | |
noncopyable () | |
Protected Attributes | |
ea_type & | m_ea |
reference to the external array to be written More... | |
std::vector< iterator > | m_live_boundary |
optimization: hold live iterators for the expected boundary blocks of multiway_merge(). More... | |
mutex | m_mutex |
mutex for reference counting array (this is actually nicer than openmp's critical) More... | |
std::vector< unsigned int > | m_ref_count |
reference counters for the number of live iterators on the corresponding block in external_array. More... | |
unsigned int | m_ref_total |
total number of iterators referencing this writer More... | |
typedef ea_type::block_type stxxl::ppq_local::external_array_writer< ExternalArrayType >::block_type |
Definition at line 1236 of file parallel_priority_queue.h.
typedef ExternalArrayType stxxl::ppq_local::external_array_writer< ExternalArrayType >::ea_type |
Definition at line 1231 of file parallel_priority_queue.h.
typedef external_array_writer stxxl::ppq_local::external_array_writer< ExternalArrayType >::self_type |
Definition at line 1233 of file parallel_priority_queue.h.
typedef ea_type::value_type stxxl::ppq_local::external_array_writer< ExternalArrayType >::value_type |
Definition at line 1235 of file parallel_priority_queue.h.
|
inline |
Definition at line 1514 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inline |
Definition at line 1549 of file parallel_priority_queue.h.
References STXXL_ASSERT.
|
inline |
Definition at line 1558 of file parallel_priority_queue.h.
Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level(), and stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_internal_arrays().
|
inline |
Definition at line 1563 of file parallel_priority_queue.h.
|
inlineprotected |
decrease reference count on the block, and possibly write it to disk (called when an iterator releases live mode).
Definition at line 1293 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
inlineprotected |
read block into memory and increase reference count (called when an iterator goes live on the block).
Definition at line 1268 of file parallel_priority_queue.h.
References STXXL_DEBUG.
|
static |
scope based debug variable
Definition at line 1242 of file parallel_priority_queue.h.
|
protected |
reference to the external array to be written
Definition at line 1246 of file parallel_priority_queue.h.
|
protected |
optimization: hold live iterators for the expected boundary blocks of multiway_merge().
Definition at line 1263 of file parallel_priority_queue.h.
|
protected |
mutex for reference counting array (this is actually nicer than openmp's critical)
Definition at line 1259 of file parallel_priority_queue.h.
|
protected |
reference counters for the number of live iterators on the corresponding block in external_array.
Definition at line 1255 of file parallel_priority_queue.h.
|
protected |
total number of iterators referencing this writer
Definition at line 1250 of file parallel_priority_queue.h.