|
|
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: Roman Dementiev, Johannes Singler, Andreas Beckmann
|
|
|
|
Questions concerning use and development of the STXXL library
mail to Roman Dementiev or consult the forum.
|
|
|
|
|
|
|
|
| · Linux (kernel >=
2.4.18) g++ (versions 3.3.x-4.2.x) |
| · SunOS (g++ versions 3.3.x-4.2.x) |
| ·
Windows 2000/XP (Microsoft Visual C++ 7.1 and 8.0 (.NET)) |
|
|
|
| Version 1.1.0 (31 July 2007)
contains an implementation of the lower layers (memory
management, disk virtualization, prefetching,...). From the higher
layers, (pipelined) sorting with
SMP and multicore procesor support, (pipelined) scanning and containers
(vectors, stacks, priority queues, maps (B+Tree) , queues, deques) are supported.
Currently that
sums to about 25 thousand lines of code (25 KSLOC). |
|
| What's
new in the latest release |
|
| ·
Pipelined stream::sort, stream::runs_creator and stream::runs_merger are parallelized using MCSTL |
|
|
| ·
Restructured the source layout |
|
|
| ·
Overhauled the build system |
|
|
| ·
More compilers tested (see CHANGELOG) |
|
|
| ·
stxxl::vector: implemented some more functions |
|
|
| ·
And many many more: cleanup, reformat the code to a consistent format (Thanks, uncrustify!), obsolete files removed, fixed include dependencies, fixed lots of warnings, fixed lots of small bugs, add header compilation tests, ... |
|
|
|
|
|
Current Stable Version |
Development Version (subversion) |
|
· Installation manual:
|
[1.1.0]
|
[trunk]
|
|
· Programmer documentation:
|
[1.1.0]
|
[trunk]
|
|
· Download:
[sf.net page]
|
[1.1.0] tgz,zip (sf.net)
|
subversion checkout
|
· Subversion repository:
https://stxxl.svn.sourceforge.net/...
|
[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] |
|
|
|