1BRC - C med eller utan malloc

Hur implementerar man en hash-tabell i C? Ska man använda malloc eller kan man klara sig utan? Hur ska man resonera om minneshantering i C. Har det tillkommit något nytt i språket de senaste 30 åren?

I vår serie om 1BRC (1 Billion Row Challenge), så har turen nu kommit till C, efter att vi avverkat Java, C++, Python, Perl, JavaScript/Node.js och nu senast Erlang. Gemensamt för all dessa är att det finns en hyfsad uppsättning av datastrukturer att använda. Alla dessa språk har dessutom automatisk minneshantering. I C++ använder man datatyper, som implementerar sin egen minneshantering, vilket är nästan som att arbeta i något av övriga språk. Så icke i C; där får man ordna allt på egen hand.

Om du är ny här, så länkar jag till tidigare artiklar i denna serie, sist i denna artikel. I korthet går programmet jag ämnar skriva, ut på att läsa en textfil med namn på väderstationer och tillhörande temperatur separerade av semikolon och ett sådant par per rad. Temperaturen för respektive väderstation ska aggregeras till medelvärde samt lägsta och högsta temperatur. Resultatet ska skrivas ut sorterat på stationsnamnen i alfabetisk ordning.

Själva temperatur-aggregeringen brukar man hantera med en hash-tabell, där nyckel utgörs av stationsnamnen och värdet av en sammansatt datatyp kallat record/tuple/struct eller liknande. En dylik datastruktur har vi kunnat ta för given oavsett programspråk. Emellertid, gäller det inte för standardbiblioteket till C.

Programstruktur

Jag ämnar designa datastrukturer i denna artikel, som är skräddarsydda för uppgiften. Det innebär att funktionalitet som inte behövs för 1BRC inte finns med. Ett exempel är att hash-tabellen inte behöver kunna ändra sin kapacitet, eftersom vi redan på förhand vet hur många väderstationer det finns i uppgiften, nämligen 413 stycken.

Objekt-orienterad C

Det finns lite olika stilar för hur man implementerar datatyper i C. Den mest klassiska varianten, som för övrigt kom att ligga till grund för designen av C++, brukar ibland kallas för object-oriented C. Den här stilen används i många POSIX typer eller grafikbibliotek.

En datatyp, representeras av en struct och har alltid ett typ-alias, så att man slipper skriva struct framför hela tiden. Om struct:en inte ska peka på ett annat object av samma typ, behöver den inte ha ett namn, bara ett alias.

typedef struct { ... } MyType; 
MyTYpe  my_type = {};

Förutom att definiera typen så kan vi skapa ett objekt genom att deklarera en variabel och använda typ-alias:et. Syntaxen med Type var = {}, är en vidareutveckling i C23 av default-initialization i C11 Type var = {0}. Denna innebär att minnesblocket skrivs över med bara 0:or, för att undvika slumpmässiga startvärden. Denna syntax finns även i modern C++ (C++11). Där kan man också skriva så här Type var{}.

Rent tekniskt betyder syntaxen Type var = {42} att första elementet sätts till det värde som anges inom '{}' och resten av minnesblocket paddas med 0. Den förenklade syntaxen i C23 gör default-initialization mer intuitiv.

Oftast önskar man initiera ett objekt med vissa värden. I C kan man använda designated initializer. Något som också kom i C++20. Så här kan det se ut i modern C.

typedef struct { int a; int b; } MyType; 
MyTYpe  my_type = {.a = 3, .b = 7};

Emellertid, är det för det mesta rekommendabelt att skriva en separat funktion för detta, eftersom man då enkelt kan lägga in validering och initiering av interna variabler. Varje funktion som tillhör en datatyp får ett namn på formen prefix_method(MyType* self, ...). Prefix:et ska vara detsamma för samtliga funktioner som tillhör samma datatyp. Metod-namnet anger vad som ska utföras. Första parameter är alltid en pekare till ett minnesblock av datatypen ifråga. Parameternamnet bör alltid vara densamma, såsom self eller this.

typedef struct { int a; int b; } MyType; 

Mytype* mytype_init(Mytype* self, int x) {
    self->a = 2*x;
    self->b = 3*x;
    return self;
}

MyTYpe  my_type = {};
mytype_init(&my_type, 42);

struct ParseResult

För varje inläst rad från indata-filen, behöver vi splittra upp denna i stationsnamn och temperatur. Eftersom vi behöver två värden ut från vår parsningsfunktion, så representera vi det som en liten struct.

typedef struct {
    char* station;
    double temperature;
} ParseResult;

entry_parse()

Eftersom denna utgör en del av datatypen Entry (se nedan), får funktionen ha prefix entry_.

void entry_parse(ParseResult* self, char* CSV) {
    char* semicolon = strchr(CSV, ';');
    if (semicolon == NULL) {...exit...}
    *semicolon        = '\0';
    self->station     = CSV;
    self->temperature = atof(semicolon + 1);
}

