étant dans la réalisation d'un programme qui doit analyser un ou plusieurs fichiers, je me demandais comment faire pour optimiser la vitesse de traitement. En effet, certains fichiers peuvent contenir quelques lignes, et d'autres s’étendre sur plusieurs KO. Le tout assemblé, on peut obtenir des gigas octets de donnée. J'ai peur que mon analyse s'étire sur plusieurs minutes en fait, et je me demandais alors comment les compilateurs faisant pour justement optimiser la vitesse de lecture des fichiers. En effet, ils analysent toutes les bibliothèques importées, puis notre code, et ce, en quelque millisecondes à peine.
J'utilise, pour lire le fichier, std::ifstream. Mais j'ai lu que, pour optimiser la vitesse de lecture, les fluxes n'étaient pas la meilleur solution, et qu'il fallait ce rabattre sur les fonctions C. Sauf que j'en ai vraiment pas envie.
J'ai fait un petit teste en analysant tout le code HTML de la page d'accueille de Google (226 014 octets → 226 KO). Mon lexer a parcouru et tokenizé ce gros fichier en 52 secondes. J'ai l'impression que c'est énorme... Et le programme n'avait même pas encore analyser, donc j'estime que pour un tel fichier, cela aurait pris environs 60-70 secondes (en comptant le temps de retranscription du fichier analysé). N'y aurait-il pas un moyen d'optimiser la vitesse de lecture ?
En gros, on peux estimer les temps suivants : trouver le fichier ~ moins de 2 * temps d'accès disque ~ <9ms (c'est très lent, correspond à environ 10 millions d'instructions perdues) Lire le fichier ~ débit moyen disque pour un petit fichier ~ 226000/4M = 6ms Transfert de la mémoire vive vers le cache : 226000/16*7ns = 0,1ms Temps d'analyse ~ le reste ~ 52s - 15,5ms ~ 52s Pour analyser chaque octet de ton fichier, il te faut : 52s / 226000 = 0,2ms En 0,2ms on effectue environ 0,0002*1G = 230000 instructions / octet Je me demande en quoi consiste ton analyse.
Mais, soit vous n'avez pas tout lu, soit je n'ai pas été claire, mais ce qui prend 52 secondes, ce n'est pas le temps pris pour simplement lire le fichier, c'est le temps qu'il lui faut pour parcourir chaque lexèmes du fichier. Par exemple ça :
if (2 < 5) {
print("ok")
}
Ce texte sera "tokenizé" à chaque appel de la fonction qui renvois le prochain lexème :
if
(
2
<
5
)
{
print
(
"ok"
)
}
Et (ca je ne l'avais pas précisé), chaque lexème se voit attribué une catégorie ainsi que l'information de sa position actuelle dans le fichier.
Je l'avait précisé ici :
Geralt de Riv avait écrit:
... mon lexer a parcouru et tokenizé ce gros fichier en 52 secondes ...
Ce qui sous entends donc un lexing, et je conçois que cela puisse prendre un peu plus de temps que de simplement lire le fichier.
Et ce schéma est le même pour chaque jeton renvoyé par la fonction du lexer.
PS: Je pense comprendre @Daflab, je parles depuis le début du code source de la page d'accueil de Google (226 KO), ce petit code que j'ai posé à titre d'exemple est parcouru / tokenizé en 0.038s par mon programme. Je dis ça, mais on ne sais jamais qu'il y ait une confusion
Il faudrait changer le titre par "Optimiser mon lexer", parce que normalement lexer sans fout de savoir que cela vient d'une chaîne de caractère ou d'un fichier.
Il faut donc trouver les fonctions qui prennent du temps. Heaptrack, valgrind, perf sont des outils Linux qui peuvent aider. Il y a aussi des équivalents sur Windows.
Mais sans information sur le code je dirais qu'il y a des copies inutiles et des constructions répétées d'objets constants (je pense notamment au regex puisque tu n'utilises que ça si je ne me trompe pas.)
Il faut en effet commencer par "profiler" des exécutions du programme pour savoir où passe tout ce temps de calcul.
Essayer de le faire "au feeling" ca fait partie (comme l'estimation des probabilités au pif) des choses pour lesquelles nous autres bipèdes sommes extrêmement incompétents. Trop de biais psychologiques. Du coup on va optimiser un truc qui nous paraît super important et qui en fait correspond à 3% si on mesure vraiment.
> Peux-être le profiler de performance de Visual Studio suffirait ?
Oui
> C'est une règle chez moi : n'utiliser les RegEx qu'en dernier recourt :
>
> 1) Trop lent ;
> 2) Occupe beaucoup de place dans l'exécutable (ce n'est pas le plus important, mais c'est beaucoup de place pour pas grand chose) ;
> 3) Énervant à utiliser ;
> 4) Difficilement maintenable.
1) ce n'est pas toujours le cas. Une regex peut créer un automate fini et déterministe qui est extrêmement complexe à faire à la main sans rendre le code incompréhensible.
2) On peut faire des regex compile-time. Le seul projet que j'ai en tête (sre) ne construit pas de DFA, ce qui n'est pas forcement gênant.
3) et 4) Il y a des projets de regex expressive qui passe par l'utilisation de fonction pour la construire (Char('a').OneOrMore()). sre le fait aussi à ça manière.
Une regex est un langage à part entière qui se veut concis. Pour un lexer, je ne pense pas qu'il y a grande difficultés à en lire. La même chose fait à la main avec des boucles n'est à mon avis pas plus lisible. J'ai déjà écrit des regex de plusieurs centaines de caractères et je n'imagine pas l'horreur que cela donne avec des boucles et des conditions à la pelle.
Après, je ne dis pas que les regex sont à utiliser partout. Mais faire un parseur à la main n'est pas plus efficace. Des trucs fait avec boost.x3 ou boost.metaparse sont beaucoup plus faciles à maintenir, à lire et à utiliser en plus d'être performants.
Mais, soit vous n'avez pas tout lu, soit je n'ai pas été claire, mais ce qui prend 52 secondes, ce n'est pas le temps pris pour simplement lire le fichier, c'est le temps qu'il lui faut pour parcourir chaque lexèmes du fichier.
J'avais surtout bien compris que tu melangeais le temps de lecture du fichier (ie lire les infos sur le disque pour les mettre dans la memoire vive) et le temps d'interpretation des donnees. Ta question initiale concernait le temps de lecture. L'optimisation de chacune de ces 2 parties est completement different.
Comme tes fichiers ne sont pas trop gros, tu peux les lire en une seule fois. Donc ton code doit ressembler a ca (voire doit etre exactement ca) :
const auto file = openFile(name);
const auto content = file.readAll();
const auto ast = parse(content);
Et donc tu peux mesurer tres facilement le temps de lecture et le temps de traitement separement.
Et si tu generes une sortie, cela doit etre fait egalement dans une fonction differentes. (Dit autrement, quand tu mesures le temps de la fonction "parse", il ne doit y avoir aucun "std::cout" dedans)
Je fais quelque chose d'equivalent en python, avec des regex, pour lire des AST dump files generes par Clang. Ce sont des fichiers de plusieurs centaines de milliers de lignes et plusieurs Mo. Et ca me prend entre 1 et 2 secondes par fichier. (Je ne parse pas tout).
52 secondes, c'est enorme. Tu n'as pas de github pour montrer le code ?
Comme tes fichiers ne sont pas trop gros, tu peux les lire en une seule fois. Donc ton code doit ressembler a ca (voire doit etre exactement ca) :
const auto file = openFile(name);
const auto content = file.readAll();
const auto ast = parse(content);
A part que ce n'est pas const, cela ressemble effectivement à cela :
Lexer lexer(filename); // on initialise le lexer
Parser parser(lexer); // dans le parser, nous itérons à chaque jetons lu et envoyée en temps réel par le lexer pour tisser l'ast.
EDIT:
J'ai compris pourquoi cela prenait tant de temps !
Je n'y avait pas fait attention, mais dans mon code, il y a une instruction stupide qui fait de la récursion répétitive à chaque fois que le lexer rencontre un certain jeton.
Et ca prend donc plus de temps puisqu'il fait autant de fois le travail qu'il n'y a alors présence de ce jeton (CTRL+F donne 5.000 résultats)...
Evidemment, il ne met plus que 8 secondes maintenant (c'est encore beaucoup, mais cela vient du fichier que j'ai utilisé pour mon teste qui n'a en plus pas le bon format, dans de vrais projets, ce temps devrait être nettement amoindris).
Je me demande si je suis le seule à mettre des instructions inutiles comme ça moi...
En tout cas, merci beaucoup à vous ! Vous m'avez aidez plus que vous ne le pensez.
Optimisation de la vitesse de traitement dun lexer
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Discord NaN. Mon site.
Discord NaN. Mon site.
En recherche d'emploi.
En recherche d'emploi.
Discord NaN. Mon site.
Discord NaN. Mon site.