Jag blev nerd sniped - 1BRC++

Förra veckans artikel om The 1 Billion Row Challenge (1BRC), blev kolossalt populär och flitigt läst. För egen del, kunde jag inte släppa tanken på 1BRC och spenderade helgen på en egen implementation i C++. Det här fenomenet att bli helt absorberad av ett problem och spendera löjligt mycket tid på det, kallas för att ha blivit Nerd Sniped. Mer info om termen finns i länksamlingen sist i artikeln.

1BRC statusuppdatering

Antalet tävlingsbidrag är nu uppe en bra bit över hundra och Gunnar Morling, som är initiativtagaren har nu bett folk via X/Twitter att inte skicka in flera bidrag, såvida de inte klart kvalar in på en topplacering.

Evalueringsservern är en dedikerad maskin med 32 core (64 threads), 128 GB RAM, AMD EPYC 7502P (Zen2). Data laddas från en RAM-disk, vilket kan vara bra att ha i åtanke. Så här är ställningen i skrivande stund. Som du kan se nedan, så har lösningarna blivit snabbare på ett helt spektakulärt sätt. Från strax under fem minuter ned till drygt 2 sekunder!! 😮

Modern C++

I resten av denna artikel beskriver jag en rättfram implementation av 1BRC i Modern C++ (C++20/23). I nästa uppföljande artikel, kommer jag beskriva min andra mer optimerade implementation, baserad på memory-mapped I/O av datafilen, multi-threaded bearbetning av filen i minnet, thread-private heap för respektive hash-map, optimerad parsningen av flyttalstexterna. Så, se till att läsa denna artikel och missa inte uppföljningen i nästa artikel.

Generera väderdata

Första steget var att flexibelt kunna generera väderdata, att använda som indata för huvudprogrammet. Nu fanns det förvisso ett (eller flera Java program) i 1BRC GitHub repo:n att använda. Men jag ville ha bättre kontroll över vad och hur data genererades, vilket medförde att jag skrev ett eget i Modern C++.

Java versionen hade en inbyggd lista på 413 väderstationsnamn med tillhörande medeltemperaturvärde. Detta tycket jag var lite oflexibelt, så jag extraherade ut dessa till en separat textfil. Formatet är ett väderstationsnamn och tillhörande medeltemperatur per rad, separerade av semikolon.

Abha;18.0
Abidjan;26.0
Abéché;29.4
. . .
Zagreb;10.7
Zanzibar City;26.0
Zürich;9.3

Först ska alla stationer laddas in, vilket görs med funktionen nedan. Den läser en rad i taget, delar upp textraden vid semikolon i namn och temperatur. Den sistnämnda tolkas till ett flyttal. Dessa två spara i ett Station objekt, som i sin tur läggs i en lista (std::vector), vilken också returneras från funktionen.

struct Station {
    const string name{};
    const double temperature{};
    Station(string name, double temperature) 
        : name(std::move(name)), temperature(temperature) {}
};

auto loadStations(string const& filename) -> std::vector<Station> {
    auto f = std::ifstream{filename};
    if (!f) throw std::invalid_argument{"cannot open "s + filename};

    auto stations = std::vector<Station>{};
    stations.reserve(500);
    for (string line; std::getline(f, line);) {
        //Austin;20.7
        auto sep  = line.find(';');
        auto name = line.substr(0, sep);
        auto temp = std::stod(line.substr(sep + 1));
        stations.emplace_back(name, temp);
    }

    return stations;
}

Sedan, ska ett önskat antal data-rader genereras och sparas till en fil. Själva genereringen utförs av funktionen nedan. In-argumenten är dels listan med väderstationer och dels en slumptalsmotor. Först väljs en station slumpmässigt, sedan slumpas en ny normalfördelad temperatur fram, där stationens temperaturvärde utgör medelvärde och standardavvikelsen är 10. Till sist, formateras namn och temperatur till en textsträng. Här använder jag den nya formateringsfunktionen i C++20, std::format. Denna funktion har helt nyligen blivit implementerad i GCC. Jag kompilerar med GCC C++ version 13.2.

auto generate(std::vector<Station> const& stations, std::default_random_engine& r) -> string {
    auto nextStation = std::uniform_int_distribution{0UL, stations.size() - 1};
    auto& station    = stations[nextStation(r)];

    auto nextTemperature = std::normal_distribution<double>{station.temperature, 10.0};
    auto temperature     = std::round(nextTemperature(r) * 10.0) / 10.0;

    return std::format("{};{:.1f}", station.name, temperature);
}

