I min förra artikel använde jag ranges & views från C++20/23 för att implementera ett program som läste in alla ord från en textfil och matade ut en HTML-fil med orden, där storleken var proportionell mot dess frekvens, samt att varje ord fick en slumpmässigt vald färg. Tonvikten i den artikeln låg på att illustrera modern C++. I denna uppföljande artikel tänkte jag stegvis optimera programmet, för att se hur snabbt programmet kan köra.

Strategin i denna artikel är att steg-för-steg optimera programmet, enligt följande steg.

Version 1 - Baseline

Jag visar först startversionen (baseline) för vårt program och sen i de följande stegen försöker jag göra programmet snabbare. Ibland lyckas det, ibland kanske resultatet uteblir eller blir mediokert.

Jämfört med koden i förra artikeln, så har jag extraherat ut den del som läser och genererar html texten. Detta för att senare kunna köra benchmarks på de olika versionerna. Den kompletta koden finns i en GitHub repo; se länksamlingen sist i denna artikel. Tänk också på att jag visar bara relevanta delar av koden och hänvisar till GitHub repon för övrig kod.

Så här ser run() funktionen ut.

auto run(Params const& params) -> string {
    // --- loading words ---
    auto infile = std::ifstream{params.filename};
    if (not infile) throw std::invalid_argument{"cannot open "s + params.filename.string()};

    auto freqs = std::unordered_map<string, unsigned>{};
    
    auto keep_nonsmall_words = [&params](string const& word) { return word.size() >= params.min_length; };
    auto to_lowercase = [](string const& word) {
        auto result = string{};
        for (char ch: word) {
            auto c = static_cast<unsigned char>(ch);
            result.push_back(static_cast<char>(std::tolower(c)));
        }
        return result;
    };
    auto keep_nonmodern_words = [](string const& word) {
        static auto const modern_words = std::unordered_set{
            "electronic"s, "distributed"s, "copies"s, "copyright"s, "gutenberg"s
        };
        return not modern_words.contains(word);
    };
    
    auto load_pipeline =
            r::subrange{WordIterator{infile}, WordIterator{}}
            | v::filter(keep_nonsmall_words)
            | v::transform(to_lowercase)
            | v::filter(keep_nonmodern_words);
    auto count_words = [&freqs](string const& word) { ++freqs[word]; };

    r::for_each(load_pipeline, count_words);

    // --- sorting <word,count> pairs ---
    using WordFreq = std::pair<string, unsigned>;
    auto sortable = std::vector<WordFreq>{freqs.begin(), freqs.end()};

    auto by_freq_desc = [](WordFreq const& a, WordFreq const& b) { return a.second > b.second; };
    r::sort(sortable, by_freq_desc);

    // --- making html span tags ---
    auto items    = sortable | v::take(params.max_words) | r::to<std::vector<WordFreq>>();
    auto max_freq = items.front().second;
    auto min_freq = items.back().second;
    auto scale    = static_cast<double>(params.max_font - params.min_font) / (max_freq - min_freq);
    auto R        = std::default_random_engine{std::random_device{}()};

    struct SpanTagGenerator {
        Params const& params;
        double        scale;
        unsigned      min_freq;
        std::default_random_engine& R;

        auto color() -> string {
            auto Byte = std::uniform_int_distribution<unsigned short>{0, 255};
            return std::format("#{:02X}{:02X}{:02X}", Byte(R), Byte(R), Byte(R));
        }

        SpanTagGenerator(Params const& params_, double scale_, unsigned min_freq_, std::default_random_engine& R_)
            : params(params_), scale(scale_), min_freq(min_freq_), R(R_) {}

        auto operator()(WordFreq& wf) -> string {
            auto word = wf.first;
            auto freq = wf.second;
            auto size = static_cast<unsigned>((freq - min_freq) * scale + params.min_font);
            auto colr = color();
            constexpr auto fmt =
                    R"(<span style="font-size: {} px; color: {};" title="The word '{}' occurs {} times">{}</span>)";
            return std::format(fmt, size, colr, word, freq, word);
        }
    };

    r::shuffle(items, R);
    auto tags        = std::vector<string>{};
    auto to_span_tag = SpanTagGenerator{params, scale, min_freq, R};
    for (WordFreq& item: items) tags.push_back(to_span_tag(item));

    // --- generating html text ---
    auto html = std::ostringstream{};
    html << R"(<!DOCTYPE html>
        <html lang="en">
            <head>
                <meta charset="UTF-8">
                <meta name="viewport" content="width=device-width, initial-scale=1.0, shrink-to-fit=yes">
                <title>Word Frequencies</title>
            </head>
        <body>)";
    html << std::format("<h1>The {} most frequent words in {}</h1>", params.max_words, params.filename.string());
    for (string const& tag: tags) html << tag << "\n";
    html << "</body></html>\n";

    return html.str();
}

