# Jag blev nerd sniped - 1BRC++

16 januari 2024 | https://www.ribomation.se/blog/2024/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!! 😮

#

Result (m:s.ms)

JDK

Submitter

1

00:02.552

Graal Native

Thomas Wuerthinger, Quan Anh Mai, Alfonso Peterssen

2

00:02.575

OpenJDK

Quan Anh Mai

3

00:02.855

Graal

Roy van Rijn

\---

N

04:49.679

OpenJDK

Gunnar Morling (_baseline_)

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.

```text
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.

```cpp
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.

```cpp
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.

```cpp
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å.

```cpp
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.

```cpp
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.

```cpp
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()`.

```cpp
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.

```cpp
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.

```cpp
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.

```shell
$ 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.

```shell
$ 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.

```shell
$ 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.

```shell
$ ./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.