1BRC in C++

onebrc.cpp

#if 0  // self-compiling code: just 'chmod +x' this file and run it directly!
c++ -std=c++11 -Wall -Wextra -pedantic -Werror -g -O3 -march=native $0 || exit 1
exec ./a.out $*
#endif

// SPDX-FileCopyrightText: 2023 Martin J. Fiedler <keyj@emphy.de>
// SPDX-License-Identifier: MIT

// C++11 implementation for the One Billion Row Challenge
// (https://github.com/gunnarmorling/1brc)
//
// The input file must be named "measurements.txt".
//
// Techniques used here:
// - 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, 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.
// Everything else is standard C++11 fare.

#include <cstdint>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#include <string>
#include <array>
#include <vector>
#include <algorithm>
#include <functional>
#include <chrono>
#include <thread>

// CONFIGURATION SECTION.

int threadCount = 8;  // default thread count (can be set on command line too)

// hash map configuration
constexpr int hashBuckets = 2048;  // number of buckets in the hash map
constexpr int probeLimit  = 1;     // number of steps of quadratic probing
                                   // before falling back to a linked list
typedef uint16_t hash_t;           // data type to use for the hash
constexpr int rotateAmount = 13;   // bits to rotate left after each step
#define HASH_OP ^                  // operation to add the current byte: + or ^

// derived parameters
constexpr hash_t hashMask = hash_t(hashBuckets - 1);
static_assert((hashBuckets & (hashBuckets - 1)) == 0, "hashBuckets must be a power of two");

///////////////////////////////////////////////////////////////////////////////

// memory-mapped input helper class

#ifdef _WIN32
    // WARNING: Win32 support hasn't been tested as thoroughly!
    #define WIN32_LEAN_AND_MEAN
    #define NOMINMAX
    #include <windows.h>
    class MemoryMappedInputFile {
        HANDLE hFile = INVALID_HANDLE_VALUE;
        HANDLE hMap  = NULL;
    public:
        void* data = nullptr;
        size_t size = 0;
        inline MemoryMappedInputFile(const char* filename) {
            hFile = CreateFileA(filename, GENERIC_READ, FILE_SHARE_READ, nullptr, OPEN_EXISTING, 0, nullptr);
            if (hFile == INVALID_HANDLE_VALUE) { return; }
            DWORD sizeH, sizeL;
            sizeL = GetFileSize(hFile, &sizeH);
            size = (size_t(sizeH) << 32) | size_t(sizeL);
            hMap = CreateFileMappingA(hFile, nullptr, PAGE_READONLY, sizeH, sizeL, nullptr);
            if (hMap == NULL) { return; }
            data = MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, size);
        }
        inline ~MemoryMappedInputFile() {
            if (data) { UnmapViewOfFile(data); }
            if (hMap != NULL) { CloseHandle(hMap); }
            if (hFile != INVALID_HANDLE_VALUE) { CloseHandle(hFile); }
        }
    };
#else
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/mman.h>
    #include <fcntl.h>
    #include <unistd.h>
    class MemoryMappedInputFile {
        int fd = -1;
    public:
        void* data = nullptr;
        size_t size = 0;
        inline MemoryMappedInputFile(const char* filename) {
            fd = open(filename, O_RDONLY);
            if (fd < 0) { return; }
            size = lseek(fd, 0, SEEK_END);
            if (size == size_t(-1)) { return; }
            data = mmap(nullptr, size, PROT_READ, MAP_SHARED, fd, 0);
        }
        inline ~MemoryMappedInputFile() {
            if (data) { munmap(data, size); }
            if (fd >= 0) { close(fd); }
        }
    };
#endif

///////////////////////////////////////////////////////////////////////////////

// simple bump allocator heap (so we don't need to use malloc() much at runtime)

