This website is a diverse collection of **interesting ideas**, thus it is **panthematic**. It contains free open-source software and projects (FOSS), computer science research results, blog articles and more, all created by myself, Timo Bingmann. Over the years, the amount of information, source code and other content has grown rather large. All entries are ordered chronologically in the weblog, with some special projects highlighted in the following summary:

2015-08-22

Thrill (in development)A C++ framework for distributed Big Data computations with emphasis on high performance and a convenient interface like Apache Spark or Flink.

2014-10-29

STXXL 1.4Library of external memory algorithms, including external block paging and efficient external sorting

2014-09-19

malloc_count 0.7.1Simple tool for run-time memory usage analysis and profiling under Linux

2014-03-17

SqlPlotToolsAutomatically import key=value experimental RESULTS into SQL tables and generate plots from them.

2011-01-30

CryptoTE 0.5.390Text editor with transparent strong encryption, useful for password lists and more.

2010-07-30

STX ExecPipe 0.7.1Convenient C++ interface to execute child programs connected via Unix pipes.

2015-04-03

External Memory AlgorithmsAdditionally to maintaining STXXL, we also developed a bulk-parallel priority queue for EM.

2014-03-09

Parallel String SortingExperimental implementations of many string sorting algorithms, including Parallel Super Scalar String Sample Sort (pS5) and Parallel Multiway LCP-Mergesort

2012-11-19

External Memory Suffix SortingExperimental implementation of eSAIS and DC3, two suffix and LCP array construction algorithms for external memory, using STXXL.

2014-10-26 1.000.000 Views of Sound of Sorting YouTube Video

2014-06-22 Recording of a Talk "STXXL 1.4.0 and Beyond"

2013-10-24 Sound of Sorting: Viral Video on KIT Informatik Webpage

2013-05-06 STX B+ Tree Speed Test Measurements on Raspberry Pi (Model B)

2013-05-05 STX B+ Tree Measuring Memory Usage with malloc_count

2013-01-24 Coding Tricks 101: How to Save the Assembler Code Generated by GCC

2008-09-01 C++ Code Snippet - Print Stack Backtrace Programmatically with Demangled Function Names

2007-03-28 C++ Code Snippet - Compressing STL Strings with zlib

2014-06-22 Recording of a Talk "STXXL 1.4.0 and Beyond"

2013-10-24 Sound of Sorting: Viral Video on KIT Informatik Webpage

2013-05-06 STX B+ Tree Speed Test Measurements on Raspberry Pi (Model B)

2013-05-05 STX B+ Tree Measuring Memory Usage with malloc_count

2013-01-24 Coding Tricks 101: How to Save the Assembler Code Generated by GCC

2008-09-01 C++ Code Snippet - Print Stack Backtrace Programmatically with Demangled Function Names

2007-03-28 C++ Code Snippet - Compressing STL Strings with zlib

Posted on 2016-01-14 18:30 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

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

Bispanning graphs are undirected graphs with an edge set that can be decomposed into two disjoint spanning trees. The operation of symmetrically swapping two edges between the trees, such that the result is a different pair of disjoint spanning trees, is called an edge exchange or a symmetric base exchange. The graph of symmetric base exchanges of a bispanning graph contains a vertex for every valid pair of disjoint spanning trees, and edges between them to represent all possible edge exchanges. We are interested in a restriction of these graphs to only unique symmetric base exchanges, which are edge exchanges wherein selecting one edge leaves only one choice for selecting the other. In this thesis, we discuss the structure of the graph of unique symmetric edge exchanges, and the open question whether these are connected for all bispanning graphs.

This abstract problem can be nicely rephrased into a coloring game with two players: Alice and Bob are given a bispanning graph colored with two disjoint spanning trees, and Alice gets to flip the color of any edge. This creates a cycle in one color and a cut in the other, and Bob must then flip a different edge to repair the constraint that both colors represent disjoint spanning trees. Alice's objective is to invert the color of all edges in the graph, and Bob's to prevent this. We are interested in whether Alice can find a sequence of unique edge exchanges for any bispanning graph, since these leave Bob no choice in which edge to select, hence allowing Alice to win with certainty.

In this thesis, we first define and discuss the properties of bispanning graphs in depth. Intuitively, these are locally dense enough to allow the two disjoint spanning trees to reach all vertices, but sparse enough such that disjoint edge sets do not contain cycles. The whole class of bispanning graphs can be inductively constructed using only two operations, which makes the class tractable for inductive proofs.

We then describe in detail directed, undirected, and simplified versions of edge exchange graphs, first with unrestricted edge exchanges, and then with the restriction to unique symmetric base exchanges. These exchange graphs are related to a set of conjectures put forth by White in 1980 on base exchanges in matroids, and also to conjectures on cyclic base orderings of matroids. To date, these conjectures have not been proven in full generality, despite overwhelming computational evidence.