Huvudprogrammet ser ut som följer. Först sätts parametrar, vilka kan ändras på kommandoraden. Resten av koden körs under tidsmätning, via funktionen rm::elapsed; se längre ned.

int main(int argc, char* argv[]) {
    auto stationsFile = "src/resources/stations.txt"s;
    auto numValues = 1000U;
    auto filename = "data/weather-data.csv"s;

    for (auto k = 1; k < argc; ++k) {
        auto arg = string{argv[k]};
        if (arg == "-n"s) {
            numValues = std::stoi(argv[++k]);
        } else if (arg == "-f"s) {
            filename = argv[++k];
        } else if (arg == "-s"s) {
            stationsFile = argv[++k];
        } else {
            std::cerr << "usage: " << argv[0] << " [-n <int>] [-f <str>] [-s <str>]\n";
            return 1;
        }
    }
    cout << "# values: " << numValues << "\n";
    cout << "filename: " << filename << "\n";

    rm::elapsed([stationsFile, numValues, filename]() {
        auto stations = loadStations(stationsFile);
        cout << "loaded " << stations.size() << " names\n";

        auto f = std::ofstream{filename};
        if (!f) throw std::invalid_argument{"cannot open output file "s + filename};

        auto devRandom = std::random_device{};
        auto r = std::default_random_engine{devRandom()};
        for (auto k = 1U; k <= numValues; ++k) {
            f << generate(stations, r) << "\n";
        }
    });
}

Så här ser tidsmätningsfunktionen ut. Den tar ett lambda-uttryck, som anropas mellan start och stop av realtidsklockan. Denna funktion används av övriga program också.

namespace cr = std::chrono;
void elapsed(std::function<void()> const& stmts) {
    auto startTime = cr::high_resolution_clock::now();
    stmts();
    auto endTime = cr::high_resolution_clock::now();
    auto elapsed = cr::duration<double, std::ratio<1, 1>>{endTime - startTime};
    cout << std::format("Elapsed time: {:.3f} seconds\n", elapsed.count());
}

Aggregera väderdata

Att aggregera all väderdata med Modern C++ är tämligen rättframt. Öppna datafilen, läs radvis, extrahera stationsnamn och temperaturvärde, samt aggregera de numeriska värdena i en hash-map där varje entry svarar mot en station.

Ett aggregeringsobjekt, vilket utgör värde i hash-map:en, ser ut så här. Ett dylikt objekt innehåller fyra värden, lämpligt initierade. Aggregeringen sker med den överlagrade += operatorn. Tja, kunde inte stå emot att skriva en operator i stället för en funktion.

struct Aggregation {
    unsigned count = 0;
    double sum = 0;
    double min = std::numeric_limits<double>::max();
    double max = std::numeric_limits<double>::min();

    void operator+=(double t) {
        ++count;
        sum += t;
        min = std::min(min, t);
        max = std::max(max, t);
    }

    friend auto operator<<(std::ostream& os, Aggregation const& a) -> std::ostream& {
        return os << std::format("{:+.2f}C, {:+.1f}/{:+.1f} ({:Ld})",
                                 (a.sum / a.count), a.min, a.max, a.count);
    }
};

Klassen innehåller också en vänlig utskriftsoperator. Class och struct är samma sak i C++, så när som att i den förstnämnda är default visibility private med det omvända gäller för den sistnämnda. Vänsterskifts-operatorn (<<) är tekniskt inte del av klassen men kan läggas innanför genom att markera den som friend (åtkomst till privata delar).

Huvudprogrammet är tämligen rättframt; öppna indatafilen, läs radvis, extrahera namn och temperatur, samt aggregera temperaturen data[name] += temp. Till sist, så ska resultatet skrivas ut i alfabetisk stationsordning.

int main(int argc, char** argv) {
    auto filename = rm::getFilename(argc, argv);
    cout << "filename: " << filename << "\n----\n";

    rm::elapsed([filename]() {
        auto f = std::ifstream{filename};
        if (!f) throw std::invalid_argument{"cannot open "s + filename};

        auto data = std::unordered_map<string, Aggregation>{};
        data.reserve(500);
        auto count = 0U;
        for (string line; std::getline(f, line);) {
            ++count;
            auto semi = line.find(';');
            auto name = line.substr(0, semi);
            auto temp = std::stod(line.substr(semi + 1));
            data[name] += temp;
        }

        // auto sorted = std::map<string, Aggregation>{data.begin(), data.end()};
        auto sorted = std::vector<std::pair<string, Aggregation>>{data.begin(), data.end()};
        std::sort(sorted.begin(), sorted.end(), [](auto&& lhs, auto&& rhs){
            return lhs.first < rhs.first;
        });
        for (auto&& [name, aggr]: sorted) {
            cout << name << ": " << aggr << "\n";
        }
        cout << "------\n# records: " << count << "\n";
    });
}

