panthema (page 1 of 1 2 3 4 5 6 7 8 9 10)

Welcome to panthema.net

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:

Open-Source Projects

since 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.
since 2018-05-28
TLX
Collection of Sophisticated C++ Data Structures, Algorithms, and Miscellaneous Helpers
2014-10-29
STXXL 1.4
Library of external memory algorithms, including external block paging and efficient external sorting
2014-09-19
malloc_count 0.7.1
Simple tool for run-time memory usage analysis and profiling under Linux
2014-07-02
vncrec-rgb 0.4
Patched vncrec for frame-perfect high-resolution screencasts.
2014-05-15
The Sound of Sorting 0.6.5
Viral "audibilization" and visualization of sorting algorithms
2014-03-17
SqlPlotTools
Automatically import key=value experimental RESULTS into SQL tables and generate plots from them.
2013-12-12
pmbw 0.6.2
Benchmark tool for parallel memory bandwidth / measurement under Linux
2013-05-07
disk-filltest 0.7.1
Tool to detect bad disks by filling with random data
2013-05-05
STX B+ Tree 0.9
Main memory B+ tree implementation with STL compatible interfaces
2011-01-30
digup 0.6.40
Console tools to verify file integrity by updating MD5 and SHA digest files
2011-01-30
CryptoTE 0.5.390
Text editor with transparent strong encryption, useful for password lists and more.
2010-07-30
STX ExecPipe 0.7.1
Convenient C++ interface to execute child programs connected via Unix pipes.
2009-09-05
Flex Bison C++ Example 0.1.4
Example of using GNU flex and bison in a C++ program.

Computer Science Research

2015-04-03
External Memory Algorithms
Additionally to maintaining STXXL, we also developed a bulk-parallel priority queue for EM.
2014-03-09
Parallel String Sorting
Experimental 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 Sorting
Experimental implementation of eSAIS and DC3, two suffix and LCP array construction algorithms for external memory, using STXXL.

Miscellaneous Weblog Posts

2018-07-03  Dissertation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools"
2016-01-14  "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" - Diploma Thesis in Mathematics
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

Weblog

Photo of a Uniserv prize and my dissertation

(Foto: Andreas Drollinger, KIT)

Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for my Dissertation

Posted on 2019-06-19 19:00 by Timo Bingmann at Permlink with 1 Comments. Tags: dissertation university

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


YouTube Video: "Animation of the US Treasury Yield Curve with Inversions from 1962-01-01 to 2019-04-01"

Posted on 2019-04-03 23:30 by Timo Bingmann at Permlink with 0 Comments. Tags: market fun

Today I published the first animation of market data by my new charting tool on Youtube. In light of recent events this was an video of inversions of the US Treasury Yield Curve. The video is created with QCustomPlot and a large Qt program to process data.

The dancing green line plots the yields of all constant maturity treasury notes. The trailing blue line shows the efficient 30 day Federal Funds rate. The orange line is the broad stock market SPX index. The background of each day is painted red if an inversion of the 1y/5y, 1y/10y, or 2y/10y yields occurs. The darker the red color, the greater the inversion.

Watch the yield curve and the stock market index change over the decades, notice their behaviour in times of crisis. The video ends with the current inversion around April 2019. More about the yield curve and inversions: https://en.wikipedia.org/wiki/Yield_curve#Inverted_yield_curve

The Federal Funds rate data was taken from FRED (Federal Reserve Bank of St. Louis), series DFF: https://fred.stlouisfed.org/series/DFF. The US Treasury yields data was also taken from FRED, series DGS1MO, DGS3MO, DGS1, DGS2, DGS5, DGS7, DGS10, DGS20, DGS30, e.g. https://fred.stlouisfed.org/series/DGS30. Across the decades the various durations were sometimes not emitted, which is visible by points being added or removed from the green curve. SPX data was taken from Stooq.com, series ^SPX.


Photo of a Samsung NVMe SSD

NVMe "Disk" Bandwidth and Latency for Batched Block Requests

Posted on 2019-03-22 16:00 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ stxxl thrill

Last week I had the pleasure of being invited to the Dagstuhl seminar 19111 on Theoretical Models of Storage Systems. I gave a talk on the history of STXXL and Thrill, but also wanted to include some current developments. Most interesting I found is the gap closing between RAM and disk bandwidth due to the (relatively) new Non-Volatile Memory Express (NVMe) storage devices.

Since I am involved in many projects using external memory, I decided to perform a simple set of fundamental experiments to compare rotational disks and newer solid-state devices (SSDs). The results were interesting enough to write this blog article about.

Among the tools of STXXL/FOXXLL there are two benchmarks which perform two distinct access patterns: Scan (benchmark_disks) and Random (benchmark_disks_random).