Struct:en Params innehåller alla program-parametrar samt en funktion för att läsa in dessa från kommandoraden. Klassen WordIterator är densamma som i förra artikeln. Kör vi programmet har vi en förfluten tid att utgå ifrån.

Yes> g++ -std=c++23 -Wall -o baseline \
     ../wordcount/utils.cxx ../wordcount/baseline.cxx ../wordcount/baseline-main.cxx
Yes> ./baseline --file ../data/shakespeare.txt
--- WordCount - Baseline ---
loading 5.3 MB from ../data/shakespeare.txt
written: ./shakespeare.html
elapsed: 1470 ms

Version 2 - Kompilera med optimering

Ett första grundläggande steg är att kompilera programmet med optimering påslagen. Det finns några olika kompileringsflaggor att välja på.

En annan kompileringsflagga är -march=native, som instruerar kompilatorn att generera maskin-kod optimerad för den CPU som kompileringen körs på. Detta fungerar bra när man vet att programmet inte ska köras på datorer med annan CPU typ.

Det finns ytterligare en kompileringsflagga som skulle kunna vara av intresse, som aktiverar link-time optimization (LTO). Flaggan är -flto. Emellertid, har den obefintlig inverkan på ett program bestående av en eller få *.cxx filer, vilket kallas för TU (Translation Unit).

Så, vi kompilerar med flaggorna: -O3 -march=native

Yes> g++ -std=c++23 -Wall -O3 -march=native  -o baseline-opti \
     ../wordcount/utils.cxx ../wordcount/baseline.cxx ../wordcount/baseline-main.cxx
wordcount/baseline-main.cxx
Yes> ./baseline-opti --file ../data/shakespeare.txt
--- WordCount - Baseline ---
loading 5.3 MB from ../data/shakespeare.txt
written: ./shakespeare.html
elapsed: 131 ms
Yes>

Oj, vilken uppsnabbning det blev bara genom att ändra lite på kommandoraden 😃

Version 3 - Förallokering

De containers vi använder sköter sin egen minneshantering, vilket innebär att de börjar med en liten intern datastruktur och allt eftersom man stoppar in fler element så omallokeras den interna datastrukturen. Det innebär att ett eller flera minnesblock allokeras och de befintliga destrueras. Genom att förallokera med metoden reserve(), kan alla (eller de flesta) omallokeringar undvikas. Det här är en enkel kod-optimering, vilken jag förvisso rekommenderar att alltid göra.

Först förallokerar vi hash-map freqs. Eftersom vi inte vet det exakta antalet unika ord, så gör vi en estimering. Vi föreställer oss att orden i genomsnitt är 8 bokstäver, vilket låter oss dela filstorleken med 8. Sedan, tänker vi oss att en fjärdedel av dessa utgörs av unika ord. Detta värde används för att förallokera map:en.

auto freqs    = std::unordered_map<string, unsigned>{};
auto filesize = fs::file_size(params.filename);
auto approx_total_words  = filesize / 8;
auto approx_unique_words = approx_total_words / 4;
freqs.reserve(approx_unique_words);

I lambdat to_lowercase vet vi att retur-värdet kommer att ha samma längd som in-argumentet. Således blir det enkelt att förallokera string-objektet result.

