Accueil

Préambule

Oui ce site est moche malgré tous mes efforts. Cela tombe bien, je ne suis pas web designer mais développeur C. Cette page est ici pour présenter quelques projets personnels et deviendra peut-être un vrai blog (j'ai tout un tas de développements à présenter). Et donc retravailler un peu la forme.

Il s'agit pour le moment davantage d'une carte de visite pour présenter mes compétences.

A propos de cette page, je voulais juste préciser qu'elle est entièrement codée à la main, avec juste du bootstrap dedans pour être responsive. Et que vous pouvez la sauvegarder en tant que simple (et petit) fichier html sans altérer son fonctionnement, parce que ça ne sert à rien mais j'ai trouvé ça cool.

À qui / de quoi parle-t-on?

Je ne vous cache pas que pour comprendre ce qu'il se raconte dans ces pages, il va falloir être à l'aise en C et avoir un minimum de la culture qui va avec.

La page FCGI on steroids présente un projet de remplacement de PHP axé sur les performances. Celle concernant les hashtables présente de manière détaillée la conception d'une petite librairie de table de hash avec les performances en tête.

On finira par une petite digression sur la réelle utilité de test de la valeur de retour de malloc, je l'étendrai sûrement pour parler d'autres choses sensibles (qui a dit goto?).

D'autres choses devraient suivre.

fgci on steroids

Description

Comment ce site ( <= ceci est un lien ) arrive-t-il à tourner aussi vite sur un hardware médiocre.

Sur la même machine, le meilleur temps de réponse minimum que j'obtenais en PHP était de 65ms.

Il s'agit de l'évolution des prix des royaumes européens sur les enchères dans le jeu World of Warcraft (oui, j'aime jouer tant que je peux faire participer excel ou du dev, en passant je salue le jeu space engineers qui a réussi à me faire toucher à C# alors que je m'étais juré que non). En sélectionnant une catégorie, puis un objet, vous verrez la courbe d'évolution de son prix. Une requête est effectuée à chaque clic. Le temps de traitement et le nombre de données en base est affiché en bas.

Genèse

Au cours de mes aventures, une de mes connaissances a hérité d'un projet réalisé par ce que j'appellerais avec retenue une "honte du métier". Cette application était en l'occurrence un logiciel de gestion de centre d'appels réalisé sous forme de plateforme web.

Les temps de réponse étaient de l'ordre de 20 secondes pour certaines pages, le système devenait inutilisable à certaines périodes... Et la base de données devait bien contenir 200 000 enregistrements, hébergée sur Xeon SAS etc...

Cette connaissance, dont je salue le courage et l'abnégation remarquables, je lui dois de m'avoir fait découvrir le fonctionnement RESTful (les échanges entre le navigateur et le serveur ne consistent qu'en des requêtes http et des réponses json). Étant alors en plein excursion dans le domaine du développement web, j'avais trouvé mon marteau, et tous les problèmes commençaient à ressembler à des clous à mon regard.

Pour en revenir à son problème, et ayant déjà participé à des projets qui brassaient plusieurs milliards d'enregistrements par jour, j'ai fait tout ce que toute personne sensée aurait fait à ma place: j'ai pouffé intérieurement, envisagé à la fois de porter assistance et d'inventer la potion d'invisibilité. Au final mon agenda ne collait de toutes façons pas à l'ampleur de la tâche (facilement divisible par deux en se contentant de refaire le projet de zéro). Mais j'étais intimement persuadé que la même application pas trop mal écrite aurait pu fonctionner sans problème sur un raspberry pi.

N'empêche que.. Ayant toujours été intéressé par les performances, ayant un certain sens du datamodelling et des performances SQL, je me posais désormais la question: jusqu'où pouvais-je aller dans les performances sur la partie "serveur web"?

Je tue le suspense tout de suite: moins de 15 millisecondes en traitement de réponse http sur une base MySQL de quelques dizaines de millions d'enregistrements, avec un celeron quand core de 2017 et un MySQL non tuné (Mais avec un SSD SATA tout de même!)

Ce voyage m'a emmené très loin. J'ai tout d'abord conçu ma base façon "Merise", des index au poil, et j'étais alors à 45ms. Cela ne me suffisait pas. Je regardais alors le coupable: PHP (pourtant lancé en fcgi via php-fpm). J'ai donc voulu recréer mon code PHP en un module fcgi directement écrit en C. Un module qui maintiendrait la connexion MySQL ouverte entre les requêtes http, qui mettrait en cache les requêtes préparées (pour les données c'est à la base de le faire)... Effectivement les performances étaient foudroyantes. Mais devant la lourdeur de développement de chaque requête en C, je me suis dit "pourquoi ne pas faire exécuter un script à mon module plutôt que de coder en dur les requêtes?". Cela ressemblait à un pas en arrière, mais j'avais trois cartes en mains: le maintien de la connexion à la base, le cache des requêtes préparées, et... j'allais créer mon microlangage, ainsi qu'un compilateur bytecode pour mon script qui sera exécuté au lancement pour m'affranchir du parsing pendant l'exécution des requêtes http. Et le tout allait donc tourner sur une VM maison.

Je me suis donc lancé, avec le même ressenti qu'un homme sur le bord d'un pont avec un élastique aux pieds... Et je m'en suis sorti. De plus j'ai conçu mon bytecode pour qu'il ressemble fortement à de l'assembleur, des fois que dans une nouvelle crise de folie je me trouve l'envie de générer du code natif (spoil: c'est déjà dans les tuyaux, et avec llvm).

Je l'ai appelé le Machin.

La base de données

Considérations

Machin est installé sous forme de service systemd. Les connexions avec apache et mySQL sont configurées via des sockets UNIX afin de maximiser les performances. Tous les urls pointant vers getdata seront redirigés vers lui via le module proxy.

Les données sont importées toutes les heures via l'API blizzard et un crontab.

La base de données présentant le goulot d'étranglement des performances, son optimisation se doit d'être irréprochable. Ici, nous ne sommes pas dans un système transactionnel, par conséquent je n'ai touché à rien d'autre que la mémoire allouée au moteur.

Par contre au niveau des tables et des index, le travail a été soigné

La grande tricherie