Funktionen tar in en textsträng (Uppsala City;123.4\n), letar efter semikolon via biblioteksfunktionen strchr. Semikolonet skrivs sen över med en null-byte, vilket signalerar slutet på en text i C. Resterande del parsas till en flyttal. Det objekt som skickades in (self) uppdateras med stationsnamn och temperatur.

Några saker att vara observant på är att CSV måste vara modifierbar och att efter anropet pekar self->station rakt in i början av CSV.

Jag använder det eminenta test-ramverket Catch2 för alla enhets-tester. Detta är skrivet i modern C++, men funkar alldeles utmärkt för att test C program också. Så här ser testfunktionen ut.

TEST_CASE("should be possible to parse a CSV string") {
    char CSV[] = "Uppsala City;123.4\n";

    ParseResult r;
    entry_parse(&r, CSV);
    
    REQUIRE(r.station == "Uppsala City"s);
    REQUIRE(r.temperature == 123.4);
}

Här skapar vi först en tecken-array CSV[] för indata och inte som en pekare till text char* CSV = "Uppsala...". Det sistnämnda utgör en textkonstant och leder till programkrasch om man ändrar i den. Vi anropar parse funktioen och utvärderar sen resultatet. Som synes går det lysande att mixa C med C++: r.station == "Uppsala City"s

Vänsterledet är en C text och högerledet är en C++ text. Jämförelse-operatorn är C++ och leder till att vänsterledet implicit konverteras till en C++ text och sen jämförs. Catch2 har också en trevlig hantering av jämförelse av flyttal. Vad som ser enkelt ut r.temperature == 123.4 är i själva verket en olikhet mellan en minsta tolerans och absolutdifferensen av aktuellt och önskat värde.

När man mixar C med C++ är det viktigt att förstå begreppet name-mangling. Detta vill man inte ha för C funktioner anropade från C++. Därför inkluderar man C header-filer på följande vis. Vilket vi gjort i C++ programmet unit-tests.

extern "C" {
#include "entity.h"
}

struct Entry

Den datatyp som hanterar temperatur aggregerandet kallar vi för Entry. Som minimum behöver den innehålla variabler för summa, antal samt minsta och största temperatur-värde för en viss väderstation.

typedef struct {
    double sum;
    unsigned count;
    double min;
    double max;
} Entry;

Fast detta räcker inte, när vi väl börjar implementera hash-tabellen. Av det skälet lägger vi till

• Stationsnamn, så att vi kan skriva ut detta när vi kommer till den delen av programmet
• Hash-nyckel, så att vi kan hålla reda på objektet i hash-tabellen
• Näst-pekare, så att vi kan peka på nästa element i fall vi har en så kallad bucket conflict

enum {
    STATION_MAX_LENGTH = 32
};

typedef struct sEntry {
    char station[STATION_MAX_LENGTH];
    unsigned count;
    double sum;
    double min;
    double max;
    unsigned long key;
    struct sEntry* next;
} Entry;

entry_init()

Vi behöver spara stationsnamnet som en textsträng. I alla andra programspråk så är detta en no-brainer; dock inte i C. Vi kunde peka på en tecken-array som ligger i heap:en, men det är onödigt besvär. I vårt fall har vi en hyfsat bra uppfattning om hur långa text-strängar vi behöver hantera. Av det skälet är det bättre att baka in en tecken-array direkt i vår struct. Som synes kan man använda en anonym enum till att skapa heltalskonstanter (compile-time).

Vi behöver implementera tre primära metoder/funktioner för datatypen Entry. Dels, (1) init, dels (2) update, samt (3) print. Här kommer först init.

Entry* entry_init(Entry* self, const char* station, double temperature) {
    strcpy(self->station, station);
    self->count = 1;
    self->sum = self->min = self->max = temperature;
    self->key = 0;
    self->next = NULL;
    return self;
}

Notera att stationsnamnet kopieras in till tecken-array:en, med biblioteksfunktionen strcpy. Det här förutsätter att vi på förhand vet att antalet teckenplatser räcker till i vänster argument och att texten i höger argument avslutas med en null-byte ('\0'), vilket vi ordnade i entry_parse. Så här är de två funktionerna relaterade. Dvs vi läser in en textrad från indata-filen, splittrar denna och initierar ett entry-objekt.

char CSV[128] = {};
fgets(CSV, sizeof CSV, input_file);
ParseResult r;
entry_parse(&r, CSV);
Entry e;
entry_init(&e, r.station, r.temperature);

Så här ser en enkel testfunktion ut, som validerar init-funktionen.

TEST_CASE("should be possible to initialize an entry object") {
    Entry e;
    entry_init(&e, "Stockholm City", 7);
    REQUIRE(e.count == 1);
    REQUIRE(e.sum == 7);
    REQUIRE(e.station == "Stockholm City"s);
}

