# 1BRC - C med eller utan malloc 5 februari 2024 | https://www.ribomation.se/blog/2024/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. ```cpp 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. ```cpp 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`. ```cpp 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. ```cpp 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_`. ```cpp 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. ```cpp 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`. ```cpp 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. ```cpp 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_ ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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`. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp auto capture_stdout(std::function 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_. ```cpp 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 ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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. ```text 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. ```cpp #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); } } ``` ```text 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. ```cpp 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. ```cpp 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); } } ``` ```text 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. ```cpp 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. ```cpp 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 ```shell $ 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. ```shell $ 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. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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. ```cpp 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 ```shell $ ./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 ```shell $ 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 ```shell $ 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. # Rows With malloc \[s\] Without malloc \[s\] Reduction \[%\] 1 100.000 0,053 0,052 98% 2 1.000.000 0,480 0,466 97% 3 10.000.000 4,778 4,563 96% 4 100.000.000 103,001 97,553 95% 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. ```cpp struct Aggregation { unsigned count = 0; double sum = 0; double min = std::numeric_limits::max(); double max = std::numeric_limits::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{}; 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>{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>{endTime - startTime}; std::cerr << std::format("[C++] elapsed {:.3f} seconds, {}\n", elapsed.count(), filename); } ``` Så här ser exekveringstiderna ut. # Rows C \[s\] C++ \[s\] Reduction \[%\] 1 100.000 0,053 0,078 147% 2 1.000.000 0,480 0,407 85% 3 10.000.000 4,778 4,129 86% 4 100.000.000 103,001 55,606 54% 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.