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 history about STXXL can be found in the blog post to 1.4.0. Today, the second release of the new 1.4 branch was published:

What's new in 1.4.1 ?

• Integrated support for kernel based asynchronous I/O on Linux (new file type "linuxaio"), which exploits Native Command Queuing (NCQ) if available.
• Merged stxxl::unordered_map branch, which provides a hash map backed by external memory.
• Replaced struct default_completion_handler with a NULL pointer, thus avoiding superfluous new/delete work for each I/O request.
• Added stxxl::external_shared_ptr which is a proxy class to allow use of shared_ptr classes inside stxxl containers.
• Fixing bugs and warnings on 32-bit systems (yes, they still exist).
• Use atomic_counted_object in class file for request reference counting.
• Adding support for MinGW-w64 (64-bit) systems with working SJLJ thread implementations.

See the CHANGELOG for further minor changes.

Some time last week my YouTube video "15 Sorting Algorithms in 6 Minutes" reached 1 million views. The original video was uploaded on 2013-05-20 which is just 524 days ago, so on average about every 45.2 seconds someone started to watch the video (which itself is about 6 minutes long). The world is a really big place. Most of the views, however, occured in spikes of interest, as seen in the graph below.

The original video contained only 15 algorithms. The program "Sound of Sorting" itself, which was used to create the animations, now contains 30 algorithms or variants. For some of the additional algorithms I also created videos on YouTube, which are also worthwhile watching.

There are two parallel algorithms based on sorting networks, where each left-to-right sweep is one parallel sorting step:

• Batcher's Odd-Event Mergesort and Batcher's Bitonic Sort

An algorithm, which is optimal in terms of the number of writes to sort the array:

• Cycle Sort

An adaptive sorting algorithm which detects presorted areas, and is used in many modern programming language runtime libraries:

• Tim Sort

An in-place stable mergesort with O(1) extra space:

• Block Merge Sort (WikiSort)

And two algorithms, that have a high asymptotic worst-case complexity, and are thus more a joke, but still pretty to watch:

• Slow Sort and Stooge Sort

Last Friday we were able to finish a technical report on "Practical Massively Parallel Sorting -- Basic Algorithmic Ideas", which is now available on arXiv as 1410.6754 or locally: 1410.6754v1.pdf with source 1410.6754v1.tar.gz (130 KiB). A big thanks goes to all the other authors, Michael Axtmann, Peter Sanders, and Christian Schulz.

The report proposes two new hierarchical algorithms "Recurse Last Mergesort" (RLM-Sort) and "Adaptive Multipass Sample Sort" (AMS-Sort), together with randomized data exchange schemes to avoid worst case behavior on large instances.

We now plan to implement some of the new algorithms.

Last week I produced a recording of a talk about "STXXL 1.4.0 and Beyond". I thought it would be trivial in the year 2014 to create a frame-perfect high-resolution recording of a PDF presentation slideshow with moving mouse cursor on Linux. I was so wrong.

In the end, I created a patched version of vncrec: now called "vncrec-rgb 0.4", and the tutorial on the vncrec-rgb webpage. But now, why do screen recording with vncrec?

This is a recording of a talk that I gave last week at the 3rd LSDMA Topical Meeting in Berlin. The talk covers a basic introduction into the STXXL library's features and contains many short code examples that serve as a tutorial.

The slides of the presentation 2014-06-22 STXXL 1.4.0 and Beyond.pdf are available online and the recorded talk can be seen on Youtube video below.

And here is the video of the recording: https://www.youtube.com/watch?v=UswxcAOJKBE

This short post announces the second public version of our parallel string sorting project. It is a test framework and algorithm collection containing most sequential and parallel string sorting implementations.

The collection includes parallel super scalar string sample sort (pS⁵), which we developed and showed to have the highest parallel speedups on modern single-socket multi-core shared memory systems. Additionally, the collection now contains parallel multiway LCP-mergesort, which can be used to speed up string sorting on NUMA multi-socket machines.

See the parallel-string-sorting project page for our technical report and more information about version 0.6.