entry_new()

I nästa program-steg ska entry-objektet sättas in en hash-tabell, och sen kommer koden ovan att upprepas för nästa textrad. Om vi inte först räddar undan aktuellt värde på e, så kommer det bli överskrivet av nästa inläsningsrunda. I denna artikel ska vi implementera två lösningar på detta. Dels, att på konventionellt vis spara objektet på heap:en (a), och dels på ett mer minnesoptimerat vis genom att inte använda heap:en (b).

Vi börjar med alternativ (a) och fortsätter med detta tills vi är klara med den första programversion, Sen implementerar en programversion enligt alternativ (b).

Att allokera ett minnesblock på heap:en görs i C med malloc (eller calloc). Då init-funktionens första parameter är en pekare till ett Entry objekt, och funktionen returnerar densamma, så kan vi kombinera detta med malloc.

Entry* e = entry_init((Entry*) malloc(sizeof(Entry)), station, temperature);

För övrigt är detta exakt vad som sker i ett C++ program när man skriver Entry* e = new Enntry{station, temperature}; Vi snyggar till användningen genom att lägga in detta i en ny funktion.

Entry* entry_new(const char* station, double temperature) {
    return entry_init((Entry*) malloc(sizeof(Entry)), station, temperature);
}

Entry* e = entry_new(station, temperature);

entry_update()

Nästa funktion hos datatypen Entry, är den som hanterar temperatur-aggregeringen. Den utför samma operation som vi sett i tidigare språkversionen i denna artikelserie.

Entry* entry_update(Entry* self, double temperature) {
    self->count++;
    self->sum += temperature;
    self->min = fmin(temperature, self->min);
    self->max = fmax(temperature, self->max);
    return self;
}

Så här ser ett enkelt enhetstest ut för denna funktion.

TEST_CASE("updating an entry object twice, should set count=3") {
    Entry e;
    entry_init(&e, "Uppsala", 0);
    entry_update(&e, +1);
    entry_update(&e, -1);

    REQUIRE(e.count == 3);
    REQUIRE(e.sum == 0);
    REQUIRE(e.min == -1);
    REQUIRE(e.max == +1);
}

entry_print()

Sista funktionen hos datatypen Entry, är den som skriver ut resultatet för en viss väderstation. Och med denna, är vi klara för att gå vidare till den primära datatypen Hashtable.

void entry_print(Entry* self) {
    printf("%s: %.2f C, %.1f/%.1f (%d)\n",
           self->station,
           self->sum / self->count,
           self->min,
           self->max,
           self->count
    );
}

Hur enhetstestar vi en funktion som skriver ut på stdout, utan att ändra i själva funktionen? Låt mig då visa ett trick man kan använda på Linux.