auto to_lowercase = [](string const& word) {
    auto result = string{};
    result.reserve(word.size());

Vi vet att vektorn sortable ska innehålla samtliga std::pair element i map:en freqs. Eftersom vi först behöver förallokera och sedan sätta in data, så kan vi inte använda den behändiga konstruktorn vi använde i baseline. Innehållet i freqs flyttas nu över till vektorn sortable, med hjälp av metoden insert och ett intervall av move-iterators.

//auto sortable = std::vector<WordFreq>{freqs.begin(), freqs.end()};
auto sortable = std::vector<WordFreq>{};
sortable.reserve(freqs.size());
sortable.insert(sortable.end(), std::make_move_iterator(freqs.begin()), std::make_move_iterator(freqs.end()));

När det gäller sortering, så vet vi att bara de N mest frekventa orden är av intresse, vilket medför att vi kan nöja oss med att sortera dessa, vilket är precis vad partial_sort gör. Här sätter vi N till den minsta av max_words och antal element i sortable, vilket skyddar mot att vi läst in en väldigt liten fil.

//r::sort(sortable, by_freq_desc);
auto const N = std::min<unsigned>(params.max_words, sortable.size());
r::partial_sort(sortable, sortable.begin() + N, by_freq_desc);

I stället för att köra en liten cool pipeline, så är det mer effektivt att sonika kapa bort de osorterade element vi inte behöver. Metoden resize trunkerar innehållet om argumentet är mindre än den aktuella storleken. Sedan, för att inte behöva ändra variabel-namn, behåller vi namnet items och flyttar innehållet från sortable till items.

//auto items = sortable | v::take(params.max_words) | r::to<std::vector<WordFreq>>();
sortable.resize(N);
auto items = std::move(sortable);

Vektorn tags ska ha samma storlek som items.

auto tags = std::vector<string>{};
tags.reserve(items.size());

Till slut, har vi kommit fram till HTML genereringen. Buffert-typen std::ostringstream, som vi använder i baseline, saknar dessvärre en reserve metod, vilket innebär att vi använder ett string-objekt direkt, vilket går att förallokera.

auto html = string{};
html.reserve(500 + (items.size() * 150));
html += R"(<!DOCTYPE html>
    <html lang="en">
        <head>
            <meta charset="UTF-8">
            <meta name="viewport" content="width=device-width, initial-scale=1.0, shrink-to-fit=yes">
            <title>Word Frequencies</title>
        </head>
    <body>)";
html += std::format("<h1>The {} most frequent words in {}</h1>", params.max_words, params.filename.string());
for (string const& tag: tags) html += tag + "\n";
html += "</body></html>\n";

return html;

Så med dessa kod-modifieringar, så kompilerar och kör vi programmet på nytt.

Yes> g++ -std=c++23 -Wall -O3 -march=native  -o using-reserve \
    ../wordcount/utils.cxx ../wordcount/using-reserve.cxx ../wordcount/using-reserve-main.cxx
Yes> ./using-reserve --file ../data/shakespeare.txt
--- WordCount - Using reserve and partial_sort ---
loading 5.3 MB from ../data/shakespeare.txt
written: ./shakespeare.html
elapsed: 129 ms

Ja, det blev en förbättring, men tämligen blygsam 🫤

Version 4 - Optimering av tecken-funktioner

Funktionen bool is_letter(char c) anropas för varje inläst bokstav, vilket är tusentals. Går det att snabba upp denna, samt den tillhörande to_lowercase().

Om vi vet att indata utgörs av engelsk ASCII-text, så går det att förenkla de två funktioner som hanterar tecken och bokstäver. Med hjälp benchmarking kan vi också estimera hur mycket bättre kan det bli.

Jämförande benchmark av is_letter

Jag använder mig av ramverket Google Benchmark. I GitHub repon kan du se hur jag använder CMake för att ladda ned och inkorporera ramverket med övrig kod.

static bool is_letter_orig(char c) {
    const auto ch = static_cast<unsigned char>(c);
    return std::isalpha(ch) || ch == '\'';
}

static bool is_letter_opti(char c) {
    const auto ch = static_cast<unsigned char>(c);
    return ('A' <= ch && ch <= 'Z')
           || ('a' <= ch && ch <= 'z')
           || ch == '\'';
}

static void is_letter_orig_bm(benchmark::State& state) {
    for (auto _ : state) {
        auto result = is_letter_orig('A');
        benchmark::DoNotOptimize(result);
    }
}
BENCHMARK(is_letter_orig_bm)
    ->Unit(benchmark::kNanosecond)
    ->Name("is_letter original");

