Hva CS50 til slutt lærte meg om C

CS50s speller-oppgave er der pekere faktisk ble ekte for meg, ikke forelesningen som introduserer dem. Det er også oppgaven som holdt meg oppe to netter etter jeg egentlig skulle vært ferdig med den, så denne har litt historie.

Jeg hadde brukt Python i årevis på det tidspunktet (et Django-CRM, en haug med scrapere, bookbot fra boot.dev) uten noensinne å måtte tenke på minne som noe jeg administrerte selv. Python spør deg bare ikke om det. C spør deg med en gang, og speller er oppgaven som får deg til faktisk å svare.

oppgaven, omtrent

Last en ordbok på omtrent 143 tusen ord inn i en hashtabell, med lenkede lister for kollisjoner, og stavekontroller så en tekstfil mot den raskt nok til at check50 ikke tidsavbryter. Startkoden gir deg header-filen med funksjonssignaturene: load, check, hash, size, unload. Alt annet bygger du selv.

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

En lenket liste av disse, én per hash-bøtte. Første gang jeg faktisk måtte forstå at next ikke er en kopi av neste node, det er adressen til den, var øyeblikket forelesningens whiteboard-diagrammer ble til noe jeg kunne resonnere om i stedet for bare å nikke med til.

min første hash-funksjon, som var dårlig med vilje uten å mene å være det

CS50 forteller deg på forhånd at hash-funksjonen er der hastigheten lever eller dør, og jeg tok ikke det seriøst første gangen.

unsigned int hash(const char *word)
{
    return tolower(word[0]) % N;
}

Første bokstav i ordet, modulo tabellstørrelsen. Den kompilerte. Den kjørte til og med riktig, i den forstand at check fortsatt returnerte riktig svar for hvert ord. Den brukte bare rundt førti sekunder på å laste og sjekke en ekte ordbok, noe check50 ikke anser som en godkjent tid.

hva det faktisk betydde

Tjueseks bokstaver spredt over hvor mange bøtter jeg enn hadde satt N til betydde at hver bøtte inneholdt tusenvis av ord i én lang lenket liste, og å slå opp et ord betydde å gå gjennom hele den listen, én node om gangen, sammenligne strenger. En hashtabell er bare rask hvis hashingen faktisk sprer ordene ut. Min var i praksis bare én kjempestor lenket liste per startbokstav, som er en verre versjon av tingen lenkede lister egentlig skal hjelpe med.

fiksen, og hvor den faktiske buggen fortsatt lå

Jeg byttet til en ekte strenghash, den typen som blander inn hvert eneste tegn i stedet for bare det første.

unsigned int hash(const char *word)
{
    unsigned int h = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        h = (h * 31) + tolower(word[i]);
    }
    return h % N;
}

Lastetiden falt fra førti sekunder til under to. Den delen føltes flott. Det som ikke føltes flott var segfaulten dette introduserte i load(), som jeg ikke hadde rørt, på nøyaktig den samme ordboken som hadde fungert fint en time tidligere.

hvor det faktisk gikk i stykker

node *n = malloc(sizeof(node));
strcpy(n->word, word);
n->next = table[index];
table[index] = n;

Så bra ut. Kjørte fint på den lille ordboken. valgrind (som CS50 får deg til faktisk å bruke, ikke bare nevne i en forelesning) fortalte meg nøyaktig hva som var galt så snart jeg kjørte den mot den store.

==12345== Invalid write of size 1
==12345==    at 0x1091A2: load (dictionary.c:47)
==12345==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

Jeg sjekket ikke mallocs returverdi, og på den store ordboken, dypt nok inn i en kjøring, feilet én allokering faktisk. Med den dårlige hash-funksjonen hadde dette aldri kommet til overflaten, fordi alt var så tregt at minnepresset aldri bygget seg opp på samme måte før testrammeverket ga opp å vente. Den raskere hash-funksjonen betydde at flere allokeringer skjedde på kortere tid, noe som betydde at jeg faktisk traff feiltilfellet min gamle, tregere, dårligere kode hadde skjult for meg hele tiden ved et uhell.

