Once BlinkenSort successfully showed fascinatingly complex sorting algorithms on an LED strip using an ESP8266 (see other article), I naturally ventured to add the sound output from the Sound of Sorting program. This turned out much harder than initially thought, because the sound generation software required more processing power than available in the cheap standard microcontrollers. After much trail and error, I found out that a sufficiently new Raspberry Pi (I happened to have a Pi 3 model B) has the rare combination of enough compute power, can drive an LED strip directly via SPI, and has an audio line-out.

The Raspberry Pi, however, cannot drive the same type of LED strip reliably as the ESP8266 can, because the Raspberry Pi runs a time-shared Linux system instead of a real-time program. But it can drive the more expensive APA102 or SK9822 LEDs which have a separate clock line. These are 4-pin LED strips with clock and data, which can easily be attached to the Pi's SPI output pins. Furthermore, the APA102 LEDs can be driven at a much higher refresh rate than the WS2812B and SK6812, due to the extra clock signal. This ultimately makes the sorting animations even smoother than with the ESP8266 (where the frame rate is already unnoticeable). I could not find any off-the-shelf library to drive the APA102 with a C++ program on the Pi, but it was trivial to write a frame buffer class and access the /dev/spi0.0 devices directly.

Then there was the question of adding a display. And after more experimentation, I found the MAX7219 dot LED matrix modules work well. These can also be driven by SPI from the Pi, which actually has two SPI outputs on the models with 40 pins. And as a bonus these dot LED matrix models can pull off an amazing frame rate. That means that besides showing the algorithm name, the super-fast refresh rate enables displaying of (nearly) every comparison counter increment, despite the human viewer only being able to see around 25 changes per second. Simply adding a HDMI display to the Pi would have also worked, but the LED matrix is cooler and has a retro feeling to it.

As you can see in the following YouTube video, each algorithm does something quite different which makes this a very interesting art installation with deep connections to informatics. BlinkenSort currently contains the following eighteen sorting algorithms (listed in the same order as in the video): MergeSort, Insertion Sort, QuickSort (LR) Hoare, QuickSort (LL) Lomoto, QuickSort Dual Pivot, ShellSort, HeapSort, CycleSort, RadixSort-MSD (High First), RadixSort-LSD (Low First), std::sort, std::stable_sort, WikiSort, TimSort, Selection Sort, Bubble Sort, Cocktail-Shaker Sort, and BozoSort. Besides sorting algorithms the collection also contains four hash table implementations: Linear Probing Hash Table, Quadratic Probing Hash Table, Cuckoo-Hashing with two places, and Cuckoo-Hashing with three places.

