STXXL

STXXL: Standard Template Library for Extra Large Data Sets.

The core of STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i. e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. While the closeness to the STL supports ease of use and compatibility with existing applications, another design priority is high performance. [more info]

The key features of STXXL are:

• Transparent support of parallel disks. The library provides implementations of basic parallel disk algorithms. STXXL is the only external memory algorithm library supporting parallel disks.
• The library is able to handle problems of very large size (tested to up to dozens of terabytes).
• Improved utilization of computer resources. STXXL implementations of external memory algorithms and data structures benefit from overlapping of I/O and computation.
• Small constant factors in I/O volume. A unique library feature called "pipelining" can save more than half the number of I/Os, by streaming data between algorithmic components, instead of temporarily storing them on disk. A development branch supports asynchronous execution of the algorithmic components, enabling high-level task parallelism.
• Shorter development times due to well known STL-compatible interfaces for external memory algorithms and data structures.
• STL algorithms can be directly applied to STXXL containers; moreover, the I/O complexity of the algorithms remains optimal in most of the cases.
  [more info]
• For internal computation, parallel algorithms from the MCSTL or the libstdc++ parallel mode are optionally utilized, making the algorithms inherently benefit from multi-core parallelism.

Current contributors: Andreas Beckmann, Johannes Singler
Past contributors: Roman Dementiev (author), Peter Sanders

Support

Questions concerning use and development of the STXXL should be posted to the forums.

Bugs should be reported in the Bugzilla Bug Tracker

License

STXXL is free, open source, and available under the Boost Software License 1.0.

Platforms supported

Current version

Version 1.3.1 (March 10, 2011) contains memory management, disk virtualization, prefetching, and so on, as the lower layers, and as part of the higher layer (pipelined) sorting with SMP and multi-core processor support, (pipelined) scanning and containers (vectors, stacks, priority queues, maps (B+Tree), queues, deques). Currently that sums to about 35,000 lines of code.

Branches

Special features are maintained in up-to-date branches until they are merged into trunk. Until inclusion into trunk, the interface may change without further notice. Please refer to Installing from subversion for a description on how to build these branches.

• Native Command Queuing (NCQ) on Linux: kernelaio
• Asynchronous Pipelining/Streaming: parallel_pipelining_integration
• Matrix Operations: matrix
• Hash Tables: unordered_map

Major improvements in the latest release

• parallel mode can be turned on for stxxl algorithms selectively (i.e. without enabling it for the the non-stxxl part of an application)
• support for latest compiler versions
• I/O-layer adjustments to avoid performance decrease with recent kernels
• support for arbitrarily large I/O requests (syscall file), will be split internally if necessary
• improve support for input files with a partial last block
• many, many bug fixes
• many under-the-hood improvements
• Added several new test programs.
• For a detailed list, please read the the CHANGELOG file.

Links/Download

• FAQ - Frequently Asked Questions [html]
• Design paper - library overview [pdf] [html]
• Tutorial (draft) [pdf]
• MCSTL homepage: [link] (optional)
• libstdc++ parallel mode homepage: [link] (optional, comes with GCC)

Ongoing and completed projects using STXXL

• External Memory Breadth-First Search (BFS) [paper (pdf)][project page][graph generators]
• External Memory Minimum Spanning Trees [project page][paper (ps)][paper (pdf)]
• External Memory Spanning Forests and Connected Components [report][src tarball]
• External Memory Suffix Array Construction and Suffix Array Checker [project page][paper(pdf)][input instances]

Publications

A. Beckmann, R. Dementiev, J. Singler: Building A Parallel Pipelined External Memory Algorithm Library IPDPS 2009: International Parallel and Distributed Processing Symposium (May 2009, Rome, Italy) [full text]

R. Dementiev, L. Kettner, P. Sanders: STXXL: standard template library for XXL data sets, Software: Practice and Experience (August 2007, DOI: 10.1002/spe.844): [link][preprint]

D. Ajwani, R. Dementiev, U. Meyer: A Computational Study of External-Memory BFS Algorithms. SODA2006: ACM-SIAM Symposium on Discrete Algorithms (January 2006, Miami, Florida, USA) [pdf]

R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. ESA2005: 13th Annual European Symposium on Algorithms (October 2005, Palma de Mallorca, Spain) [pdf] (see also the extended version)

R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. Technical Report 2005/18, Department of Informatics, University of Karlsruhe [pdf] [html]

R. Dementiev, J. Kaerkkaeinen, J. Mehnert, P. Sanders: Better External Memory Suffix Array Construction ALENEX05: Algorithm Engineering and Experiments (January 2005, Vancouver, Canada): [pdf][input instances]

R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn: Engineering an External Memory Minimum Spanning Tree Algorithm. TSC04: 3rd IFIP International Conference on Theoretical Computer Science (August 24-26, 2004, Toulouse): [ps][pdf]

R. Dementiev, P. Sanders: Asynchronous Parallel Disk Sorting. In 15th ACM Symposium on Parallelism in Algorithms and Architectures (June 7-9, 2003, San Diego, California, USA): pages 138-148 [pdf]