-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.html
333 lines (320 loc) · 18.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-type" content="text/html; charset=iso-8859-1"/>
<title>STXXL - Standard Template Library for Extra Large Data Sets</title>
<link href="stxxl.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="navbar">
<h1>STXXL</h1>
<div style="float: right">
<ul>
<li><a href="#downloads">Downloads</a></li>
<li><a href="tags/master/">Documentation</a></li>
<li><a href="#references">References</a></li>
</ul>
</div>
</div>
<p style="margin-top: 1ex">
<b>STXXL: Standard Template Library for Extra Large Data Sets.</b>
</p>
<table align="right">
<tr>
<td style="text-align: left">
<script type="text/javascript" src="http://www.ohloh.net/p/11530/widgets/project_basic_stats.js"></script><br/>
</td>
<td>
<img src="layer_diagram.png" align="right" alt="STXXL Layers Figure" width="350" height="251" />
</td>
</tr>
</table>
<p>
The core of <b>STXXL</b> is an implementation of the C++ <a href="http://en.wikipedia.org/wiki/Standard_Template_Library">standard template library STL</a> for external memory (out-of-core) computations, i. e., <b>STXXL</b> implements containers and algorithms that can process <b>huge volumes of data</b> 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.
</p>
<p style="padding-bottom: 0">
The key features of <b>STXXL</b> are:
</p>
<ul style="margin-left: 20px;">
<li>Transparent support of parallel disks. The library provides implementations of basic <b>parallel disk</b> algorithms. <b>STXXL</b> is the only external memory algorithm library supporting parallel disks.</li>
<li>The library is able to handle problems of <b>very large</b> size (tested to up to dozens of terabytes).</li>
<li>Improved utilization of computer resources. <b>STXXL</b> implementations of external memory algorithms and data structures benefit from overlapping of I/O and computation.</li>
<li>Small constant factors in I/O volume. A unique library feature called <b>"pipelining"</b> can save more than <b>half</b> the number of I/Os, by streaming data between algorithmic components, instead of temporarily storing them on disk. A development branch supports <b>asynchronous</b> execution of the algorithmic components, enabling high-level task parallelism.</li>
<li>Shorter <b>development times</b> due to well known <b>STL-compatible</b> interfaces for external memory algorithms and data structures.</li>
<li>STL algorithms can be directly applied to <b>STXXL</b> containers; moreover, the I/O complexity of the algorithms remains optimal in most of the cases. [<a href="http://algo2.iti.kit.edu/dementiev/stxxl/report/">more info</a>]</li>
<li>For internal computation, <b>parallel</b> algorithms from the MCSTL or the libstdc++ parallel mode are optionally utilized, making the algorithms inherently benefit from <b>multi-core</b> parallelism.</li>
<li><b>STXXL</b> is free, open source, and available under the <a href="tags/master/license.html">Boost Software License 1.0</a>.</li>
</ul>
<p>
<b>Current maintainers:</b> Andreas Beckmann, <a href="http://panthema.net">Timo Bingmann</a><br/>
<b>Past contributors:</b> Roman Dementiev (author), Peter Sanders, Johannes Singler, Raoul Steffen, Markus Westphal
</p>
<h2><a id="downloads"></a>Downloads and Documentation</h2>
<div style="float: right; margin: 1em">
<a href="https://travis-ci.org/stxxl/stxxl"><img src="https://travis-ci.org/stxxl/stxxl.png?branch=master" title="Travis CI master branch status" alt="Travis CI master branch status" /></a>
<iframe src="http://ghbtns.com/github-btn.html?user=stxxl&repo=stxxl&type=watch&count=true"
frameborder="0" scrolling="no" width="80" height="20"></iframe>
<iframe src="http://ghbtns.com/github-btn.html?user=stxxl&repo=stxxl&type=fork&count=true"
frameborder="0" scrolling="no" width="80" height="20"></iframe>
<iframe src="http://ghbtns.com/github-btn.html?user=stxxl&repo=stxxl&type=follow&count=true"
frameborder="0" scrolling="no" width="110" height="20"></iframe>
</div>
<table>
<tr>
<td></td>
<td style="padding-right: 2em"><b>Current Stable</b></td>
<td style="padding-right: 2em"><b>Previous Stable</b></td>
<td><b>Development</b></td>
</tr>
<tr>
<td>
<ul><li>Documentation:</li></ul>
</td>
<td><img class="ficon" src="filelink-doc.png" width="13" height="17" alt="Doxygen" /> [<a href="tags/1.4.1/">1.4.1</a>]</td>
<td><img class="ficon" src="filelink-doc.png" width="13" height="17" alt="Doxygen" /> [<a href="tags/1.3.1/">1.3.1</a>]</td>
<td><img class="ficon" src="filelink-doc.png" width="13" height="17" alt="Doxygen" /> [<a href="tags/master/">1.4-dev</a>] <img class="ficon" src="filelink-doc.png" width="13" height="17" alt="Doxygen" /> [<a href="tags/1.3/">1.3-dev</a>]</td>
</tr>
<tr>
<td>
<ul><li>Download: [<a href="http://sourceforge.net/projects/stxxl/">sf.net page</a>]</li></ul>
</td>
<td>
<img class="ficon" src="filelink-archive.png" width="13" height="17" alt="Download" /> [<a href="http://sourceforge.net/projects/stxxl/files/stxxl/1.4.1/stxxl-1.4.1.tar.gz/download">1.4.1</a>] tar.gz
</td>
<td>
<img class="ficon" src="filelink-archive.png" width="13" height="17" alt="Download" /> [<a href="http://sourceforge.net/projects/stxxl/files/stxxl/1.3.1/stxxl-1.3.1.tar.gz/download">1.3.1</a>] tar.gz
</td>
<td></td>
</tr>
<tr>
<td>
<ul><li>git Repository:<br/><a href="https://github.com/stxxl/stxxl">https://github.com/stxxl/stxxl</a></ul>
</td>
<td>
[<a href="https://github.com/stxxl/stxxl/tree/1.4.1">Browse</a>]
</td>
<td>
[<a href="https://github.com/stxxl/stxxl/tree/1.3.1">Browse</a>]
</td>
<td>
[<a href="https://github.com/stxxl/stxxl/tree/master">1.4-dev</a>]
[<a href="https://github.com/stxxl/stxxl/tree/1.3">1.3-dev</a>]
</td>
</tr>
</table>
<ul class="space">
<li><a href="tags/master/"><b>Tutorial and Design Documentation</b></a></li>
<li><a href="http://panthema.net/2014/0622-Talk-STXXL-1.4.0-and-Beyond/">Recording of a Talk "STXXL 1.4.0 and Beyond"</a> given on 2014-06-22 by Timo Bingmann</li>
<li>Further, older documentation is available below:
<ul>
<li>
FAQ- Frequently Asked Questions [<a href="tags/master/faq.html">html</a>]
</li>
<li>
Design paper (2005) - library overview [<a href="http://algo2.iti.kit.edu/dementiev/files/TRKA2005_18.pdf">pdf</a>] [<a href="http://algo2.iti.kit.edu/dementiev/stxxl/report/">html</a>]
</li>
<li>
libstdc++ parallel mode homepage: [<a href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html">link</a>] (optional, comes with GCC)
</li>
</ul>
</li>
</ul>
<h2>Support Channels</h2>
<p>
Questions concerning use and development can be search for and asked on <a href="http://stackoverflow.com/questions/tagged/stxxl"><b>Stack Overflow</b></a>, and longer user-contributed solutions may also be shared via the <a href="https://github.com/stxxl/stxxl/wiki"><b>Github Wiki</b></a>..
</p>
<p>
Bugs and issues should be reported via <a href="https://github.com/stxxl/stxxl/issues"><b>Github's issue tracker</b></a>
</p>
<p>
Discussions about future development and details of the STXXL should be posted to the <a href="http://sourceforge.net/projects/stxxl/forums"><b>sourceforge forums</b></a>.
</p>
<h2>Platforms supported</h2>
<table>
<tr>
<td>
<b>Operating Systems</b>
</td>
<td>
<b>Compilers</b>
</td>
<td>
<b>Extras</b>
</td>
</tr>
<tr>
<td>
<ul><li>Linux (kernel >= 2.4.18)</li></ul>
</td>
<td>
g++ (3.4-4.9)<br/>
icpc (2011,2013,2015)<br/>
clang++ (3.1-3.5)
</td>
<td>
<a href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html">libstdc++ parallel mode</a> (optional, included with g++ 4.3+)
<br/>
<a href="http://www.boost.org/">Boost</a> (optional)
</td>
</tr>
<tr>
<td>
<ul><li>Mac OS X</li></ul>
</td>
<td>
clang++ (3.5)
</td>
</tr>
<tr>
<td>
<ul><li>FreeBSD</li></ul>
</td>
<td>
g++
</td>
</tr>
<tr>
<td>
<ul><li>Windows</li></ul>
</td>
<td>
Visual C++ 2010, 2012 and 2013
</td>
<td>
-- <a href="http://www.boost.org/">Boost </a>(required only for VS 2010)
</td>
</tr>
</table>
<h2>Versions</h2>
<ul>
<li>
<p>Version 1.4.1 (October 29, 2014)</p>
<ul>
<li>Integrated support for kernel based asynchronous I/O on Linux (new file type "linuxaio"), which exploits Native Command Queuing (NCQ) if available.</li>
<li>Merged stxxl::unordered_map branch, which provides a hash map backed by external memory.</li>
<li>Replaced struct default_completion_handler with a NULL pointer, thus avoiding superfluous new/delete work for each I/O request</li>
<li>Added stxxl::external_shared_ptr which is a proxy class to allow use of shared_ptr classes inside stxxl containers</li>
<li>Fixing bugs and warnings on 32-bit systems (yes, they still exist).</li>
<li>Use atomic_counted_object in class file for request reference counting.</li>
<li>Adding support for MinGW-w64 (64-bit) systems with working SJLJ thread implementations.</li>
</ul>
</li>
<li>
<p>Version 1.4.0 (December 12, 2013)</p>
<ul>
<li>reorganized source hierarchy into include/ lib/ tests/ examples/ doc/ tools/</li>
<li>CMake build system for cross-platform compilation</li>
<li>greatly improved documentation with tutorials and examples</li>
<li>efficient external matrix operations</li>
<li>new containers stxxl::sequence and stxxl::sorter</li>
<li>improved .stxxl disk configuration files and additional options</li>
<li>combined stxxl_tool of disk benchmarks</li>
<li>simple examples and skew3 as real-world stream application</li>
<li>support for Visual Studio 2012 and 2013 _without_ Boost</li>
<li>important bug fixes in stxxl::queue and stxxl::priority_queue</li>
</ul>
</li>
<li>
<p>Version 1.3.1 (March 10, 2011)</p>
<p>Contains memory management, disk virtualization, prefetching, and so on, as the lower layers, and as part of the higher layer (pipelined) sorting with <a href="http://algo2.iti.kit.edu/singler/mcstl/">SMP and multi-core processor support</a>, (pipelined) scanning and containers (vectors, stacks, priority queues, maps (B+Tree), queues, deques). Currently that sums to about 35,000 lines of code.</p>
</li>
</ul>
<p>See the current <a href="tags/master/changelog.html">Changelog</a> for detailed lists of changes.</p>
<h2>Branches</h2>
<p>
Special features are maintained as Github forks until they are merged into master. Until inclusion into the master branch, the interface may change without further notice.
</p>
<ul class="space">
<li>
Asynchronous Pipelining/Streaming: <a href="https://github.com/bingmann/stxxl/tree/parallel_pipelining_integration">parallel_pipelining_integration</a><br/>This contains an unfinished integration attempt of the async nodes and parallel sorting/pipelining described in the IPDPS 2009 paper. If someone has a stake or interest in this branch, please contact me (Timo) about further work on it. -- 2014-10-23
</li>
</ul>
<h2><a id="references"></a>Publications, Ongoing and Completed Projects using <b>STXXL</b></h2>
<p>If you use STXXL and wish to appear in the following list, please provide a description line via email to one of the maintainers.</p>
<ul class="space">
<li>
Open-Source Routing Machine (Project OSRM) (2011 - ongoing) [<a href="http://project-osrm.org/">project page</a>]
</li>
<li>
Thomas Keh: "Bulk-Parallel Priority Queue in External Memory", 2014: Bachelor Thesis, Supervisor: Timo Bingmann and Peter Sanders
[<a href="http://algo2.iti.kit.edu/2386.php">pdf</a>]
</li>
<li>
Timo Bingmann, Johannes Fischer, Vitaly Osipov: "Inducing Suffix and LCP Arrays in External Memory", ALENEX 2013: Workshop on Algorithm Engineering and Experiments (Jan 2013, New Orleans, LA, USA)
[<a href="http://algo2.iti.kit.edu/2125.php">pdf</a>] [<a href="http://panthema.net/2012/esais/">project page</a>]
</li>
<li>
Daniel Feist: "External Batched Range Minimum Queries and LCP Construction", 2013: Bachelor Thesis, Supervisor: Timo Bingmann and Peter Sanders
[<a href="http://algo2.iti.kit.edu/2172.php">pdf</a>]
</li>
<li>
Dennis Luxen, Christian Vetter: "Real-Time Routing with OpenStreetMap Data", ACM GIS 2011: 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (Nov 2011, Chicago, IL, USA)
[<a href="http://algo2.iti.kit.edu/1927.php">pdf</a>]
</li>
<li>
Mirko Rahn, Peter Sanders, Johannes Singler: "Scalable Distributed-Memory External Sorting", ICDE 2010: International Conference on Data Engineering (Mar 2010, Long Beach)
[<a href="http://arxiv.org/abs/0910.2582">arXiv</a>]
</li>
<li>
Raoul Steffen: "Matrix Operations for STXXL", 2010: Bachelor Thesis, Supervisor: Johannes Singler and Peter Sanders
[<a href="http://algo2.iti.kit.edu/1920.php">pdf</a>]
</li>
<li>
Andreas Beckmann, Roman Dementiev, Johannes Singler: "Building A Parallel Pipelined External Memory Algorithm Library", IPDPS 2009: International Parallel and Distributed Processing Symposium (May 2009, Rome, Italy)
[<a href="http://algo2.iti.kit.edu/singler/publications/parallelstxxl-ipdps2009.pdf">full text</a>]
</li>
<li>
Roman Dementiev, Lutz Kettner, Peter Sanders: "STXXL: standard template library for XXL data sets", Software: Practice and Experience (August 2007, DOI: 10.1002/spe.844)
[<a href="http://www3.interscience.wiley.com/cgi-bin/abstract/114300511/ABSTRACT">link</a>] [<a href="http://algo2.iti.kit.edu/dementiev/files/stxxl_spe.pdf">preprint</a>]
</li>
<li>
D. Ajwani, Roman Dementiev, Ulrich Meyer: "A Computational Study of External-Memory BFS Algorithms", SODA 2006: ACM-SIAM Symposium on Discrete Algorithms (January 2006, Miami, Florida, USA)
[<a href="http://algo2.iti.kit.edu/dementiev/files/ebfs.pdf">pdf</a>]
</li>
<li>
Roman Dementiev, Lutz Kettner, Peter Sanders: "Stxxl: Standard Template Library for XXL Data Sets", ESA 2005: 13th Annual European Symposium on Algorithms (October 2005, Palma de Mallorca, Spain)
[<a href="http://algo2.iti.kit.edu/dementiev/files/DKS05.pdf">pdf</a>] [see also <a href="http://algo2.iti.kit.edu/dementiev/files/TRKA2005_18.pdf">the extended version</a>]
</li>
<li>
Roman Dementiev, Lutz Kettner, Peter Sanders: "Stxxl: Standard Template Library for XXL Data Sets", Technical Report 2005/18, Department of Informatics, University of Karlsruhe
[<a href="http://algo2.iti.kit.edu/dementiev/files/TRKA2005_18.pdf">pdf</a>] [<a href="http://algo2.iti.kit.edu/dementiev/stxxl/report/">html</a>]
</li>
<li>
Roman Dementiev, Juha Kaerkkaeinen, Jens Mehnert, Peter Sanders: "Better External Memory Suffix Array Construction", ALENEX 2005: Algorithm Engineering and Experiments (January 2005, Vancouver, Canada):
[<a href="http://algo2.iti.kit.edu/dementiev/files/DKMS05.pdf">pdf</a>] [<a href="http://algo2.iti.kit.edu/dementiev/esuffix/instances.shtml">input instances</a>] [<a href="http://algo2.iti.kit.edu/dementiev/esuffix/docu/index.html">project page</a>]
</li>
<li>
Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn: "Engineering an External Memory Minimum Spanning Tree Algorithm", TSC 04: 3rd IFIP International Conference on Theoretical Computer Science (August 24-26, 2004, Toulouse): [<a href="http://algo2.iti.kit.edu/dementiev/files/emst.ps">ps</a>] [<a href="http://algo2.iti.kit.edu/dementiev/files/emst.pdf">pdf</a>] [<a href="http://www.dominik-schultes.de/emmst/">project page</a>]
</li>
<li>
Dominik Schultes: "External Memory Spanning Forests and Connected Components" (2003)
[<a href="http://algo2.iti.kit.edu/dementiev/files/cc.pdf">report</a>] [<a href="http://algo2.iti.kit.edu/dementiev/files/cc.tgz">src tarball</a>]
</li>
<li>
Roman Dementiev, Peter Sanders: "Asynchronous Parallel Disk Sorting", SPAA 2003: 15th ACM Symposium on Parallelism in Algorithms and Architectures (June 7-9, 2003, San Diego, California, USA)
[<a href="http://algo2.iti.kit.edu/dementiev/files/DS03.pdf">pdf</a>]
</li>
</ul>
<h2>
<a href="https://sourceforge.net/projects/stxxl/"><img src="http://sflogo.sourceforge.net/sflogo.php?group_id=131632&type=1" width="88" height="31" border="0" alt="SourceForge.net Logo" /></a>
</h2>
<!-- Piwik -->
<script type="text/javascript">
var _paq = _paq || [];
_paq.push(["trackPageView"]);
_paq.push(["enableLinkTracking"]);
(function() {
var u=(("https:" == document.location.protocol) ? "https" : "http") + "://panthema.net/wik-331/";
_paq.push(["setTrackerUrl", u+"js/"]);
_paq.push(["setSiteId", "1"]);
var d=document, g=d.createElement("script"), s=d.getElementsByTagName("script")[0]; g.type="text/javascript";
g.defer=true; g.async=true; g.src=u+"js/"; s.parentNode.insertBefore(g,s);
})();
</script>
<noscript><img src="http://panthema.net/wik-331/js/?idsite=1&rec=1" style="border:0" alt="" /></noscript>
<!-- End Piwik Code -->
</body>
</html>
<!--
vim: et:ts=4:sw=4
-->