static void is_letter_opti_bm(benchmark::State& state) {
    for (auto _ : state) {
        auto result = is_letter_opti('A');
        benchmark::DoNotOptimize(result);
    }
}
BENCHMARK(is_letter_opti_bm)
    ->Unit(benchmark::kNanosecond)
    ->Name("is_letter optimized");

När jag kör programmet, så får jag följande utdata

Run on (8 X 1992 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x4)
  L1 Instruction 32 KiB (x4)
  L2 Unified 256 KiB (x4)
  L3 Unified 8192 KiB (x1)
Load Average: 1.71, 0.69, 0.52
--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
is_letter original        11.3 ns         11.5 ns    104799236
is_letter optimized      0.913 ns        0.926 ns    679818028

Följande tabell sammanfattar ovanstående utdata

Det var en signifikant förbättring och helt klart värt att tillämpa i programmet.

Jämförande benchmark av to_lower

Hur blir det då för to_lower? Här följer en benchmark för denna, plus körexempel.

static char to_lower_orig(char c) {
    return static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
}

static char to_lower_opti(char c) {
    if ('A' <= c && c <= 'Z') {
        return static_cast<char>((c - 'A') + 'a');
    }
    return c;
}

static void to_lower_orig_bm(benchmark::State& state) {
    for (auto _ : state) {
        auto result = to_lower_orig('A');
        benchmark::DoNotOptimize(result);
    }
}
BENCHMARK(to_lower_orig_bm)
    ->Unit(benchmark::kNanosecond)
    ->Name("to_lower original");

static void to_lower_opti_bm(benchmark::State& state) {
    for (auto _ : state) {
        auto result = to_lower_opti('A');
        benchmark::DoNotOptimize(result);
    }
}
BENCHMARK(to_lower_opti_bm)
    ->Unit(benchmark::kNanosecond)
    ->Name("to_lower optimized");

--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
to_lower original         8.41 ns         8.53 ns     77731484
to_lower optimized        1.11 ns         1.13 ns    599801894

Sammanfattning av resultatet

Även med denna funktion får vi en förbättring. I och med att den anropas för alla ord så är det värt att byta ut denna också. Dessutom, är det värt att konvertera till gemener redan i samband med inläsningen.

Optimerade tecken-funktioner

Så här ser relevanta delar av fjärde versionen av vårt program ut. Först, modifieringen av read_next i WordIterator.

void read_next() {
    if (input == nullptr) {
        at_eof = true;
        return;
    }

    current_word.clear();
    for (char ch; input->get(ch) && not is_letter(ch);) {}
    if (input->gcount()) input->unget();

    if (current_word.empty() && input->eof()) {
        at_eof = true;
        input = nullptr;
        return;
    }

    for (char ch; input->get(ch) && is_letter(ch);) {
        current_word.push_back(to_lower(ch));
    }
    at_eof = false;
}

static bool is_letter(char c) {
    const auto ch = static_cast<unsigned char>(c);
    return ('A' <= ch && ch <= 'Z')
           || ('a' <= ch && ch <= 'z')
           || ch == '\'';
}

static char to_lower(char c) {
    if ('A' <= c && c <= 'Z') {
        return static_cast<char>((c - 'A') + 'a');
    }
    return c;
}

Sedan, borttagning av to_lowercase i run.

auto load_pipeline =
    r::subrange{WordIterator{infile}, WordIterator{}}
    | v::filter(keep_nonsmall_words)
  //  | v::transform(to_lowercase)
    | v::filter(keep_nonmodern_words);

Kompilerar och kör vi programmet, får vi

Yes> g++ -std=c++23 -Wall -O3 -march=native  -o char-fn \
    ../wordcount/utils.cxx ../wordcount/char-fn.cxx ../wordcount/char-fn-main.cxx
Yes> ./char-fn --file ../data/shakespeare.txt
--- WordCount - Optimized char functions ---
loading 5.3 MB from ../data/shakespeare.txt
written: ./shakespeare.html
elapsed: 108 ms