class Heap {
    struct Page {
        Page* prev;
        size_t offset;
        uint8_t data[1];
    };
    size_t pageSize;
    Page* currentPage = nullptr;
    void newPage();
public:
    inline Heap(size_t pageSize_=1048576) : pageSize(pageSize_) { newPage(); }
    void* alloc(size_t size);
    inline char* addString(const char* str) {
        size_t size = strlen(str) + 1;
        void* res = alloc(size);
        memcpy(res, static_cast<const void*>(str), size);
        return static_cast<char*>(res);
    }
    template <typename T> inline T* addObject() {
        T* obj = static_cast<T*>(alloc(sizeof(T)));
        new(obj) T;
        return obj;
    }
    ~Heap();
};

void Heap::newPage() {
    Page* p = static_cast<Page*>(malloc(pageSize + sizeof(Page)));
    assert(p != nullptr);
    p->prev = currentPage;
    p->offset = 0;
    currentPage = p;
}

void* Heap::alloc(size_t size) {
    assert(size <= pageSize);
    if ((currentPage->offset + size) > pageSize) { newPage(); }
    void* res = static_cast<void*>(&currentPage->data[currentPage->offset]);
    currentPage->offset = (currentPage->offset + size + 15) & (~15);
    return res;
}

Heap::~Heap() {
    while (currentPage) {
        Page *prev = currentPage->prev;
        free(static_cast<void*>(currentPage));
        currentPage = prev;
    }
}

///////////////////////////////////////////////////////////////////////////////

// single statistics slot
struct StatsSlot {
    const char* key  = nullptr;  // key ("city name"); if NULL, slot is unused
    StatsSlot*  next = nullptr;  // linked list of 
    // using stats as fixed-point values with a precision of 1/10th,
    // because libc's strtod() is too slow to be useful
    int16_t vMin  =  32767;
    int16_t vMax  = -32768;
    int     count = 0;
    int64_t sum   = 0;
    // note: the size of this structure is exactly 32 bytes ... isn't that convenient?
    inline StatsSlot() {}
    void mergeFrom(const StatsSlot& source);
    inline void mergeTo(StatsSlot& dest) const { dest.mergeFrom(*this); }
};

// statistics generator class, representing a single worker thread
class StatsGenerator {
    std::array<StatsSlot, hashBuckets> map;  // main hash map
    Heap heap;  // keys and additional linked list slots go here
    std::thread *thread = nullptr;  // thread (non-NULL while running)
    static void threadFunc(StatsGenerator* self);
    // main key lookup function; always returns a valid slot, either a newly-
    // created one, or an existing one
    StatsSlot* get(const char* key);
public:
    char* pos = nullptr;  // start position (inside of run(): current position)
    char* end = nullptr;  // one past end position (MUST end with a newline!)
    inline StatsGenerator() {}
    void run();           // process until pos == end
    void runThread();     // spawn a new thread that executes run()
    void joinThread();    // wait for thread to finish
    void mergeFrom(StatsGenerator& source);
    void mergeTo(StatsGenerator& dest) { dest.mergeFrom(*this); }
    void dump(FILE *out);
    // run a callback function on all used statistics slots
    void visit(std::function<void(const StatsSlot&)> visitor) const;
};

StatsSlot* StatsGenerator::get(const char* key) {
    // compute rotate-and-ADD/XOR hash
    hash_t h = 0;
    for (const char* keyPos = key;;) {
        uint8_t c = uint8_t(*keyPos++);
        if (!c) { break; }
        h = (h << rotateAmount) | (h >> (sizeof(h) * 8 - rotateAmount));
        h = h HASH_OP hash_t(c);
    }

    // look up (and, possibly, create) a slot using a hash map with quadratic probing
    StatsSlot* slot = &map[h & hashMask];
    for (int probe = 0;;) {
        if (!slot->key) {  // empty slot -> claim it
            slot->key = heap.addString(key);
            assert(slot->next == nullptr);
            assert(slot->count == 0);
            return slot;
        } else if (!strcmp(slot->key, key)) {  // correct slot found
            return slot;
        } else if (slot->next) {  // other slot -> follow the linked list
            slot = slot->next;
        } else if (probe < probeLimit) {  // end of list -> try quadratic probing
            h += (++probe);
            slot = &map[h & hashMask];
        } else {  // still no free slot found -> add one to the last examined slot's list
            slot->next = heap.addObject<StatsSlot>();
            slot = slot->next;
            slot->key = heap.addString(key);
            return slot;
        }
    }
}

