Optimisons!
De la théorie à la pratique
Mots-clés : Servist, DILIB, programmation, XML
Ces jours-ci, au boulot, nous avons une machine récente qui fait des statistiques depuis plusieurs jours (presque une semaine en fait).
En projetant le temps qu'elle mettrait, et, il faut le dire, en discutant avec un collègue, l'idée m'est venue qu'on pourrait optimiser le processus.
Cet article décrit le chemin que j'ai suivi (attention, c'est technique, et je n'ai pas encore tout relu).
Comme ces index sont des « fichiers » HFD, et qu'ils contiennent une liste inversée des identifiants de documents par terme, il est facile d'obtenir le nombre de termes, par exemple en comptant le nombre de lignes dans l'index.
En revanche, ce qui est plus long est de savoir combien de documents uniques sont présents dans chaque index, puisque chaque document peut correspondre à plusieurs termes du même index.
Il faut donc éditer une liste des documents (leur identifiant), et les dédoublonner.
Par défaut, le système Servist utilise cette série de commandes UNIX:
À notre surprise, l'index suivant (pourtant avec un nombre de termes moins élevé: 99) n'est pas fini en une semaine de calculs (sur une machine récente avec 2 Go de mémoire)...
En discutant avec un collègue, nous nous disons que le bât blesse peut-être dans la commande SgmlSelect, qui interprète le format XML, en faisant des allocations de mémoire (c'est un programme C) pour chaque élément XML. Or une ligne peut contenir plusieurs dizaines de millions d'éléments.
C'est décidé: on va essayer d'optimiser ça.
Aussitôt dit, aussitôt fait: au bout de deux petites heures de programmation C, une commande censée être plus rapide est créée.
Petit test sur un petit index (pour ne pas attendre des heures le résultat): 3 minutes. Pas mal.
Petite comparaison avec la méthode classique, utilisant les commandes UNIX: 2 secondes!
Gulps.
On m'aurait menti?
Le C ne serait pas plus rapide?
Ma machine à réfléchir se remet en marche (mieux vaut tard que jamais), et me signale que j'ai programmé en C, certes, mais en utilisant une bibliothèque censée simplifier la programmation, pas l'optimiser.
J'ai en particulier utilisé deux objets pratiques, certes, mais gourmands en mémoire en l'occurrence:
Quelques minutes plus tard, mon programme lex était prêt.
Même petit test sur les mêmes données: je n'avais gagné qu'une demi-seconde!
Argh!
Re-réflexion (je l'ai déjà dit, mais mieux vaut tard que jamais).
Bon. Ce ne peut être que le tableau associatif.
Évidemment, l'inconvénient, c'est que pour cent millions de documents, on occupe environ 100Mo en mémoire vive. Mais bah! Nous disposons de 2Go.
Re test.
Bingo!
0,04 secondes! Au lieu d'environ 3 secondes!
Test grandeur nature sur l'index qui avait mis 26 heures à se calculer:
Argh!
Le programme s'est planté? Au bout de quelques secondes il est arrêté.
Vérification.
Oh. Non. Il a fini. Et le résultat correspond!
En 27,742 secondes de processeur!
Un rapport de plus de 3000!
Vérification avec l'index en cours de calcul depuis plus de 6 jours: 15,873 secondes!
Oho.
Oui: le nombre de lignes de cet index est inférieur, donc les lignes sont plus longues (donc plus dures à traiter d'un seul coup, la machine swappe).
En une grosse demi-journée, nous avons gagné plusieurs semaines de calcul!
Ces jours-ci, au boulot, nous avons une machine récente qui fait des statistiques depuis plusieurs jours (presque une semaine en fait).
En projetant le temps qu'elle mettrait, et, il faut le dire, en discutant avec un collègue, l'idée m'est venue qu'on pourrait optimiser le processus.
Cet article décrit le chemin que j'ai suivi (attention, c'est technique, et je n'ai pas encore tout relu).
État actuel
Introduction
Tout d'abord, que fait ce programme? C'est le programme qui calcule la bibliométrie basique liée à un (gros) Servist (comme Amerigeo). Pour chaque champ (ou index), on calcule le nombre de termes découverts et le nombre de documents pointés par les termes de l'index. Ex:| Nom | Nb d'items | Nb docs |
| Auteur | 1464 | 1228 |
| Type | 2 | 1232 |
| Sous-type | 7 | 1232 |
| Année | 24 | 1230 |
| Périodique | 235 | 924 |
| Affiliation | 62 | 59 |
Comme ces index sont des « fichiers » HFD, et qu'ils contiennent une liste inversée des identifiants de documents par terme, il est facile d'obtenir le nombre de termes, par exemple en comptant le nombre de lignes dans l'index.
En revanche, ce qui est plus long est de savoir combien de documents uniques sont présents dans chaque index, puisque chaque document peut correspondre à plusieurs termes du même index.
Il faut donc éditer une liste des documents (leur identifiant), et les dédoublonner.
Par défaut, le système Servist utilise cette série de commandes UNIX:
DamCat $HFD | SgmlSelect -s idx/l/e# -p @s1 | sort -u | wc -l
Le DamCat permet de lire le fichier HFD concerné, et le SgmlSelect de sélectionner les éléments (e) de la liste (l) de l'item (idx) de l'index HFD.
Voici à quoi ressemble une telle ligne du HFD:
Voici à quoi ressemble une telle ligne du HFD:
<idx><kw>ARG</kw><lc>arg</lc><f>3</f><l><e>0000003777</e><e>0000003778</e><e>0000003779</e></e></l></idx>
Le SgmlSelect donne donc, pour cette ligne:
0000003777 0000003778 0000003779
Ensuite, on utilise sort -u pour trier ces données et les dédoublonner.
Enfin, le wc -l compte le nombre de lignes (donc d'identifiants de documents).
Constat
Malheureusement, sur l'énorme Servist que nous nous apprêtons à construire, il y a plusieurs millions de notices, et le calcul de cette simple statistique a pris 26 heures pour un index contenant 202 termes et indexant 13 millions de documents.À notre surprise, l'index suivant (pourtant avec un nombre de termes moins élevé: 99) n'est pas fini en une semaine de calculs (sur une machine récente avec 2 Go de mémoire)...
En discutant avec un collègue, nous nous disons que le bât blesse peut-être dans la commande SgmlSelect, qui interprète le format XML, en faisant des allocations de mémoire (c'est un programme C) pour chaque élément XML. Or une ligne peut contenir plusieurs dizaines de millions d'éléments.
C'est décidé: on va essayer d'optimiser ça.
Optimisation simple
Le plus simple quand on veut optimiser une suite de commandes dont une interprète le XML de manière générique (sans tenir compte de sa DTD), et que la DTD du XML est fixe et connue, c'est de remplacer le traitement du XML par du traitement de chaînes de caractères simple.Aussitôt dit, aussitôt fait: au bout de deux petites heures de programmation C, une commande censée être plus rapide est créée.
Petit test sur un petit index (pour ne pas attendre des heures le résultat): 3 minutes. Pas mal.
Petite comparaison avec la méthode classique, utilisant les commandes UNIX: 2 secondes!
Gulps.
On m'aurait menti?
Le C ne serait pas plus rapide?
Ma machine à réfléchir se remet en marche (mieux vaut tard que jamais), et me signale que j'ai programmé en C, certes, mais en utilisant une bibliothèque censée simplifier la programmation, pas l'optimiser.
J'ai en particulier utilisé deux objets pratiques, certes, mais gourmands en mémoire en l'occurrence:
- un objet de gestion de chaînes de caractères de taille variable (appelée Buffer),
- un tableau associatif (appelé StrSearch).
Optimisation poussée
En effet, des lignes de plusieurs millions de caractères sont un poids à traiter. Je me dis donc que je vais traiter l'entrée standard caractère par caractère, et que donc un petit programme lex serait le bienvenu.Quelques minutes plus tard, mon programme lex était prêt.
Même petit test sur les mêmes données: je n'avais gagné qu'une demi-seconde!
Argh!
Re-réflexion (je l'ai déjà dit, mais mieux vaut tard que jamais).
Bon. Ce ne peut être que le tableau associatif.
Vraie optimisation
Je vais donc me passer du tableau associatif, et déclarer un tableau statique suffisamment grand (au moins le nombre de documents), et l'initialiser à zéro, et à chaque fois que je rencontre un numéro de document, j'y associe une valeur dans le tableau. Si cette valeur était nulle, j'ajoute un à un compteur.Évidemment, l'inconvénient, c'est que pour cent millions de documents, on occupe environ 100Mo en mémoire vive. Mais bah! Nous disposons de 2Go.
Re test.
Bingo!
0,04 secondes! Au lieu d'environ 3 secondes!
Test grandeur nature sur l'index qui avait mis 26 heures à se calculer:
Argh!
Le programme s'est planté? Au bout de quelques secondes il est arrêté.
Vérification.
Oh. Non. Il a fini. Et le résultat correspond!
En 27,742 secondes de processeur!
Un rapport de plus de 3000!
Vérification avec l'index en cours de calcul depuis plus de 6 jours: 15,873 secondes!
Oho.
Oui: le nombre de lignes de cet index est inférieur, donc les lignes sont plus longues (donc plus dures à traiter d'un seul coup, la machine swappe).
Conclusion
L'optimisation pour gagner un micropoil de seconde n'est pas très utile, mais pour un facteur d'accélération de plus de 32000, ça vaut le coup!En une grosse demi-journée, nous avons gagné plusieurs semaines de calcul!
Partagez cet article!
Par H_I
|
| 06/11/2007 18:38
| Boulot
|
aucun commentaire
| 