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

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:

• To have a library of well implemented and tested advanced algorithms and things missing from the C++ STL.
• Target high modularity with as little dependencies between modules as possible.
• Zero external dependencies: no additional libraries are required.
• Only have compile time configuration (no platform dependent checks).
• Compile on all platforms with C++ -- smartphones, supercomputers, windows, maybe even embedded microcontrollers.
• Attempt to never break existing interfaces.
• Warning and bug-freeness on all compilers.
• Keep overhead down -- small overall size such that is can be included without bloating applications.
• Collect code only under the Boost license, which one of the most liberal licenses and can be used any project.

Currently, tlx contains

• The fast tournament (loser) trees from MCSTL by Johannes Singler, with many fixes.
• A fast intrusive reference counter called CountingPtr, which has considerably less overhead than std::shared_ptr.
• Efficient and fast multiway merging algorithms from Johannes Singler, which were previously included with gcc. The tlx version has many fixes and is available for clang and MSVC++.
• Many string manipulation algorithms for std::string.
• An improved version of my stx-btree implementation, which is basically always a better alternative to std::map (but not std::unordered_map).
• A copy of siphash for string hashing.
• Efficient sequential string sorting implementation such as radix sort and multikey quicksort (described in length in my PhD thesis).

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