Par souci d'honnêteté, je dois vous prévenir d'une triche: en effet le script ne va pas piocher dans la monstrueuse table de données. Durant l'importation, une table annexe ne stockant que les prix minimum (c'est-à-dire ceux que l'on veut afficher) est également alimentée. Par souci de performances, plutôt que d'y placer les données après l'import via une requête (ce qui implique une relecture des données), elles sont calculées au fil de l'import et insérées tout à la fin. Bien sûr, cela ne met pas en cause le Machin, qui reste quasiment 10 fois plus rapide que PHP (le temps de traitement d'une requête http via PHP via cette "triche" supérieur à celui du SQL, celui de Machin est quasi nul (<1ms)).

Évidemment, il s'agit davantage d'une optimisation que d'une triche, mais ma façon de vendre la chose fait tout de même pencher la balance du côté de la triche. Rassurez-vous, la table réellement interrogée fait tout de même 8 millions de lignes!

Un dernier mot sur l'importation des données: elle est réalisée (en PHP) en récupérant la réponse json des serveurs, convertie en csv puis envoyée au SGBD via la commande "LOAD DATA FROM FILE", 20x plus rapide que des insertions.

Les index

Un mot sur les index, parce qu'en dehors du C mon autre point fort est le requêtage et le datamodeling.

Lors de l'analyse d'une requête, un explain plan ne doit contenir que des ref ou des eq_ref. L'ordre des colonnes dans la création des inde est importante. Une bonne recette est de commencer par celles du where, ensuite celles du order by de la table principale pour finir par celles de la jointure. A partir de ce point de départ il faudra malheureusement procéder à des essais, en effet le moteur dela base de données est le seul juge. Et parfois la montée en volumétrie va faire changer son plan d'exécution, pensez donc à les surveiller régulièrement. Parfois un STRAIGHT JOIN permet de fixer un plan d'exécution récalcitrant.

La performance de votre base est cruciale pour les performances. N'hésitez pas à créer des tables utilisées uniquement pour la récupération de données en plus des tables "Merise", plutôt qu'à avoir une modélisation optimisée mais complètement "tordue" fonctionnellement.

Aperçu du Machin

Principe

Le programme est un module fastcgi, c'est à dire que le serveur web (apache, nginx) redirige certaines requêtes http (celles qui doivent renvoyer un objet json) vers lui. Il tourne donc en permanence et est à l'écoute d'un socket (UNIX ou réseau). Rien ne l'oblige à fonctionner sur la même machine mais pour des performances optimales il est préférable de le configurer pour un socket UNIX. En fait extérieurement il fonctionne de la même manière que php-fpm.

A son lancement, il lit son fichier de configuration, puis compile le script fourni (l'équivalent d'un code PHP) en bytecode. Pour finir il se connecte à la base MySQL (socket réseau ou UNIX au choix).

Une fois prêt, il attend de recevoir une requête et exécute le bytecode à chacune d'elle.

Outils utilisés

Bien sûr, je me suis appuyé sur quelques utilitaires et librairies. Pour commencer, j'ai ENFIN réussi à me servir de bison et flex (et en fait ce n'est pas si compliqué) pour le parsing du langage. Et j'ai utilisé les librairies libfcgi (pour la redirection des entrées/sorties sur socket) et libcjson (pour la génération du json). Et ce cher valgrind, car il est très difficile de ne pas être pris en défaut de fuite mémoire en écrivant un compilateur. Au vu de la nature du programme elles sont à exclure.

Le langage Machin

Le langage est assez simpliste et limité, je l'étendrai sûrement a mes heures perdues. Il s'avère toutefois robuste. Ainsi on peut y écrire:

// ce code ne fait rien de logique ni d'intelligent, c'est un exemple
i = 4
j[i + 1] = i - 2
// label = "mylabel22"
label = "mylabel" + 2 + "2"
if i + 2 = 6
	select("SELECT colonne FROM table WHERE id=? AND label = ?", i - j[5], mylabel + "fr")
	return "data": i - 5
fi

Bref, il gère correctement les expressions et leur enchaînement, les bases sont saines et il n'y a aucun "bricolage" dans sa conception (vous pouvez le vérifier dans les sources (lien en bas de page)).

Pour le moment, les fonctionnalités suivantes sont supportées:

En ce qui concerne les types:

C'est à la fois peu, turing-complet et bien trop pour faire fonctionner le site présenté au chapitre 1 (c'est d'ailleurs pour cela que j'ai fait une pause dans le développement). Voyons le bout de script qui va récupérer les éléments du menu de gauche:

if $todo == "getConfig"
	classes = sql("SELECT id,nom FROM classe_item ORDER BY nom")
	sousclasses = sql("SELECT id,id_classe,IFNULL(nom_long,nom)AS nom FROM sous_classe_item ORDER BY nom")
	invtypes = sql("SELECT id, nom,type FROM item_inventory_type ORDER BY nom")

	return "erreur": false, "time": millis(), "data": {"classes": classes["id": "id", "nom": "nom"],
		"sousclasses": sousclasses["id": "id", "id_classe": "id_classe", "nom": "nom"],
		"inv_types": invtypes["id": "id", "nom": "nom", "type": "type"]}
fi

Le bloc n'est exécuté que si la variable post "todo" vaut "getConfig". Ensuite on effectue trois requêtes en base. L'instruction return, qui renvoie un objet json, a une syntaxe un peu particulière. Elle fonctionne sous la forme paire clé/valeur, mais pour une valeur on peut spécifier "<variable type tableau>[<clé1>:<colonne1>, <clé2>:<colonne2>...]". Elle génèrera alors un tableau json comprenant toutes les lignes du résultat de requête incriminé. Et bien sûr on peut aussi spécifier un objet en tant que valeur au moyen des "{}", tout imbriquer à sa guise...

Encore une fois, le but n'est pas de réécrire PHP mais bien de faire un moteur ultrarapide faisant le pont entre mySQL et la partie front. Et donc de faire transiter un minimum de données, reléguant les traitements complexes à la partie SQL ou au javascript (ou au script d'importation dans mon cas).

Le bytecode

Ce code:

if $query == "test"
	i = 8
	j = i + 2
	field = "j"
	return "i": i, field: j
fi

