1BRC in C++11

[kajott]

A friend dropped the link to 1BRC in our Mattermost chat, and I couldn't resist writing an implementation for it:

https://gist.github.com/kajott/8a7c3f56a9a035fdfe3b2c79e17c8eed

It's plain C++11 with moderate use of the standard library. No external libraries.

It uses more or less the same techniques as Danny van Kooten's C implementation:

• memory mapping: Instead of read()ing chunks of the input file, it's mmap()ed in its entirety.
• multithreading: Split the file into as many (approximately) equal-sized chunks as there are threads, process them separately, and merge the measurements at the end.
• integer values: As it turns out, strtod() / atof() are very slow! Since the values are only using (at most) one decimal digit anyway, a fast custom parser for those can be used, and all math can be integer.
• custom hash map: std::unordered_map is also slow, so a custom hash map implementation is used. It's using a simple rotate-and-XOR or rotate-and-add hash function, and can use a configurable number of steps of quadratic probing before falling back to a linked list for each bucket.
• custom allocator: To avoid implicit locks from malloc(), each thread gets its own heap for run-time allocations (such as the key strings of the hash map, and the extra objects in the linked list) with a simple bump allocator.

Performance should be in the same ballpark as most other implementations; I get 6.7 seconds on an i7-1185 notebook CPU (4 cores + HT, running at ~4 GHz) with 8 threads.