Sesion 13: 1BRC

El reto de “mil millones de filas” (1BRC: one billion rows challenge) es un reto de programación ideado para comprobar la velocidad de Java.

Mi idea es que lo abordemos en esta asignatura para ver lo rápido que pude ser un programa C que hagamos nosotros.

1BRC

La descripción concreta del reto la puedes encontrar en https://www.morling.dev/blog/one-billion-row-challenge/.

El objetivo es simple: escribir un programa en C que lea valores de medidas de temperaturas de un fichero de texto y calcule temperatura mínima, media y máxima de cada estación meteorológica. El “único” problema al que quizás te enfrentas es que el fichero tiene mil millones de filas.

La estructura de la entrada es sencilla, una medida por de una estación por cada fila:

1
2
3
4
5
6

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
...

La salida del programa tiene que imprimir como acumulados el mínimo, la media y el máximo valor de cada estación, con las estaciones alfabéticamente ordenadas y siguiendo este formato:

1

 {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, Abéché=12.1/29.4/35.6, Accra=14.7/26.4/33.1, Addis Ababa=2.1/16.0/24.3, Adelaide=4.1/17.3/29.7, ...}

Para poder probar tu programa tienes dos ficheros (comprimidos!) con medidas:

• Mil medidas: para probar que la funcionalidad es correcta.
• Un millón de medidas: para empezar a ver la velocidad.
• Un “billion” de medidas: como este fichero ocuparía casi 5G (15G sin comprimir), puedes generarlo tú misma usando las instrucciones en https://github.com/gunnarmorling/1brc (tienes que compilar los generadores y luego ejecutar, probablemente, create_measurements_fast.sh).

Ideas

• Necesitarás declarar structs para representar medidas por estación (station and temp) y para representar el acumulado de cada estación (station, min, max, sum y n). Asumamos que estos serán los tipos:
  • measure_t
  • accum_t
• Define una función para leer cada medida:

1
2
3
4
5

/*
 * Lee una medida de stream y la deja en la variable measure.
 * Devuelve 0 para indicar que la lectura ha falla.
 */
int read_temp(FILE *stream, measure_t *measure);

• Necesitarás tener una tabla en la que ir apuntado los acumulados de cada estación. No puedes asumir nada sobre el número de estaciones (aunque en el reto original se asumen algunas limitaciones). Esto significa que deberás realizar una gestión eficiente de la memoria.
• Piensa en lo que tienes que hacer con cada medida e implementa funciones para trabajar con la tabla de acumulados.

Más ideas

Te ofrezco alguna idea extra si ves que andas atascada:

• Probablemente merezca la pena que crees un tipo para representar la tabla de datos acumulados: map_accum_t.
• La función principal sobre dicha tabla podría ser la siguiente:

1
2
3
4
5

/*
 * Busca la estación station, la añade a la tabla si no está.
 * Devuelve un puntero a los datos acumulados de dicha estación.
 */
accum_t *get_or_add_station(map_accum_t *map, char *station);

• Quizás estas otra funciones que te propongo puedan esclarecer aún más tu visión del algoritmo que podrías implementar:

1
2
3
4
5
6
7
8

/* Actualiza los datos de la estación. */
void update_accum(accum_t *accum, double temp)

/* Ordena la tabla alfabéticamente por estación. */
void sort_by_station(map_accum_t *map);

/* Imprime los acumulados de acuerdo a la salida esperada. */
void print_accums(map_accum_t *map);

Need for speed?

• A ver qué tal te va, pero probablemente tu primera implementación sea un poco lenta (especialmente para ser C).
• ¿Dónde pueden estar los cuellos de botella?
• Sería estupendo que pensaras tú misma en ello antes de pasar a leer las pistas que te ofrezco:
• La lectura de datos es lenta, pero si lees los datos línea a línea entonces es mucho más lenta. Una propuesta es leer muchas medidas de un solo golpe, pero ¿cómo?
• No hay ninguna función que pueda leer de golpe n líneas, sólo tienes funciones que pueden leer un bloque de m caracteres. Pero si por ejemplo haces m = 65536 (64Kb), entonces la última línea quizás esté partida y tendrás que pensar en resolver ese problema.
• Otro cuello de botella puede ser la función get_or_add_station. ¿Por qué?
• Bien, esa es una función que vas a tener que ejecutar mil millones de veces. Si no haces nada elaborado, cada llamada a esa función tendrá que recorrer la tabla de acumulados buscando la estación. Imagina que eso tarde en ejecutarse 0.1 milisegundo… mil millones por 0.11 milisegundo son caso ¡2 minutos!.
• Una primera idea puede ser mantener la tabla ordenada y que la función get_and_add_station haga la busqueda y la inserción conociendo que está ordenada.
• Otra idea para acelerar esa busqueda/inserción necesitas implementar algún tipo de mecanismo de Hashing para que dada una estación la velocidad a la que se localiza sea lo más cercano a O(1).
• Una idea muy sencilla sería usar como hash algunos códigos ASCII del nombre de la estación meteorológica. Por ejemplo:
  • “Madrid”: el código ascii de los dos primeros caracteres son 77 y 97, por lo tanto podriás asignarle el hash *256 * 77 + 97: 19809.
  • “Barcelona”: el código ascii de los dos primeros caracteres son 66 y 97, por lo tanto podriás asignarle el hash *256 * 6 + 97: 16993.
  • Quizás la tabla de acumulados podría ser un array de 65536 entradas (hash) y cada elemento es una lista de los acumulados de las estaciones con ese mismo hash.
  • Lamentablemente esto puede complicar la ordenación aunque si piensas en una función de hashing más apropiada quizás puedes tener la tabla prácticamente ordenada sin hacer nada.
• Otra cosa interesante al respecto de la velocidad para leer datos es que la lectura de disco es increíblemente lenta. De hecho, para valorar el reto, se usa una trampa: en vez de usar un disco de verdad se crea un disco virtual en memoria. Podrías hacerlo así desde tu terminal Bash (necesitarás 15G de memoria libre!):

1
2
3

mkdir /tmp/ramdisk
sudo mount -t tmpfs -o size=15G tmpfs /tmp/ramdisk
cp measurements_1b.txt /tmp/ramdisk

• Y ahora podrías ejecutar tu programa haciendo que leyera el fichero /tmp/ramdisk/measurements_1b.txt (Importante: recuerda desmontar el disco RAM con sudo umount /tmp/ramdisk)
• ¡Cuéntame a qué velocidad corre tu código!