Hmm, en klar förbättring. Inte så mycket som jag hoppats på. Jag misstänker att kompilator-optimeringen har gjort ganska mycket helt på egen hand. Hursomhelst, en intressant övning, att detaljstudera en del av programmet.

Version 5 - Minnesmappad indata-fil

Låt oss göra en sista optimering, för att se om det går att kapa ned exekveringstiden ytterligare. Denna gång tänkte jag byta ut filhanteringen mot att mappa in text-filen direkt i minnet och därmed ha tillgång till en stor tecken-array.

Dessutom, låta alla text-strängar i freqs representeras av string_view objekt, vilka pekar tillbaka in i den minnesmappade filen. Tanken är att dels snabba upp inläsningen och dels drastiskt minska ned minnesallokeringen av text-strängar.

När väl det är sagt, så vill jag till protokollet nämna att std::string sparar korta strängar direkt i objekten (Short String Optimization), vilket innebär att strängar på 15 eller färre tecken sparas i objektet, utan någon heap-allokering (gäller för GCC). Så man bör förvänta sig blott en marginell förbättring med string_view i detta fall.

Class MemoryMappedFile

Fördelen med att mappa in en fil i minnet är att den då blir en del av det virtuella minnessystemet. Detta system delar in hela adressrummet i lika stora delar, så kallade VM pages. Även det fysiska minnet (RAM) delas in på samma sätt. VM systemet håller reda på vilka pages som finns inlästa i RAM.

Första åtkomst-operationen till en adress inom en VM-page, leder till en så kallad page-fault. När detta inträffar kommer en ledig plats i RAM tas i anspråk. Finns det ingen, så kommer en väljas och innehållet, om det har blivit modifierat, sparas till en dedikerad partition på hårddisken, kallad swap-area. Om en adresserad VM-page finns i swap kommer denna att läsas in. Om den inte var sparad så skapas den ur "tomma intet".

Det är just detta vi är intresserad av för en minnesmappad fil. Genom att mappa om en del av VM till en fil på hårddisken, så kommer filen läsas in som en del av upprepade page-faults. Det här tricket gör man med systemanropet mmap.

Nedan visar jag min implementation. Konstruktorn utför mappningen genom att först öppna filen med systemanropet open och sen anropa mmap. Destruktorn avslutar mappningen. Själva minnessegmentet exponeras med metoden data(), som returnerar ett std::span<char> objekt. Denna datatyp kom i C++20 och är perfekt för att representera ett sammanhängande minnesblock.

Copy, move och default constructors är markerade som delete, vilket innebär att kompilatorn inte genereras dessa medlemmar. Detta för att förhindra att någon kopierar eller flyttar ut ett dylikt objekt från det block det är deklarerat i. Samt, förhindra att man skapar ett objekt utan tillhörande fil.

class MemoryMappedFile {
    void* storage = nullptr;
    size_t size = 0;
public:
    explicit MemoryMappedFile(const fs::path& filename) {
        const auto fd = open(filename.string().c_str(), O_RDWR);
        if (fd == -1) throw std::invalid_argument{"cannot open "s + filename.string()};

        size = fs::file_size(filename);
        storage = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
        if (storage == MAP_FAILED) throw std::runtime_error{"mmap failed: "s + strerror(errno)};
        close(fd);
    }
    ~MemoryMappedFile() {
        munmap(storage, size);
    }
    [[nodiscard]] auto data() const -> std::span<char> {
        return std::span{static_cast<char *>(storage), size};
    }
    MemoryMappedFile() = delete;
    MemoryMappedFile(MemoryMappedFile const&) = delete;
    MemoryMappedFile& operator=(MemoryMappedFile const&) = delete;
    MemoryMappedFile(MemoryMappedFile&&) noexcept = delete;
    MemoryMappedFile& operator=(MemoryMappedFile&&) noexcept = delete;
};

Minnessegmentet skapas med flaggorna PROT_READ | PROT_WRITE, vilket gör segmentet både läs- och skrivbart. Det sistnämnda behövs eftersom vi avser att skriva tillbaka gemener för de bokstäver som är versaler. Så länge man inte anropar systemanropet msync, så kommer inte innehållet i minnesblocket skrivas tillbaka till filen, vilket vi ju inte vill.

Class WordIterator

