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.

See the disk-filltest project page for more information about version 0.7.

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.

See the malloc_count project page for more information about version 0.7.

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 available: alenex13esais-slides.pdf . They contain little text and an example of the eSAIS algorithm with a simplified PQ.

We have also submitted a full version of the eSAIS paper to a journal. Due to long publication cycles, we make a pre-print of the journal article is available here: esais-preprint.pdf . The full paper contains more details on the inducing algorithm for the LCP array and additional experimental details.

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).

eSAIS and DC3 with LCP version 0.5.4 (current) updated 2013-12-13
Source code archive: (includes STXXL 1.4.0)	eSAIS-DC3-LCP-0.5.4.tar.bz2 (1.37 MiB)	Browse online
Git repositories	Suffix and LCP construction algorithms git clone https://github.com/bingmann/eSAIS cd eSAIS; git submodule init; git submodule update
	STXXL 1.4.0 git clone https://github.com/stxxl/stxxl

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.

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf (2.79 MiB).

After four years I have decided to release an updated version 0.8.6 of the STX B+ Tree C++ Template Classes package. The updated release contains all patches that have accumulated in my inbox over the years. So yes, please send me patches for this project, it is not in vain! Below the highlights on the changes in this release:

• Implemented a missing function: erase(iterator iter) by recursively searching for the referenced leaf node inside the subtree containing equal keys.
• Applied a patch which adds support for STL allocators as template parameters.
• Corrected limits of a for loop when shifting pairs from left to right leaf nodes during deletion.

I also reran the speed test done back in 2007 on my new hardware and compared the results with the old data. Due to the larger L2 cache sizes in my new Intel Core i7, the B-tree speed-up first starts to show at about 100,000 integer items, rather than 16,000 items with my older Pentium 4. This might also have something to do with the new CPU using 64-bit pointers and thus requiring larger nodes for child references. Read the complete speed test here.

The updated source code package is available for download from this webpage.