Sed, substitutions et performances

Auteurice : Arthur Pons

Temps de lecture : ~15 minutes

Le problème

Il y a peu une ingénieure de l’Université de Strasbourg est venue me voir avec un problème. Elle travaille avec une équipe de recherche sur un projet d’édition numérique du manuscrit d’un certain George Flohr, alsacien au XVIIIe enrolé dans la guerre d’indépendance des Etats-Unis. A son retour, il rédige tout un journal de bord de son aventure, des lieux qu’il a traversé, des personnes qu’il a rencontré. Il s’agit de ce manuscrit que ce projet d’édition numérique souhaite publier en ligne. Pour cela, les fichiers de transcription et de traduction sont encodés en TEI. Les nom de lieux sont référencés via des balises qui comportent des identifiants. Par exemple pour Strasbourg :

Geschehen zu <placeName corresp="https://sws.geonames.org/2973783/about.rdf">Straßburg</placeName> den <date when="1787-06-05">5 J[uni]<lb/>

Ici 2973783 est l’identifiant geonames du lieux. L’ingénieure a créé un référentiel pour chacun des lieux. Ce référentiel fait correspondre un identifiant geonames à un identifiant maison. Elle souhaitait donc modifier la valeur des balises corresp en substituant l’url geonames à l’identifiant maison correspondant. Nous avons d’abord préparé une table de correspondance qui a, pour Strasbourg par exemple, cette tête :

flohr_place_00074
2973783

On veut modifier le texte de la pièce pour qu’apparaisse :

Geschehen zu <placeName corresp="flohr_place_00074">Straßburg</placeName> den <date when="1787-06-05">5 J[uni]<lb/>

Le texte d’origine est ici (544Ko) et le fichier de correspondance là (8Ko).

La solution naïve

Qui dit substitution dit sed. une commande qui ferait l’affaire serait

sed -i "s;https://sws.geonames.org/2973783/about.rdf;flohr_place_00074;g" text.xml

Petit tips, souvenez vous que l’on peut choisir le caractère que l’on veut comme délimiteur de la commande s de sed. Pratique quand on bosse avec des urls et que l’on ne peut pas utiliser /.

Pour exécuter une commande de ce type pour toutes les paires “ancien id/nouvel id” on peut utiliser xargs. En imaginant que la table de correspondance se trouve dans un fichier nommé corres :

xargs -a corres -d'\n' -n2 sh -c 'sed -i "s;https://sws.geonames.org/$2/about.rdf;$1;g" text.xml' --

Ce script exécute à la suite toutes les commandes sed nécessaires pour faire toutes les substitutions. Il prend environ 1,3s à finir. L’ingénieure s’est ensuite demandée si ce script était plus ou moins rapide et/ou énergivore (deux choses différentes) que celui qu’elle avait l’intention d’écrire. Sans aucune mesure j’ai estimé qu’il était probable qu’il soit très peu optimisé sur ces deux métriques notamment parce qu’il ouvre et ferme le fichier à modifier à chaque substitution, ce qui est notoirement coûteux en temps. Or il y en a 213 en tout, il est donc raisonnable de penser qu’il existe d’autres techniques pour aller beaucoup plus vite.

Optimisations en temps

Attention !

Je tiens à prévenir et que je n’y connais rien en programmation parallèle et je me cantonne volontairement au shell. J’imagine qu’il existe d’autres techniques, plus ou moins coûteuses en code et en temps, bien plus efficaces que ce que je vais développer ci dessous. Aussi, mon manque de compétences dans ce domaine m’empêche de bien comprendre pourquoi telle technique fonctionne mieux ou moins bien qu’une autre. J’ai entre autre du mal à identifier les “bottlenecks”. Si vous faite fréquemment du calcul intensif la lecture de ce qui suit risque de vous être désagréable.

Les mesures de temps on été faites avec time, généralement deux trois fois sans particulièrement faire attention à ce que le reste de l’environnement soit équivalent d’une commande à l’autre. A prendre donc avec quelques gros grain de sel.

J’ai connaissance de GNU parralel sans pour autant l’utiliser. Il est possible que ce soit un outil bien plus approprié qu’xargs pour faire ce qui suit. Je me demande entre autre s’il est possible non seulement de parraléliser les commandes mais aussi de découper l’exécution sur différents morceaux du fichier.

Quelques métriques

Le texte d’origine en TEI fait 12307 lignes pour 54095 mots. Il y a 213 substitutions à faire. Il y a en tout 377 occurrences de ces 213 substitutions puisque certains lieux apparaissent plusieurs fois dans le texte.