Denna klass är delvis densamma som tidigare, men med några viktiga förändringar. För att kunna fungera ihop med ett span segment, så returneras string_view objekt, i stället för string dito.

Här är det på sin plats att understryka vikten av att livslängden för samtliga string_view objekt inte får överstiga livslängden för den minnesmappade filen, eftersom all textdata ju pekar rakt in i minnesblocket.

class WordIterator {
    span<char>              payload{};
    span<char>::iterator    current_pos{};
    unsigned                min_length{};
    string_view             current_word{};
    bool                    at_end = true;
public:
    using iterator_concept  = std::input_iterator_tag;
    using iterator_category = std::input_iterator_tag;
    using value_type        = string_view;
    using reference         = value_type;
    using pointer           = void;
    using difference_type   = std::ptrdiff_t;

    WordIterator() = default;
    explicit WordIterator(span<char> payload_, unsigned min_length_)
        : payload(payload_), current_pos(payload.begin()), min_length(min_length_) {
        read_next();
    }

    reference operator*() const { return current_word; }
    WordIterator& operator++() { read_next(); return *this; }
    WordIterator operator++(int) {
        auto tmp = *this; ++(*this); return tmp;
    }

    friend bool operator==(WordIterator const& a, WordIterator const& b) {
        if (a.at_end && b.at_end) return true;
        return a.at_end == b.at_end &&
               a.payload.data() == b.payload.data() &&
               a.current_pos == b.current_pos;
    }
    friend bool operator!=(WordIterator const& a, WordIterator const& b) {
        return !(a == b);
    }
private:
    //...
};

En annan modifiering är att efterbehandlingen av inlästa ord är flyttade direkt till read_next() metoden. Det innebär att denna skippar såväl korta som moderna ord, och omvandlar bokstäver till gemener.

void read_next() {
    while (true) {
        while (current_pos != payload.end() && !is_letter(*current_pos)) {
            ++current_pos;
        }

        if (current_pos == payload.end()) {
            at_end = true;
            current_word = {};
            return;
        }

        auto start = current_pos;
        while (current_pos != payload.end() && is_letter(*current_pos)) {
            *current_pos = to_lower(*current_pos);
            ++current_pos;
        }

        auto sp = span<char>(start, current_pos);;
        auto sv = string_view{sp.data(), sp.size()};
        if (sv.size() < min_length || modern_words.contains(sv)) {
            continue;
        }
        
        current_word = sv;
        at_end = false;
        break;
    }
}

inline static std::unordered_set<string_view> const modern_words = {
    "electronic"sv, "distributed"sv, "copies"sv, "copyright"sv, "gutenberg"sv
};
static bool is_letter(char c) {
    const auto ch = static_cast<unsigned char>(c);
    return ('A' <= ch && ch <= 'Z')
           || ('a' <= ch && ch <= 'z')
           || ch == '\'';
}
static char to_lower(char c) {
    if ('A' <= c && c <= 'Z') {
        return static_cast<char>((c - 'A') + 'a');
    }
    return c;
}

Function WordCount::run()

I huvudfunktionen run() så är givetvis den stora förändringen hur inläsningen sker. Här visar jag detta kod-fragment.

auto freqs = std::unordered_map<string_view, unsigned>{};
//...
freqs.reserve(approx_unique_words);

auto file  = MemoryMappedFile{params.filename};
auto first = WordIterator{file.data(), params.min_length};
auto last  = WordIterator{};
r::for_each(r::subrange{first, last}, [&freqs](string_view word) {
    ++freqs[word];
});

Kompilerar och kör vi programmet, så kan det se ut som följande

Yes> g++ -std=c++23 -Wall -O3 -march=native -o memmap \
    ../wordcount/utils.cxx ../wordcount/mem-map-file.cxx ../wordcount/mem-map-file-main.cxx
Yes> ./memmap  --file ../data/shakespeare.txt
--- WordCount - Memory-mapped file ---
loading 5.3 MB from ../data/shakespeare.txt
written: ./shakespeare.html
elapsed: 35 ms

Oj, oj, oj! Från 1470 ms ned till 35 ms, genom att optimera programmet. 😃

Jämförande benchmark