auto capture_stdout(std::function<void()> stmts) -> std::string {
    char buf[10'000] = {};
    freopen("/dev/null", "a", stdout);
    setvbuf(stdout, buf, _IOFBF, sizeof(buf));
    stmts();
    fflush(stdout);
    freopen("/dev/tty", "a", stdout);
    return buf;
}

TEST_CASE("should be possible to print an entry object") {
    Entry e;
    entry_init(&e, "Stockholm City", 7);

    auto content = capture_stdout([&e](){
        entry_print(&e);
    });
    REQUIRE_THAT(content, StartsWith("Stockholm City"));
    REQUIRE_THAT(content, ContainsSubstring("7.00 C"));
    REQUIRE_THAT(content, EndsWith("(1)\n"));
    REQUIRE_THAT(content, Equals("Stockholm City: 7.00 C, 7.0/7.0 (1)\n"));
}

Funktionen capture_stdout tar ett lambda-uttryck, som anropas och den text som skrivits ut returneras som en C++ sträng, vilken sen kan valideras. Jag kan inte nog understryka hur bekvämt det är att testa C-kod med modern C++ kod.

struct Hashtable

En hash-tabell är en array, där varje element är kan vara en länkad lista av värde-objekt. Väsentligt för att denna ska fungera på önskat sätt är att det är hyfsat glest mellan elementen och att de flesta listor består av ett objekt. I länksamlingen sist i denna artikel, finns en länk till Wikipedia som går igenom allt du behöver i detalj.

Centralt för funktionen av en hash-tabell är en hash-funktion. Dess uppgift är att generera ett positivt heltalsvärde baserat på en nyckel som indata. Om nyckeln är en textsträng, så blir hash-funktionens uppgift att generera ett hyfsat unikt heltalsvärde. Jag googlade runt lite och hittade något användbart på Stack-Overflow.

enum {
    MAX_KEY_STEPS = 7,
};

unsigned long key_of(const char* station) {
    //https://stackoverflow.com/questions/7666509/hash-function-for-string
    //http://www.cse.yorku.ca/~oz/hash.html
    unsigned long hash = 5381;
    unsigned k = 0;
    for (unsigned char ch = *station; ch != '\0' && k < MAX_KEY_STEPS; ch = *++station, ++k) {
        hash = ((hash << 5) + hash) + ch;
    }
    return hash;
}

TEST_CASE("should be possible to generate hash keys") {
    unsigned long key = key_of("Stockholm City");
    REQUIRE(key == 229441708521312);

    unsigned long key2 = key_of("Stockholm City");
    REQUIRE(key == key2);

    unsigned long key3 = key_of("Stocksund");
    REQUIRE_FALSE(key == key3);
    REQUIRE(key3 == 229441708521681);
}

Eftersom vi har förhandsinformation om att det finns 413 stationsnamn, så kan analysera efter hur många inledande tecken ett namnprefix blir unikt. På så sätt besparar vi oss att loop:a igenom långa namn såsom "Las Palmas de Gran Canaria". Så här ser vår struct ut

enum {
    MAX_BUCKETS = 997,
};

typedef struct {
    Entry*      buckets[MAX_BUCKETS];
    unsigned    count;
} HashTable;

Vi behöver ingen init-funktion, utan det räcker med default initialization, vilket innebär att hela minnesblocket blir "nollat". De två primära funktionerna för denna datatyp är insert och get. Vi börjar med insättning.

hashtable_insert()

Insättningsfunktionen tar emot ett Entry-objekt, som ju innehåller stationsnamnet, vilket vi vill använda som nyckel i tabellen. Det första vi gör är att generera en nyckel och sen beräkna modulo på array:ens storlek så att vi erhållet ett insättningsindex.

void hashtable_insert(HashTable* self, Entry* entry) {
    unsigned long  key   = key_of(entry->station);
    unsigned int   index = key % MAX_BUCKETS;
    entry->key  = key;
    entry->next = self->buckets[index];
    self->buckets[index] = entry;
    self->count++;
}

Efter det länkar vi in Entry-objektet först i den länkade listan för vald plats. Som redan nämnts tidigare, så förutsätter vi att de flesta listor kommer att bara bestå av ett element. Emellertid, finns det en viss risk för bucket conflict, då två nycklar resulterar i samma index, vilket är skälet till att vi måste vara beredda på att trycka in fler än ett objekt i en bucket.

hashtable_get()

Uppslagnings-funktionen börjar på samma sätt genom ta fram en bucket, som sen traverseras för att hitta önskat element. Hittas inget, returneras NULL annars pekaren till funnet objekt.

Entry* hashtable_get(HashTable* self, const char* station) {
    unsigned long  key    = key_of(station);
    unsigned int   index  = key % MAX_BUCKETS;
    Entry*         bucket = self->buckets[index];
    for (Entry* e = bucket; e != NULL; e = e->next) {
        if (e->key == key) return e;
    }
    return NULL;
}

hashtable_dispose()

Om Entry-objekten ligger på heap:en, behöver dessa städas undan när man är klar med ett hash-tabells objekt. Det görs med dispose funktionen, vilken skannar efter icke-tomma buckets och loopar igenom dess listor rekursivt, så att objekten städas bort från slutet av varje lista. Kom ihåg att i de flesta fall, så har varje lista bara en medlem.

static void entry_dispose(Entry* e) {
    if (e == NULL) return;
    entry_dispose(e->next);
    free(e);
}

void hashtable_dispose(HashTable* self) {
    for (unsigned k = 0; k < MAX_BUCKETS; ++k) {
        if (self->buckets[k] != NULL) {
            entry_dispose(self->buckets[k]);
        }
    }
}

Funktionen entry_dispose är deklarerad som static, vilket innebär att den är helt privat för den källkodsfil funktionen är deklarerad i.

Enhetstester

Test-ramverket Catch2 möjliggör också att skriva ett så kallat scenario, vilket är vida överlägset vad som erbjuds i andra test-ramverk såsom Google Test med flera. Så här ser vårt första testfall ut, där vi sätter in ett enstaka objekt.

SCENARIO("simple hashtable usage") {
    GIVEN("a hash-table") {
        HashTable tbl{};

        THEN("is should start as empty") {
            REQUIRE(tbl.count == 0);
        }

        WHEN("inserting a single entry") {
            hashtable_insert(&tbl, entry_new("Uppsala", -5.5));
            THEN("the count == 1") {
                REQUIRE(tbl.count == 1);
            }

            AND_WHEN("retrieving the entry") {
                Entry* e = hashtable_get(&tbl, "Uppsala");
                THEN("it should be found") {
                    REQUIRE_FALSE(e == NULL);
                    REQUIRE(e->count == 1);
                    REQUIRE(e->sum == -5.5);
                }
            }

            AND_WHEN("looking for something else") {
                Entry* e = hashtable_get(&tbl, "Sundsvall");
                THEN("it should NOT be found") {
                    REQUIRE(e == NULL);
                }
            }
        }

        hashtable_dispose(&tbl);
    }
}

När man kör detta scenario, blir utskriften på följande vis.

Scenario: simple hashtable usage
      Given: a hash-table
       Then: is should start as empty

Scenario: simple hashtable usage
      Given: a hash-table
       When: inserting a single entry
       Then: the count == 1

Scenario: simple hashtable usage
      Given: a hash-table
       When: inserting a single entry
   And when: retrieving the entry
       Then: it should be found

Scenario: simple hashtable usage
      Given: a hash-table
       When: inserting a single entry
   And when: looking for something else
       Then: it should NOT be found

Notera att varje THEN-gren utgör ett eget test-fall, där det skapas ett nytt hash-tabells-objekt för varje omgång och att innehållet städas upp efter varje omgång. Jämför detta med andra test-ramverk för C++, där man måste skriva klasser med SetUp och TearDown metoder.

Vi har ett annat scenario med flera insättningar, vilket jag visar här nedan.

#define ARR_SIZE(arr)   (sizeof(arr) / sizeof(arr[0]))

typedef struct {
    char   name[STATION_MAX_LENGTH];
    double temperature;
} Measurement;

Measurement data[] = {
        {"Uppsala",   10.0},
        {"Stockholm", -3.0},
        {"Göteborg",  -1.0},
        {"Umeå",      -15.0},
        {"Uppsala",   5.0},
        {"Stockholm", 6.0},
        {"Uppsala",   -3.0},
};
constexpr unsigned data_size = ARR_SIZE(data);

SCENARIO("typical hashtable usage") {
    GIVEN("a hash-table and a bunch of data") {
        HashTable   tbl{};

        WHEN("inserting all data") {
            for (unsigned k = 0; k < data_size; ++k) {
                Entry* e = hashtable_get(&tbl, data[k].name);
                if (e == NULL) {
                    e = entry_new(data[k].name, data[k].temperature);
                    hashtable_insert(&tbl, e);
                } else {
                    entry_update(e, data[k].temperature);
                }
            }

            THEN("there should be 4 items") {
                REQUIRE(tbl.count == 4);
            }

            AND_WHEN("fetching Uppsala") {
                Entry* e = hashtable_get(&tbl, "Uppsala");
                
                THEN("its count == 3 and sum == 12") {
                    REQUIRE_FALSE(e == NULL);
                    REQUIRE(e->count == 3);
                    REQUIRE(e->sum == 12.0);
                    REQUIRE(e->min == -3.0);
                    REQUIRE(e->max == 10.0);
                }
            }
        }

        hashtable_dispose(&tbl);
    }
}

Scenario: typical hashtable usage
      Given: a hash-table and a bunch of data
       When: inserting all data
       Then: there should be 4 items

Scenario: typical hashtable usage
      Given: a hash-table and a bunch of data
       When: inserting all data
   And when: fetching Uppsala
       Then: its count == 3 and sum == 12

hashtable_entries()

Om du följt med i vår artikel-serie, så har du en hyfsad koll på hur själva programmet fungerar. Dvs, läs radvis, splittra och aggregera, samt skriv ut resultaten sorterat på stationsnamn. Vi ska nu adressera den sista delen här. I andra programspråk har det varit enkelt. Antingen med hjälp av en sorterande data-struktur som en TreeMap, eller genom att hälla över all data till en lista och sortera denna. Hur ska implementera det sistnämnda i C?

Det gör vi genom att traversera samtliga buckets och kopiera pekarvärdena till en lämpligt stor array. Sen anropar vi den sorterings-funktion som finns i C biblioteket och skickar med en pekare till en komparator-funktion, som jämför stationsnamn. Som synes kan vi välja om vi vill populera och sortera en befintlig array, eller dessutom allokera array:en på heap:en.

int entry_comparator(const void* a, const void* b) {
    const Entry* lhs = *(const Entry**) a;
    const Entry* rhs = *(const Entry**) b;
    return strcmp(lhs->station, rhs->station);
}

Entry** hashtable_entries(HashTable* self, Entry** entries) {
    unsigned index = 0;
    for (unsigned k = 0; k < MAX_BUCKETS; ++k) {
        if (self->buckets[k] != NULL) {
            for (Entry* e = self->buckets[k]; e != NULL; e = e->next) {
                entries[index++] = e;
            }
        }
    }
    qsort(entries, self->count, sizeof(Entry*), entry_comparator);
    return entries;
}

Entry** hashtable_entries_alloc(HashTable* self) {
    Entry** entries = (Entry**) calloc(self->count, sizeof(Entry*));
    return hashtable_entries(self, entries);
}

Så här vårt enhets-test ut, tillsammans med utskrifterna.

SCENARIO("hashtable entries") {
    GIVEN("a hash-table and a bunch of data") {
        HashTable tbl{};

        WHEN("inserting all data") {
            for (unsigned k = 0; k < data_size; ++k) {
                Entry* e = hashtable_get(&tbl, data[k].name);
                if (e == NULL) {
                    e = entry_new(data[k].name, data[k].temperature);
                    hashtable_insert(&tbl, e);
                } else {
                    entry_update(e, data[k].temperature);
                }
            }

            THEN("there should be 4 items, as before") {
                REQUIRE(tbl.count == 4);
            }

            AND_WHEN("getting all entries, as an array of pointers") {
                Entry** entries = hashtable_entries_alloc(&tbl);

                THEN("it should be sorted, indeed") {
                    std::string names[] = {
                            "Göteborg", "Stockholm", "Umeå", "Uppsala"
                    };
                    constexpr unsigned names_size = ARR_SIZE(names);
                    for (unsigned k = 0; k < names_size; ++k) {
                        REQUIRE(names[k] == entries[k]->station);
                    }
                }

                free(entries);
            }
        }

        hashtable_dispose(&tbl);
    }
}

Scenario: hashtable entries
      Given: a hash-table and a bunch of data
       When: inserting all data
       Then: there should be 4 items, as before

Scenario: hashtable entries
      Given: a hash-table and a bunch of data
       When: inserting all data
   And when: getting all entries, as an array of pointers
       Then: it should be sorted, indeed

Calc. Avg. using malloc

Efter att vi diskuterat de olika beståndsdelarna av huvudprogrammet är det (äntligen) dags att gå igen den första programversionen. Så här ser main ut.

int main(int argc, char** argv) {
    ElapsedTime t;
    elapsed_start(&t);

    char* filename = "../../../data/weather-data-1M.csv";
    if (argc > 1) {
        filename = argv[1];
    }
    printf("filename: %s\n----\n", filename);

    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        fprintf(stderr, "cannot open '%s'", filename);
        exit(1);
    }

    HashTable data = {};
    char CSV[128] = {};
    while (fgets(CSV, sizeof CSV, file) != NULL) {
        ParseResult parseResult;
        entry_parse(&parseResult, CSV);
        Entry* e = hashtable_get(&data, parseResult.station);
        if (e == NULL) {
            e = entry_new(parseResult.station, parseResult.temperature);
            hashtable_insert(&data, e);
        } else {
            entry_update(e, parseResult.temperature);
        }
    }
    fclose(file);

    Entry** entries = hashtable_entries_alloc(&data);
    for (unsigned k = 0; k < data.count; ++k) {
        entry_print(entries[k]);
    }
    free(entries);
    hashtable_dispose(&data);
    printf("----\n");

    fprintf(stderr, "[C w malloc] elapsed %.3f seconds, %s\n", elapsed_time(&t), filename);
}

