This short post announces the first public version of our parallel string sorting project. It is a test framework and algorithm collection containing many 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 multi-core shared memory systems.

This blog post announces the new version 0.9 of my popular STX B+ Tree library of C++ templates, speedtests and demos. Since the last release in 2011, many patches and new ideas have accumulated. Here a summary of the most prominent changes:

• Changed the find_lower() function, which is central to finding keys or insertion points to not use binary search for small node sizes. The reasoning behind this change is discussed in another blog post.
• Added a bulk_load() to all map and set variants to construct a B+ tree from a pre-sorted iterator range. The sorted range is first copied into leaf nodes, over which then the B+ tree inner nodes are iteratively built.
• The B+ tree template source code is now published under the Boost Software License! Use it!
• More minor changes are listed in the ChangeLog.

STX B+ tree version 0.9 is available from the usual project webpage.

The switch from binary search to linear scan, and all further patches and optimization call for a direct comparison of version 0.8.6 and 0.9. Because of special optimizations to the btree_set specializations, the following plots differentiate between set and maps.

The Raspberry Pi is maybe one of the most hyped embedded system projects in the last year, and I also got myself one for experiments. People are doing amazing things with this Linux-in-a-box SoC. Doubtlessly, the popularity is due to the standardized platform and a large community forming around it, which makes fixing the many small problems with Linux on ARM systems feasible. For me, the Raspberry Pi is an alternative architecture on which to test my algorithms and libraries, which exhibits somewhat different characteristics than the highly optimized desktop CPUs.

So I decided to run my STX B+ Tree speed test on the Raspberry Pi Model B, because most people use the SoC for multimedia purposes and little other memory performance data is available. The B+ tree speed test gives insight into the platform's overall memory and processing performance, and thus yields a better assessment of how useful the system is for general purpose applications (unlike multimedia decoding). Most benchmarks focus solely on floating point or integer arithmetic, which alone are very poor indicators for overall system performance. The Raspberry Pi forums say it has performance similar to a "Pentium 2 with 300 MHz", but that is for arithmetic.

Within the next few days, a new version of my popular STX B+ Tree library will be released. In light of this imminent release, I created a memory profile with my malloc_count tool, comparing the requirements of four different C++ maps with integer keys and values.

The test is really simple: create a map container, insert 8 Mi random integer key/value pairs, and destruct it. The memory profile shows the amount of memory over time as allocated via malloc() or new. The test encompasses the usual gcc STL's map which is a red-black tree, the older hash_map from gcc's STL extensions, the newer gcc C++ tr1::unordered_map, and of course the stx::btree_map with default configuration. As a reference, I also added the usual STL vector and deque (not map containers), to verify the plotting facilities.

To isolate heap fragmentation, the profiler fork()s separate process contexts before each run. To avoid problems with multiple equal random keys, the multimap variant of all containers is used. Here is the memory profile (also included in the STX B+ Tree tarball):

While developing another piece of software, I happened to require a customizable binary search implementation, which lead me to revisit the binary search function of my quite popular STX B+ Tree implementation.

The binary search is a central component in the container, both for performance and correctness, as it is used when traversing the tree in search for a key or an insertion point. It is implemented in the find_lower() (and find_upper()) functions.

In a first step, I cleaned the implementation to use an exclusive right boundary. In this binary search variant, hi points to the first element beyond the end (with the same meaning as usual end() C++ iterator). This got rid of the special case handled after the while loop. The exclusive right boundary is also a more natural implementation variant (even though most computer science textbooks contain the inclusive version).

Having thus changed the binary search, I reran the speed tests. However, to my surprise, the performance of the library decreased slightly, but consistently. See the code diff 39580c19 and resulting speed test PDF, where solid lines are after the patch and dashed ones before.

After some research, I found a good, independent study of binary search variants by Stephan Brumme. His summary is that a linear scan is more efficient than binary search, if the keys are located in only one cache line. This (of course) explained the performance decrease I measured, as my "special case" after the search was in fact a very short linear scan of two element.

This post announces the first version of disk-filltest, a very simple tool to test for bad blocks on a disk by filling it with random data. The function of disk-filltest is simple:

• Write files random-######## to the current directory until the disk is full.
• Read the files again and verify the pseudo-random sequence written.
• Any write or read error will be reported, either by the operating system or by checking the pseudo-random sequence.
• Optionally, delete the random files after a successful run.

This post announces the first version of malloc_count, a very useful tool that I have been fine-tuning in the past months. The code library provides facilities to

• measure the current and peak heap memory allocation, and
• write a memory profile for plotting.
• Furthermore, separate stack_count function can measure stack usage.

The code tool works by intercepting the standard malloc(), free(), etc functions. Thus no changes are necessary to the inspected source code.

This is the first issue of a series of blog posts about some Linux coding tricks I have collected in the last few years.

Folklore says that compilers are among the most complex computer programs written today. They incorporate many optimization algorithms, inline functions and fold constant expressions; all without changing output, correctness or side effects of the code. If you think about it, the work gcc, llvm and other compilers do is really amazing and mostly works just great.

Sometimes, however, you want to know exactly what a compiler does with your C/C++ code. Most straight-forward questions can be answered using a debugger. However, if you want to verify whether the compiler really applies those optimizations to your program, that your intuition expects it to do, then a debugger is usually not useful, because optimized programs can look very different from the original. Some example questions are:

• Is a local integer variable stored in a register and how long does it exist?
• Does the compiler use special instructions for a simple copy loop?
• Are special conditional instructions used for an if or switch statement?
• Is a specific function inlined or called each time?

These questions can be answered definitely by investigating the compiler's output. On the Net, there are multiple "online compilers," which can visualize the assembler output of popular compilers for small pieces of code: see the "GCC Explorer" or "C/C++ to Assembly v2". However, for inspecting parts of a larger project, these tools are unusable, because the interesting pieces are embedded in much larger source files.

Luckily, gcc does not output binary machine code directly. Instead, it internally writes assembler code, which then is translated by as into binary machine code (actually, gcc creates more intermediate structures). This internal assembler code can be outputted to a file, with some annotation to make it easier to read.

This web page accompanies our conference paper "Inducing Suffix and LCP Arrays in External Memory", which we presented at the Workshop on Algorithm Engineering and Experiments (ALENEX 2013). A PDF of the publication is available from this site as alenex13esais.pdf or from the online proceedings. The paper was joint work with my colleagues Johannes Fischer and Vitaly Osipov.

The slides to my presentation of the paper on January 7th, 2013 in New Orleans, LA, USA is also available: alenex13esais-slides.pdf . They contain little text and an example of the eSAIS algorithm with a simplified PQ.

Our implementations of eSAIS, the eSAIS-LCP variants, DC3 and DC3-LCP algorithms as described in the paper are available below under the GNU General Public License v3 (GPL).

The algorithm implementations requires a special version of the STXXL library, which is also listed above. For more information about compiling and testing the implementation, please refer to the README included in the source.

This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

• Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
• Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
• Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
• Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
• Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
• Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf , which however are not self-explanatory due to my minimum-text presentation style.