Pour que les optimisations soient plus flagrantes j’ai créé un nouveau fichier qui est 100 fois le texte d’origine. Il y a donc 1 million 230 mille lignes, 5 millions 409 milles mots et les 213 commandes de substitutions vont en tout modifier 377 mille occurrences. Pour comparaison, Guerre et Paix c’est 587 mille mots.

La parallélisation

La première optimisation très peu coûteuse à coder en partant de notre script est la parallélisation. Pour le moment le script exécute sed -i ..., attend que cela termine puis passe au suivant de manière séquentielle. Forcément, avec un très gros fichier cela prend un très gros bout de temps. En l’occurence plus de 2m10s sur notre gros fichier.

Les processeurs modernes disposent de plusieurs coeurs. Ils peuvent donc mener plusieurs processus en simultané. A l’aide de l’option -Pn de la commande xargs nous pouvons dire au script de lancer jusqu’à n processus en simultané. Par exemple avec -P4 c’est quatre substitutions qui se feront en même temps.

D’expérience je ne sais jamais vraiment combien de processus lancer, j’expérimente pour trouver le “sweet spot”. Avec 10 le script passe de 2m10 à 1m42. Sans donner de limite c’est 1m54. On voit que le gain de temps est modéré. Le PC a tendance à légèrement freeze sans pour autant toujours utiliser les processus à 100%. J’imagine que paralléliser beaucoup d’accès mémoire n’est pas particulièrement efficace.

Économiser des accès au fichier

Pour tester l’hypothèse selon laquelle une bonne partie du temps est passé à ouvrir text.xml et à l’écrire, faisons un seul appel à sed. Pour cela je manipule le fichier corres de façon à en faire un script sed contenant toutes les substitutions :

s,https://sws.geonames.org/3411865/about.rdf,flohr_place_00010,g;
s,https://sws.geonames.org/5106834/about.rdf,flohr_place_00035,g;
s,https://sws.geonames.org/3038230/about.rdf,flohr_place_00106,g;
...

Pour l’obtenir j’ai fait
cat corres | paste - - | sed -E 's+(.*).(.*)+s,https//sws.geonames.org/\2/about.rdf,\1,g;+'.
Alternativement, et sûrement plus proprement :
xargs -a corres printf 's;https://sws.geonames.org/%s/about.rdf;%s;g\n'

Ainsi on appelle sed une seule fois

sed -i -f subs.sed text.xml

Cette technique permet de faire tomber le temps d’exécution à 30s soit une division par 3 ou 4. Notre hypothèse se vérifie bien. Aucun scoop je crois que c’est vraiment le b-a-ba de l’optimisation de calcul.

Combiner les deux

Dans l’exemple précédent nous utilisons un seul processus. L’un de nos coeurs sera possiblement à 100% mais nous n’utilisons pas la puissance des trois autres. Pour améliorer encore nos performances nous pouvons séparer les commandes de substitutions en quelques gros groupes et les exécuter via quelques appels simultanés à sed. Je ne sais pas bien comment estimer la quantité optimale de processus à lancer ici, j’ai choisi quatre.

sed -e 'les_50_premières_sub_de_subs.sed' text.xml |
sed -e 'les_50_suivantes' |
...
... > res.xml

Avec cette technique nous tombons à environ 10s. Pour le fichier d’origine on passe de 1,3s avec la première technique à 0,15s avec celle-ci.

Dans une ancienne version de ce script j’avais proposé le script suivant

xargs -a subs.sed -d'\n' -P4 -n54 sh -c 'sed -i "$*" big.xml' --

Il se révèle, pour tout œil un peu entrainé, qu’il n’accomplit pas du tout la tâche. L’accès concurrentiel de quatre processus à un même fichier pour y faire des substitutions inplace donne à la fin un fichier dans lequel n’a été substitué que ce que le dernier processus se terminant aura fait. C’est lui qui aura écrit le fichier en dernier.

Si vous avez énormément de substitutions et/ou un gigantesque fichier il peut être intéressant d’avoir un script qui génère automatiquement ce script. Je propose :

set 50 text.xml
sed "1~$1 s/^/sed '/; $1 s/$/' $2 |/; $(($1*2))~$1 s/$/' |/; $ s/$/'/" subs.sed
    | sh > res.xml

Attention, l’adressage sed n~m n’est pas POSIX. Dans $1 la valeur de la taille des groupes de commandes de substitutions, dans $2 le chemin du fichier résultat.

On me dit que ce serait mieux avec split, c’est sûrement vrai. Exemple :

split -l50 corres CHANGES
echo '< big.xml' $( printf 'sed -f%s| ' CHANGES* ) 'cat > new.xml' | sh

Synthèse

Optimisation en énergie

Méthodologie^{très nulle©™}