void StatsGenerator::visit(std::function<void(const StatsSlot&)> visitor) const {
    for (hash_t h = 0;  h <= hashMask;  ++h) {
        const StatsSlot* slot = &map[h];
        do {
            if (slot->key) { visitor(*slot); }
        } while ((slot = slot->next));
    }
}

void StatsGenerator::run() {
    constexpr size_t MaxKeyLen = 80;
    char key[MaxKeyLen];
    while (pos < end) {
        // parse the key
        char *keypos = key;
        char c;
        do {
            c = *pos++;
            *keypos++ = c;
        } while (c != ';');
        keypos[-1] = '\0';

        // parse the value
        bool negative = (*pos == '-');
        if (negative) { ++pos; }
        int16_t value = 0;
        bool haveDot = false;
        while (pos < end) {
            char c = *pos++;
            if (c == '\n') { break; }
            if ((c >= '0') && (c <= '9')) { value = value * 10 + c - '0'; }
            if (c == '.') { haveDot = true; }
        }
        if (!haveDot) { value *= 10; }
        if (negative) { value = -value; }

        // enter stats
        StatsSlot *slot = get(key);
        if (value < slot->vMin) { slot->vMin = value; }
        if (value > slot->vMax) { slot->vMax = value; }
        slot->sum += int64_t(value);
        slot->count++;
    }
}

void StatsGenerator::threadFunc(StatsGenerator* self) {
    self->run();
}

void StatsGenerator::runThread() {
    assert(!thread);
    thread = new std::thread(StatsGenerator::threadFunc, this);
}

void StatsGenerator::joinThread() {
    if (thread) {
        thread->join();
        delete thread;
        thread = nullptr;
    }
}

void StatsSlot::mergeFrom(const StatsSlot& source) {
    if (source.vMin < vMin) { vMin = source.vMin; }
    if (source.vMax > vMax) { vMax = source.vMax; }
    sum   += source.sum;
    count += source.count;
}

void StatsGenerator::mergeFrom(StatsGenerator& source) {
    source.joinThread();
    source.visit([&] (const StatsSlot& slot) { get(slot.key)->mergeFrom(slot); });
}

void StatsGenerator::dump(FILE *out) {
    std::vector<std::string> keys;
    visit([&] (const StatsSlot& slot) { keys.emplace_back(slot.key); });
    std::sort(keys.begin(), keys.end());
    const char* prefix = "{";
    for (const auto& key : keys) {
        const StatsSlot* slot = get(key.c_str());
        fprintf(out, "%s%s=%.1f/%.1f/%.1f", prefix, key.c_str(), double(slot->vMin) * 0.1, double(slot->sum) / double(slot->count) * 0.1, double(slot->vMax) * 0.1);
        prefix = ", ";
    }
    fprintf(out, "}\n");
}

///////////////////////////////////////////////////////////////////////////////

int main(int argc, char* argv[]) {
    if (argc > 1) {
        // override thread count; special setting: 0 = don't use threads at all
        threadCount = std::max(atoi(argv[1]), 0);
    }

    auto tStart = std::chrono::steady_clock::now();

    MemoryMappedInputFile infile("measurements.txt");
    if (!infile.data) {
        fprintf(stderr, "ERROR: failed to load input file\n");
        return 1;
    }

    std::vector<StatsGenerator> threads(threadCount);
    char *startPos = static_cast<char*>(infile.data);
    char *splitPos = startPos;
    for (int i = 0;  i < threadCount;  ++i) {
        threads[i].pos = splitPos;
        splitPos = startPos + (infile.size * (i + 1) / threadCount);
        if (i < (threadCount - 1)) {  // always split at line boundary
            while (splitPos[-1] != '\n') { ++splitPos; }
        }
        threads[i].end = splitPos;
        threads[i].runThread();
    }

    StatsGenerator result;
    if (threadCount < 1) {
        // run true single-threaded mode
        result.pos = startPos;
        result.end = startPos + infile.size;
        result.run();
    }
    for (auto& thread : threads) {
        result.mergeFrom(thread);
    }

    result.dump(stdout);

    auto tEnd = std::chrono::steady_clock::now();
    fprintf(stderr, "took %.3f seconds with %d threads\n", std::chrono::duration_cast<std::chrono::duration<double>>(tEnd - tStart).count(), threadCount);
    return 0;
}

