My Project
|
The I/O efficient stack is perhaps the simplest external memory data structure. Stacks provide only restricted subset of sequence operations: insertion, removal, and inspection of the element at the top of the stack. Stacks are a "last in first out" (LIFO) data structures: the element at the top of a stack is the one that was most recently added. Stacks does not allow iteration through its elements.
The basic variant of EM stack keeps the top k elements in the main memory buffer, where
operation | internal work | I/O (amortized) |
---|---|---|
insertion at the end | ![]() | ![]() |
removal at the end | ![]() | ![]() |
The STXXL library contains four different variants of stacks, each implementation is specialized for a certain access pattern:
To make use of stxxl::stack, one can use the generator template stxxl::STACK_GENERATOR which expects the parameters from left to right as shown in the table below.
The stxxl::normal_stack is a general purpose implementation of the external memory stack. The stack has two pages, the size of the page in blocks is a configuration constant and can be given as a template parameter. The implementation of the methods follows the description given in the previous section.
The cache of stxxl::normal_stack largely dominates in its internal memory consumption. Other members consume very small fraction of stxxl::normal_stack's memory even when the stack size is large. Therefore, the internal memory consumption of stxxl::normal_stack can be estimated as
The stxxl::grow_shrink_stack specialization is optimized for an access pattern where the insertions are (almost) not intermixed with the removals, and/or vice versa, the removals are (almost) not intermixed with the insertions. In other words the stack first grows to its maximal size, then it shrinks, then it might again grow, then shrink, and so forth, i.e. the pattern is
The cache of stxxl::grow_shrink_stack largely dominates in its internal memory consumption. Other members consume very small fraction of stxxl::grow_shrink_stack's memory even when the stack size is large. Therefore, the internal memory consumption of stxxl::grow_shrink_stack can be estimated as
The stxxl::grow_shrink_stack has the same set of members as the stxxl::normal_stack. The running times of stxxl::grow_shrink_stack are the same as stxxl::normal_stack except that when the stack switches from growing to shrinking (or from shrinking to growing)
The stxxl::grow_shrink_stack2 is optimized for the same kind of access pattern as stxxl::grow_shrink_stack. The difference is that each instance of stxxl::grow_shrink_stack uses an own internal buffer to overlap I/Os and computation, but stxxl::grow_shrink_stack2 is able to share the buffers from the pool used by several stacks.
Not counting the memory consumption of the shared blocks from the pools, the stack alone consumes about
The stxxl::grow_shrink_stack2 has almost the same set of members as the stxxl::normal_stack, except that it does not have the default constructor. The stxxl::grow_shrink_stack2 requires prefetching and write pool objects (see stxxl::prefetch_pool, stxxl::write_pool and stxxl::read_write_pool) to be specified in the creation time.
Consequently, the constructor requires a read_write_pool for prefetching and buffered writing. But it also has a second parameter, which tells how many blocks from the prefetching pool are used, this is called "prefetch_aggressiveness".
The stxxl::migrating_stack is a stack that migrates from internal memory to external when its size exceeds a certain threshold (template parameter). The implementation of internal and external memory stacks can be arbitrary and given as a template parameters.
The stxxl::migrating_stack memory consumption depends on the memory consumption of the stack implementations given as template parameters. The current state is internal (external), the stxxl::migrating_stack consumes almost exactly the same space as internal (external) memory stack implementation. (The stxxl::migrating_stack needs only few pointers to maintain the switching from internal to external memory implementations.)
The stxxl::migrating_stack extends the member set of stxxl::normal_stack. Additionally, there are stxxl::migrating_stack::internal() and stxxl::migrating_stack::external(), which return true if the currently used implementation is internal or external.
To provide an easy way to choose and configure the stack implementations, STXXL offers a template meta program called stxxl::STACK_GENERATOR.
The stxxl::STACK_GENERATOR has the following template parameters:
double's
double's
double's
double's
, internal implementation is std::stack<double>
double's
with 1 block per page and block size 512 KiB (total memory occupied = 1 MiB)TODO-df : but use read_write_pool instead of the two pools.