Efter att infilen öppnats, skapas en hash-map, vilket i C++ heter std::unordered_map. Eftersom vi "vet" att det finns 413 unika stationsnamn, kan vi förallokera lämpligt antal hash-buckets med funktionen reserv().

auto data = std::unordered_map<string, Aggregation>{};
data.reserve(500);

Efter aggregeringen vill vi ha utskriften sorterad på stationsnamnen. Enklast här att hälla över alla entries till en tree-map, som i C++ heter std::map. Argument till konstruktorn är ett iterator-par med alla element som ska kopieras över.

auto sorted = std::map<string, Aggregation>{data.begin(), data.end()};
for (auto&& [name, aggr]: sorted) {
    cout << name << ": " << aggr << "\n";
}

Ett alternativ till en tree-map, är att hälla över elementen i en lista och sortera denna. Det visade sig att totaltiden halverades att göra på detta sätt.

auto sorted = std::vector<std::pair<string, Aggregation>>{data.begin(), data.end()};
std::sort(sorted.begin(), sorted.end(), [](auto&& lhs, auto&& rhs){
    return lhs.first < rhs.first;
});

Efter det skriver vi ut alla entries med en for-each loop (aka range-based for-loop), samt tillämpar destructuring (aka structured binding) på varje returnerat entry-pair. Som du säkert noterat i koden ovan, gillar jag auto och har helt gått in för att tillämpa AAA (se länk i slutet).

Evaluering

Självklart, ska vi köra programmet och jämföra denna C++ version med förra veckans Java version.

Java

Först kompilerar vi programmet.

$ java --version
java 21.0.1 2023-10-17
Java(TM) SE Runtime Environment Oracle GraalVM 21.0.1+12.1 (build 21.0.1+12-jvmci-23.1-b19)
$ javac --version
javac 21.0.1
$ javac -d binary src/java/ribomation/CalculateAverage.java
tree binary/
binary/
└── ribomation
    ├── CalculateAverage$Aggregation.class
    ├── CalculateAverage$Measurement.class
    ├── CalculateAverage$Result.class
    └── CalculateAverage.class

2 directories, 4 files

Sen är det dags att köra programmet. Min laptop är inte på långa vägar lika kraftfull som Gunnar's utvärderingsserver, så jag kör med en mer måttlig datamängd på 10M rader.

$ java -cp binary/ ribomation.CalculateAverage -f data/weather-data-10M.csv
input file: data/weather-data-10M.csv
Abha: 18.1C, -22.1/52.9 (24124)
Abidjan: 25.9C, -14.3/66.6 (24234)
. . .
Ürümqi: 7.3C, -40.5/46.4 (24012)
İzmir: 17.9C, -20.6/56.8 (24241)
----
Elapsed time: 4.543 secs (10,000,000 records)

C++

Vi gör på samma sätt med C++ versionen. Först kompilering.

$ g++ --version
g++ (Ubuntu 13.2.0-4ubuntu3) 13.2.0
$ g++ -std=c++23 -O3 -Wall -Isrc/cxx/util -o binary/calculate-average \
      src/cxx/util/util.cxx src/cxx/calculate-average.cxx
$ tree binary/
binary/
├── calculate-average
└── ribomation
    ├── CalculateAverage$Aggregation.class
    ├── CalculateAverage$Measurement.class
    ├── CalculateAverage$Result.class
    └── CalculateAverage.class

2 directories, 5 files

Sedan, kör vi programmet.

$ ./binary/calculate-average -f data/weather-data-10M.csv
filename: data/weather-data-10M.csv
----
Abha: +18.06C, -22.1/+52.9 (24124)
Abidjan: +25.92C, -14.3/+66.6 (24234)
. . .
Zürich: +9.27C, -34.3/+51.8 (24223)
Ürümqi: +7.35C, -40.5/+46.4 (24012)
İzmir: +17.92C, -20.6/+56.8 (24241)
------
# records: 10000000
Elapsed time: 3.460 seconds

Slutsatser

Jag upprepade körningarna med respektive program några gånger och redovisar den bästa, dvs kortaste, tiden. Med stor förvåning kan vi konstatera att det skiljer bara 1 sekund mellan Java programmet och C++ programmet. Här har jag använt den (relativt) nya Graal JVM, vilken uppenbarligen lovar mycket gott framgent.