Pour mesurer à la louche la consommation énergétique des commandes j’utilise un programme nommé energy, disponible chez Bitreich¹. Du propre aveu de la personne l’ayant écrit, c’est peu fiable². En plus de n’être pas fiable energy ne fait pas la différence entre les processus et renvoie donc l’énergie totale consommée lors de l’exécution de la commande. J’ai donc écrit un wrapper qui fait la différence entre l’énergie totale et celle habituellement consommée par l’ordinateur au repos. Evidemment cela dépend fortement du matériel.

Mon script est le suivant :

res=$( (time -f %e energy $*) 2>&1 1>/dev/null)
timeres=$(echo "$res" | tail -n1)
idleenergy=$(echo "11.03 * $timeres" | bc -l)
totenergy=$(echo "$res" | sed -nE '1,2 s/.* ([0-9]+\.[0-9]+).*/\1/ p' | paste -s -d'+' | bc -l)
diffenergy=$(echo "$totenergy - $idleenergy" | bc -l)
echo "$timeres : command exec time"
echo "$idleenergy : estimated J consumption for $timeres of idle time"
echo "$totenergy : total energy consumption"
echo "$diffenergy : added consumption of command"

Pas bien joli mais ça fonctionne. La constante 11.03 est la conso moyenne en joule de mon pc durant une seconde avec uniquement l’environnement de bureau et une console ouverte.

Le script récupère la durée d’exécution de la commande ainsi que la totalité de l’énergie consommée durant puis fait la différence entre ce total et 11.03 fois la durée d’exécution en seconde.

Évidemment la moyenne de 11.03 n’est pas tout à fait juste, mon pc fait plein de choses en arrière plan³ et je n’ai pas la patience de faire plusieurs mesures pour faire des moyennes. Je m’astreins donc à ne tirer des conclusions définitives que de grosses différences de mesure.

Il faudrait refaire toutes les mesures avec un logiciel et une méthode plus sérieuse.

Mon est un Dell Latitude 5480 avec un Intel i5-7200U @ 2.50 GHz.

Les mesures

Pour la toute première solution sur le petit fichier :

1.167 : command exec time
12.87201 : estimated J consumption for 1.167 of idle time
29.96 : total energy consumption
17.08799 : added consumption of command

L’exécution de cette commande aurait donc plus que doublé la quantité d’énergie consommée. A vérifier parce que ça me semble beaucoup.

Cette même solution mais sur le gros fichier

133.03 : command exec time
1467.3209 : estimated J consumption for 133.03 of idle time
2608.30 : total energy consumption
1140.9791 : added consumption of command

Ici la commande ajoute proportionnellement moins d’énergie. A noter que le temps d’exécution est tellement long que l’écart inévitable entre la moyenne de consommation au repos et la réelle valeur risque d’être très grande. Par exemple, juste après ce test j’ai lancé un

energy sleep 133.03

et j’ai obtenu 1061.39 et donc une consommation supplémentaire de 1549.91 J soit 400 J de plus qu’annoncé ! L’une des valeurs n’est pas plus vraie que l’autre, simplement avec cette technique plus le temps d’exécution est long plus le résultat est peu fiable.

Toutes les substitutions en un seul appel à sed :

29.90 : command exec time
329.7970 : estimated J consumption for 29.90 of idle time
696.41 : total energy consumption
366.6130 : added consumption of command

et la technique la plus rapide :

9.717 : command exec time
107.17851 : estimated J consumption for 9.717 of idle time
400.66 : total energy consumption
293.48149 : added consumption of command

Avec les fortes incertitudes de notre méthode je pense que l’on peut conclure que ces deux techniques se valent en terme de consommation d’énergie.

Synthèse

Remarques

Il faut reconnaître que ce travail d’optimisation n’est qu’à but expérimental. Le texte d’origine et la taille du corpus dont il vient ne sont pas d’ampleur suffisante pour que cela vaille nécessairement le coup. Cela dit passer du premier script au dernier a été assez rapide, les outils sed et xargs permettant d’écrire du code très expressif et d’itérer très rapidement.

Donnons momentanément du crédit à notre méthode de calcul de consommation d’énergie. On apprend que notre première solution, en plus d’être lente n’est pas efficace. Je suppose que le temps perdu en accès mémoire, à relancer sed à chaque fois etc se traduit aussi par de l’énergie perdue à les exécuter. Autrement dit, on met une quantité non négligeable d’énergie à faire d’autres choses que des substitutions. Un peu comme lorsque l’on pédale sur un mauvais vélo. On y met de l’énergie mais seulement une fraction sert réellement à nous faire avancer.