The video above (https://youtu.be/kAjQ8shElP8) shows the LED strip with sound in action and I added a voice-over commentary about the algorithms. There is also a second YouTube video available, without my commentary.

All source code for the sorting algorithms and other Neopixel animations is available from Github:
https://github.com/bingmann/BlinkenAlgorithms.git

About two years ago I first got my hands on one of the fancy addressable "Neopixel" LED strips, which can be programmed to show colorful animations. I quickly saw there was one project I just had to do with these strips: use them to display sorting algorithms as animations. Since my Sound of Sorting project already contained the source code for many algorithms, the step to using an addressable LED strip as a "display" was not a large one. The strips can be animated using microcontrollers such as the Arduino or Espressif ESP chips, which have way enough compute power for running sorting algorithms on a few hundred items. Since all sorting algorithms run on random input data and may make random decisions themselves, the shown animations are near infinitely varying and fascinatingly complex.

The outcome of my project of displaying sorting algorithms on LED strips are two pieces of art:

• "BlinkenSort", which are sorting algorithms animated on SK6812 RGBW LEDs using an ESP8266 microcontroller, is described in this article.
• "BlinkenSort with Sound", which are sorting algorithms animated using APA102 RGB LEDs and a Raspberry Pi 3 with real-time sound, is detailed in a second blog article!

For both projects I created a YouTube video and provide a construction manual on this website if you are interested in the internals or want to build something similar.

Today was the ceremonial graduation day on which new bachelors, masters, and also Dr.s (PhDs in the Anglo-Saxon world) were celebrated who received their degrees from the department of informatics at the Karlsruhe Institute of Technology (KIT) within the last year. This year's graduation day coincided with the 50th anniversary of the introduction of computer science as a field of study and as a diploma degree.

I was among those honoured for completing the Dr. last year, (see my dissertation page). In total 44 freshly minted Dr.s, 292 masters, and 261 bachelors where celebrated today.

Furthermore, I was awarded the Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for the best dissertation in the field of fast algorithms in the academic year 2017/2018 at the KIT department of informatics by the talent committee of the department.

I would like to thank Uniserv for endowing the department and my dissertation with this prize and especially the talent committee for selecting my work. It was a great and pleasant surprise to receive such a notification in the morning email inbox, which as usual contained many "prize and distant inheritance" emails. But on that day one of them was real, and I nearly overlooked it.

My dissertation was the central purpose in my life for many years, and receiving the prize helps me feel the time was well spent and consider it as confirmation of having furthered the field of informatics a tiny bit. It is rare to receive such honours and I am truly grateful.

Uniserv wrote a much longer honorific press release in German.

The road to a Dr. title (PhD in the Anglo-Saxon world) is often long, rough, and twisted. First you have to do original research, produce novel results, publish articles, and then write and ultimately publish a dissertation. Defending your research in the dissertation in front of a panel of professors is one of the final milestones on that journey.

On July 3rd, I successfully defended my dissertation at the Karlsruhe Institute of Technology and the dissertation text has now been published as a book.

Published Dissertation

My final dissertation PDF is available here: dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf .

It has also been published at the KIT library, on arXiv:1808.00963, and finally as a print-on-demand paperback from Amazon.

The published book cover's background shows a list of most common words in the Wikipedia. The words are sorted and their distinguishing prefix is marked in blue. The cover is available as a double-page PDF: dissertation-cover.pdf , and as front and back separately: dissertation-cover-front.pdf and dissertation-cover-back.pdf .

The LaTeX source code for my dissertation is available for download: dissertation-source.zip (791 KiB). The complete text is in one .tex file, all figures (except the creative commons logo) are generated from the LaTeX code.

Dissertation Defense Presentation

The slides of my presentation during the defense are available for download here: dissertation-defense-slides.pdf .

The presentation was only part of the whole defense. My actual slide set also had almost 200 more backup slides, which however were collected from all the other talks already available on this homepage. These backup slides helped greatly in the examination question after the presentation.

After a long exhausting period with many interruptions my diploma thesis in mathematics "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" is finalized and submitted. The full abstract of the thesis is shown below, and an additional German abstract is available further down the page.

The final version of the thesis is available here: thesis pdf , and was also uploaded to arXiv.org as 1601.03526.

The underlying problem discussed in the thesis is best explained using a game on a bispanning graph. You can play the game with this Java Applet or using the Java WebStart Launcher (if the Applet does not work). You play Alice's role and want to flip the colors of all edges in the graph. Bob will try to prevent this from happening.

In addition to the thesis itself, the source code of the accompanying computer program is also available. It was used while preparing the thesis to calculate exchanges graphs and to test many hypothesis about bispanning graphs. The program can enumerate all bispanning graphs and their exchange graphs for small numbers of vertices. See the program page for downloadable lists and PDFs of all bispanning graphs for small numbers of vertices.

Abstract

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

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

Little did I expect what would happen when coding the Sound of Sorting demo program. The initial motivation was to create a program that counts the number of comparisons of sorting algorithms, so that the students in our lecture "Algorithms 1" could compare the results of theoretical analysis and real implementations. There were many programs similar to the one I finally made, but there was no program in which the sorting algorithms were easily readable, and not entwined with visualization code. I needed the third-year students to see "simple" code and at the same time have comparison counting and nice visualizations. And none of the existing programs highlighted the internal workings of the algorithms well.

These were the initial goals what became the Sound of Sorting. The program itself took only about seven days of coding work, which was done from the 17th to 21st of May this year. The program had to be finished for the lecture on the 22nd, so there was a hard deadline to meet. The videos were created on the following weekends, and additional algorithms were added later.

Adding sound effects was very much an afterthought, because I had done some similar work previously with manipulating waveforms. Thus there was no learning curve to overcome to have comparisons play sounds. What kind of sound to play, however, needed a lot of artistic touch, trial and error, and the ability to map and transform frequency, oscillators and envelopes as needed. Forming, mixing and bending sound waves as done in the Sound of Sorting requires a mathematical mindset and some appropriate background.

The by-product of this demo program for teaching sort algorithms was the YouTube video "15 Sorting Algorithms in 6 Minutes" which, to my great surprise, went viral on social networks and was viewed 420.000 times to-date. I'm glad that many people with otherwise no connections to algorithmics find this video interesting, and hope that those with further interest view the slower videos, which provide more insight into the algorithms.

Today, the video infected the front page of my current employer: the Department of Informatics at the Karlsruhe Institute of Technology (KIT), which is of course whom I originally made the demo program for. The text, which I wrote for that occasion, can be viewed in German at the original news article about the viral video (or in the screenshots below). I have translated it into English below, since it contains some further comments about the video.

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

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.

Yesterday I was tasked to analyzed an inner function of a reasonably complex software package. The inner function was called thousands of times from many different parts of the program, a simple counter print-out showed that. However I was interested in which execution paths reach this inner function and how often the different parts access the function.

My straight-forward idea was to dump a stack backtrace each time the inner function is called, similar to the one printed by a debugger. However I needed some code snippet to dump the stack backtrace programmatically, without using gdb to halt the program each time.

Stack backtraces can be saved with backtrace(3), resolved into symbolic names using backtrace_symbols(3) and printed using backtrace_symbols_fd(3). These functions are well documented and fairly easy to use.

However I was debugging a C++ program, which made heavy use of templates and classes. C++ symbols names (including namespace, class and parameters) are mangled by the compiler into plain text symbols: e.g. the function N::A<int>::B::func(int) becomes the symbol _ZN1N1AIiE1B4funcEi. This makes the standard backtrace output very unreadable for C++ programs.

To demangle these strings the GNU libstdc++ library (integrated into the GNU Compiler Collection) provides a function called __cxa_demangle(). Combined with backtrace(3) a pretty stack backtrace can be outputted. The demangling function only works for programs compiled with g++.

The following header file contains a function print_stacktrace(), which uses backtrace(3), backtrace_symbols(3) and __cxa_demangle() to print a readable C++ stack backtrace.

The zlib library can be found on virtually every computer. It is THE general-purpose lossless patent-free compression library.

This small C++ code snippet features a pair of functions which use this ubiquitous library to compress ordinary STL strings. There are many uses for this code snippet, like compressing string data stored in a database or binary data transfered over a network. Keep in mind that the compressed string data is binary, so the string's c_str() representation must be avoided.

To compile the following small program use "gcc testzlib.cc -o testzlib -lz" where testzlib.cc is the code.

// Copyright 2007 Timo Bingmann <tb@panthema.net>
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include <string>
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <sstream>

#include <zlib.h>

/** Compress a STL string using zlib with given compression level and return
  * the binary data. */
std::string compress_string(const std::string& str,
                            int compressionlevel = Z_BEST_COMPRESSION)
{
    z_stream zs;                        // z_stream is zlib's control structure
    memset(&zs, 0, sizeof(zs));

    if (deflateInit(&zs, compressionlevel) != Z_OK)
        throw(std::runtime_error("deflateInit failed while compressing."));

    zs.next_in = (Bytef*)str.data();
    zs.avail_in = str.size();           // set the z_stream's input

    int ret;
    char outbuffer[32768];
    std::string outstring;

    // retrieve the compressed bytes blockwise
    do {
        zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
        zs.avail_out = sizeof(outbuffer);

        ret = deflate(&zs, Z_FINISH);

        if (outstring.size() < zs.total_out) {
            // append the block to the output string
            outstring.append(outbuffer,
                             zs.total_out - outstring.size());
        }
    } while (ret == Z_OK);

    deflateEnd(&zs);

    if (ret != Z_STREAM_END) {          // an error occurred that was not EOF
        std::ostringstream oss;
        oss << "Exception during zlib compression: (" << ret << ") " << zs.msg;
        throw(std::runtime_error(oss.str()));
    }

    return outstring;
}

/** Decompress an STL string using zlib and return the original data. */
std::string decompress_string(const std::string& str)
{
    z_stream zs;                        // z_stream is zlib's control structure
    memset(&zs, 0, sizeof(zs));

    if (inflateInit(&zs) != Z_OK)
        throw(std::runtime_error("inflateInit failed while decompressing."));

    zs.next_in = (Bytef*)str.data();
    zs.avail_in = str.size();

    int ret;
    char outbuffer[32768];
    std::string outstring;

    // get the decompressed bytes blockwise using repeated calls to inflate
    do {
        zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
        zs.avail_out = sizeof(outbuffer);

        ret = inflate(&zs, 0);

        if (outstring.size() < zs.total_out) {
            outstring.append(outbuffer,
                             zs.total_out - outstring.size());
        }

    } while (ret == Z_OK);

    inflateEnd(&zs);

    if (ret != Z_STREAM_END) {          // an error occurred that was not EOF
        std::ostringstream oss;
        oss << "Exception during zlib decompression: (" << ret << ") "
            << zs.msg;
        throw(std::runtime_error(oss.str()));
    }

    return outstring;
}

/** Small dumb tool (de)compressing cin to cout. It holds all input in memory,
  * so don't use it for huge files. */
int main(int argc, char* argv[])
{
    std::string allinput;

    while (std::cin.good())     // read all input from cin
    {
        char inbuffer[32768];
        std::cin.read(inbuffer, sizeof(inbuffer));
        allinput.append(inbuffer, std::cin.gcount());
    }

    if (argc >= 2 && strcmp(argv[1], "-d") == 0)
    {
        std::string cstr = decompress_string( allinput );

        std::cerr << "Inflated data: "
                  << allinput.size() << " -> " << cstr.size()
                  << " (" << std::setprecision(1) << std::fixed
                  << ( ((float)cstr.size() / (float)allinput.size() - 1.0) * 100.0 )
                  << "% increase).\n";

        std::cout << cstr;
    }
    else
    {
        std::string cstr = compress_string( allinput );

        std::cerr << "Deflated data: "
                  << allinput.size() << " -> " << cstr.size()
                  << " (" << std::setprecision(1) << std::fixed
                  << ( (1.0 - (float)cstr.size() / (float)allinput.size()) * 100.0)
                  << "% saved).\n";

        std::cout << cstr;
    }
}