- En réduisant la structure d’enregistrement des ICMP Echo Request d’un système de surveillance de connectivité, l’usage mémoire du ring buffer est passé de 12 KiB à 4 KiB
- En ne stockant pas à la fois
sent_ns et received_ns, mais seulement la latence après réception via une union, la taille du tableau a été réduite à 8 KiB
- Le passage d’une précision en nanosecondes à des unités de 100 microsecondes et la conversion de
received en champ de bits n’ont apporté aucune réduction supplémentaire à cause du padding de structure
- En remplaçant l’adresse source par une partie de la sémantique de l’
identifier ICMP sous la forme d’un compteur sur 4 bits, la structure est passée à 8 octets et un tableau de 512 éléments à 4 KiB
- L’application n’était pas contrainte en mémoire, donc il n’y avait pas de besoin pratique, mais cela a servi d’expérience d’optimisation sur la disposition des champs et jusqu’au coût d’accès aux bits
Mise en situation : comment stocker l’historique des ping
- Le système de surveillance de connectivité envoie des ICMP Echo Request à plusieurs serveurs et observe les moyennes de latence et de perte de paquets sur des fenêtres de 1, 5 et 15 minutes
- La première approche imaginée était un ring buffer de 512 entrées, chaque entrée contenant l’instant d’envoi, l’instant de réception, l’adresse source, le numéro de séquence et l’état de réception
- La taille initiale du tableau de structures
pings_rb[512] a été mesurée à 12 KiB
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Première réduction : fusionner l’instant d’envoi et le temps écoulé dans une union
- La valeur réellement utile après réception est la latence
received - sent, il n’est donc pas nécessaire de conserver simultanément l’instant d’envoi et le temps écoulé
- La structure qui regroupe
sent_ts et elapsed_ts dans une union utilise le même emplacement comme instant d’envoi avant réception, puis comme temps écoulé après réception
- Après ce changement, la taille du tableau de 512 éléments est passée de 12 KiB à 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;
};
Deuxième tentative : réduire la précision et utiliser des champs de bits
- Les temps de ping se mesurent en dizaines, centaines ou milliers de millisecondes, il n’est donc pas nécessaire de stocker toute la précision à la nanoseconde
- En passant à une unité de temps de 100 microsecondes, soit 0,1 ms, 43 bits suffisent pour suivre des ping sur une durée maximale de 20 ans
- Utiliser 8 bits pour la valeur booléenne
received est excessif, donc un champ de bits a été appliqué
- Mais la taille du tableau de
ping_timestamp_3 est restée de 8 KiB, sans réduction supplémentaire
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;
};
Une taille qui ne baisse pas à cause du padding de structure
ping_timestamp_2 reçoit à la fin des octets de padding pour satisfaire les contraintes d’alignementping_timestamp_3 place dans les 8 premiers octets le temps, l’état de réception et le numéro de séquence, mais il reste ensuite l’adresse source et du padding- Malgré l’usage de champs de bits, 36 bits de padding subsistent, ce qui empêche de réduire la taille totale de la structure
- Réduire simplement un booléen à un bit ne suffit pas à résoudre les problèmes de disposition mémoire et d’alignement
Suppression de l’adresse source et compteur sur 4 bits
- Comme le produit fonctionne sur des réseaux de données mobiles, l’adresse source change souvent ; la structure initiale stockait donc cette adresse
- Quand l’adresse change, le numéro de séquence est aussi réinitialisé, et il est déjà arrivé que des paquets avec des adresses sources différentes mais le même numéro de séquence soient traités en même temps
- Les ICMP Echo Request disposent d’un champ
identifier sur 16 bits permettant à l’application d’identifier les paquets qu’elle a envoyés
- Il n’est pas nécessaire d’utiliser les 16 bits entiers ; les 4 bits restants sont donc réutilisés comme compteur tournant, incrémenté quand l’adresse source change
- Ce compteur est incrémenté en fonction des changements d’adresse source surveillés ailleurs dans l’application
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
Résultat final et disposition des champs
- La structure finale supprime le champ d’adresse source et place le temps, l’état de réception, le compteur et le numéro de séquence dans 64 bits
- Le tableau du ring buffer de 512 éléments tombe à 4 KiB, soit une seule page de données
- Cela représente un gain total de 8 KiB par rapport aux 12 KiB initiaux
- L’ordre des champs est ajusté pour que
seq_no soit aligné sur une frontière de 16 bits, ce qui permet une lecture via une seule instruction ldrh sans décalage
- La lecture de
elapsed_or_sent_ts ne nécessite qu’un masque
Optimisation supplémentaire : réduire le coût d’accès au bit de réception
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
Conclusion
- Le résultat de l’optimisation a réduit l’usage mémoire de 12 KiB à 4 KiB, mais l’application elle-même n’était pas limitée par la mémoire
- Au-delà du besoin réel, cela a servi d’expérience sur la disposition des structures, le padding, les champs de bits et le coût d’accès au niveau des instructions
- Dans le dernier commentaire, l’auteur précise aussi que le terme de « problème » est employé assez librement et qu’aucun benchmark n’a même été réalisé
1 commentaires
Avis sur Lobste.rs
Le jour où réfléchir à ce genre de problèmes ne m’amusera plus, je considérerai que ce sera le jour d’arrêter la programmation
L’optimisation prématurée est toujours amusante
Gérer les conséquences une fois qu’on a compris pourquoi elle était prématurée, en revanche, n’est généralement pas amusant
Le passage sur l’utilisation de 43 bits pour le timestamp me semble un peu confus. 24 bits paraissent suffisants
Vu qu’on parle d’un ring buffer de 512 éléments, on dirait qu’un nouveau ping est envoyé toutes les 2 secondes et qu’on suit les pings des 17 minutes et 4 secondes les plus récentes
Comme première étape, il suffirait d’utiliser un encodage delta par rapport au timer/numéro de séquence idéal. Si on incrémente l’heure du dernier envoi de 2 secondes et qu’on regarde l’index du ring buffer, on peut facilement savoir quand le paquet aurait dû être envoyé ; il suffit alors d’enregistrer s’il a été envoyé exactement à l’heure, avec 0,1 ms de retard, avec 2,3 ms de retard, etc.
Le temps écoulé n’a pas non plus besoin de dépasser 17 minutes et 4 secondes, puisque le ping expirera au-delà. 512 × 2s = 10,240,000 × 100μs, donc à cette précision environ 23,3 bits suffisent, et on peut monter à 24 bits si on veut. Les quelque 6 536 216 motifs de bits invalides restants pourraient peut-être servir à autre chose
En bonus, avec 24 bits on peut augmenter nettement la précision de « envoyé » et réduire l’erreur de quantification. Même avec une précision à la microseconde, un ping pourrait encore être envoyé avec jusqu’à 16 secondes de retard, ce qui semble largement suffisant
Je ne sais pas si réduire les échantillons de 64 bits à 48 bits aiderait ou nuirait aux performances. Je ne serais pas surpris que le résultat diffère selon les environnements 32 bits/64 bits sur x86 et ARM
Cela dit, la taille d’origine tient déjà très facilement dans le cache de données de processeurs assez anciens, donc il est peu probable que l’économie mémoire change grand-chose
Je suis convaincu que c’est précisément pour ça qu’on fait de l’optimisation prématurée. C’est un sport pratiqué pour le plaisir
Quand on conçoit des systèmes ou qu’on travaille dans des langages système bas niveau, l’optimisation prématurée est honnêtement l’une de mes activités préférées
Au minimum, il y a l’espoir qu’elle fasse gagner du temps et de la mémoire plus tard. Dans un cas intermédiaire, le résultat, c’est juste un peu plus de mal de tête à essayer de comprendre « pourquoi j’ai construit ça comme ça ? ». Dans le pire cas — et parfois c’est même préférable —, l’optimisation pendant la conception prend une telle ampleur qu’on finit par ne pas faire le projet du tout. On ferme le programme en se disant : « ah, c’est devenu trop tordu, pourquoi je fais ça ? »