File TwoLevelMemory.h

↰ Parent directory (ADS/external)

The two-level memory model of Aggarwal and Vitter, simulated so that the algorithms of the external memory can be run and their I/Os counted: an internal memory of M items and a disk of unbounded size, read and written by blocks of B items, an I/O moving one block.

Definition (ADS/external/TwoLevelMemory.h)

Detailed Description

The time of the computation in memory is free; what is counted is the number of reads and the number of writes.

  • TwoLevelMemory holds B and M, the two counters of the I/Os and the occupation of the memory: every buffer and every array that an algorithm keeps in memory is allocated from it, by a MemoryLease, and an allocation beyond M violates a precondition, so that a test of an algorithm checks at once its result, its I/Os and the memory it used (peak());

  • DiskFile is a file on the disk, a sequence of items laid out in blocks of B items, the last one possibly partial; readBlock() and appendBlock() are the only accesses to its items, one I/O each, and contents() is the view without I/Os, for the checks of the tests;

  • DiskReader reads a file through a buffer of one block: next() scans it in order, ceil( n / B ) reads for n items, and at( i ) reads any item, loading its block only when it is not the one in the buffer, so that a sorted set of m positions costs at most :math:` min{ m , lceil n / B rceil } ` reads;

  • DiskWriter appends to a file through a buffer of one block, a write per full block and one for the last partial block.

The bounds of the model are those of the notes: a scan of n items takes :math:` Theta( n / B ) ` I/Os, a sort :math:` Theta( ( n / B ) log_{M / B} ( n / M ) ) ` [see File ExternalSorting.h], and an algorithm that follows pointers on the disk pays up to one I/O per pointer, which is what the external algorithms of this library avoid. The files are not containers with iterators on purpose: an iterator would read the items without paying the I/Os.

The contracts [see File Contract.h]: :math:` B geq 1 ` and :math:` M geq 2 B `; the memory in use never exceeds M; a block read exists; a block is appended only after full blocks; a file and its reader or writer share the memory. The functions are defined in TwoLevelMemory.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapters 1 and 5

  1. Aggarwal, J. S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM 31(9), 1116-1127, 1988, doi:10.1145/48529.48535

    1. Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys 33(2), 209-271, 2001, doi:10.1145/384192.384193

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes