Lo que CS50 finalmente me enseñó sobre C

El problema speller de CS50 es donde los punteros se volvieron reales de verdad para mí, no la clase que los presenta. También es el pset que me tuvo despierto dos noches más de lo que pretendía, así que este tiene algo de historia.

Para entonces ya llevaba años usando Python (un CRM en Django, un montón de scrapers, bookbot de boot.dev) sin necesitar nunca pensar en la memoria como algo que administraba yo mismo. Python simplemente no te lo pide. C te lo pide de inmediato, y speller es la tarea que te obliga a responder de verdad.

el pset, a grandes rasgos

Cargar un diccionario de unas 143 mil palabras en una tabla hash, usando listas enlazadas para las colisiones, y luego corregir un archivo de texto contra ella lo bastante rápido como para que check50 no expire por tiempo. El código inicial te da el archivo de cabecera con las firmas de las funciones: load, check, hash, size, unload. Todo lo demás lo construyes tú.

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

Una lista enlazada de estos, uno por cubo del hash. La primera vez que de verdad necesité entender que next no es una copia del siguiente nodo, sino su dirección, fue el momento en que los diagramas de la pizarra de la clase se convirtieron en algo sobre lo que podía razonar en vez de solo asentir.

mi primera función hash, que era mala a propósito sin querer serlo

CS50 te dice desde el principio que la función hash es donde vive o muere la velocidad, y no me lo tomé en serio la primera vez.

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

La primera letra de la palabra, módulo el tamaño de la tabla. Compilaba. Incluso corría correctamente, en el sentido de que check seguía devolviendo la respuesta correcta para cada palabra. Solo que tardaba unos cuarenta segundos en cargar y comprobar un diccionario real, cosa que check50 no considera un tiempo aprobado.

lo que eso significaba en realidad

Veintiséis letras repartidas entre los cubos que fuera que hubiera puesto en N significaba que cada cubo contenía miles de palabras en una única lista enlazada larga, y buscar una palabra significaba recorrer esa lista entera, un nodo a la vez, comparando cadenas. Una tabla hash solo es rápida si el hashing de verdad reparte las palabras. La mía era funcionalmente solo una lista enlazada gigante por letra inicial, que es una versión peor de aquello con lo que se supone que ayudan las listas enlazadas.

el arreglo, y dónde seguía estando el bug real

Cambié a un hash de cadenas de verdad, del tipo que mezcla cada carácter en lugar de solo el primero.

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

El tiempo de carga cayó de cuarenta segundos a menos de dos. Esa parte se sintió genial. Lo que no se sintió genial fue el segfault que esto introdujo en load(), que no había tocado, con exactamente el mismo diccionario que había funcionado bien una hora antes.

dónde se rompía en realidad

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

Se veía bien. Corría bien con el diccionario pequeño. valgrind (que CS50 te obliga a usar de verdad, no solo a mencionar en una clase) me dijo exactamente qué estaba mal en cuanto lo ejecuté contra el grande.

==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

No estaba comprobando el valor de retorno de malloc, y en el diccionario grande, bastante avanzada una ejecución, una asignación de memoria falló de verdad. Con la función hash mala esto nunca había salido a la superficie, porque todo era tan lento que la presión de memoria nunca se acumulaba de la misma manera antes de que el sistema de pruebas se rindiera esperando. La función hash más rápida significaba que ocurrían más asignaciones en menos tiempo, lo cual significaba que de verdad llegué al caso de fallo que mi código viejo, más lento y peor había estado escondiéndome por accidente todo el tiempo.

Un if (n == NULL) return false; lo arregló. El bug en realidad no tenía nada que ver con punteros. Tenía que ver con asumir que una función que puede fallar siempre va a tener éxito, porque lo tuvo las primeras cincuenta veces que la ejecuté, y hacer que el resto del programa vaya más rápido es exactamente el tipo de cambio que puede sacar a la luz un bug que siempre estuvo ahí.

el segundo bug, en una función completamente distinta

unload() se supone que debe recorrer cada cubo y liberar cada nodo. El mío me parecía, a mí, completamente correcto:

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 otra vez, paciente como siempre:

==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

Lectura después de liberar. Estaba liberando cursor, y luego leyendo inmediatamente cursor->next de memoria a la que le acababa de decir al asignador que podía reutilizar. En esta ejecución en concreto resultó que seguía teniendo el valor correcto, hasta que a veces no lo tenía, que es exactamente el tipo de bug que pasa en local y falla en otro sitio sin ninguna razón que puedas ver. El arreglo fue guardar el puntero siguiente antes de liberar el nodo actual, no después.

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

Dos bugs, mismo pset, la misma causa raíz debajo de ambos: seguía usando el valor de un puntero después del momento en que dejó de ser seguro confiar en él, una vez porque una función que llamaba podía fallar en silencio, otra vez porque ya le había dicho al sistema que esa memoria estaba libre para reutilizarse. C no te impide hacer ninguna de las dos cosas. Simplemente, al final, te lo muestra, en un momento y lugar de su elección, normalmente no la línea donde se cometió el error real.

un pequeño inciso, porque quedarse despierto por este pset se merece una digresión honesta

En algún momento cerca de la una de la madrugada de la segunda noche me convencí de que el propio archivo del diccionario estaba corrupto, porque una ejecución en concreto se comportaba distinto de una ejecución anterior de apariencia idéntica. No era el archivo. Era que ese fallo de malloc era probabilístico bajo presión de memoria, no determinista, así que la misma entrada exacta no siempre lo disparaba, dependiendo de qué más estuviera haciendo la máquina en ese momento. Me pasé una cantidad genuinamente vergonzosa de tiempo comparando un archivo de diccionario contra sí mismo antes de aceptar que el bug estaba en mi código, no en los datos.

lo que en realidad se me quedó

No la sintaxis. La regla: cada puntero, o apunta a algo real, o es NULL, o es basura, y C nunca te va a decir cuál de las tres, así que tienes que hacerlo tú. Python te protege en silencio de tener que pensar nunca en eso. C te entrega toda la responsabilidad y en su mayor parte se aparta, incluida la responsabilidad de no leer memoria justo en el instante después de haberla liberado.

qué haría distinto en el próximo pset

Correr valgrind desde la primerísima versión que funcione, no solo cuando algo se rompe. Los dos bugs de aquí estaban sentados en código que se veía bien y pasaba pruebas informales durante un rato antes de salir a la superficie de verdad. Esperar a que algo se rompa para ir a buscar la herramienta que lo habría detectado antes es un hábito que me gustaría desaprender antes de que me cueste más de una noche tarde.

Todavía no confío del todo en mi propia aritmética de punteros con arrays. Eso es un problema para un pset posterior.