L’appel unique à sed est manifestement beaucoup plus efficace. Il est raisonnable de penser qu’en s’économisant tout ce travail superflu il va plus vite en consommant moins.

La technique la plus rapide a une consommation d’énergie similaire à la précédente. Je suppose que les 3 cycles supplémentaires de lancement de sed d’ouverture de fichier etc sont trop peu nombreux pour avoir une incidence significative sur la consommation d’énergie. Ici la parallélisation a considérablement accéléré la tâche⁴ (divisé par ~3) ce qui a suffit pour compenser la charge presque quatre fois plus grande imposée au CPU. On constate donc une accélération “gratuite” en terme de consommation d’énergie. Le temps d’exécution de la tâche s’est plus ou moins linéairement réduite avec la quantité de puissance mise dedans. D’ailleurs, et c’est certainement bien connu des personnes bossant dans le domaine, j’ai le sentiment que l’on a des rendements décroissants avec l’augmentation du nombre de processus parallélisé et qu’ici quatre était le chiffre magique. Du moins c’est ce que je constate souvent, j’imagine que ça dépend du matériel et du type de processus. Sur des CPU avec de très nombreux cœurs on peut peut-être continuer à constater des rendements linéaires pour des quantités de processus plus élevés. Est-ce que la meilleure quantité de processus a un rapport avec la quantité de cœurs de son CPU ? Si vous avez la réponse n’hésitez pas à m’éduquer. D’ailleurs si vous avez une quelconque expertise en calcul intensif je veux bien un retour sur cet article. J’ai l’impression de redécouvrir la roue mais en commençant avec un prototype carré.

Aller plus loin en consommant moins

Le périmètre initiale de notre problème était celui de sed. Nous sommes probablement allez aussi loin que possible sans avoir à y passer une quantité de temps déraisonnable. Il est cependant possible de résoudre ce problème de façon bien plus efficace à l’aide de langages de programmation plus complexes.

Marc Chantreux et Pierre Gerhard en font la démonstration avec respectivement un script perl et un script python. Sur mon pc les perfs sont :

Les deux scripts ont des performances énergétiques drastiquement meilleures que tous nos scripts sed. Elles ajoutent une consommation énergétique d’environ 9J pour le gros fichier soit deux ordres de grandeur en dessous de notre meilleur résultat sed.

Pourquoi ? Parce que ces deux scripts n’ont qu’une commande de substitution. Pour chaque ligne une seule tentative de substitution est faite contre 213 dans les scripts sed. Pour que cela puisse fonctionner quand bien même il y a bien des chaînes différentes à substituer dans chacune des paires dans corres ils utilisent une astuce avec un tableau associatif. En se reposant sur le principe que toutes les substitutions vont commencer par la même chaine https://... ont peut créer un “template” de substitution type :

s;https://sws.geonames.org/ID/about.rdf;NEWID;g

Où l’on récupère la clef ID pour chercher la valeur correspondante NEWID dans le tableau associatif. Ainsi on construit une seule substitution que l’on modifie à la volée lorsque l’on a matché le début de notre chaîne. Pour saisir pourquoi c’est beaucoup plus efficace imaginons une ligne sur laquelle il n’y a rien à substituer. Nos scripts sed vont tester une première fois de trouver un h, puis un t, puis un t sans succès puis passer à une autre substitution pour tenter de retrouver un h puis un t puis un t alors même que la première substitution n’a pas matché et que l’on sait donc qu’aucune autre ne matchera ! Nos scripts perl et python vont tenter de trouver un h, puis un t, puis un t mais une fois arrivé au bout de la ligne sans match ils passeront à la ligne suivante. La complexité en sed croît avec le produit de nb_sub*nb_lignes quand nos scripts perl/python croient en nb_lignes uniquement.

Il semblerait donc que pour un problème de substitution de ce type et pour de très gros volumes de donnée la complexité supplémentaire d’embarquer perl/python et la relative verbosité des scripts associés puissent valoir le coup temporellement et énergétiquement. C’est un cas intéressant d’arbitrage coût/bénéfice, selon moi ici plutôt à l’avantage de perl/python. C’est aussi une belle démonstration que la compétence des développeurs et l’adéquation des outils peut faire des miracles pour les performances. Parfois bien plus que du matériel plus puissant. C’est cette idée là qui me fait penser que la meilleure chose que l’on puisse faire pour réduire l’impact environnemental d’un centre de calcul est d’embaucher des ingénieur·e·s calcul supplémentaires pour accompagner les chercheureuses. Bien évidemment les problèmes scientifiques auxquels iels sont confronté·e·s sont extrêmement divers et ne peuvent pas tous être aussi bien optimisés mais je parie que l’on serait surpris.