onebrc_gen.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# SPDX-FileCopyrightText: 2023 Martin J. Fiedler <keyj@emphy.de>
# SPDX-License-Identifier: MIT

# 1BRC (https://github.com/gunnarmorling/1brc) data file generator in Python.

import random
import sys
import time

def fmt_time(t):
    t = int(t + 0.9)
    return f"{t//3600}:{(t//60)%60:02d}:{t%60:02d}"

def main():
    try:
        count = int(float(sys.argv[1]))
    except (IndexError, ValueError):
        print("Usage:", sys.argv[0], "<number of lines>", file=sys.stderr)
        sys.exit(2)

    stations_enc = [(name.encode('utf-8'), temp) for name, temp in Stations]
    with open("measurements.txt", "wb") as f:
        t0 = time.time()
        for i in range(count):
            if i and not(i & 65535):
                eta = int((time.time() - t0) * (count - i) / i + 0.9)
                sys.stdout.write(f"\r{i/count*100:6.2f}% completed, ETA {fmt_time(eta)} ")
                sys.stdout.flush()
            city, temp = random.choice(stations_enc)
            temp = str(round(random.gauss(temp, 10.0) * 10.0) / 10.0).encode()
            f.write(city + b';' + temp + b'\n')
        f.flush()
        dt = time.time() - t0
        print(f"\rDone. Generated {f.tell()/1e6:.1f} MB of data in {fmt_time(dt)} ({dt*1e6/count:.2f} µs/line)")