The Scan experiment is probably the fastest access method as it reads or writes the disk (actually: storage device) sequentially. The Random experiment is good to determine the access latency of the disk as it first has to seek to the block and then transfer the data. Notice that the Random experiment does batched block accesses like one would perform in a query/answering system where the next set of random blocks depends on calculations performed with the preceding blocks (like in a B-Tree). This is a different experiment than done by most "throughput" measurement tools which issue a continuous stream of random block accesses.

This blog entry continues on the next page ...

First slide of the talk

Presentation "Scalable Construction of Text Indexes with Thrill" at IEEE Big Data 2018

Posted on 2018-12-12 16:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk thrill

Today, I gave a presentation of our paper "Scalable Construction of Text Indexes with Thrill" at the IEEE International Conference on Big Data 2018 in Seattle, WA, USA.

The slides of the presentation at the IEEE conference are available here:
slides-Scalable-Construction-of-Text-Indexes-with-Thrill.pdf slides-Scalable-Construction-of-Text-Indexes-with-Thrill.pdf.

The full paper is available from this webpage: paper-Scalable-Construction-of-Text-Indexes-with-Thrill.pdf paper-Scalable-Construction-of-Text-Indexes-with-Thrill.pdf
or refer to the longer version in my dissertation on scalable suffix array construction.

Download Scalable-Construction-of-Text-Indexes-with-Thrill.pdf

Abstract

The suffix array is the key to efficient solutions for myriads of string processing problems in different application domains, like data compression, data mining, or bioinformatics. With the rapid growth of available data, suffix array construction algorithms have to be adapted to advanced computational models such as external memory and distributed computing. In this article, we present five suffix array construction algorithms utilizing the new algorithmic big data batch processing framework Thrill, which allows scalable processing of input sizes on distributed systems in orders of magnitude that have not been considered before.


Print Quality of Print-On-Demand Books from Amazon Createspace/KDP, epubli.de, and Ingram Spark

Posted on 2018-11-05 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: dissertation

Having just finished my PhD thesis in computer science (see the corresponding dissertation), I ventured to actually print it as a proper book. In this article I want to share some of my experience with three print-on-demand book publishers:

Disclaimer: these are my experiences, yours will probably be different. And I hope print-on-demand quality will improve further in the future.

Below are macro photographs of the various print proof and other copies I received from the publishers. The photographs were taken with a Samsung Galaxy S9 smartphone with a (cheap) macro lens. Hence the colors and blur in the photos should be considered with caution, but the sharpness and detail level is sufficient for some discussion.

TL;DR: Amazon's print proof from the USA has the nicest print and color, but they only produce paperback covers. IngramSpark's prints are second best, have a lower resolution, but they produce hardcovers and consistent quality.

Amazon Print Proof from the USA

   

Uploading the PDF to Amazon CreateSpace is straight-forward due to the convenient web interface. The Amazon CreateSpace print proof was manufactured in Lexington, KY, USA, it was shipped three days after ordering, and arrived eleven days after ordering. For an international shipment from the USA to Germany that is a very acceptable delivery time.

The print quality of the Amazon Print Proof was in my option the best. It has the highest resolution, bright colors, and solid black. The paper and entire book has the feel of high-quality color laser printer output. Sadly, they the only produce paperback softcover books and I preferred a hardcover. On the plus side, publishing via Amazon gives you a free CreateSpace-ISBN and it is immediately listed in the world-wide Amazon catalog.

Original PDF

   

As a comparison to the printed books, the pictures above show the same excepts rendered as a bitmap image. Note that the layout of the words in each cover image may differ, because each cover needed to by typeset individually to the individual specifications of the publisher.

This blog entry continues on the next page ...

First slide of the talk

Tutorial on Boost.Spirit at C++ User Group Karlsruhe

Posted on 2018-09-12 19:30 by Timo Bingmann at Permlink with 0 Comments. Tags: talk c++ parsing

On September 12th, 2018, I gave another 90min talk with live-coding examples in German at the C++ User Group Karlsruhe in rooms of the Karlsruhe Institute of Technology (KIT).

This time I was asked to present a more advanced topic around C++ and libraries and I chose to present a tutorial on Boost.Spirit.

Boost.Spirit is a parser and generator template meta-programming framework and maybe one of the most crazy and advanced uses of C++. It enables one to write context-free grammars inline as C++ code, which are translated into recursive descent parsers and fully optimized by the compiler.

This powerful framework is however not easy to get started with. I hope my tutorial helps more people to skip the steep learning curve and use Boost.Spirit for securely parsing user input and other structure data.

The tutorial consisted of a set of introduction slides: slides-2018-09-12-Cpp-Meetup.pdf slides-2018-09-12-Cpp-Meetup.pdf. Followed by a live-coding session in German which was recorded by the KIT (see below for the youtube video).