Förutom att starta stopp-uret, så öppnar vi infilen med fopen. I while-loop:en som följer läser vi en rad i taget, splittrar raden i stationsnamn och temperatur, letar efter namnet i hash-tabellen, om den inte finns allokerar vi ett Entry objekt på heap:en och stoppar in detta i tabellen, annars uppdaterar vi det objekt som redan finns på plats.

Efter while-loop:en, stänger vi filen med fclose, plockar ut en dynamiskt allokerad array sorterad på stationsnamnen, skriver ut innehållet, och sen till sist, städar upp på heap:en och läser av och skriver ut förfluten tid.

struct ElapsedTime

Vi har en liten hjälp-datatyp som kapslar in detaljerna för tidsmätningen. Så här ser koden ut.

typedef struct {
    struct timeval startTime;
} ElapsedTime;

void elapsed_start(ElapsedTime* t) {
    gettimeofday(&(t->startTime), NULL);
}

double elapsed_time(ElapsedTime* t) {
    struct timeval endTime;
    gettimeofday(&endTime, NULL);
    return (endTime.tv_sec + endTime.tv_usec * 1E-6)
           - (t->startTime.tv_sec + t->startTime.tv_usec * 1E-6);
}

Exekvering

Jag använder CMake för att bygga applikationen. I länksamlingen i slutet av denna artikel, finns en länk till all källkod, inklusive CMakeLists.txt filen. Kör vi programmet med den lilla indata-filen, kan det se ut så här