Stations = [
    # the following lines are copied (almost) verbatim from
    # https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CreateMeasurements.java
    ("Abha", 18.0),
    ("Abidjan", 26.0),
    ("Abéché", 29.4),
    ("Accra", 26.4),
    ("Addis Ababa", 16.0),
    ("Adelaide", 17.3),
    ("Aden", 29.1),
    ("Ahvaz", 25.4),
    ("Albuquerque", 14.0),
    ("Alexandra", 11.0),
    ("Alexandria", 20.0),
    ("Algiers", 18.2),
    ("Alice Springs", 21.0),
    ("Almaty", 10.0),
    ("Amsterdam", 10.2),
    ("Anadyr", -6.9),
    ("Anchorage", 2.8),
    ("Andorra la Vella", 9.8),
    ("Ankara", 12.0),
    ("Antananarivo", 17.9),
    ("Antsiranana", 25.2),
    ("Arkhangelsk", 1.3),
    ("Ashgabat", 17.1),
    ("Asmara", 15.6),
    ("Assab", 30.5),
    ("Astana", 3.5),
    ("Athens", 19.2),
    ("Atlanta", 17.0),
    ("Auckland", 15.2),
    ("Austin", 20.7),
    ("Baghdad", 22.77),
    ("Baguio", 19.5),
    ("Baku", 15.1),
    ("Baltimore", 13.1),
    ("Bamako", 27.8),
    ("Bangkok", 28.6),
    ("Bangui", 26.0),
    ("Banjul", 26.0),
    ("Barcelona", 18.2),
    ("Bata", 25.1),
    ("Batumi", 14.0),
    ("Beijing", 12.9),
    ("Beirut", 20.9),
    ("Belgrade", 12.5),
    ("Belize City", 26.7),
    ("Benghazi", 19.9),
    ("Bergen", 7.7),
    ("Berlin", 10.3),
    ("Bilbao", 14.7),
    ("Birao", 26.5),
    ("Bishkek", 11.3),
    ("Bissau", 27.0),
    ("Blantyre", 22.2),
    ("Bloemfontein", 15.6),
    ("Boise", 11.4),
    ("Bordeaux", 14.2),
    ("Bosaso", 30.0),
    ("Boston", 10.9),
    ("Bouaké", 26.0),
    ("Bratislava", 10.5),
    ("Brazzaville", 25.0),
    ("Bridgetown", 27.0),
    ("Brisbane", 21.4),
    ("Brussels", 10.5),
    ("Bucharest", 10.8),
    ("Budapest", 11.3),
    ("Bujumbura", 23.8),
    ("Bulawayo", 18.9),
    ("Burnie", 13.1),
    ("Busan", 15.0),
    ("Cabo San Lucas", 23.9),
    ("Cairns", 25.0),
    ("Cairo", 21.4),
    ("Calgary", 4.4),
    ("Canberra", 13.1),
    ("Cape Town", 16.2),
    ("Changsha", 17.4),
    ("Charlotte", 16.1),
    ("Chiang Mai", 25.8),
    ("Chicago", 9.8),
    ("Chihuahua", 18.6),
    ("Chișinău", 10.2),
    ("Chittagong", 25.9),
    ("Chongqing", 18.6),
    ("Christchurch", 12.2),
    ("City of San Marino", 11.8),
    ("Colombo", 27.4),
    ("Columbus", 11.7),
    ("Conakry", 26.4),
    ("Copenhagen", 9.1),
    ("Cotonou", 27.2),
    ("Cracow", 9.3),
    ("Da Lat", 17.9),
    ("Da Nang", 25.8),
    ("Dakar", 24.0),
    ("Dallas", 19.0),
    ("Damascus", 17.0),
    ("Dampier", 26.4),
    ("Dar es Salaam", 25.8),
    ("Darwin", 27.6),
    ("Denpasar", 23.7),
    ("Denver", 10.4),
    ("Detroit", 10.0),
    ("Dhaka", 25.9),
    ("Dikson", -11.1),
    ("Dili", 26.6),
    ("Djibouti", 29.9),
    ("Dodoma", 22.7),
    ("Dolisie", 24.0),
    ("Douala", 26.7),
    ("Dubai", 26.9),
    ("Dublin", 9.8),
    ("Dunedin", 11.1),
    ("Durban", 20.6),
    ("Dushanbe", 14.7),
    ("Edinburgh", 9.3),
    ("Edmonton", 4.2),
    ("El Paso", 18.1),
    ("Entebbe", 21.0),
    ("Erbil", 19.5),
    ("Erzurum", 5.1),
    ("Fairbanks", -2.3),
    ("Fianarantsoa", 17.9),
    ("Flores,  Petén", 26.4),
    ("Frankfurt", 10.6),
    ("Fresno", 17.9),
    ("Fukuoka", 17.0),
    ("Gabès", 19.5),
    ("Gaborone", 21.0),
    ("Gagnoa", 26.0),
    ("Gangtok", 15.2),
    ("Garissa", 29.3),
    ("Garoua", 28.3),
    ("George Town", 27.9),
    ("Ghanzi", 21.4),
    ("Gjoa Haven", -14.4),
    ("Guadalajara", 20.9),
    ("Guangzhou", 22.4),
    ("Guatemala City", 20.4),
    ("Halifax", 7.5),
    ("Hamburg", 9.7),
    ("Hamilton", 13.8),
    ("Hanga Roa", 20.5),
    ("Hanoi", 23.6),
    ("Harare", 18.4),
    ("Harbin", 5.0),
    ("Hargeisa", 21.7),
    ("Hat Yai", 27.0),
    ("Havana", 25.2),
    ("Helsinki", 5.9),
    ("Heraklion", 18.9),
    ("Hiroshima", 16.3),
    ("Ho Chi Minh City", 27.4),
    ("Hobart", 12.7),
    ("Hong Kong", 23.3),
    ("Honiara", 26.5),
    ("Honolulu", 25.4),
    ("Houston", 20.8),
    ("Ifrane", 11.4),
    ("Indianapolis", 11.8),
    ("Iqaluit", -9.3),
    ("Irkutsk", 1.0),
    ("Istanbul", 13.9),
    ("İzmir", 17.9),
    ("Jacksonville", 20.3),
    ("Jakarta", 26.7),
    ("Jayapura", 27.0),
    ("Jerusalem", 18.3),
    ("Johannesburg", 15.5),
    ("Jos", 22.8),
    ("Juba", 27.8),
    ("Kabul", 12.1),
    ("Kampala", 20.0),
    ("Kandi", 27.7),
    ("Kankan", 26.5),
    ("Kano", 26.4),
    ("Kansas City", 12.5),
    ("Karachi", 26.0),
    ("Karonga", 24.4),
    ("Kathmandu", 18.3),
    ("Khartoum", 29.9),
    ("Kingston", 27.4),
    ("Kinshasa", 25.3),
    ("Kolkata", 26.7),
    ("Kuala Lumpur", 27.3),
    ("Kumasi", 26.0),
    ("Kunming", 15.7),
    ("Kuopio", 3.4),
    ("Kuwait City", 25.7),
    ("Kyiv", 8.4),
    ("Kyoto", 15.8),
    ("La Ceiba", 26.2),
    ("La Paz", 23.7),
    ("Lagos", 26.8),
    ("Lahore", 24.3),
    ("Lake Havasu City", 23.7),
    ("Lake Tekapo", 8.7),
    ("Las Palmas de Gran Canaria", 21.2),
    ("Las Vegas", 20.3),
    ("Launceston", 13.1),
    ("Lhasa", 7.6),
    ("Libreville", 25.9),
    ("Lisbon", 17.5),
    ("Livingstone", 21.8),
    ("Ljubljana", 10.9),
    ("Lodwar", 29.3),
    ("Lomé", 26.9),
    ("London", 11.3),
    ("Los Angeles", 18.6),
    ("Louisville", 13.9),
    ("Luanda", 25.8),
    ("Lubumbashi", 20.8),
    ("Lusaka", 19.9),
    ("Luxembourg City", 9.3),
    ("Lviv", 7.8),
    ("Lyon", 12.5),
    ("Madrid", 15.0),
    ("Mahajanga", 26.3),
    ("Makassar", 26.7),
    ("Makurdi", 26.0),
    ("Malabo", 26.3),
    ("Malé", 28.0),
    ("Managua", 27.3),
    ("Manama", 26.5),
    ("Mandalay", 28.0),
    ("Mango", 28.1),
    ("Manila", 28.4),
    ("Maputo", 22.8),
    ("Marrakesh", 19.6),
    ("Marseille", 15.8),
    ("Maun", 22.4),
    ("Medan", 26.5),
    ("Mek'ele", 22.7),
    ("Melbourne", 15.1),
    ("Memphis", 17.2),
    ("Mexicali", 23.1),
    ("Mexico City", 17.5),
    ("Miami", 24.9),
    ("Milan", 13.0),
    ("Milwaukee", 8.9),
    ("Minneapolis", 7.8),
    ("Minsk", 6.7),
    ("Mogadishu", 27.1),
    ("Mombasa", 26.3),
    ("Monaco", 16.4),
    ("Moncton", 6.1),
    ("Monterrey", 22.3),
    ("Montreal", 6.8),
    ("Moscow", 5.8),
    ("Mumbai", 27.1),
    ("Murmansk", 0.6),
    ("Muscat", 28.0),
    ("Mzuzu", 17.7),
    ("N'Djamena", 28.3),
    ("Naha", 23.1),
    ("Nairobi", 17.8),
    ("Nakhon Ratchasima", 27.3),
    ("Napier", 14.6),
    ("Napoli", 15.9),
    ("Nashville", 15.4),
    ("Nassau", 24.6),
    ("Ndola", 20.3),
    ("New Delhi", 25.0),
    ("New Orleans", 20.7),
    ("New York City", 12.9),
    ("Ngaoundéré", 22.0),
    ("Niamey", 29.3),
    ("Nicosia", 19.7),
    ("Niigata", 13.9),
    ("Nouadhibou", 21.3),
    ("Nouakchott", 25.7),
    ("Novosibirsk", 1.7),
    ("Nuuk", -1.4),
    ("Odesa", 10.7),
    ("Odienné", 26.0),
    ("Oklahoma City", 15.9),
    ("Omaha", 10.6),
    ("Oranjestad", 28.1),
    ("Oslo", 5.7),
    ("Ottawa", 6.6),
    ("Ouagadougou", 28.3),
    ("Ouahigouya", 28.6),
    ("Ouarzazate", 18.9),
    ("Oulu", 2.7),
    ("Palembang", 27.3),
    ("Palermo", 18.5),
    ("Palm Springs", 24.5),
    ("Palmerston North", 13.2),
    ("Panama City", 28.0),
    ("Parakou", 26.8),
    ("Paris", 12.3),
    ("Perth", 18.7),
    ("Petropavlovsk-Kamchatsky", 1.9),
    ("Philadelphia", 13.2),
    ("Phnom Penh", 28.3),
    ("Phoenix", 23.9),
    ("Pittsburgh", 10.8),
    ("Podgorica", 15.3),
    ("Pointe-Noire", 26.1),
    ("Pontianak", 27.7),
    ("Port Moresby", 26.9),
    ("Port Sudan", 28.4),
    ("Port Vila", 24.3),
    ("Port-Gentil", 26.0),
    ("Portland (OR)", 12.4),
    ("Porto", 15.7),
    ("Prague", 8.4),
    ("Praia", 24.4),
    ("Pretoria", 18.2),
    ("Pyongyang", 10.8),
    ("Rabat", 17.2),
    ("Rangpur", 24.4),
    ("Reggane", 28.3),
    ("Reykjavík", 4.3),
    ("Riga", 6.2),
    ("Riyadh", 26.0),
    ("Rome", 15.2),
    ("Roseau", 26.2),
    ("Rostov-on-Don", 9.9),
    ("Sacramento", 16.3),
    ("Saint Petersburg", 5.8),
    ("Saint-Pierre", 5.7),
    ("Salt Lake City", 11.6),
    ("San Antonio", 20.8),
    ("San Diego", 17.8),
    ("San Francisco", 14.6),
    ("San Jose", 16.4),
    ("San José", 22.6),
    ("San Juan", 27.2),
    ("San Salvador", 23.1),
    ("Sana'a", 20.0),
    ("Santo Domingo", 25.9),
    ("Sapporo", 8.9),
    ("Sarajevo", 10.1),
    ("Saskatoon", 3.3),
    ("Seattle", 11.3),
    ("Ségou", 28.0),
    ("Seoul", 12.5),
    ("Seville", 19.2),
    ("Shanghai", 16.7),
    ("Singapore", 27.0),
    ("Skopje", 12.4),
    ("Sochi", 14.2),
    ("Sofia", 10.6),
    ("Sokoto", 28.0),
    ("Split", 16.1),
    ("St. John's", 5.0),
    ("St. Louis", 13.9),
    ("Stockholm", 6.6),
    ("Surabaya", 27.1),
    ("Suva", 25.6),
    ("Suwałki", 7.2),
    ("Sydney", 17.7),
    ("Tabora", 23.0),
    ("Tabriz", 12.6),
    ("Taipei", 23.0),
    ("Tallinn", 6.4),
    ("Tamale", 27.9),
    ("Tamanrasset", 21.7),
    ("Tampa", 22.9),
    ("Tashkent", 14.8),
    ("Tauranga", 14.8),
    ("Tbilisi", 12.9),
    ("Tegucigalpa", 21.7),
    ("Tehran", 17.0),
    ("Tel Aviv", 20.0),
    ("Thessaloniki", 16.0),
    ("Thiès", 24.0),
    ("Tijuana", 17.8),
    ("Timbuktu", 28.0),
    ("Tirana", 15.2),
    ("Toamasina", 23.4),
    ("Tokyo", 15.4),
    ("Toliara", 24.1),
    ("Toluca", 12.4),
    ("Toronto", 9.4),
    ("Tripoli", 20.0),
    ("Tromsø", 2.9),
    ("Tucson", 20.9),
    ("Tunis", 18.4),
    ("Ulaanbaatar", -0.4),
    ("Upington", 20.4),
    ("Ürümqi", 7.4),
    ("Vaduz", 10.1),
    ("Valencia", 18.3),
    ("Valletta", 18.8),
    ("Vancouver", 10.4),
    ("Veracruz", 25.4),
    ("Vienna", 10.4),
    ("Vientiane", 25.9),
    ("Villahermosa", 27.1),
    ("Vilnius", 6.0),
    ("Virginia Beach", 15.8),
    ("Vladivostok", 4.9),
    ("Warsaw", 8.5),
    ("Washington, D.C.", 14.6),
    ("Wau", 27.8),
    ("Wellington", 12.9),
    ("Whitehorse", -0.1),
    ("Wichita", 13.9),
    ("Willemstad", 28.0),
    ("Winnipeg", 3.0),
    ("Wrocław", 9.6),
    ("Xi'an", 14.1),
    ("Yakutsk", -8.8),
    ("Yangon", 27.5),
    ("Yaoundé", 23.8),
    ("Yellowknife", -4.3),
    ("Yerevan", 12.4),
    ("Yinchuan", 9.0),
    ("Zagreb", 10.7),
    ("Zanzibar City", 26.0),
    ("Zürich", 9.3),
]

