|
|
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 compatibility to the STL
supports ease of use and compatibility with existing applications,
another design priority is high performance.
[more info]
|
|
 |
|
The following are some key features of
STXXL:
· 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
(up to dozens of terabytes).
· Improved utilization of computer resources.
STXXL
supports explicitly overlapping between I/O and computation.
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 ``pipelining'' can save more than half the number of I/Os
performed by many applications.
· 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]
Current contributors: Andreas Beckmann, Johannes Singler
Past contributors: Roman Dementiev (author), Peter Sanders
|
|
|
|
Questions concerning use and development of the STXXL library
mail to Roman Dementiev or consult the forum.
|
|
|
|
|
|
|
|
| |
Operating System |
Compilers |
Extras |
| · |
Linux (kernel >= 2.4.18) |
g++ (3.3-4.3)
icpc (9.0-10.1) |
Boost (optional),
MCSTL (optional, only with g++ 4.2 or icpc 10.x) |
| · |
Solaris |
g++ (3.3-4.3) |
|
| · |
Mac OS X |
g++ |
|
| · |
Windows 2000/XP/Vista |
Microsoft Visual C++ 8.0, 9.0 |
Boost (required) |
|
|
|
| Version 1.2.1 (14 August 2008)
contains an implementation of the lower layers (memory
management, disk virtualization, prefetching,...). From the higher
layers, (pipelined) sorting with
SMP and multi-core processor support, (pipelined) scanning and containers
(vectors, stacks, priority queues, maps (B+Tree), queues, deques) are supported.
Currently that
sums to about 29 thousand lines of code (29 KSLOC). |
|
| What's
new in the latest release |
|
| ·
Added support for the libstdc++ parallel mode (successor of MCSTL),
requires g++ 4.3.2 or later.
|
| ·
Fixed locking problem in recursive block allocation.
|
| ·
Fixed problem in sorters where blocks were released too early.
|
| ·
Properly destroy singleton objects and remove temporary files at program end.
|
| ·
Simplify and unify thread and mutex handling.
|
| ·
Print I/O statistics also in a human readable way.
|
| ·
Add c++0x style const_iterator cbegin()/cend() to all containers.
|
| ·
Add a special file mem_file type intended to ease debugging.
|
| ·
Propagate block deletion to the I/O level, advanced file types can use this information.
|
| ·
Always use std::numeric_limits<...>::min/max().
|
| ·
Build system: improved dependency handling.
|
| ·
Added several new test programs.
|
| ·
Lots of small fixes and many more changes.
For a detailed list, please read the the CHANGELOG file.
|
|
|
|
| |
Current Stable Version |
Previous Stable Version |
Development Version (subversion) |
|
· Installation manual:
|
[1.2.1]
|
[1.1.0]
|
[trunk]
|
|
· Programmer documentation:
|
[1.2.1]
|
[1.1.0]
|
[trunk]
|
|
· Download:
[sf.net page]
|
[1.2.1] tgz, zip (sf.net)
|
[1.1.0] tgz, zip (sf.net)
|
subversion checkout
|
· Subversion repository:
https://stxxl.svn.sourceforge.net/...
|
[Browse]
[Checkout]
.../svnroot/stxxl/tags/1.2.1/
|
[Browse]
[Checkout]
.../svnroot/stxxl/tags/1.1.0/
|
[Browse]
[Checkout]
.../svnroot/stxxl/trunk/
|
|
|
· FAQ - Frequently Asked Questions
[html]
|
| · Design paper - library overview
[pdf] [html]
|
| · Tutorial
(draft)
[pdf]
|
| · Older version (0.77 - Linux only):
[tgz (sf.net)]
[tgz]
|
| ·
MCSTL library homepage: [link] (optional)
|
|
|
Ongoing and completed projects using STXXL
|
|
|
|
|
|
|
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, Fakultät für Informatik, University of Karlsruhe
[pdf] [html]
|
|
| R. Dementiev, J.
Kärkkäinen, 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] |
|
|
|