Én if (n == NULL) return false; fikset det. Buggen handlet egentlig ikke om pekere i det hele tatt. Den handlet om å anta at en funksjon som kan feile alltid vil lykkes, fordi den gjorde det de første femti gangene jeg kjørte den, og å gjøre resten av programmet raskere er nøyaktig den typen endring som kan avsløre en bug som alltid var der.

den andre buggen, i en helt annen funksjon

unload() skal gå gjennom hver bøtte og frigjøre hver node. Min så, for meg, helt riktig ut:

bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];
        while (cursor != NULL)
        {
            free(cursor);
            cursor = cursor->next;
        }
    }
    return true;
}

valgrind igjen, tålmodig som alltid:

==12345== Invalid read of size 8
==12345==    at 0x109310: unload (dictionary.c:63)
==12345==  Address 0x51fc0a0 is 0 bytes inside a block of size 24 free'd

Les-etter-frigjort. Jeg frigjorde cursor, og leste så umiddelbart cursor->next fra minne jeg nettopp hadde fortalt allokatoren at den kunne gjenbruke. På denne spesifikke kjøringen holdt det seg til å ha riktig verdi, helt til det av og til ikke gjorde det, som er nøyaktig den typen bug som består lokalt og feiler et annet sted uten noen grunn du kan se. Fiksen var å lagre neste-pekeren før den nåværende noden frigjøres, ikke etter.

node *cursor = table[i];
while (cursor != NULL)
{
    node *next = cursor->next;
    free(cursor);
    cursor = next;
}

To bugs, samme oppgave, samme grunnårsak under begge: jeg fortsatte å bruke en pekers verdi etter øyeblikket det sluttet å være trygt å stole på den, én gang fordi en funksjon jeg kalte kunne feile stille, én gang fordi jeg allerede hadde fortalt systemet at det minnet var fritt til gjenbruk. C stopper deg ikke fra å gjøre noen av delene. Den viser deg det bare til slutt, på et tidspunkt og sted den selv velger, som som regel ikke er linjen der den faktiske feilen ble gjort.

en mindre sidebemerkning, siden å være oppe på denne oppgaven fortjener en ærlig avstikker

Et sted rundt klokken ett på den andre natten ble jeg overbevist om at selve ordbokfilen var korrupt, fordi en spesifikk kjøring oppførte seg annerledes enn en identisk utseende tidligere kjøring. Det var ikke filen. Det var at den malloc-feilen var sannsynlighetsbasert under minnepress, ikke deterministisk, så nøyaktig samme input utløste den ikke alltid, avhengig av hva annet maskinen tilfeldigvis holdt på med. Jeg brukte en genuint flau mengde tid på å diffe en ordbokfil mot seg selv før jeg godtok at buggen var i koden min, ikke dataene.

hva som faktisk satte seg

Ikke syntaksen. Regelen: hver peker peker enten et sted ekte, eller den er NULL, eller den er søppel, og C vil aldri fortelle deg hvilken, så det må du. Python beskytter deg stille fra noensinne å måtte tenke på det. C gir deg hele ansvaret og holder seg for det meste unna, inkludert ansvaret for å ikke lese minne i samme øyeblikk du har frigjort det.

hva jeg ville gjort annerledes på neste oppgave

Kjøre valgrind fra aller første fungerende versjon, ikke bare når noe går i stykker. Begge buggene her satt i kode som så bra ut og besto tilfeldig testing en stund før de faktisk kom til overflaten. Å vente på et krasj før man går og leter etter verktøyet som ville fanget det tidligere er en vane jeg gjerne vil avlære før den koster meg mer enn én sen kveld.

Jeg stoler fortsatt ikke helt på min egen pekerartimetikk på arrays. Det er et problem for en senere oppgave.