$ cmake -S . -B bld -DCMAKE_BUILD_TYPE=Release
. . .
$ cmake --build bld
. . .
$ ./bld/calc-with-malloc ../../data/weather-data-tiny.csv 
filename: ../../data/weather-data-tiny.csv
----
Cairo: 28.30 C, 28.3/28.3 (1)
Changsha: -0.10 C, -0.1/-0.1 (1)
Douala: 25.70 C, 25.7/25.7 (1)
Hong Kong: 28.40 C, 28.4/28.4 (1)
Kampala: 5.30 C, 5.3/5.3 (1)
Knutby: -6.63 C, -24.2/8.5 (3)
Las Palmas de Gran Canaria: 23.50 C, 23.5/23.5 (1)
Madrid: 18.60 C, 18.6/18.6 (1)
Stockholm: 30.40 C, 30.4/30.4 (1)
Sundsvall: 18.10 C, 18.1/18.1 (1)
Uppsala: 5.10 C, -5.0/14.0 (4)
Zürich: 10.30 C, 10.3/10.3 (1)
İzmir: 9.90 C, 9.9/9.9 (1)
----
[C w malloc] elapsed 0.004 seconds, ../../data/weather-data-tiny.csv

Vi kan också köra programmet med valgrind, för att säkerställa att vi inte har några minnesläckage. Tänk på att kompilera för debug, så att valgrind kan rapportera om var eventuell fel finns.