def hashtest():
    for hbits in range(8, 21):
        print(f"best solutions with {1<<hbits} (2^{hbits}) buckets:")
        hmask = (1 << hbits) - 1
        options = []
        for abits in (hbits, 16, 32, 64):
            amask = (1 << abits) - 1
            for shift in range(abits):
                for op, op_func in (("ADD", lambda a,c: a+c), ("XOR", lambda a,c: a^c)):
                    for probe_limit in range(10):
                        raw_depth = [0] * (1 << hbits)
                        probed_depth = [0] * (1 << hbits)
                        maxchecks = 0
                        maxprobe = 0
                        for city, _ in Stations:
                            a = 0
                            for c in city.encode('utf-8'):
                                a = op_func((a << shift) | (a >> (abits - shift)), c) & amask
                            a = a & hmask
                            raw_depth[a] += 1
                            checks = probed_depth[a]
                            probe = 0
                            while probed_depth[a] and (probe < probe_limit):
                                probe += 1
                                a = (a + probe) & hmask
                                checks += probed_depth[a]
                            probed_depth[a] += 1
                            maxchecks = max(checks, maxchecks)
                            maxprobe = max(probe, maxprobe)
                        numcoll = sum(f > 1 for f in raw_depth)
                        maxcoll = max(probed_depth)
                        if maxprobe >= probe_limit:
                            options.append((numcoll, maxchecks, maxcoll, probe_limit, abits, shift, op))
        opt = sorted(options)
        for numcoll, maxchecks, maxcoll, probe_limit, abits, shift, op in opt:
            if (numcoll, maxchecks, maxcoll) > tuple(opt[10][:3]): break
            print(f"- {abits:2d}-bit rot-{shift:02d}-and-{op}, probe limit {probe_limit:2d}: {numcoll:3d} coll, {maxchecks:3d} max checks, {maxcoll:3d} max depth")

if __name__ == "__main__":
    if "hash" in ' '.join(sys.argv[1:]):
        hashtest()
    else:
        main()