sera compilé vers le bytecode suivant (les noms d'instructions sont en clair, en interne ce sont des entiers):

eq   0x7fffec42c6f0, 0x7fffec435b00 // test si POST['query'] == "test"
jz   ax,             0x7fffec434ce0 // saut si false
mov  0x7fffec435e50, 0x7fffec435cd0 // copie de 8 dans i
add  0x7fffec435e50, 0x7fffec436000 // addition de i et de 2
mov  0x7fffec42c960, ax             // copie du résultat dans j
mov  0x7fffec4366d0, 0x7fffec4368a0 // copie de "j" dans field
push 0x7fffec42c960                 // empilement de j
push 0x7fffec4366d0                 // empilement de field
push 0x7fffec435e50                 // empilement de i
push 0x7fffec434880                 // empilement de "i"
ret  2                              // exécution de "return" avec 2 paires de paramètres (et dépilage de ceux-ci)

Cela vous est-il familier? J'ai voulu rester relativement proche de l'assembleur dans le cadre d'une future optimisation. Les adresses visibles sont celles de nos variables ou des valeurs en dur (je pourrais les gérer en direct en utilisant des instructions séparées exactement comme les processeurs x86, mais je préfère ne pas alourdir le code à ce stade). A noter l'appel de la fonction return avec un passage de paramètres par pile (par opposition à un AST), toujours dans l'esprit de "coller" à l'esprit asm (et même de respecter la procédure d'appel du C). Enfin on note que l'instruction ret (qui renvoie un objet json) ne "pop" que deux valeurs, mais comme il s'agit forcément de paires dans les faits elle "popera" le double (elle est codée pour).

Évidemment, avec une décomposition du script en opérandes aussi simples, l'écriture de la VM va s'avérer trivial. Celle du compilateur sera une autre paire de manches.

Les entrailles du machin

Le code

Ici on ne va pas faire une analyse du code section par section, ce serait trop fastidieux. Je me contenterai des parties intéressantes.

la compilation

Ici j'ai utilisé flex et bison, n'ayant aucune raison de ne pas le faire. Je ne me lancerai pas dans un tuto pour plusieurs raisons:

Cependant, si j'ai un conseil, c'est de vous lancer, d'essayer de faire un quelque chose sans essayer de tout comprendre au début (ce qui mène à l'intimidation et dans mon cas a causé quelques refus d'obstacle). Cela va alors très vite et on apprend au fur et à mesure. Par ailleurs je me permets un point: quel que soit le sujet privilégiez TOUJOURS la doc officielle une fois le pied à l'étrier. Je ne compte plus le nombre d'horreurs et d'approximations que l'on trouve dans les forums. De plus vous risquez de découvrir des fonctionnalités qui vont grandement vous faciliter l'existence.

Pour en revenir à nos moutons, on parse donc les parties du script par ordre de priorité et construit une liste chaînée d'instructions morceau par morceau. Cette partie n'est pas critique en terme de performances vu qu'elle n'est exécutée qu'une fois au lancement du programme.

Les variables sont des structures constituées d'un entier pour spécifier leur type et d'un union de leurs valeurs échéantes (long double, bool, pointeur vers une chaîne de caractères...) Elles sont allouées pendant la compilation, ce qui simplifie leur gestion, les constantes sont traitées de la même manière. Toutes les variables sont donc globales (n'oubliez pas qu'on est que (pour l'instant) sur un bricolage sur un coin de table).

On créée aussi deux "registres" ax et bx, ax stockant le résultat de chaque opération/fonction, et bx pour des cas comme "fonction() == fonction()". On intercalera alors une copie ax dans bx avant d'évaluer la seconde.

La VM

La VM se place dans une boucle qui, à chaque requête http, va récupérer les variables POST puis exécuter les instructions une par une dans la liste chaînée. Le gros de la complexité se situant dans la compilation, l'exécution à proprement parler n'a rien de remarquable, si ce n'est deux points.

La copie d'une variable à une autre (beaucoup employée dans les appels de fonction et les opérateurs mathématiques) est optimisée lorsque l'opérateur source est ax: comme il n'est jamais réutilisé par la suite on se contente de copier le contenu de la structure et pas les valeurs pointées (la chaine de caractères pour un string ou la table de hash pour un tableau). J'en profite au passage pour signaler que l'on peut copier une structure avec l'opérateur "=" en C, ce qui évite un appel système (ou pas, gcc inlinant très bien memcpy).

En ce qui concerne la génération JSON de la fonction return, j'ai commencé par utiliser la librairie cjson. Et sur de grosses sorties, les performances n'étaient pas au rendez-vous. J'ai ensuite essayé la librairie "la plus rapide du monde". Pas suffisant. J'ai réalisé qu'utiliser une telle librairie pour le travail demandé était complètement overkill, et mon code s'en est même retrouvé simplifié lorsque j'ai codé la sortie sans passer par une représentation intermédiaire des objets. Moralité: quand on a juste besoin d'aller de A à B et qu'un outil nécessite de passer par C, il n'est pas forcément judicieux.

Le cache de requêtes préparées et la connexion

Chaque requête qui transite dans la VM passe par les points suivants

En ce qui concerne le cache des requêtes préparées, il faut savoir que MySQL en maintient un également. Ici, il s'agit d'un cache additionnel évitant des appels supplémentaires entre le programme et le SGBD (préparation de la requête). Le binding des variables n'est également effectué qu'une seule fois.

La gestion des tableaux

Les tableaux sont en fait des tables de hash. J'ai en effet réutilisé ce code que j'ai un peu modifié en intégrant directement la structure des variables dans celle d'un élément de table de hash. Ceci pour une raison très simple: lorsqu'on utilise un élément de tableau flexible pour stocker une structure, une copie par l'opérateur "=" de structure à cet élément de tableau flexible provoque un segfault. C'est en effet interdit, le compilateur ne connaissant pas la taille de la structure à la compilation.

Cela m'a suffisamment chiffonné pour faire la modification, et a également permis de simplifier un peu le code.

A noter que la taille de la clé est limitée, c'est une limitation peu coûteuse à faire sauter mais qui se ferait au détriment des performances.

Le bêtisier

Durant le développement, j'ai rencontré deux écueils notables:

Dans ma gestion de tableaux, les index pouvaient prendre la forme de long double. Ce qui m'a amené à un problème qui peut être simplifié par le code suivant:

long double f1 = 0;
long double f2 = 0;
int i = memcmp(&f1, &f2, sizeof(long double));

Si vous pensez que i contiendra systématiquement zéro, je vous répondrais que cela va souvent fonctionner. Et aussi ne pas fonctionner. Je me suis arraché les cheveux pendant deux heures sur un code au comportement aléatoire à cause de ce coupable.

En effet, les long double ont leur valeur significative stockée sur 80 bits. Ils sont ensuite "allongés" à 128 bits pour des raisons d'alignement mémoire, et les bits additionnels ne sont pas garantis d'avoir une valeur à zéro. Le bon code est donc:

long double f1 = 0;
long double f2 = 0;
int i = memcmp(&f1, &f2, 10); // 80 bits = 10 octets

Dans un autre ordre d'idées, mon NUC étant une machine très peu performante (ne m'envoyez pas d'argent, j'ai aussi du vrai matos), je me suis mis en tête d'afficher sur le site lorsqu'un import de données était en cours (cela arrive une fois par heure) afin de prévenir que les performances étaient dégradées.

Tout allait bien, sauf que... Le site était encore plus rapide durant l'import (mais beaucoup).

Et là je remercie un neurone anonyme logé dans un coin de ma tête pour m'avoir donné rapidement une explication sans laquelle j'aurais pu chercher des jours.

Les processeurs modernes font varier leur fréquence en fonction de la charge de travail. Ainsi au repos ils ont une fréquence plus basse, et donc peuvent travailler à une tension plus basse, et donc dissiper moins de puissance, ce qui engendre une consommation d'énergie moindre et une chauffe moindre (et donc un ventilateur qui travaille moins). En cas de montée en charge ils remontent en fréquence.

Mon code s'exécutait tout simplement trop rapidement pour que le processeur ait le temps de monter suffisamment en fréquence. Pour vous dire la vérité, rien n'aurait pu me flatter davantage lorsque j'ai découvert cela.

J'aurais pu bloquer le processeur en mode "performances" (ce qui le laisse en permanence à cadence maximale), mais pour des raisons aussi bien sonores, qu'économiques (on parle d'un TDP de 10W tout de même :-D ) et écologiques je me devais de trouver une solution. Qui a consisté à faire basculer le processeur en mode "performances" durant deux minutes après chaque requête http. Ainsi même si la première requête est "lente" les suivantes fonctionnent à pleine vitesse et lorsque le site est inactif mon "serveur" repasse en mode basse consommation. Le tout est évidemment paramétrable.

Le manuel

On utilise un fichier de configuration

# BASE MYSQL
# ne pas remplir pour une connexion à la base par socket
db_host     = 192.168.0.4
# vide pour port par défaut
db_port     =
db_user     = wow
# vide si pas de mot de passe
db_password = motdepasse
db_name     = wow
# inutilisé si db_host est défini. socket alternatif pour connexion à mysql
db_socket   =


# CHEMIN DU SCRIPT À EXÉCUTER
program = /usr/local/etc/wow.machin

# CONNEXION APACHE
# à laisser vide pour un lancement CGI (utile pour le debug)
# sinon mettre un chemin pour un socket UNIX ou bien
# ":XXXX" (sans les guillemets) pour écouter le port XXXX 
fcgi_socket =  /run/machin/machin-fcgi.sock

# AUTRES OPTIONS

# nombre de requêtes préparées à garder en cache (algorithme LRU)
query_cache_size = 20

# si <= 1 le gouverneur CPU ne sera pas géré
# sinon le gouverneur CPU sera choisi à execution_governor après chaque requête durant
# execution_governor_duration secondes, avant de retourner au idle_governor
# regardez /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor pour votre liste
# de gouverneurs disponibles
execution_governor_duration = 0
execution_governor = performance
idle_governor = schedutil

On lance ensuite le programme avec le chemin du fichier de configuration en guise d'argument. Pour ma part j'ai créé une unité Systemd pour son lancement et ne pas avoir à le gérer à chaque reboot:

[Unit]
After=mysql.service
[Service]
Group=www-data
RuntimeDirectory=machin
RuntimeDirectoryMode=0775
PIDFile=/run/machin/machin.pid
ExecStart=/usr/local/bin/machin-fcgi /usr/local/etc/machin-fcgi.conf
[Install]
WantedBy=multi-user.target

Notez la directive RuntimeDirectory qui va créer automatiquement le répertoire sous /run avec le bon groupe afin qu'apache puisse converser avec le socket.

Pour apache il suffit d'ajouter, similairement avec ce que l'on fait pour un php-fpm:

<FilesMatch "^getdata">
	SetHandler "proxy:unix:/run/machin/machin-fcgi.sock|fcgi://localhost/"
</FilesMatch>

Remplacez getdata par tout url qui vous convient.

Le langage

Le langage étant très limité, je pense qu'il est plus simple de vous montrer en exemple exhaustif de ses possibilités

Imaginons que nous ayons une table "matable" contenant "id", "macolonne1" et "macolonne2"


if $listeafaire == "listertable" || $listeafaire == "gettable" // si POST['listeafaire'] == "listertable" ou "gettable"
	if $id == undefined      // undefined pour les valeurs non définies
		return error: "pas de valeur POST \"id\""   // échappement des "
	fi
	startquery = millis()   // chronomètre  depuis le lancement du script
	contenu = sql("SELECT * FROM matable WHERE id < ?", $id)   // exécution de la requête, les ? ont remplacés par les paramètres
	endquery = millis()
	i = 0
	while(contenu[i])     // équivalent à while(contenu[i] != undefined)
		debug("colonne1: ", contenu[i]["macolonne1"], ", colonne 2: ", contenu[i]["macolonne1"]); // partira dans la log apache
		i = i + 1
	wend

	labeldata = "dat"
	/* ceci va renvoyer
	  une chaîne json à apache */
	return error: false, // on gère les booleens
		"lines": i,
		"objetlambda": {"un": 1, "deux": 2}, // sous objet
		"magic_number": (i + 2) * 7,
		"querytime": endquery - startquery,
		// va renvoyer un tableau avec le contenu des deux colonnes de la table
		labeldata + "a": contenu["colonne 1": "macolonne1", "colonne 2": "macolonne2"]
fi

Évidemment, chaque variable ou chaîne peut être remplacée par une expression complexe. Faites des essais, ça ne devrait pas être trop dur à prendre en main.

Code Source

Le code est ici, je sollicite toutefois votre indulgence, il est pour l'instant assez "brut de décoffrage", c'est-à-dire qu'il manque de commentaires, est franchement encore brouillon par endroits, et les allocations mémoire ne sont pas vérifiées (voir le lien sur le pourquoi, mais c'est une chose à ajouter à terme). Bref il n'a pas encore passé l'étape du refactoring post dev initial.

Une petite librairie de Table de Hash...

Notions abordées

Localité de référence, alignement mémoire, éléments de tableau flexibles

Introduction

Le hash, pour ceux qui l'ignorent, permet généralement d'associer une chaîne de caractères à une valeur et de retrouver rapidement cette valeur à partir de cette chaîne de caractères.

On va donc chercher à créer une librairie qui fournirait à minima les deux fonctions suivantes:

// place dans la table de hash htable la valeur value ayant pour clé key
int ht_set(struct hashtable *htable, char *key, void *value);
// récupère dans la table de hash htable la valeur value ayant pour clé key
void* ht_get(struct hashtable *htable, char *key);

Ainsi pour stocker la valeur 1 associée à la clé "étage" on procèdera de la minière suivante:

int etage = 1;
ht_set(htable, "étage", &etage);

Et pour récupérer la valeur associée à la clé "étage":

int *etage;
etage = ht_get(htable, "étage");

Bien évidemment les performances devront être aussi élevées que possibles et c'est sur ce point que l'exercice s'avèrera intéressant. Comme nous le verrons la fonction de hash à employer n'est qu'une partie du problème.

D'ailleurs traitons ce point tout de suite: une fonction de hash prend en entrée une suite d'octets, et retourne un nombre d'octets fixe dont la valeur est fonction de son entrée. En outre, une bonne fonction de hash a une distribution la plus uniforme possible, c'est à dire que pour plusieurs valeurs d'entrée les valeurs de sortie sont uniformément réparties dans leur plage de sortie. Ceci permet d'éviter aux maximum les collisions (deux valeurs d'entrée qui partagent la même valeur de sortie). C'est un phénomène inévitable (on ne peut pas indexer toutes les valeurs d'une suite de 8 octets dans des index de 4 octets).

L'implémentation faite ici est axée sur les optimisations de vitesse et ce qu'elle gagne en vitesse, elle le perd (comme souvent) en économie mémoire! Je déconseille son utilisation en embarqué par exemple (mais cela tombe bien, les tables de hash sont rarement une bonne idée dans des environnements contraints en mémoire). Comptez une utilisation en RAM environ 3-4 fois supérieure à la taille des couples clé/valeurs stockés.

J'utiliserai la fonction de Fowler–Noll–Vo, pour moi c'est un bon compromis générique entre performances et efficacité, vous serez libres d'employer toute autre, celle-ci n'étant qu'un détail de l'implémentation et fait partie des réglages finaux (en effet, la nature des données influence fortement le choix de cette fonction).

Le fonctionnement (naïf) sera donc le suivant:

Évidemment, tout ne sera pas aussi rose: il faudra gérer les collisions, et notre tableau devra utiliser une mémoire en adéquation avec la quantité de valeurs stockées; sa taille devra par conséquent être variable

Mise en œuvre

La structure de la table de hash

Nous allons tout d'abord créer une structure permettant le bon fonctionnement de notre table de hash. Voici son détail:

typedef struct{
	ht_entry* entries;   // le tableau qui va stocker toutes les entrées
	size_t capacity;     // le nombre d'éléments de ce tableau
	size_t mincapacity;  // le nombre d'éléments minimum du tableau (sa taille est dynamique)
	size_t length;       // le nombre d'éléments effectivement stockés
	size_t valuesize;    // taille en octets d'une valeur
	size_t entrysize;    // taille en octets d'un élément du tableau
	ht_entry *lastentry; // dernier élément du tableau (pour optimisation)
} ht;

entrysize semble à priori surprenant car chaque élément du tableau étant une structure, un simple sizeof semble plus indiqué. Nous allons voir que c'est en réalité plus compliqué. Voyons la structure de chaque élément du tableau:

typedef struct {
	char key[MAX_KEY_LENGTH];  // la clé
	uint64_t hash;             // son hash
	uint8_t value[];           // la valeur stockée
} ht_entry;

Diantre! Trois éléments qui méritent chacun une explication!

En fait pour bien comprendre mes choix, il faut parler rapidement de la localité de référence. Si un processeur travaille sur des zones contiguës en mémoire, il travaillera entièrement en cache (la mémoire est chargée en cache par blocs entiers). Un échec de cache provoque un arrêt du pipeline d'exécution le temps d'aller chercher les valeurs en RAM, et cette opération est très coûteuse. Le cache est plus rapide d'un facteur 50 en moyenne et comme ici nous effectuons principalement un travail de recherche en RAM cette optimisation est cruciale. J'ai donc pris le parti de stocker les valeurs non pas via un pointeur, mais dans la structure elle-même. Ainsi toutes les données seront contiguës et le processeur pourra travailler à pleine vitesse.

Si l'on utilise des pointeurs les valeurs sont réparties un peu partout en mémoire, provoquant de fréquents échecs de cache.
En plaçant les valeurs dans des structures, toutes les données sont contigues, le cache processeur peut jouer à plein.

Évidemment cela va compliquer un peu nos affaires.

Tout d'abord nous ne connaissons pas à la compilation la taille de la valeur que nous allons stocker. Heureusement depuis le C99 nous avons les éléments de tableau flexibles que nous utilisont pour l'élément value. Ceci fait que l'utilisation de sizeof est proscrite pour obtenir la taille de la structure et explique la présence du champ entrysize dans la structure ht.

Voyons maintenant les deux autres champs (nous y reviendrons plus tard): la clé est stockée pour la gestion des collisions, et le hash pour ne pas a avoir à être recalculé lors du redimensionnement du tableau.

Initialisation de la structure de hash

On créée une fonction acceptant en arguments la taille des valeurs que l'on souhaite stocker et la capacité minimale de la table de hash

ht* ht_create(const size_t datasize, const size_t capacity) {
	ht* const restrict hash = malloc(sizeof(ht));
	if (hash == NULL) return NULL;

	hash->length = 0;
	hash->capacity = hash->mincapacity = capacity;
	hash->entrysize = datasize + sizeof(intmax_t) - datasize % sizeof(intmax_t) + offsetof(ht_entry, value);
	hash->valuesize = datasize;

	hash->entries = alloc_entries(capacity, hash->entrysize, &(table->lastentry));
	if (hash->entries == NULL) {
		free(hash);
		return NULL;
	}
	return hash;
}

Comme vous pouvez le remarquer, je suis assez fan des const et des restrict. Même si les progrès de GCC rendent les const quasiment inutiles du point de vue du code généré, les warnings à la compilation lorsque l'on tente de modifier une variable qui ne devrait pas l'être (y compris dans les fonctions appelées) participent à vérifier la robustesse du code. Le restrict étant ici le seul pointeur de la fonction, il est par conséquent parfaitement inutile. Mais c'est un réflexe. Et mon code. Je fais ce que je veux. Laissez-moi tranquille avec mes manies! :-D

La fonction est triviale SAUF la valorisation de entrysize. Elle répond à deux problèmes: la compacité de la structure et l'alignement mémoire.

Tout d'abord, lorsqu'un processeur cherche à accéder à une valeur, si son adresse mémoire n'est pas un multiple de la taille du registre accédé l'accès mémoire subit une pénalité (le temps d'accès est à peu près doublé). On doit donc s'assurer que la taille de notre structure soit un multiple de 32 ou 64 bits pour être sûr que quel que soit le contenu de notre structure, les accès soient optimums. Le compilateur fait très bien les choses pour des structures classiques mais là la taille du dernier membre est inconnue et nous allons générer un tableau de cette structure.

Ensuite, si l'on fait un sizeof(ht_entry) on devrait récupérer MAX_KEY_LENGTH (+ quelques octets si nécessaire afin d'aligner la mémoire) + 64 bits (pour la valeur hash). value est ignoré par le compilateur, comportement normal en ce qui concerne les éléments de tableaux flexibles. Or il arrive assez souvent que les compilateurs ajoutent encore un peu d'espace après ces données. Si l'on veut la taille minimale de la structure pour gratter quelques octets, on peut utiliser la macro offsetof() sur le membre value. On aura alors son offset et donc la taille employée par les deux premiers membres.

Reste alors à ajouter datasize paddé jusqu'à la valeur maximum d'un entier (qui correspond à minima au nombre de bits du processeur), par la formule datasize + sizeof(intmax_t) - datasize % sizeof(intmax_t). Un tableau de telles structures sera donc aligné tout du long ainsi que ses membres. L'utilisation de sizeof(intmax_t) n'est pas optimale (certains compilateurs 32 bits définissent intmax_t à 64 bits) mais elle a l'avantage d'être simple et portable.

Attention les valeurs sont fantaisistes, il ne s'agit que d'une illustration du concept
On a ajouté la valeur directement à la suite de la structure, dont la taille finale n'est pas un multiple de 64 bits. Seule la première est alignée, les autres verront leur temps d'accès pénalisé.
En ajoutant quelques octets pour compléter leur taille, leur alignement permet un accès à pleine vitesse.

Nous avons désormais toutes les valeurs nécessaires pour allouer la table de hash proprement dite via la fonction alloc_entries:

// deux macros qui vont bien resservir
// la taille de la structure ht_entry étant inconnue à la compilation, l'arithmétique des pointeurs ne s'applique plus
// on repasse donc par des calculs pour avoir l'adresse d'un élément dans la table
#define ENTRYINDEX(x, y, z) (ht_entry*)((uint8_t*)(x)+(y)*(z))
#define NEXTENTRY(x, y) (x)=(ht_entry*)((uint8_t*)(x)+(y))


static ht_entry* alloc_entries(const size_t capacity, const size_t entrylength, ht_entry **lastentry){
	ht_entry * const restrict entries = malloc(capacity * entrylength);
	if(entries == NULL) return entries;
	ht_entry *entry;
	*lastentry = ENTRYINDEX(entries, entrylength, capacity - 1);
	// plus rapide qu'un calloc(), il est inutile de mettre à zéro toutes les données
	for(entry = entries; entry <= *lastentry; NEXTENTRY(entry, entrylength))
		entry->key[0] = '\0';

	return entries;
}

Notez que la fonction est statique, ce qui va la rendre en quelque sorte "privée" au fichier source et permettra à gcc de l'inliner même en l'absence de link time optimization (-flto). En ce qui concerne le membre lastentry, il est positionné sur le dernier élément du tableau, nous verrons pourquoi plus tard. Pour chaque élément du tableau, on positionne la clé à "chaîne vide" pour signifier que la place est libre.

Pour finir, la libération de la table de hash:

void ht_destroy(ht* const restrict hash) {
	free(hash->entries);
	free(hash);
}

Ajout d'un élément

Maintenant que nous avons évité les écueils de performance, nous allons devoir gérer ceux inhérents aux tables de hash: les collisions.

Pour obtenir un index de tableau, nous allons utiliser la formule "hash obtenu" modulo "nombre d'éléments du tableau"

void* ht_set(ht* const restrict table, const char * const restrict key, const void * const restrict value){
	// si + de 50% de capacité on double la taille de la table
	if(table->length > table->capacity / 2 && ht_expand(table)) return NULL;
	// calcul du hash et de son index
	const uint64_t hash = hash_key(key);
	const size_t index = hash % table->capacity;

	ht_entry * restrict entry = ENTRYINDEX(table->entries, table->entrysize, index);

	// on recherche la première place libre
	while(entry->key[0] != '\0') {
		// même clé: on met à jour la valeur
		if (strcmp(key, entry->key) == 0){
			memcpy(entry->value, value, table->valuesize);
			return entry->value;
		}
		NEXTENTRY(entry, table->entrysize);
		// on boucle si l'on atteint la fin de la table
		if(entry > table->lastentry) entry = table->entries;
	}
	table->length++;
	return setentry(entry, key, hash, value, table->valuesize);
}

La première ligne de la fonction a pour but de doubler la taille de la table lorsque celle-ci a atteint la moitié de sa capacité. Ceci dans le but de minimiser les collisions. Nous appelons dans ce but la fonction ht_expand décrite plus loin.

La boucle while va gérer effectivement les collisions. Certains langages (Java, C++, Python et Perl entre autres) stockent les valeurs dans des listes chaînées, ce qui permet de stocker plusieurs valeurs dans le même hash. Or pour des raisons de localité de référence, nous avons exclus toute utilisation de pointeurs dans la structure. La solution appliquée ici est simplement de parcourir le tableau à la recherche du prochain emplacement libre. Les données étant en cache processeur, l'opération de lecture ou d'écriture sera très rapide (rappelons que nous parlons d'un facteur 50). L'inconvénient étant de toujours devoir avoir sur la main un tableau comportant toujours beaucoup d'espace libre. Ici nous avons choisi 50% comme valeur en dessous de laquelle ne pas descendre. Nous sacrifions l'utilisation de la mémoire en faveur des performances (mais ça reste raisonnable).

Voyons maintenant la fonction de hash (Fowler–Noll–Vo), implémentation triviale:

static uint64_t hash_key(const char * restrict key) {
	uint64_t hash = FNV_OFFSET;
	while(*key){
		hash ^= (uint64_t)*key;
		hash *= FNV_PRIME;
		key++;
	}
	return hash;
}

Nous sommes libres à l'avenir de la remplacer par toute fonction plus adéquate aux données traitées ou aux résultats espérés.

La fonction setentry est triviale et permet d'aérer le code (elle sera réutilisée plus tard), et sa déclaration static permettra au compilateur de l'inliner:

static void* setentry(ht_entry * const restrict entry, const char * const restrict key, const uint64_t hash,
                                 const void * const restrict value, const size_t valuesize){
	strcpy(entry->key, key);
	memcpy(entry->value, value, valuesize);
	entry->hash = hash;
	return entry->value;
}

Attaquons-nous au gros morceau: la fonction ht_expand. Outre le doublement de la taille de la table (ou sa réduction par moitié pour les suppressions), nous devrons également relocaliser tous ses éléments. Voilà pourquoi dans chaque élément de la structure ht_entry nous stockons le hash complet (dans le membre hash): nous n'aurons pas à le recalculer, mais simplement son index via un modulo.

static int ht_expand(ht* const restrict table) {
	if(table->capacity > SIZE_MAX / 2) return 1; // dépassement de capacité de l'entier
	const size_t new_capacity = table->length <= table->capacity / 4 ? table->capacity / 2 : table->capacity * 2;

	ht_entry *entrysrc, *entrydst;
	const ht_entry * const restrict maxentrysrc = table->lastentry;
	
	ht_entry* const restrict new_entries = alloc_entries(new_capacity, table->entrysize, &(table->lastentry));
	if(new_entries == NULL) return 1;

	for(entrysrc = table->entries; entrysrc <= maxentrysrc; NEXTENTRY(entrysrc, table->entrysize)){
		if(entrysrc->key[0] == '\0') continue;
		const size_t index = entrysrc->hash % new_capacity;
		entrydst = ENTRYINDEX(new_entries, table->entrysize, index);
		while(entrydst->key[0] != '\0'){
			NEXTENTRY(entrydst, table->entrysize);
			if(entrydst > table->lastentry) entrydst = new_entries;
		}
		memcpy(entrydst, entrysrc, table->entrysize);
	}
	free(table->entries);
	table->entries = new_entries;
	table->capacity = new_capacity;

	return 0;
}

La fonction commence par calculer la nouvelle taille de la table, puis par allouer la nouvelle capacité. On procède ensuite au calcul du nouvel index de chaque élément (grâce au hash que nous avons conservé en mémoire afin de ne pas le recalculer à chaque fois) et l'on recopie cet élément à sa nouvelle place dans la nouvelle table. On utilise toujours la stratégie de placer l'élément au prochain emplacement disponible si la plae est déjà prise.

La fonction alloc_entries() est séparée pour plus de clarté; elle remplit le même rôle qu'un calloc(), mais comme nous n'avons qu'un octet par enregistrement à mettre à zéro elle est un peu plus rapide (et avec les instructions SSE utilisées dans la libc cela ne se joue pas à grand chose):

static ht_entry* alloc_entries(const size_t capacity, const size_t entrylength, ht_entry **lastentry){
	ht_entry * const restrict entries = malloc(capacity * entrylength);
	if(entries == NULL) return entries;
	ht_entry *entry;
	*lastentry = ENTRYINDEX(entries, entrylength, capacity - 1);
	// plus rapide qu'un calloc()
	for(entry = entries; entry <= *lastentry; NEXTENTRY(entry, entrylength))
		entry->key[0] = '\0';

	return entries;
}

Voilà, nous pouvons maintenant déclarer une table de hash et insérer des éléments à l'intérieur. Ce n'était pas tout à fait trivial, heureusement la récupération l'est.

Lecture d'un élément

void* ht_get(ht* const restrict table, const char * const restrict key, const void * const restrict defaultval) {
	const uint64_t hash = hash_key(key);
	const size_t index = hash % table->capacity;
	ht_entry * restrict entry = ENTRYINDEX(table->entries, table->entrysize, index);

	while(entry->key[0] != '\0') {
		if (strcmp(key, entry->key) == 0) return entry->value;
		NEXTENTRY(entry, table->entrysize);
		if(entry > table->lastentry) entry = table->entries;
	}
	if(defaultval == NULL) return NULL;
	table->length++;
	return setentry(entry, key, hash, defaultval, table->valuesize);
}

Ici, on calcule juste l'index théorique de l'élément recherché et on recherche l'élément correspondant à la clé (rappelons qu'en cas de collision on aura inséré à la première place libre et que les performances ne devraient pas trop souffrir du fait de la localité de référence). Pour cela on parcourt tous les éléments successifs jusqu'à trouver la bonne clé ou une case vide. A noter le paramètre defaultval qui permet d'insérer une valeur par défaut si la valeur n'a pas été trouvée. Comme la boucle se termine au premier emplacement libre on a juste à écrire la valeur à l'aide de la fonction décrite dans le chapitre précédent

Suppression d'une entrée

Là nous entrons dans la partie la plus complexe de la librairie. Nous allons devoir gérer la taille dynamique de la table ET un autre problème:

Rappelez-vous qu'en cas de collision, si la place était déjà occupée, nous ajoutons notre valeur à la première place disponible. Donc en supprimant notre élément nous allons potentiellement créer un trou dans une suite de valeurs, et à terme provoquer l'échec des recherches. On devra par conséquent veiller à réorganiser les éléments consécutifs à celui que l'on vient de supprimer afin de conserver la cohérence e notre table.

nous allons d'abord créer une fonction qui a partir d'une clé va renvoyer son index (ou NULL en cas d'échec) et le nombre d'entrées immédiatement consécutives à celle-ci. Ainsi nous aurons la liste des entrées à relocaliser.

static ht_entry* findentriestorelocate(const ht * const restrict table, const char * const restrict key, size_t * const restrict count){
	const uint64_t hash = hash_key(key);
	const size_t index = hash % table->capacity;
	const ht_entry *entry = ENTRYINDEX(table->entries, table->entrysize, index);
	const ht_entry *entrystart = NULL;
	
	*count = 0;
	
	while(entry->key[0] != '\0') {
		if(entrystart == NULL){
			if(strcmp(key, entry->key) == 0) entrystart = entry;
		}
		else (*count)++;
		NEXTENTRY(entry, table->entrysize);
		if(entry > table->lastentry) entry = table->entries;
	}
	// vaudra NULL si la clé n'est pas trouvée
	return (ht_entry*)entrystart;
}

La fonction retourne un pointeur sur l'enregistrement correspondant à la clé (ou NULL), et *count le nombre d'enregistrement à relocaliser.

Maintenant, nous allons avoir besoin d'une fonction qui va créer une copie de ces enregistrements avant de les effacer de la table de hash, car nous ne pouvons pas nous permettre de simplement décaler les enregistrements pour occuper la place qui sera libérée. En effet, on prend le risque de placer un enregistrement qui se trouve à une place légitime AVANT celle-ci. Toute recherche échouera par conséquent.

static ht_entry* moveentries(const ht * const restrict table, ht_entry *src, const size_t count){
	ht_entry *lastentry = ENTRYINDEX(src, table->entrysize, count - 1);
	ht_entry * const restrict dst = malloc(count * table->entrysize);
	if(dst == NULL) return NULL;

	if(lastentry <= table->lastentry){
		memcpy(dst, src, count * table->entrysize);
		while(src <= lastentry){
			src->key[0] = '\0';
			NEXTENTRY(src, table->entrysize);
		}
	}
	else{
		lastentry = src + ((char*)lastentry - (char*)table->lastentry);
		memcpy(dst, src, (char*)table->lastentry - (char*)src);
		while(src <= table->lastentry) {
			src->key[0] = '\0';
			NEXTENTRY(src, table->entrysize);
		}
		src = table->entries;
		memcpy(dst + ((char*)table->lastentry - (char*)src), table->entries, (char*)lastentry - (char*)table->entries);
		while(src <= lastentry) {
			src->key[0] = '\0';
			NEXTENTRY(src, table->entrysize);
		}
	}
	return dst;
}

La fonction prend en paramètre les sorties de la fonction précédente (minus la première entrée qui est celle à supprimer), et retourne un buffer de count entrées qui auront été transférées à partir de table. Nous n'avons plus qu'à les réinsérer proprement via la fonction suivante:

static void insertentries(const ht *const restrict table, const ht_entry * restrict src, size_t count){
	ht_entry * restrict dst;

	while(count > 0){
		size_t index = src->hash % table->capacity;
		dst = ENTRYINDEX(table->entries, table->entrysize, index);
		while(dst->key[0] != '\0'){
			NEXTENTRY(dst, table->entrysize);
			if(dst > table->lastentry) dst = table->entries;
		}
		memcpy(dst, src, table->entrysize);
		NEXTENTRY(src, table->entrysize);
		count--;
	}
}

On aurait pu procéder en utilisant la fonction d'insertion classique, mais le calcul du hash et celui du redimensionnement de la taille sont inutiles (et rappelez-vous qu'on recherche de la vitesse).

Il ne nous reste plus qu'à lier le tout pour obtenir la fonction recherchée:

int ht_unset(ht* const restrict table, const char* const restrict key){

	if(table->capacity > table->mincapacity * 2 && table->length <= table->capacity / 4 && ht_expand(table)) return -1;  // ajouter une option pour ça dans le ht_create?

	size_t count;
	ht_entry *entrystart = findentriestorelocate(table, key, &count);
	if(entrystart == NULL) return 1;

	entrystart->key[0] = '\0';
	table->length--;

	if(count == 0) return 0;

	NEXTENTRY(entrystart, table->entrysize);
	if(entrystart > table->lastentry) entrystart = table->entries;
	
	ht_entry *buf = moveentries(table, entrystart, count);
	if(buf == NULL) return 1;

	insertentries(table, buf, count);

	free(buf);

	return 0;
}

Notons qu'entre l'apper à findentriestorelocate() et celui à moveentries() nous procédons à l'effacement de l'entrée en elle-même et incrémentons entrystart vers la position suivante.

Bonus: un itérateur

pour finir, ajoutons un itérateur qui nous permettra de lister le contenu de notre table de la manière suivante:

hti *iterator = hti_create(hashtable);
		while(iterator->key){
		printf("%s %s\n", iterator->key, iterator->value);
		hti_next(iterator);
	}
}
free(iterator);

L'implémentation ne pose aucun problème après ce que nous avons traversé:

typedef struct{
	ht *table;
	ht_entry *current;
	void *value;
	char *key;
} hti;

hti* hti_create(ht * const restrict table){
	hti *ret = malloc(sizeof(ht));
	if(ret == NULL) return NULL;
	ret->table = table;

	hti_reset(ret);

	return ret;
}

void hti_next(hti * const restrict iter){
	do{
		NEXTENTRY(iter->current, iter->table->entrysize);
	}while(iter->current->key[0] == '\0' && iter->current <= iter->table->lastentry);
	if(iter->current > iter->table->lastentry){
		iter->current = NULL;
		iter->key = NULL;
		iter->value = NULL;
	}
	else{
		iter->key = iter->current->key;
		iter->value = iter->current->value;
	}
}

void hti_reset(hti * const restrict iter){
	if(iter->table->length == 0){
		iter->key = NULL;
		iter->value = NULL;
		return;
	}
	for(iter->current = iter->table->entries; iter->current->key[0] == '\0'; NEXTENTRY(iter->current, iter->table->entrysize));
	iter->key = iter->current->key;
	iter->value = iter->current->value;
}

Conclusion

Nous venons de réaliser une librairie de gestion de hashtables qui semble relativement performante, simplement conçue sans défaut rédhibitoire au niveau de l'architecture processeur (les échecs de cache) et opté pour une stratégie exploitant au mieux la localité de référence (la recherche dans des cases contiguës). Nous avons également pris soin de respecter l'alignement mémoire. Tout ceci ne constitue pas à mon sens des optimisations, mais du savoir-faire, et si un travail d'optimisation doit avoir lieu, c'est à partir du point actuel (la mise en cache du hash en est toutefois une, j'en conviens).

Après quelques tests de performances, j'ai pu remarquer deux choses:

Code source

Vous pouvez télécharger l'intégralité du code source ici.

Malloc et NULL, ce n'est pas si simple...

Introduction

Dans mon développement fascgi, vous remarquerez très vite que je ne vérifie pas si mes allocations retournent NULL. Cela me permet un code plus beaucoup plus simple à lire et un développement de mes expérimentations beaucoup plus rapide. Cependant, nous allons voir que cette pratique n'est pas aussi "sale" que l'on pourrait penser sous Linux. Je décourage fortement cette pratique sous d'autres systèmes ou dans des applications de production.

Historique

Les temps anciens et l'embarqué

Sur MS-DOS, d'autres systèmes anciens et sur certains systèmes à mémoire contraintes (l'Arduino par exemple), la taille de la mémoire est fixe et limitée. Par fixe on entend le fait que la mémoire n'est pas virtualisée, et donc pas de swap et d'extension de celle-ci. Dans ce cas une allocation fait exactement ce que l'on attend d'elle et cherche une place libre en mémoire, l'alloue et rend un pointeur vers elle, ou NULL si aucune place n'est disponible.

Ignorer la valeur nulle de retour expose à de gros problèmes :

Nous comprenons rapidement que le dogme de la vérification des retours d'allocation est parfaitement fondé.

Linux de nos jours

Linux, dans l'écrasante majorité des cas, renverra toujours un pointeur non null dans le cas d'une allocation, même s'il n'y a plus de mémoire disponible.

Vous avez bien lu.

En effet, Linux, avec ses réglages par défaut, utilise un allocateur dit "optimiste". L'allocation proprement dite ne sera faite qu'au moment de l'utilisation de la mémoire, mais à ce moment nous avons déjà un pointeur qui semble valide (Il est possible de modifier ce comportement moyennant un effondrement des performances).

Cette décision a été prise pour des considérations de performances, et elle est mitigée par le fait que les systèmes modernes disposent d'un espace d'échange permettant un accroissement de sa mémoire au delà de sa capacité physique. Lorsque cela ne suffit plus, un process appelé "oom_killer" se chargera de tuer d'autres processus plus ou moins au hasard afin de faire de la place. Mais pour cela il faut soit remplir tout l'espace mémoire (physique plus échange), soit dépasser sa capacité d'adressage (4Go en 32 bits sans PAE, et 256To en 64 bits).

Check NULLs or do no check?

Pourquoi ne pas vérifier

La première réponse est que dans la plupart des cas, c'est inutile, vu que malloc renverra toujours quelque chose. En 25 ans de métier, je n'ai jamais vu une ligne de log écrivant "out of memory" quand bien même le cas était traité explicitement dans le code.

Mieux, j'ai déjà vu (et probablement écrit) du code où le traitement de cette erreur invoquait, directement ou implicitement, une nouvelle allocation. Bien traiter ce genre d'erreurs (avec écriture dans la log et sortie propre) est quelque chose qui n'est pas aussi trivial que la plupart des traitements "à la légère" que j'ai pu constater. Parfois un simple exit() serait beaucoup plus sûr. Et encore une fois, tout ceci en espérant que notre processus ne soit pas victime du "oom_killer" entre temps.

On peut donc dire que la gestion des allocations alourdit considérablement le code pour un bénéfice aléatoire, cette erreur étant dans les cas classiques indétectable.

Pour finir, dans un système multitâche comme Linux, un épuisement de la mémoire se résume à une chose : le chaos. Une machine qui rame, des processus qui meurent en cascade... A ce stade le système n'est plus capable de grand-chose et une sortie propre du programme n'est plus le souci principal.

Pourquoi vérifier

Conclusion

Sous Linux (j'insiste), et pour des applications non critiques il n'est pas vraiment utile de vérifier si une allocation s'est bien déroulée étant donné qu'elle n'échouera pratiquement jamais.

En ce qui concerne des applications de production, il me semble indispensable de gérer proprement ces cas, en ne faisant pas appel à une nouvelle allocation. On ne sait jamais dans quel environnement futur celle-ci sera amenée à évoluer. Sans aller jusqu'aux allocateurs custom avec tmalloc, il me semble plus pertinent d'encapsuler les fonctions d'allocation dans des fonctions se contentant de reporter l'erreur et de terminer immédiatement l'exécution ; c'est pour moi la manière la plus simple de convenablement gérer ceci sans alourdir le code de façon extrême.

Bien sûr, il s'agit de s'adapter à chaque cas ; ainsi une application réseau devra tenter d'envoyer un statut à ses clients; de même les grosses allocations pourront faire l'objet d'un traitement plus élaboré sans nécessiter l'arrêt du programme. Mais dans tous les cas nous ne ferons que maximiser les chances de survie du processus, et surtout éviterons les comportements indésirables ("pourrir" la base de données par exemple, ou envoyer n'importe quoi sur le réseau).

Si accepter un dogme établi permet souvent de se mettre à l'abri, quelqu'un d'expérimenté aura toujours beaucoup à apprendre en essayent de regarder ce qui se passe derrière. Mais on ne sort des sentiers balisés qu'à condition de très bien savoir ce que l'on fait ; dans le doute, abstenez-vous. Le hors piste a aussi piégé des skieurs confirmés.

La station météo ESP8266 revisitée

Les choses en l'état

Cette page a pour but de présenter un système météo WiFi avec serveur web intégré comme il en existe beaucoup, mais en essayant d'aller plus loin (écran, Amazon Alexa...).

Le but étant de viser une autonomie > 8 mois et de bénéficier de fonctionnalités très avancées sur un si petit chip. Je ferai également part de mes commentaires sur la qualité du code généralement rencontré sur ces systèmes (spoiler: c'est très souvent à vomir, probablement autant que mon circuit électronique).

Le code et le circuit sont terminés, je finalise actuellement le boîtier en impression 3D et je ferai part du tout sur cette page.

stay tuned!