$ cmake -S . -B bld -DCMAKE_BUILD_TYPE=Debug
. . .
$ cmake --build bld
. . .
$ valgrind --leak-check=full --show-leak-kinds=all \
           ./bld/calc-with-malloc ../../data/weather-data-100K.csv > /dev/null
==162460== Memcheck, a memory error detector
==162460== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==162460== Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
==162460== Command: ./bld/calc-with-malloc ../../data/weather-data-100K.csv
==162460==
[C w malloc] elapsed 0.691 seconds, ../../data/weather-data-100K.csv
==162460== 
==162460== HEAP SUMMARY:
==162460==     in use at exit: 0 bytes in 0 blocks
==162460==   total heap usage: 416 allocs, 416 frees, 48,120 bytes allocated
==162460==
==162460== All heap blocks were freed -- no leaks are possible
==162460==
==162460== For lists of detected and suppressed errors, rerun with: -s
==162460== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Calc. Avg. not using malloc

Allokering av minnesblock på heap:en kan ibland vara en källa till prestandaförlust. Gäller det också för vårt program? Låt oss undersöka saken, genom att adressera de programdelar där vi anropar malloc/calloc. Vi gör detta i två av våra funktioner, enligt nedan. Tänk på att det kan finnas biblioteks-funktioner som också gör det.

Entry* entry_new(const char* station, double temperature) {
    return entry_init((Entry*) malloc(sizeof(Entry)), station, temperature);
}

Entry** hashtable_entries_alloc(HashTable* self) {
    Entry** entries = (Entry**) calloc(self->count, sizeof(Entry*));
    return hashtable_entries(self, entries);
}

Entry Object Storage

Vi ersätter malloc(sizeof(Entry)) med en array av lämplig storlek. Givetvis måste man ha järnkoll på maximalt antal objekt som kan allokeras. I vårt fall vet vi ju att det finns 413 stationsnamn, varför vi kan välja detta eller ett värde en bit ovanför.

enum { ENTRY_STORAGE_SIZE = 512 };
Entry   entry_storage[ENTRY_STORAGE_SIZE] = {0};
Entry*  entry_storage_next = &entry_storage[0];

Att allokera ett nytt objekt, dvs ersätta anropet till entry_new, gör vi på följande vis.

Entry* e = entry_storage_next++;
entry_init(e, parseResult.station, parseResult.temperature);

Tänk på att om du skulle vara osäker på om storage verkligen räcker till, så bör du infoga ett test så att next-pekaren inte faller utanför storage.

Entries Array Storage

Vi ersätter calloc(data.count, sizeof(Entry*)) med en array av lämplig storlek och fyller upp den med pekare till Entry objekt.

Entry* entries[ENTRY_STORAGE_SIZE] = {0};
hashtable_entries(&data, entries);

Nytt huvudprogram

De två ändringar ovan är allt vi behöver göra. Så här ser main ut för vårt modifierade program.

int main(int argc, char** argv) {
    ElapsedTime t;
    elapsed_start(&t);

    char* filename = "../../../data/weather-data-1M.csv";
    if (argc > 1) { filename = argv[1]; }
    printf("filename: %s\n----\n", filename);

    FILE* file = fopen(filename, "r");
    if (file == NULL) {...}

    // Entry heap
    enum { ENTRY_STORAGE_SIZE = 512 };
    Entry   entry_storage[ENTRY_STORAGE_SIZE] = {0};
    Entry*  entry_storage_next = &entry_storage[0];

    // Hash/table
    HashTable data = {0};

    char CSV[128] = {};
    while (fgets(CSV, sizeof CSV, file) != NULL) {
        ParseResult parseResult;
        entry_parse(&parseResult, CSV);
        Entry* e = hashtable_get(&data, parseResult.station);
        if (e == NULL) {
            e = entry_storage_next++;
            entry_init(e, parseResult.station, parseResult.temperature);
            hashtable_insert(&data, e);
        } else {
            entry_update(e, parseResult.temperature);
        }
    }
    fclose(file);

    // Entries list
    Entry* entries[ENTRY_STORAGE_SIZE] = {0};
    hashtable_entries(&data, entries);
    for (unsigned k = 0; k < data.count; ++k) { entry_print(entries[k]); }
    printf("----\n");

    fprintf(stderr, "[C w/o malloc] elapsed %.3f seconds, %s\n", elapsed_time(&t), filename);
}