As steps towards showing the conjecture that the graph of unique symmetric base exchanges is connected for all bispanning graphs, we prove a composition method to construct the unique exchange graph of any bispanning graph from the exchange graphs of smaller bispanning graphs. Furthermore, using a computer program developed alongside this thesis, we are able to enumerate and make statements about all small bispanning graphs and their exchanges graphs.

Our composition method classifies bispanning graphs by whether they contain a non-trivial bispanning subgraph, and by vertex and edge connectivity. For bispanning graphs containing a non-trivial bispanning subgraph, we prove that the unique exchange graph is the Cartesian graph product of two smaller exchange graphs. For 2-vertex-connected bispanning graphs, we show that the bispanning graph is the 2-clique sum of two smaller bispanning graphs, and that the unique exchange graph can be built by joining their exchange graphs and forwarding edges at the join seam. And for all remaining bispanning graphs, we prove a composition method at a vertex of degree three, wherein the unique exchange graph is constructed from the exchange graphs of three reduced bispanning graphs.

We conclude this thesis with ideas and evidence for future approaches to proving the connectivity of the unique exchange graphs and show the most difficult bispanning graphs instances.

Posted on 2015-10-01 19:40 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ talk thrill

Today, we gave an overview presentation of the vision behind Project Thrill, its current state, and how it will be used to implement suffix and LCP array construction, and many other distributed algorithms: 2015-10-01 Massive Suffix Array Construction with Thrill.pdf .

Posted on 2015-09-22 15:46 by Timo Bingmann at Permlink with 0 Comments. Tags: research sorting university

Our paper "**Engineering Parallel String Sorting**" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf .

Please refer to the main parallel-string-sorting page for details and source code.

Posted on 2015-08-19 13:21 by Timo Bingmann at Permlink with 0 Comments. Tags: talk

At our institute I gave an ambitious presentation today which showcased much of **my daily work flow in emacs**. People have titled it the "emacs lightshow" due to the speed of flashing and changing lights on my screens. Of course, the idea is to show people what emacs can do and at the same time get them to try it. Emacs is different from other editors in that it is a life operating system that is infinitely complex, is constantly extended, and adapts to what you need.

For this presentation I made an emacs tutorial. There are many emacs tutorials online, and they are probably better than this one. However, I focused on listing something like **the top 100 key command sequences** that you need in **real day-to-day editing life**, instead of the most flashy features. This makes this tutorial something that you can print out, and go through step-by-step once to try everything out; and then start over and learn the most important keys from the top.

The emacs tutorial is available as a PDF: emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.pdf

or available as the org-mode source file: emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.org

and in my github`.emacs.d`

repo: https://github.com/bingmann/dot-emacs.git Posted on 2015-06-30 17:11 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ talk stxxl

We are very glad to have been given the opportunity to present our work on **bulk-parallel priority queues for external memory** at the 14th International Symposium on Experimental Algorithms (SEA 2015) in Paris. The talk was given by Thomas Keh, and the slides of the presentation are available online: 2015-06-29 A Bulk-Parallel Priority Queue in External Memory with STXXL.pdf . The implementation is available in the current master branch of STXXL at github.

Posted on 2015-04-03 14:54 by Timo Bingmann at Permlink with 0 Comments. Tags: research stxxl

Today, our technical report on "**A Bulk-Parallel Priority Queue in External Memory with STXXL**" is now available on arXiv as 1504.00545 or locally: 1504.00545v1.pdf with source 1504.00545v1.tar.gz (130 KiB). A big thanks goes to Thomas Keh for the hard work he did in his bachelor thesis, and to Peter Sanders for all the insights into priority queues. The technical report is an extended version of our paper that will appear at the 14th International Symposium on Experimental Algorithms - SEA 2015.

The bulk-parallel priority queue is current available in the development repository of STXXL on Github.

On 2015-06-29, Thomas Keh presented the PPQ at SEA'15 in Paris.

Posted on 2015-03-27 21:00 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ talk thrill

Today, I presented our work in progress on a **distributed computation platform for Big Data algorithms** at the LSDMA All-Hands-Meeting in Berlin. One of the currently proposed names is DALKIT. The talk covers the current state our student project is in, which consists mainly of the design of the framework's interface, architecture and future components.

The slides of the presentation 2015-03-27 Project DALKIT.pdf are available online. However, as usual, my slides are very difficult to understand without the audio track. For future "final" version presentations there will probably be more videos.

Posted on 2014-10-29 11:17 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ university stxxl

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.

Posted on 2014-10-26 17:30 by Timo Bingmann at Permlink with 1 Comments. Tags: sorting frontpage

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:

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

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

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

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

Posted on 2014-10-24 22:30 by Timo Bingmann at Permlink with 0 Comments. Tags: research massive-sorting

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.