- En el proceso de reducir la estructura que registra ICMP Echo Request en un sistema de monitoreo de conectividad, el uso de memoria del ring buffer bajó de 12 KiB a 4 KiB
- Al no guardar a la vez
sent_ns y received_ns y dejar solo la latencia después de recibir usando una unión, el tamaño del arreglo se redujo a 8 KiB
- Se cambió la precisión de nanosegundos a unidades de 100 microsegundos y
received se convirtió en bitfield, pero por el padding de la estructura no hubo ahorro adicional
- Al reemplazar parte del significado de la dirección de origen con un contador de 4 bits dentro del
identifier de ICMP, la estructura se redujo a 8 bytes y un arreglo de 512 elementos pasó a ocupar 4 KiB
- La aplicación no tenía restricciones de memoria, así que no era una necesidad práctica, pero sí terminó siendo un experimento de optimización considerando incluso la disposición de campos y el costo de acceso a bits
Planteamiento del problema: cómo guardar registros de ping
- El sistema de monitoreo de conectividad envía ICMP Echo Request a varios servidores y observa los promedios de latencia y pérdida de paquetes en intervalos de 1, 5 y 15 minutos
- La primera idea para almacenarlos fue un ring buffer de 512 entradas, donde cada entrada contiene la hora de envío, la hora de recepción, la dirección de origen, el número de secuencia y si fue recibido
- El tamaño del arreglo inicial
pings_rb[512] se midió en 12 KiB
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Primer ahorro: unir la hora de envío y el tiempo transcurrido en una unión
- El valor que realmente se quiere conservar después de recibir es la latencia
received - sent, así que no hace falta guardar simultáneamente la hora de envío y el tiempo transcurrido
- La estructura que agrupa
sent_ts y elapsed_ts en una unión usa el mismo slot como hora de envío antes de recibir y como tiempo transcurrido después
- Tras este cambio, el tamaño del arreglo de 512 elementos bajó de 12 KiB a 8 KiB
struct ping_timestamp_2 {
union {
uint64_t sent_ts;
uint64_t elapsed_ts;
};
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Segundo intento: reducir precisión y usar bitfields
- Los tiempos de ping se miden en decenas, centenas o miles de milisegundos, así que no hace falta guardar toda la precisión en nanosegundos
- Si la unidad de tiempo se cambia a 100 microsegundos, es decir, 0.1 ms, se puede rastrear ping por hasta 20 años con 43 bits
- Usar 8 bits para el valor verdadero/falso de
received es excesivo, así que se aplicó un bitfield
- Sin embargo, el tamaño del arreglo de
ping_timestamp_3 también se mantuvo en 8 KiB, así que no hubo ahorro adicional
struct ping_timestamp_3 {
uint64_t sent_or_elapsed_ts: 43;
uint64_t received: 1;
uint64_t seq_no: 16;
in_addr_t source_addr;
};
El tamaño no se redujo por el padding de la estructura
ping_timestamp_2 termina con bytes de padding para cumplir los requisitos de alineaciónping_timestamp_3 coloca tiempo, estado de recepción y número de secuencia en los primeros 8 bytes, pero detrás siguen quedando la dirección de origen y padding- Aunque se aplicaron bitfields, seguían quedando 36 bits de padding, así que el tamaño total de la estructura no se redujo
- Reducir un
bool a un bit por sí solo no resuelve los problemas de disposición de memoria y alineación
Eliminar la dirección de origen y usar un contador de 4 bits
- Como el producto funciona sobre redes de datos móviles y la dirección de origen cambia con frecuencia, la estructura original guardaba esa dirección
- Cuando cambia la dirección, el número de secuencia también se reinicia, y en el pasado se llegaron a procesar al mismo tiempo paquetes con distintas direcciones de origen pero el mismo número de secuencia
- ICMP Echo Request tiene un campo
identifier de 16 bits que permite a la aplicación identificar los paquetes que envió
- Como no hace falta usar los 16 bits completos, se usan 4 bits libres como contador rotativo que se incrementa cuando cambia la dirección de origen
- Ese contador se incrementa en otro punto de la aplicación, en sincronía con los cambios de dirección de origen que ahí se monitorean
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
Resultado final y disposición de campos
- La estructura final elimina el campo de dirección de origen y guarda tiempo, estado de recepción, contador y número de secuencia dentro de 64 bits
- El arreglo ring buffer de 512 elementos queda en 4 KiB, reduciéndose a una sola página de datos
- En total se ahorran 8 KiB frente a los 12 KiB iniciales
- El orden de los campos se ajustó para que
seq_no quedara alineado a un límite de 16 bits, permitiendo leerlo con una sola instrucción ldrh sin desplazamientos al cargarlo
- Para leer
elapsed_or_sent_ts solo hace falta una máscara
Optimización adicional: reducir el costo de acceso al bit de recepción
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
Conclusión
- El resultado de la optimización redujo el uso de memoria de 12 KiB a 4 KiB, pero la aplicación en sí no tenía restricciones de memoria
- Más allá de la necesidad real, terminó siendo un experimento para analizar layout de estructuras, padding, bitfields y el costo de acceso a nivel de instrucción
- En el comentario final también se aclara que incluso la palabra “problema” se usa de forma laxa, y que ni siquiera se hizo un benchmark
1 comentarios
Opiniones en Lobste.rs
Creo que el día en que deje de ser divertido pensar en este tipo de problemas será el día en que deje la programación
La optimización prematura siempre es divertida
Lo que normalmente deja de ser divertido es lidiar con las consecuencias después de darte cuenta de por qué esa optimización fue prematura
La parte de usar 43 bits para el timestamp me resulta un poco confusa. Parecería que 24 bits bastan
Por lo de un ring buffer de 512 elementos, parecería que envía un ping nuevo cada 2 segundos y rastrea los pings de los últimos 17 minutos y 4 segundos
Como primer paso, se podría usar delta encoding respecto de un temporizador/secuencia ideal. Si aumentas el último tiempo de envío de 2 en 2 segundos y miras el índice del ring buffer, es fácil saber cuándo debía enviarse el paquete, así que bastaría con registrar si se envió exactamente a tiempo, con 0.1 ms de retraso, con 2.3 ms de retraso, etc.
Tampoco parece necesario que el tiempo transcurrido pase de 17 minutos y 4 segundos, porque después de eso el ping expiraría. 512 × 2s = 10,240,000 × 100μs, así que con esa precisión bastan unas 23.3 bits, y si quieres puedes subirlo a 24 bits. Quizá los aproximadamente 6,536,216 patrones de bits inválidos que sobran podrían usarse para otra cosa
Además, con 24 bits se puede subir bastante la precisión de “enviado” y reducir el error de cuantización. Incluso con precisión de microsegundos, un ping podría enviarse con hasta 16 segundos de retraso, así que parece haber margen de sobra
No sé si reducir la muestra de 64 bits a 48 bits ayudaría o perjudicaría el rendimiento. No me sorprendería que el resultado cambiara entre entornos de 32 bits y 64 bits en x86 y ARM
Aun así, el tamaño original ya cabe muy fácilmente en la caché de datos de procesadores bastante viejos, así que no parece que ahorrar memoria vaya a marcar diferencia
Estoy seguro de que esa es precisamente la razón por la que optimizamos prematuramente. Es un deporte recreativo
Cuando diseñas sistemas o trabajas con lenguajes de sistemas de bajo nivel, la optimización prematura es, sinceramente, una de mis cosas favoritas
Al menos existe la esperanza de que después te ahorre tiempo y memoria. Un resultado intermedio solo significa un poco más de dolor de cabeza al tratar de entender “¿por qué hice esto así?”, y el peor caso, que a veces incluso resulta mejor, es que el trabajo de optimización durante el diseño se vuelva tan grande que termines sin poder hacer el proyecto en sí. Cierras el programa pensando: “Ah, esto ya se enredó demasiado, ¿para qué estoy haciendo esto?”