Download slides-2018-09-12-Cpp-Meetup.pdf

The extensive code examples presented in the live coding session are available on this webpage
or on github: https://github.com/bingmann/2018-cpp-spirit-parsing.

The examples can be seen as instructive templates and copy & paste sources for new development. The examples are:

  1. Learn to walk and parse simple integers and lists.
    Parse 5, [5, 42, 69, 256].
  2. Create a parser for a simple arithmetic grammar (and part two).
    Parse 5 + 6 * 9 + 42 and evaluate correctly.
  3. Parse CSV data directly into a C++ struct.
    Parse AAPL;Apple;252.50; into a struct.
  4. Create an abstract syntax tree (AST) from arithmetic (and part two).
    Parse y = 6 * 9 + 42 * x and evaluate with variables.
  5. Ogle some more crazy examples, e.g. how to parse.
    <h1>Example for <b>C++ HTML Parser<b></h1>
    This HTML <b>snippet</b> parser can also interpret
    *Markdown* style and enables additional tags
    to <% invoke("C++", 42) %> functions.

Furthermore, a recording of the live-coding in German is available on Youtube:
https://www.youtube.com/watch?v=gYAheppw73U


Book Cover of Dissertation

Dissertation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools"

Posted on 2018-07-03 18:00 by Timo Bingmann at Permlink with 1 Comments. Tags: talk university dissertation frontpage

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 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 dissertation-cover.pdf, and as front and back separately: dissertation-cover-front.pdf dissertation-cover-front.pdf and dissertation-cover-back.pdf dissertation-cover-back.pdf.

The LaTeX source code for my dissertation is available for download: dissertation-source.zip 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 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.

Download dissertation-defense-slides.pdf
This blog entry continues on the next page ...

TLX Logo

Note about the new tlx library of Advanced C++ Data Structures and Algorithms

Posted on 2018-05-28 18:20 by Timo Bingmann at Permlink with 0 Comments. Tags: c++

Last year on February 19th, I started a new github repository called tlx with the goal of de-duplicating code from three projects: Thrill, STXXL, and a private project. The idea came up after a STXXL code workshop in Frankfurt (fashionably called hackathons nowadays).

Link to library: http://github.com/tlx/tlx and Doxygen Documentation

The first main common pieces of code were:

  1. the fast loser tree implementations from MCSTL by Johannes Singler necessary for efficient multiway merging,
  2. my die() macros for testing and run-time assertions,
  3. a common intrusive reference counter called counting_ptr, and
  4. simple but vital std::string manipulation functions missing from the STL.

The initial reason for tlx to come about was to consolidate all the bug fixes to the loser tree implementations that I had scattered across the three projects. Efficient multiway merging is such a fundamental task and there was no universally available C++ library that implements the tournament tree well.

A long search for an appropriate vacant user account with three letters on github lead to "tlx". This is definitely a good C++ namespace name, but to this day, it is unclear what the letters stand for. Template Libraries for CXX? The missing Library for CXX? Template Library and more eXtensions. Have your pick, someday someone will find a good official expansion.

Since its inception, tlx has grown a lot. Its goal is to consolidate algorithms and data structures from multiple projects. In a sense tlx maybe aims to be the Boost for advanced algorithms. The goals and constraints of tlx are:

Currently, tlx contains

And much more, which one can find on the front page of the Doxygen Documentation


First slide of the talk

Presentation "C++ Goodies" at C++ User Group Karlsruhe

Posted on 2017-03-08 00:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk c++

On March 8th, 2017, I gave a 90min talk in German at the C++ User Group Karlsruhe which consisted mostly of live-coding examples of how to use new C++11/14/17 features in a practical setting. The contents were:

The source code I wrote for the presentation and the slides
are available in a github repository https://github.com/bingmann/2017-cpp-goodies.

Furthermore, a recording of talk in German is available on Youtube: https://www.youtube.com/watch?v=EvSZHXmXR1M


First slide of the talk

Presentation "Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++" at IEEE Big Data 2016

Posted on 2016-12-06 16:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk thrill

Today, I gave a presentation of our paper "Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++" at the IEEE International Conference on Big Data 2016 in Washington D.C., USA. An extended technical report of our paper is also available on this website or on arXiv.

The slides of the presentation at the IEEE conference are available here:
slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP-TalkAsGiven.pdf slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP-TalkAsGiven.pdf.

Below a longer version of the slides is available for download:
slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf.
These slides contain additional figures which are useful to understand the DIA operations in Thrill, along with many extra design slides omitted from shorter talks.

Download slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf

Show Page: 1 2 3 4 5 6 7 8 9 10 Next >
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2019 Timo Bingmann - Impressum