Exekvering

Kör vi programmet med den lilla indata-filen, kan det se ut så här

$ ./bld/calc-without-malloc ../../data/weather-data-tiny.csv 
filename: ../../data/weather-data-tiny.csv
----
Cairo: 28.30 C, 28.3/28.3 (1)
Changsha: -0.10 C, -0.1/-0.1 (1)
Douala: 25.70 C, 25.7/25.7 (1)
Hong Kong: 28.40 C, 28.4/28.4 (1)
Kampala: 5.30 C, 5.3/5.3 (1)
Knutby: -6.63 C, -24.2/8.5 (3)
Las Palmas de Gran Canaria: 23.50 C, 23.5/23.5 (1)
Madrid: 18.60 C, 18.6/18.6 (1)
Stockholm: 30.40 C, 30.4/30.4 (1)
Sundsvall: 18.10 C, 18.1/18.1 (1)
Uppsala: 5.10 C, -5.0/14.0 (4)
Zürich: 10.30 C, 10.3/10.3 (1)
İzmir: 9.90 C, 9.9/9.9 (1)
----
[C w/o malloc] elapsed 0.003 seconds, ../../data/weather-data-tiny.csv

Givetvis ska vi låta valgrind undersöka den modifierade versionen av programmet. Kom ihåg att kompilera med debug-info, så att eventuella fel kan pekas ut. Så här ser det ut

$ valgrind  --leak-check=full --show-leak-kinds=all ./bld/calc-without-malloc ../../data/weather-data-100K.csv > /dev/null
==163533== Memcheck, a memory error detector
==163533== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==163533== Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
==163533== Command: ./bld/calc-without-malloc ../../data/weather-data-100K.csv
==163533== 
[C w/o malloc] elapsed 0.641 seconds, ../../data/weather-data-100K.csv
==163533== 
==163533== HEAP SUMMARY:
==163533==     in use at exit: 0 bytes in 0 blocks
==163533==   total heap usage: 4 allocs, 4 frees, 11,952 bytes allocated
==163533== 
==163533== All heap blocks were freed -- no leaks are possible
==163533== 
==163533== For lists of detected and suppressed errors, rerun with: -s
==163533== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Som synes finns det några få allokeringar kvar, vilka utförs av biblioteks-funktioner.

Utvärdering

Först kompilerar med optimering

$ rm -rf bld
$ cmake -S . -B bld -DCMAKE_BUILD_TYPE=Release
. . .
$ cmake --build bld --target calc-with-malloc
$ cmake --build bld --target calc-without-malloc
$ $ ./bld/calc-with-malloc ../../data/weather-data-100K.csv > /dev/null
[C w malloc] elapsed 0.053 seconds, ../../data/weather-data-100K.csv
$ ./bld/calc-without-malloc ../../data/weather-data-100K.csv > /dev/null
[C w/o malloc] elapsed 0.052 seconds, ../../data/weather-data-100K.csv

Tabellen nedan summerar exekveringstiderna för körningar av programmen med olika filstorlekar.

Som synes i tabell här, är förbättringen helt marginell och inte värd mödan. När jag körde programmen upprepade gånger hände det ibland att det andra programmet tog längre tid.

Om vi jämför första programmet med mitt o-optimerade C++ program från en tidigare artikel, så ser vi något kolossalt intressant. Först kommer programkoden, så du slipper surfa iväg.

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);
    }
};

int main(int argc, char** argv) {
    auto startTime = cr::high_resolution_clock::now();
    auto filename  = "../../../data/weather-data-tiny.csv"s;
    if (argc == 2) { filename = argv[1]; }
    cout << "filename: " << filename << "\n----\n";

    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);
    for (string line; std::getline(f, line);) {
        auto semi = line.find(';');
        auto name = line.substr(0, semi);
        auto temp = std::stod(line.substr(semi + 1));
        data[name] += temp;
    }

    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";

    auto endTime = cr::high_resolution_clock::now();
    auto elapsed = cr::duration<double, std::ratio<1, 1>>{endTime - startTime};
    std::cerr << std::format("[C++] elapsed {:.3f} seconds, {}\n", elapsed.count(), filename);
}

Så här ser exekveringstiderna ut.

C++ programmet som använder vanlig minnes-allokering, är betydligt snabbare ju större fil-storlek vi har! 😮 Det såg man inte komma.

Alltså, valet av effektivt implementerade data-strukturer är helt avgörande för prestandan. Att välja programspråket C pga en förutfattad mening att DIY (Do It Yourself) alltid blir snabbare är helt enkelt inte sant. För att komma i kapp C++ programmet, måste man lägga ned en substantiell möda på att hitta effektivt implementerade data-strukturer i C och inte knåpa ihop något på egen hand.