Det sista jag tänkte göra i denna (alldeles för långa) artikel, är att jämföra de olika versionerna med ett samlande benchmark. Så här ser koden ut. Jag använder mig av Google Benchmark ramverket återigen.

#include <benchmark/benchmark.h>
#include "params.hxx"

namespace ribomation::wordcount::baseline {
    extern auto run(Params const& P) -> std::string;
}
namespace ribomation::wordcount::using_reserve {
    extern auto run(Params const& P) -> std::string;
}
namespace ribomation::wordcount::char_fn {
    extern auto run(Params const& P) -> std::string;
}
namespace ribomation::wordcount::mem_map {
    extern auto run(Params const& P) -> std::string;
}
using ribomation::wordcount::Params;


static void baseline_bm(benchmark::State& state) {
    auto params = Params{};
    for (auto _ : state) {
        auto html = ribomation::wordcount::baseline::run(params);
        benchmark::DoNotOptimize(html);
    }
}
BENCHMARK(baseline_bm)->Unit(benchmark::kMillisecond)->Name("Baseline");

static void reserve_bm(benchmark::State& state) {
    auto params = Params{};
    for (auto _ : state) {
        auto html = ribomation::wordcount::using_reserve::run(params);
        benchmark::DoNotOptimize(html);
    }
}
BENCHMARK(reserve_bm)->Unit(benchmark::kMillisecond)->Name("Using reserve()");

static void characters_bm(benchmark::State& state) {
    auto params = Params{};
    for (auto _ : state) {
        auto html = ribomation::wordcount::char_fn::run(params);
        benchmark::DoNotOptimize(html);
    }
}
BENCHMARK(characters_bm)->Unit(benchmark::kMillisecond)->Name("Opt char fns");

static void memmap_bm(benchmark::State& state) {
    auto params = Params{};
    for (auto _ : state) {
        auto html = ribomation::wordcount::mem_map::run(params);
        benchmark::DoNotOptimize(html);
    }
}
BENCHMARK(memmap_bm)->Unit(benchmark::kMillisecond)->Name("Memory-mapped file");

BENCHMARK_MAIN();

Kör man benchmark programmet, kan det se ut så här.

Yes> ./wordcount-gbench
Run on (8 X 1992 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x4)
  L1 Instruction 32 KiB (x4)
  L2 Unified 256 KiB (x4)
  L3 Unified 8192 KiB (x1)
Load Average: 1.35, 0.89, 0.56
-------------------------------------------------------------
Benchmark                   Time             CPU   Iterations
-------------------------------------------------------------
Baseline                  118 ms          121 ms            5
Using reserve()           116 ms          119 ms            6
Opt char fns             96.7 ms         99.3 ms            7
Memory-mapped file       32.0 ms         32.9 ms           21

Sammanfattning av resultatet

Sammanfattning

I denna artikel har jag stegvis optimerat ett word-count-program som jag tidigare implementerat med C++20/23 ranges och views. Utgångspunkten var en tydlig, men relativt långsam, baseline-version som analyserade Shakespeares samlade verk på cirka 1,5 sekunder.

Genom att först slå på kompilatoroptimeringar (-O3 -march=native) fick vi en stor “gratis” hastighetsökning. Därefter följde mer riktade förbättringar: förallokering av containers och strängar, användning av partial_sort för att bara sortera de mest frekventa orden samt optimerade teckenfunktioner som utnyttjar antagandet om engelsk ASCII-text. Dessa förändringar gav successivt kortare körtider, men utan att påverka programmets funktionalitet.

Den största vinsten kom när filinläsningen byggdes om till att använda en minnesmappad fil (mmap) i kombination med std::span<char> och std::string_view. Då kunde programmet både minska mängden minnesallokeringar och utnyttja operativsystemets virtuella minnessystem mer effektivt, vilket sänkte exekveringstiden från ungefär 1470 ms till runt 35 ms.

Slutligen verifierades förbättringarna med Google Benchmark, där de olika versionerna kördes sida vid sida med identiska parametrar. Förhoppningen är att artikeln inte bara visar hur mycket prestanda man kan plocka ut ur ett till synes enkelt program, utan också ger en konkret metodik för hur man systematiskt kan mäta, resonera om och genomföra optimeringar i modern C++.