arthur.bebou

git clone git://bebou.netlib.re/arthur.bebou
Log | Files | Refs |

index.sh (19986B)

 #! page
 title: Sed, substitutions et performances
 author: Arthur Pons
 description: Explorons les perfs de sed sur des gros fichiers
 publication: 2023-09-08
 sectionmd: main
 
 
 ## 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](https://fr.wikipedia.org/wiki/Text_Encoding_Initiative). 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](https://www.geonames.org/) 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)](./text.xml) et le fichier de correspondance
 [là (8Ko)](./corres).
 
 ## 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
 
 | Méthode | texte d'origine | très gros texte |
 |---------|-----------------|-----------------|
 | Un accès fichier par sub | 1,3s            | 2m10s           |
 | Parallélisation d'un accès fichier par sub | 0,5s | 1m42s |
 | Un seul accès fichier | 0,35s | 30s |
 | Parallélisation pour 4 accès fichier | 0,15s | 10s |
 
 ## 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[^1]. Du propre aveu de la
 personne l'ayant écrit, c'est peu fiable[^4]. 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[^2] 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
 
 
 | Méthode | texte d'origine | très gros texte |
 |---------|-----------------|-----------------|
 | Un accès fichier par sub | 17J            | 1140J           |
 | Parallélisation d'un accès fichier par sub | pas mesuré | pas mesuré |
 | Un seul accès fichier | pas mesuré | 366.6J |
 | Parallélisation pour 4 accès fichier | pas mesuré | 293J |
 
 ## 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[^3] (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](./sub.pl) et un [script python](./sub.py). Sur mon pc les
 perfs sont :
 
 | Méthode | texte d'origine | très gros texte |
 |---------|-----------------|-----------------|
 | script perl | 0,006s            | 0,4s           |
 | script python | 0,005s | 0,7s |
 
 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.
 
 [^1]: git clone git://bitreich.org/energy
 [^2]: #ubuntu
 [^3]: contrairement à la première tentative de parallélisation de notr solution naïve
 [^4]: Pour avoir comparé les valeurs avec un wattmètre branché sur une prise les valeurs sont étonamment justes. En tout cas les ordres de grandeur sont bons, ça nous suffit.