std::sort in C

As some of you might already know through my Twitter, I'm currently attempting to build an advanced standard library for C, with similar performance and usage characteristics as C++'s STL.
It's going really well so far, but the sort algorithm of std::sort is giving me headaches.

In theory, it's a simple hybrid sort (since the C++11 standard requires a complexity of O(N log N) in all cases, in comparison to C++03, which only required average case performance of O(N log N)). In case of the libstdc++, it's a hybrid-3 sorting algorithm, consisting of introsort (which itself is a hybrid of quicksort and heapsort), up to a defined maximum depth (in case of libstdc++ it's log2(N) * 2), followed by an insertionsort.

The whole source code can be found on Github1, here is an excerpt of the README containing the performance benchmarks:



If compiled without any compiler optimizations, that is no -O2 or -O3, the algorithm in C performs better, compared to std::sort.

If, however, compiled with optmizations turned on (-O2 or -O3), the std::sort implementation performs better. I have yet to figure out why.


Tests are done on my GNU/Linux VM (running Debian 8).
Host is an Intel Core i7-5930K @ 3.5GHz / 32GiB RAM.
Guest has 4 Cores, 8GiB RAM.

The test consists of sorting a randomly generated array of 1 million integers.

Compiler Optimizations Time
gcc 4.9.2 -O0 -march=native ~180ms
gcc 4.9.2 -O3 -march=native ~72ms
g++ 4.9.2 -O0 -march=native ~300ms
g++ 4.9.2 -O3 -march=native ~58ms
clang 3.5 -O0 -march=native ~170ms
clang 3.5 -O3 -march=native ~65ms
clang++ 3.5 -O0 -march=native ~360ms
clang++ 3.5 -O3 -march=native ~56ms

Tests compiled with gcc or clang are testing the C implementation.
Tests compiled with g++ or clang++ are testing the C++ implementation.
The Makefile contains all you need to compile the tests yourself, and see what you got.


I wrote this in about 2 hours. Don't expect it to be either production ready code, nor bugfree, nor actually optimized to be used in another scenario than what I developed it for.


Generic Makefile

Update: Now also supports C++, see the Github repository1 for the updated file.

In every single project, or even just test, I write the same simple Makefile over and over, by now I can write it without looking up anything. And if I forgot something, I would go through my old projects, to dig up the definition I need.
Today I got fed up with that, and decided to write one completely generic Makefile I can just reuse in all my projects. It only requires a reasonably new make, nothing else.

It features:

  • Automatic detection of changes in dependencies (eg header files)
  • Detection of system compiler / linker (via environment variables CC and LD)
  • Ability to amend CFLAGS, CPPFLAGS, LDFLAGS, or LDLIBS via cli
  • install and clean targets, the former also respects PREFIX
  • Generetion of gdb debug files
  • Sane compiler defaults

You can find the repository containing the file on GitHub2. Currently it only supports C, but I might add C++ support in the feature, be sure to keep an eye on my blog to be notified about any news.


Debug Messages in no$gmb and BGB

I've recently started working on a little side project, involving Gameboy development. While reading through the docs of BGB1, I noticed it supports printing debug messages to a debug console, I, however, couldn't get it working, since it was using the syntax of the no$gmb2 assembler. Thanks to the people of #gbdev on EFnet, especially beware, I've eventually got it working, and made an rgbds3 macro out of it.
Without further ado, here is a gist of the it:


; Prints a message to the no$gmb / bgb debugger
; Accepts a string as input, see emulator doc for support
        ld  d, d
        jr .end\@
        DW $6464
        DW $0000
        DB \1



SysInfo - Beautiful System Diagnosis


I've recently been reminded of a tool called Archey1, it's used to display system specs in a delightful manner. You often see it in screenshots of some other people desktops of the Arch Linux community.

I missed such a tool on OS X, and that's why I wrote SysInfo. It's available on Github2.


Fixing Slow Vim in Tmux and iTerm2

I've noticed my Vim got horribly slow once I had multiple panes in tmux open.
My initial investigation led to the fact, that tmux is slowing Vim down, and a quick Google search confirmed that.
After removing all plugins in Vim/tmux, I dug through the iTerm2 settings and found this:


Removing the tick at "Save lines to scrollback in alternate screen mode" and setting the scrollback to a reasonable amount (I chose 1000), the lag was nearly gone. I'll continue investigating, to improve the Vim performance.



I've resurrected my blog, and put my .io domain to a good use, and set-up a ghost blog.
So far, I've always had my personal websites cluttered on many domains, but this came to an end, everything is now on

You can expect new posts in the next few weeks, I already have something prepared.