je voudrais comprendre à quoi sert l'AST généré par Clang :
int add(int a, int b) {
return a + b;
}
génère cet AST :
TranslationUnitDecl
`-FunctionDecl <line:1:1, line:3:1> line:1:5 add 'int (int, int)'
|-ParmVarDecl <col:9, col:13> col:13 used a 'int'
|-ParmVarDecl <col:16, col:20> col:20 used b 'int'
`-CompoundStmt <col:23, line:3:1>
`-ReturnStmt <line:2:5, col:16>
`-BinaryOperator <col:12, col:16> 'int' '+'
|-ImplicitCastExpr <col:12> 'int' <LValueToRValue>
| `-DeclRefExpr <col:12> 'int' lvalue ParmVar 0x4fcbbf0 'a' 'int'
`-ImplicitCastExpr <col:16> 'int' <LValueToRValue>
`-DeclRefExpr <col:16> 'int' lvalue ParmVar 0x4fcbc60 'b' 'int'
Voici mes quelques questions :
Est-ce que c'est avec ça que le compilateur analyse la syntaxe et génère un code assembleur correspondant ?
Est-ce que ce format d'arbre syntaxique abstrait est commun (la manière dont il est présenté, ...) à la plupart des compilateurs ?
Est-ce que Clang génère ce fichier d'AST pour ensuite compiler le programme, ou ce fichier n'est qu'une représentation de ce qu'il se passe à l'intérieur du programme durant la compilation et que Clang fournir en "bonus" ?
Que signifie "TranslationUnitDecl" au début ?
Est-ce qu'un AST peux contenir les erreurs du programme (syntaxe, sémantique, ...) s'il est analysé par la suite ?
Je vous remercie d'avance, répondre à ces questions me permettraient de mettre davantage à bien mon projet !
Est-ce que c'est avec ça que le compilateur analyse la syntaxe et génère un code assembleur correspondant ?
La génération de l'AST est effectivement l'une des étapes de la compilation.
Geralt de Riv a écrit:
Est-ce que ce format d'arbre syntaxique abstrait est commun (la manière dont il est présenté, ...) à la plupart des compilateurs ?
L'utilisation d'un AST est classique pour l'analyse d'un langage. Mais tous les compilateurs (et plus généralement interpréteurs) n'utilisent pas le même. (Par contre, il me semble que l'AST de Clang est utilisé par les différents langages supportés par LLVM. C'est a dire que tous les langages supportés génèrent le même AST, et ensuite il y a un seul "générateur d'assembleur" qui transforme les AST en assembleur. A vérifier).
Geralt de Riv a écrit:
Est-ce que Clang génère ce fichier d'AST pour ensuite compiler le programme, ou ce fichier n'est qu'une représentation de ce qu'il se passe à l'intérieur du programme durant la compilation et que Clang fournir en "bonus" ?
Clang n'utilise pas ce fichier AST. L'AST est en fait une structure en C++ assez complexe de classes avec héritages. Ce que tu affiches est en fait la version texte de cet arbre. Mais il n'est pas utilisé directement par Clang.
Un aperçu du début cette hiérarchie de classes :
Geralt de Riv a écrit:
Que signifie "TranslationUnitDecl" au début ?
Le "translation unit" est le fichier qui sert de point de départ de la compilation. C'est le ".cpp" que tu indiques dans la ligne de commande "clang toto.cpp" et qui produira un fichier objet ".o". Cf :
Le "TranslationUnitDecl" est la classe qui represente la declaration ("Decl") de cet "translation unit". C'est le contexte globale de base, ce qui correspond a l'espace de noms general ("::").
Geralt de Riv a écrit:
Est-ce qu'un AST peux contenir les erreurs du programme (syntaxe, sémantique, ...) s'il est analysé par la suite ?
En complément, on peut essayer d'expliquer que AST est l'abréviation de Abstract Syntax Tree. La traduction littérale de ces termes est Arbre Abstrait de syntaxe.
On se rend alors compte que chaque terme est important:
le terme syntaxe indique que l'on analyse quelque chose pour s'assurer que cela correspond à "ce à quoi on peut s'attendre". Ce "quelque chose" correspond au code que le développeur aura écrit, et qui doit correspondre ... à ce à quoi le compilateur (ou l'interpréteur) s'attend.
Le terme arbre nous indique la manière dont les différents éléments de syntaxe seront organisés entre eux: il y aura généralement un "élément racine", qui servira de "point d'entrée" à l'analyse, et chaque élément peut éventuellement contenir d'autres éléments.
Les éléments qui contiennent d'autres éléments seront appelés "noeuds" et ceux qui n'en contiennent pas seront appelés "feuilles".
Enfin, le terme abstrait nous indique que, dans un premier temps, nous n'allons pas essayer de "donner un sens particulier" aux différents éléments de syntaxe: nous voulons dans un premier temps seulement être en mesure de représenter les différents termes, les différents "mots" que le code que l'on est occupé à analyser peut contenir.
L'idée derrière ce terme de Abstract Syntax Tree est donc que l'on va -- dans un premier temps -- se contenter de créer une "représentation de la syntaxe" du code que l'on analyse, sans essayer de lui donner de sens particulier.
L'obtention de cette représentation correspond à la première étape, indispensable à tous les traitements que nous pourrons envisager de faire subir au code par la suite, car tous les traitements que nous pouvons envisager ont besoin de cette représentation.
L'un des premiers traitements que nous pourrons envisager de cette représentation est -- bien sur -- de s'assurer que "chaque élément est à sa place", que la syntaxe utilisée dans le code respecte les règles de grammaires propres au langage considéré.
Ainsi, si la grammaire prévois que l'on va définir une variable en respectant l'ordre <cvQualifier_optionnel> <type de donnée> <cvQualifier_optionnel><pointeur_ou_reference_optionel><identifiant><asignation_optionnelle><end_of_statement>, nous pourrons vérifier que la syntaxe que l'on a récupérée à partir du code respecte -- effectivement -- cette forme.
Par la suite, nous pourrons modifier cet AST pour apporter certaines optimisations, selon les réglages qui ont été imposés. Et, enfin, cet AST sera -- effectivement -- utilisé pour générer le code assembleur correspondant
La plupart des compilateurs utilisent cette notion d'AST pour faire leur job. Mais la hiérarchie de classes utilisée pour représenter cet AST, les données qui sont déduites à partir du code, et les différents traitements qui seront effectués sur cet AST seront clairement spécifiques au compilateurs.
Quant à la représentation "finale" que tu obtiens, elle correspond à la manière spécifique envisagée par clang pour t'en donner une représentation "écrite". Mais nous pourrions générer des document au format *.tex ou au format .dot afin de créer une représentation "plus graphique" de l'AST.
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
En fait, je voudrais savoir comment en générer un pour un langage plus complexe qu'une simple expression mathématique... Parce que ça :
4 * (7 + 3) →
*
/ \
4 +
/ \
7 3
C'est bien joli, mais si on ne va pas plus loin, ca devient lassent, et que j'aimerai bien passé à autre chose de plus "gratifiant"...
J'ai déjà réaliser un tokenizer, il fonctionne à merveille; mais l'étape suivante s'avère nettement plus complexe; et malgré mes quelques tentations d'implémentation d'AST pour une syntaxe C-like, je n'ai toujours aucuns résultats. L'étude de la conception du générateur d'AST de Clang pourrait m'être utile. Je sais ce que vous allez dire : pourquoi ne pas justement utiliser LLVM ou ANTLR ? Et bien simplement parce qu'après avoir utiliser ces outils, je ne saurai toujours pas comment réaliser un parser qui puisse générer un AST Je ne dit pas que ce sont des outils inutiles, mais j'aimerai bien savoir comment sa fonctionne afin d'en réaliser un.
gbdivers a écrit:
Clang n'utilise pas ce fichier AST. L'AST est en fait une structure en C++ assez complexe de classes avec héritages. Ce que tu affiches est en fait la version texte de cet arbre. Mais il n'est pas utilisé directement par Clang.
D'accord, je comprends mieux, et cela paraît même plus logique. Mais, à quoi ressemble cette structure assez complexe en C++ ?
gbdivers a écrit:
Geralt de Riv a écrit:
Est-ce qu'un AST peux contenir les erreurs du programme (syntaxe, sémantique, ...) s'il est analysé par la suite ?
Oui.
Donc l'AST est générer par le parser, puis ensuite analyser, et ensuite optimisé pour enfin générer un code correspondant :
Mais qu'elles sont les optimisations qui peuvent être apportées à l'arbre ? Et comment le compilateur sait-il ce qui doit être optimisé, mise à part les codes morts et variables inutilisées ?
koala01 a écrit:
Mais nous pourrions générer des document au format *.tex ou au format .dot afin de créer une représentation "plus graphique" de l'AST.
Et à quoi est-ce que ça ressemblerait pour un expression tel qu'elle :
int add(int a, int b) {
return a + b;
}
?
Auriez-vous d'ailleurs des liens qui puissent m'aider dans la conception d'un parser/AST par hazard ? La plupart que j'ai trouvé ne parlaient que de parser des expressions mathématiques, ou utilisaient un générateur de parser, ou étaient écrits en ML-like.
Je vous remercie, je vois déjà mieux dans quel direction allée !
Et à quoi est-ce que ça ressemblerait pour un expression tel qu'elle :
int add(int a, int b) {
return a + b;
}
Ben sans doute à quelque chose de très proche de ce que tu as fait pour ton expression mathématique:
command_block
/ \
function_decl function_impl
| / \
function_name=add return_stm math_expresion
/ \ |
return_type parameters operator '+'
| | / \
name "int" separator ',' Var_value var_value
/ \ | |
param_decl param_decl "a" "b"
/ \ / \
type_decl name "a" type_decl name "b"
| |
name "int" name "int"
(l'ASCII art ne rend pas les choses très claires, désolé )
Bien sur, en générant de vrais graphiques (à l'aide de LaTex ou de dot), cela pourrait faire une "zolie image"
- Edité par koala01 17 août 2018 à 19:25:32
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Donc, si je comprends bien, sur ce schéma, chaque noeud est la directive de description de la feuille (en vert) qui va suivre ?
Oui, tout à fait...
D'ailleurs, si tu observe correctement ton graphe, tu te rend compte que tout ce qui apparaît en vert (toutes les feuilles de ton graphe ) décrivent exactement ce que ton code indique et que les parties manquantes (comme "add", "," ou "+") sont "forcément" fournies par les noeuds auxquels les feuilles sont rattachées
Si on adapte un tout petit peu ce graphe pour nous assurer d'utiliser l'équivalent d'un arbre binaire, ce qui lui donnerait la forme de
command_block
/ \
function_decl function_impl
/ \ / \
function_name=add nulmptr return_stm math_expresion
/ \ / \
return_type parameters operator '+' nullptr
/ \ / \ / \
name "int" nullptr / nullptr Var_value var_value
separator ',' / \ / \
/ \ "a" nullptr "b" nullptr
param_decl param_decl
/ \ / \
type_decl name "a" type_decl name "b"
/ \ / \
name "int" nullptr name "int" nullptr
(désolé, c'est encore moins clair, du coup)
on se rend compte que l'analyse peut se faire de manière récursive sous une forme sans doute proche de
et que cette logique parcourrait les différents termes qui ont été extrait à partir du code exactement dans l'ordre dans lequel ils apparaissaient dans le code
Nota: on appelle ce type de parcours, dans lequel on analyse d'abord un noeud enfant s'il existe avant de traiter le noeud courant et de terminer en traitant l'autre noeud enfant s'il existe un parcour infixe
On peut envisager d'autres parcours, comme le parcours dit prefixe, qui s'intéresse d'abord au noeud courant, avant de s'intéreser aux deux noeuds enfants s'ils existe, ou le parcours postfixe, qui s'intéresse d'abord aux deux noeuds enfants (s'ils existent) avant de s'intéresser au noeud courant
- Edité par koala01 17 août 2018 à 20:13:49
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Mais, à quoi ressemble cette structure assez complexe en C++ ?
Pardon, je me suis mal exprimé.
C'est de la hiérarchie de classes de clang qui est complexe. C'est le screenshot que j'ai donné (que le début).
L'AST interne utilisé par Clang a la même structure que ce que tu obtiens avec -ast-dump. Les noms qui apparaissent sont en fait le nom des classes de Clang. Par exemple :
Chaque classe contient les informations correspondantes. Par exemple FunctionDecl contient parameters() pour avoir la liste des paramètres, isConstexpr () pour savoir si la fonction est déclarée constexpr, etc.
C'est un peu le bordel, puisqu'il y a des centaines de classes, et chaque classes possède des centaines de fonctions.
Je n'ai jamais trop regardé comment Clang parse un fichier. Je n'ai utilisé que Clang après la génération de l'AST (C'est assez simple, cela utilise des pattern Visitor). Ca doit etre dans http://clang.llvm.org/doxygen/group__CINDEX.html en particulier dans les modules "Name Mangling API Functions" (interprétation des noms de fonctions), "Token extraction and manipulation" (interprétation des mots clés), les différents modules de "manipulation".
Mais tu te doutes bien qu'un parser comme Clang pour le C++ est beaucoup plus complexe qu'un parser pour une expression mathématique.
Geralt de Riv a écrit:
Mais qu'elles sont les optimisations qui peuvent être apportées à l'arbre ? Et comment le compilateur sait-il ce qui doit être optimisé, mise à part les codes morts et variables inutilisées ?
Tu parles de plusieurs centaines d'optimisation faites par Clang, a pleins de niveaux différents. Certaines sont très simple (par exemple voir que le code contient l'expression "2 + 3" et remplacer par "5") d'autres sont très complexes (analyse sémantique sur plusieurs niveau).
Honnêtement, cela sort de mes compétences. Je n'ai jamais travaillé sur un compilateur. Ni sur l'analyse syntaxe, ni sur la génération du code. J'utilise l'AST de Clang pour écrire des règles de validation statique du code dans clang-tidy. Il faut que tu lises un cours sur les compilateurs. Et sur l'architecture des ordinateurs et sur l'architecture des systèmes d'exploitation. C'est un domaine à part entière d'écrire des compilateurs. (Et ce n'est pas mon domaine).
Par contre, je pense que l'arbre en lui même n'est pas modifié par l'optimisation. Cet arbre a pour rôle de simplement représenter ce que le code contient. Il est fort possible que Clang utilise d'autres arbres pour les autres étapes de la compilation, qui eux seront optimisés.
Merci pour ces réponses complètes et détaillées, et aussi pour tes liens gbdivers ! Je sens que je vais avoir beaucoup de lecture moi...
Pour résumer, l'AST généré par Clang que l'on peut manipuler (donc le .txt), est juste la représentation du chemin que suit le programme dans son propre code suivant le texte à analyser. S'il passe dans la classe "VarDecl" de l'espace de nom "Declaration", il va l'indiquer en tant que sous-nœud. Nœud ayant comme enfants les spécifications de la déclaration de variables (si on reprend l'exemple). Et chaque feuilles est donc une donnée provenant donc directement du fichier texte analysé.
Prenons ce code (ML-like ou Rust, c'est comme vous voulez) :
let foo: int = 8 + 2;
Si j'arrive à générer un AST correspondant :
Est-ce que ce sera bon ? Ou il faudrait ajouter / enlever / modifier certaines choses ?
koala01 a écrit:
on se rend compte que l'analyse peut se faire de manière récursive sous une forme sans doute proche de ...
Donc, pour commencer, une simple structure comme ça suffirait-elle :
Ou il faut "frapper plus fort" ? J'imagine que oui. Puisque gbdivers avait dit qu'il y avait plusieurs classes et une certaine hiérarchie. Auriez-vous, dans ce cas, un autre format à suggéré que celui-ci ?
Nous sommes typiquement dans le cadre d'une hiérarchie de classes, avec toutes les chances d'avoir de l'héritage et du polymorphisme à gogo...
Une approche permettant le double dispatch (hein? qui parle du patron de conception visiteur (*) ) et mettant en place la sémantique d'entité semble donc plus proche de la réalité:
/* La notion de noeud : classe de base abstraite
* dont dériveront toutes les autres
*/
class Node{
public:
/* juste par facilité */
using NodePtr = std::unique_ptr<Node>;
Node(Node const &) = delete;
Node & operator=(Node const &) = delete;
Node() = default;
virtual ~Node() = default;
virtual void accept(Visitor const & v) = 0;
virtual void analyze(Visitor const & v) = 0;
virtual Node & inserLeft(NodePTr && newLeft) = 0;
virtual Node & insertRight(NodePtr && newRight) = 0;
virtual Node const & leftNode() const = 0;
virtual Node const & rightNode() const = 0;
/* Ajout de la "forme canonique" du patron visiteur
* sous une forme constante
*/
virtual void accept(ConstVisitor & ) const = 0;
};
/* trois grands cas possibles : les feuilles (qui n'ont
* jamais de noeud enfants et les "binary nodes"
* qui ont jusqu'à maximum deux noeuds enfants
* car un arbre binaire est amplement suffisant
* pour satisfaire n'importe quel besoin
* et les "unary node", qui n'ont jamais qu'un seul enfant
*/
class BinaryNode : public Node{
public:
void analyze(Visitor & v) final override{
if(left_)
left_.get()->analyze(v);
doAccept(v);
if(right_)
right_.get()->analyze(v);
}
/* on renvoie une référence vers le noeud enfan pour pouvoir
* travailler avec lui (y ajouter des enfants, principalement)
*/
Node & inserLeft(NodePTr newLeft) override{
assert(left_ == nullptr && "Left node already defined");
left_.reset(newLeft.release());
return *(left_.get());
}
Node & insertRight(NodePtr newRight) override{
assert(right_ == nullptr && "Right node already defined");
right_.reset(newRight.release());
return *(right_.get());
}
Node const & leftNode() const final override{
assert(left_!= nullptr && "left node undefined");
return *(left_.get());
}
Node const & rightNode() const final override{
assert(right_!= nullptr && "left node undefined");
return *(right_.get());
}
private:
virtual void doAccept(Visitor & v) = 0;
NodePtr left_;
NodePtr right_;
};
/* Ce qui ne pourra être que des feuilles */
class Leaf : public Node{
void analyze(Visitor const & v){
doAccept(v);
}
Node & inserLeft(NodePTr newLeft) override{
assert(false && "No left child allowed");
}
Node & insertRight(NodePtr newRight) override{
assert(false && "No right child allowed");
}
Node const & leftNode() const final override{
assert(false && "No left child allowed");
}
Node const & rightNode() const final override{
assert(false && "No right child allowed");
}
private:
virtual void doAccept(Visitor & v) = 0;
};
class UnaryNode : public Node{
public:
void analyze(Visitor & v) final override{
if(left_)
left_.get()->analyze(v);
doAccept(v);
}
Node & inserLeft(NodePTr newLeft) override{
assert(left_ == nullptr && "Left node already defined");
left_.reset(newLeft.release());
return *(left_.get());
}
Node & insertRight(NodePtr newRight) override{
assert(false && "No right child allowed");
}
Node const & leftNode() const final override{
assert(left_!= nullptr && "left node undefined");
return *(left_.get());
}
Node const & rightNode() const final override{
assert(false && "No right child allowed");
}
private:
virtual void doAccept(Visitor & v) = 0;
NodePtr left_;
};
qui nous offre deux classes abstraites "de base" pour traiter le reste.
Et, bien sur, nous aurions la notion de "visiteur" (*). Il est plus que vraisemblable qu'elle sera implémentée sous la forme d'une machine à états et, même si on ne sait pas encore trop bien ce que nous ferons dans les différents visiteurs, nous pouvons plus ou moins prévoir de lui donner une forme proche de
class Visitor{
public:
virtual void visit(CompileUnit &) = 0;
virtual void visit(Identifier &) = 0;
virtual void visit(EndOfStatement &) = 0;
virtual void visit(ParenthesisOperator &) = 0;
virtual void visit(ComaOperator &) = 0;
virtual void visit(CodeContent &) = 0;
/*... et pour toutes les autres classes, on fera pareil */
protected:
Visitor() = default;
Visitor(Visitor const &) = delete;
Visitor & operator = (Visitor const &) = delete;
~Visitor() = default:
};
/* Et un autre visiteur qui manipule les noeud sous forme
* constante
*/
class ConstVisitor{
public:
virtual void visit(CompileUnit const &) = 0;
virtual void visit(Identifier const &) = 0;
virtual void visit(EndOfStatement const &) = 0;
virtual void visit(ParenthesisOperator const &) = 0;
virtual void visit(ComaOperator const &) = 0;
virtual void visit(CodeContent const &) = 0;
/*... et pour toutes les autres classes, on fera pareil */
protected:
Visitor() = default;
Visitor(Visitor const &) = delete;
Visitor & operator = (Visitor const &) = delete;
~Visitor() = default:
};
afin de pouvoir créer une classe dérivée de Visitor pour chaque besoin de parcours de notre AST que nous pourrons envisager par la suite
/* un identifiant : tout ce qui permet d'identifier "quelque
* chose" par un nom qui lui est propre
*
*/
class Identifier : public Leaf{
public:
Identifier(std::string name):name_{name}{
}
/* fonction spécifique à un identifiant : */
std::string const & name() const{
return name;
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
std::string name_;
};
/* La fin d'instruction */
class EndOfStatement : public Leaf{
public:
EndOfStatement();
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
};
/* Les valeurs littérale, qui peuvent être de n'importe quel
* type primitif, ou du type "chaine de caractères"
*/
template
class LitteralValue : public Leaf{
public:
static_assert(std::is_arithmetic::value ||
std::is_same::value ||
std::is_same::value,
"litteral values should be arithmeics or strings");
LitteralValue(T value):value_{value}{
}
T const & value() const{
return value_;
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
T value_;
};
/* la notion d'unité de compilation :
* Le noeud de gauche contiendra l'identifiant de cette
* unité de compilation (le nom du fichier, par exemple :D)
* le noeud de droite contiendra le contenu du fichier
*/
class CompileUnit : public BinaryNode{
public:
CompileUnit(std::string const & filename){
insertLeft(std::make_unique<Identifier>(filename);
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
};
/* la notion de "code contenu", sans vraiment d'autres précision...
* A priori, il n'y a qu'un seul enfant ici...
*/
class CodeContent : public Unary{
public:
Node & insertRight(NodePtr && newRight){
assert(false && "cannot have a right child");
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
}
Puis nous pourrons avoir les différents opérateurs :
/* l'opérateur () n'a qu'un seul noeud de type "CodeContent"
*
class ParenthesisOperator : public UnaryNode{
public:
Node & insertRight(NodePtr && newRight){
assert(false && "cannot have a right child");
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
};
/* l'operateur virgule est un binary node : le noeud de gauche
* représente "ce qui précède", le noeud de droite représente
* ce qui suit"
*/
class ComaOperator : public BinaryNode{
public:
Node & insertRight(NodePtr && newRight){
assert(false && "cannot have a right child");
}
void accept(ConstVisitor & v) const final override{
v.visit(*this);
}
private:
void doAccept(Visitor & v) final override{
v.visit(*this);
}
};
Alors, bien sur, nous pourrions avoir les opérateurs mathématiques, les opérateur booléens, et un tas de classes qui permettent de décrire clairement l'objectif poursuivi par les différents "token" que l'on peut retrouver dans le code. Dans chacun des cas, nous créerons sans doute une classe qui hérite -- par facilité -- d'une de nos trois classes principale (BinaryNode, UnaryNode ou Leaf) et qui serait adaptée à notre beoin
Et, bien sur, pour chaque classe que nous pourorns créer, nous aurons une fonction visit(LaClasseEnQuestion &) équivalente dans notre classe visiteur (*)
(*) C'est là que nous nous rendons compte de la limite du patron de conception visiteur, car nous risquons de nous retrouver avec plusieurs centaines de classes dérivées de Node (ou plus vraisemblablement de BinaryNode / UnariNode / Leaf), et donc, avec plusieurs centaines de surcharge pour la fonction visit() .
Mais, mis à part ce nombre de surcharge important, le patron de conception visteur reste tout à fait valable
- Edité par koala01 18 août 2018 à 15:48:58
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Je ne m’attendais pas du tout à une réponse aussi complète, détaillée, et exemplifiée. Je comprends nettement mieux comment ca se passe là dedans ! Et j'espère arriver à des résultats plus concluant que ma ridicule petite structure *Node* cette fois !
Je te suis vraiment reconnaissant
Les AST n'ont désormais plus de secret pour moi
Quoique...
koala01 a écrit:
hein? qui parle du patron de conception visiteur
J'en entends en effet souvent parler du visiteur de conception, mais c'est quoi exactement ? Ca sert à s'assurer de la façon dont l'AST se conçoit ? Ou à ce positionner quelque part ? Ou simplement à lire les données ?
Je me demande également à quel moment de la conception de l'AST, Clang (pour avoir un exemple de compilateur) génère t-il son AST *.txt ?
Je me demande aussi de quel façon est ensuite analyser l'arbre ? Avec le visiteur ?
J'espère que ce ne vous dérange pas que je vous pose encore ces quelques questions
J'en entends en effet souvent parler du visiteur de conception, mais c'est quoi exactement ?
Le patron de conception visiteur est une des (plus anciennes) solutions qui te permet de mettre en place un double dispatch lorsque tu manipules une hiérarchie de classes:
est une véritable aberration!. Mais, il n'empêche qu'il arrive très souvent que tu veuilles profiter de toutes les fonctions spécifiques au type réel (dérivé) d'un objet alors que tu ne le connaît que comme étant du type de base.
L'idée est donc de travailler en deux temps en te permettant de faire appel à un comportement polymorphe (exposé par le type de base) qui fera appel à une "deuxième fonction" s'attendant à recevoir une référence (ou un pointeur) vers une instance du type dérivé manipulé, et qui "fera le boulot" en pouvant utiliser toutes les fonctions spécifique à ce type réel.
Comme chaque objet connait son type réel, le fait de transmettre *this (ou this, selon le cas) à une fonction qui s'attend spécifiquement à recevoir le type réel (dérivé) de l'objet s'assurera que tu lui transmet bel et bien... le type réel.
Le patron de conception visiteur permet de disposer de ce double dispatch en exposant une fonction spécifique (visit(Type /* const */ &)) adaptée à chacun des types de ta hiérarchie de classes
Tel que je l'ai mis en place, en transmettant une référencenon constante sur le visiteur à la fonction analyze (et à la fonction doAccept) et une référence non constante sur le type réel de l'objet à la fonction visit du visiteur, il peut strictement servir "à tout et n'importe quoi"
Geralt de Riv a écrit:
Ca sert à s'assurer de la façon dont l'AST se conçoit ?
J'aurais plutôt dit "à s'assurer de la facon dont l'AST se construit, mais oui
Geralt de Riv a écrit:
Ou à ce positionner quelque part ?
Il pourrait, mais pas sous la forme que j'ai mise en place (je vais d'ailleurs modifier tout le code pour permettre un accès "non récursif" à des références constantes sur les noeud pour permettre cela ... et bien d'aures choses encore ), parce que toute la logique est calculée pour parcourir l'AST de manière récursive (sous une forme infixe)
Geralt de Riv a écrit:
Ou simplement à lire les données ?
Bien sur! A partir du moment où tu disposes du type réel de chaque noeud, tu peux sans aucun problème accéder à toutes les données pertinentes auxquelles ton noeud te donne accès
Geralt de Riv a écrit:
Je me demande également à quel moment de la conception de l'AST, Clang (pour avoir un exemple de compilateur) génère t-il son AST *.txt ?
Très vraisemblablement avec un visiteur destiné à afficher les informations de chaque noeuds : il part du noeud racne (l'unité de compilation) et il parcoure les noeuds sous une forme prefixe et affiche les données pertinentes
Pour ce qui est de l'indentation, il retient sans doute la "profondeur" à laquelle chaque noeud se trouve par rapport à la racine
Geralt de Riv a écrit:
Je me demande aussi de quel façon est ensuite analyser l'arbre ? Avec le visiteur ?
Oui, c'est le but : comme le visiteur peut parcourir ton AST à peu près dans n'importe quel ordre (prefixe, infixe ou postfixe), ton visiteur peut manipuler chaque noeud absolument comme bon lui semble
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Donc, si je comprends bien, le patron de conception visiteur, c'est simplement un moyen de parcourir chaque noeuds de l'arbre en partant de la racine ou d'un noeud spécifique.
koala01 a écrit:
Oui, c'est le but : comme le visiteur peut parcourir ton AST à peu près dans n'importe quel ordre (prefixe, infixe ou postfixe), ton visiteur peut manipuler chaque noeud absolument comme bon lui semble.
Même les modifier ? J'imagine que c'est utile pour l'optimisation dans ce cas, mais parcourir un arbre d'un très gros programme, ça doit prendre beaucoup de temps non ?
Et, dernière question : l'arbre est-il présent "physiquement" dans le programme ? C'est à dire contenu en tant qu'un tableau, un conteneur ? Ou est-ce que c'est le programme lui-même qui représente l'arbre, mais en stockant seulement certaines de ces données ? Je ne sais pas si c'est très claire, mais en gros je voudrais savoir comment est stocker l'AST dans le programme.
(qui correspond littéralement à un code proche de 5 + 2 * 3 ) Le visiteur pourrait tout à fait remplacer toute cette partie de l'AST par un noeud unique
LitteralValue "11"
Geralt de Riv a écrit:
mais parcourir un arbre d'un très gros programme, ça doit prendre beaucoup de temps non ?
Le double dispatch (avec la nécessité de faire appel à deux fonctions) et la mécanique mise en oeuvre pour obtenir des comportements polymorphes (avec la nécessité de sélectionner le comportement "qui va bien" pour le type particulier de l'objet que l'on manipule) va -- effectivement -- prendre "plus de temps" que si on avait pu directement faire appel à une fonction -- de préférence inlinée -- spécifique au type d'objet que l'on manipule.
C'est -- d'une manière générale -- le gros problème de l'approche orientée objet. Mais il faut aussi raison garder: le "surcoût" de temps que cela occasionne doit être de l'ordre de moins de 50 "ticks" (*).A la fréquence de ton processeurs cela correspond à un "surcoût" 50/2 000 000 000 sec, avec un processeur ayant une fréquence de 2GHz par nœud que tu voudra manipuler...
(*) je n'ai pas les données réelles concernant ce surcoût, mais je ne doit pas en être très loin avec cette approximation
Je suis d'accord que ce sont les petits ruisseaux qui font les grands fleuves, et que, si tu as 2 milliards de noeuds à analyser dans les mêmes circonstances, ben, tu risques sans doute de perdre 50 secondes sur le temps de traitement total à cause de cela, mais il faut mettre ce temps en relation avec le temps nécessaire au traitement de ces 2 milliards de noeuds, qui sera sans doute de plusieurs heures (jours ???).
Et du coup, il faut se poser la question: ces cinquante secondes de perdues font elles réellement une grosse différence? A priori, on peut dire que non.
Et si tu n'as pas 2 milliards de noeuds, mais que tu n'en a "que" 4 000, tu perdras 200 000 /2 000 000 000 secondes soit ... 0,001 seconde ; soit encore beaucoup trop peu pour que tu puisse constater une différence lors de l'exécution (A titre de comparaison : quand le toubib tape sur ton genoux pour voir le réflexe, il faut à peu près 0.035 seconde pour que ta jambe reçoive l’impulsion qui la fera se lever!!!)
Par contre, la logique que tu mettra en oeuvre lors du traitement de chaque type de noeud spécifique aura un impact très important sur la durée du traitement
Geralt de Riv a écrit:
Et, dernière question : l'arbre est-il présent "physiquement" dans le programme ? C'est à dire contenu en tant qu'un tableau, un conteneur ? Ou est-ce que c'est le programme lui-même qui représente l'arbre, mais en stockant seulement certaines de ces données ?
A priori, tu vas effectivement stocker l'AST en mémoire: tu vas commencer pas "tokenizer" le code que tu lis, sans essayer de comprendre à quoi cela correspond, puis tu vas, pour chaque token, créer le noeud (ou parfois l'ensemble de noeuds) qui correspond à chaque token, et tu l'insérera dans un AST dont la racine sera "l'unité de compilation"
Ainsi, si tu as un code proche de
int foo( int a, int b){
return a * b ;
}
la première étape est de séparer les termes qui apparaissent dans le code à savoir
int
foo
OpenParenthesis
int
a
coma
int
b
CloseParenthesis
OpenBracket
return
a
star
b
SemiColon
CloseBracket
(tu adjoindra sans doute à ces éléments quelques informations utiles, comme les numéros de ligne et de colones )
Une fois que tu auras cela, tu créera les noeuds de ton AST:
int c'est un identifiant, mais c'est aussi un mot clé qui désigne un type de donnée, ce qui te donnera sans doute quelque une partie d'AST ressemblant à
TypeDecl
/ \
KeyWord nullptr #aurait pu etre "ClassName" ou "EnumName" en fonction des circonstances
/ \
Identifier nullptr
"int"
foo est un identifiant, mais c'est le nom d'une fonction, ce qui te donnera sans doute un tronçon d'AST ressemblant à
FunctionDecl
/ \
Identifier "foo" Parameters
/ \
... ... # je ne m'intéresse qu'à foo
Ce qui se trouve entre OpenParenthesis et CloseParenthesis sera regroupé dans "Parameters sous une forme proche de
Si bien que, lorsque tout sera remis en place, tu te retrouvera avec un AST dont la racine correspond à ton unité de compilation et dont l'ensemble des noeuds représent l'exacte structure de ton code
Et, une fois que tu auras cet AST en mémoire, tu pourras l'utiliser "à ta guise" :D.
Mais, bien sur, comme cela prendra "un temps bête" de créer cet AST, il s'agira de ne pas devoir le refaire "à chaque fois que tu en aura besoin"
- Edité par koala01 19 août 2018 à 0:04:25
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Si tu as 2 milliards de noeuds à analyser dans les mêmes circonstances, tu risques de perdre 50 secondes sur le temps de traitement total, mais il faut mettre ce temps en relation avec le temps nécessaire au traitement de ces 2 milliards de noeuds, qui sera sans doute de plusieurs heures (jours ???).
Ha bon ? Et comment GCC (ou Clang ou n'importe quel compilateur) arrive t-il alors à aller si vite pour compiler l'ensemble des bibliothèques inclues dans le programme ? Parce que mine de rien, il y en a quand même pour quelques milliers de lignes de code en plus du nôtre (c'est sans doute pour ça que l'exécutable fait 32 MO avec un simple hello world). Et, qui dit milliers de lignes, dit centaine de milliers de noeuds...
Au passage, penses-tu que cela soit une bonne chose que de ne pas optimiser du tout le programme si on ne l'indique pas en paramètre ? Afin justement d'augmenter la productivité du développeur, pour ne pas qu'il attende 50 secondes à chaque compilations...
En terme de rapidité justement, j'ai pu remarqué avec déception que l'utilisation de std::ifstream (bien que performante) ralentissait "beaucoup" le programme comparé aux fonctions C standard. J'ai donc un dilemme :
Faire du C++ quite à ralentir l'exécution du programme ;
Faire du C/C++.
Personnellement, mon choix est vite fait (le 1er), mais j'ai été assez étonné de voir que pas mal de compilateurs (et projets C++ en général sur GitHub) utilisait des fonctions et principes tirées du C dans des programmes en C++...
koala01 a écrit:
Et, une fois que tu auras cet AST en mémoire, tu pourras l'utiliser à ta guise.
Si je comprends bien, " l'AST en mémoire " n'est pas similaire à un vulgaire conteneur à la std::vector (enfin plutôt à la std::map si on parle de gestion de donnée à stockage non-linéaire), mais plutôt à un objet (en termes POO) dont les méthodes permettent justement de modifier ses propriétés (donc ces "champs" hérité, et polymorphiques selon les cas).
void Parser::AST::insert(Expression expr, TypeOfStatement, Infos infos) {
switch (expr) {
case Statements::VarDecl:
VariableDecl::append(expr, infos);
break;
case Statements::FuncDecl:
FunctionDecl::append(expr, infos);
break;
};
case Statements::VariableEditing:
VarEdit::append(expr, infos);
break;
// ... et ainsi de suite jusqu'à :
default:
Exception.throw("Unknown statement: '" + expr[0].str + "' at line " + infos.line + ".");
break;
};
}
Avec VariableDecl, FunctionDecl, VarEdit, ... qui sont des classes héritières, selon les cas, de la classe Node originelle et / ou de la classe UniqueNode originelle et / ou de la classe Leaf, elle aussi originelle.
La classe VariableDecl contiendrait par exemple ceci en private / friend :
struct ExprValue;
struct Decl {
Type type;
Infos infos;
ExprValue value; // par exemple, une expression : 2 + 2 sous la forme d'arbre binaire tel que + est le noeud principale, et les deux feuilles sont 2 et 2.
// pour les expressions mathématique, je pense que l'utilisation des S-expressions est plus simple, exemple : (+ 2 2)
// sous format (vérifié) std::string
};
std::map<std::string /*unique identifier*/, Decl> Variables;
Et pour que le visiteur y accède :
void Parser::AST::VarDecl::visitor(std::string identifier, T &data) const /* je sais pas si un fonction void peut être const au passage */ {
/* et là il fait ce qu'il veut, je n'y ai pas encore vraiment réfléchis ^^,
mais une référence pourrait être traitée selon ce qu'on souhaite récupérer de la structure.*/
}
Enfin voilà
Merci énormément pour l'aide que vous m'avez apporté en tout cas, j'ai appris plus de choses concernant les AST aujourd'hui qu'en une semaine de recherche ! (j'avais un peu peur de poser la question en fait...)
Si tu as 2 milliards de noeuds à analyser dans les mêmes circonstances, tu risques de perdre 50 secondes sur le temps de traitement total, mais il faut mettre ce temps en relation avec le temps nécessaire au traitement de ces 2 milliards de noeuds, qui sera sans doute de plusieurs heures (jours ???).
Ha bon ? Et comment GCC (ou Clang ou n'importe quel compilateur) arrive t-il alors à aller si vite pour compiler l'ensemble des bibliothèques inclues dans le programme ? Parce que mine de rien, il y en a quand même pour quelques milliers de lignes de code en plus du nôtre (c'est sans doute pour ça que l'exécutable fait 32 MO avec un simple hello world). Et, qui dit milliers de lignes, dit centaine de milliers de noeuds...
Au passage, penses-tu que cela soit une bonne chose que de ne pas optimiser du tout le programme si on ne l'indique pas en paramètre ? Afin justement d'augmenter la productivité du développeur, pour ne pas qu'il attende 50 secondes à chaque compilations...
Concrètement, pour mes projets au boulot avec clang-tidy, qui utiliser l'AST de clang et utilise des visitor
- plusieurs centaines de lignes de code avec inclusion
- plusieurs centaines de millier de noeuds dans l'ast
- jusque 2 secondes par fichier
- plusieurs milliers de fichiers = plusieurs dizaines de minutes pour compiler un projet
Le temps de compilation est une des critiques récurrente du C++.
Mais tu fais une erreur de calcul. Ce n'est pas 50 secondes vs 0 seconde selon l'implémentation. Ca va etre 50 secondes vs X secondes. Quand on reflechie a l'implementation, il faut voir le cout de cet implementation par rapport au gain. Si un projet prend 30 min a compiler vs 29 minutes apres optimisation, tout le monde d'en fout de cette optimisation.
Geralt de Riv a écrit:
En terme de rapidité justement, j'ai pu remarqué avec déception que l'utilisation de std::ifstream (bien que performante) ralentissait "beaucoup" le programme comparé aux fonctions C standard. J'ai donc un dilemme :
Faire du C++ quite à ralentir l'exécution du programme ;
Faire du C/C++.
Personnellement, mon choix est vite fait (le 1er), mais j'ai été assez étonné de voir que pas mal de compilateurs (et projets C++ en général sur GitHub) utilisait des fonctions et principes tirées du C dans des programmes en C++...
Personnellement, mon choix est vite fait (le 1er), mais j'ai été assez étonné de voir que pas mal de compilateurs (et projets C++ en général sur GitHub) utilisait des fonctions et principes tirées du C dans des programmes en C++...
N'utilises pas les streams. Utilises les fonctions systeme et lit le fichier en une seule fois.
Le C++ ne propose que les streams en plus des fonctions C. Et les streams sont lents. Donc il est effectivement courant d'utiliser les fonctions C ou encore mieux les fonctions systeme.
Ha bon ? Et comment GCC (ou Clang ou n'importe quel compilateur) arrive t-il alors à aller si vite pour compiler l'ensemble des bibliothèques inclues dans le programme ? Parce que mine de rien, il y en a quand même pour quelques milliers de lignes de code en plus du nôtre (c'est sans doute pour ça que l'exécutable fait 32 MO avec un simple hello world). Et, qui dit milliers de lignes, dit centaine de milliers de noeuds...
Attention: 50 secondes sur 2 000 000 000 de noeuds, c'est le surcout total auquel tu dois t'attendre du fait des problèmes posés par la virtualité et le double dispatch.
Mais il n'empêche que, si tu as 2 000 000 000 de noeuds à traiter, le seul traitement de tous ces noeuds te prendra peut être 24 heures, soit 24 * 60 * 60 = 86 400 secondes.
Alors, en toute honnêteté, que le traitement complet te prenne 86400, 86 450 ou 86 350 secondes, est ce que cela fera réellement une différence qui vaudra la peine d'essayer de faire autrement?
De toutes manières, si tu lance la compilation à 8h30, en arrivant au bureau, tu ne pourras quand même rien faire avant le lendemain matin
Et, comme l'a si bien dit gbdivers, le temps de compilation est l'un des gros problèmes auquel se heurtent tous les langage compilés.
J'ai personnellement travaillé sur un projet de plusieurs milliers de fichiers qui, lorsqu'on le compilait (complètement) sur un seul ordinateur (quad core à l'époque), mettait presque deux heures à se compiler (et les tests unitaires mettaient une demi heure de plus pour s'effectuer).
A tel point que l'on utilisait un système de compilation distribuée qui permettait d'utiliser quelques coeurs des pc de tous les développeurs de l'équipe, et qui faisait descendre le temps de compilation à plus ou moins vingt minutes
Mais crois tu sincèrement que nous ralions parce ce processus prenait 20 minutes 50 au lieu de 19 minutes 10??? Que crois tu que l'on aurait pu faire du temps ainsi gagné?
Tiens, un autre exemple : les sources de Qt représentent près de 220 000 fichiers pour un total d'un peu plus de 2 Gb. Sur l'ordinateur dont je dispose (un pc qui date déjà de 2010, quad core calibré à 1.8MHz avec ... 6Gb de RAM) la compilation complète requière pres de 36 heures.
Crois tu que j'en aie réellement quelque chose à foutre de gagner même dix minutes sur le processus complet???
Si je pouvais compiler l'ensemble en 18 ou même en 20 heures au lieu de 36 (sur le même PC, bien sur ) , là, je serais vachement content Mais, même si je pouvais gagner une demi heure sur les 36 actuelles, qu'est ce que ca changerait à ma vie?
- Edité par koala01 19 août 2018 à 0:28:47
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Vivement la technologie quantique : compiler des milliers de fichier de milliers de lignes en seulement... 0.0001 secondes
Je comprends mieux ce que vous voulez dire à présent
Mais, pour reprendre l'exemple de koala avec QT : il faut plus de 20 heurs de compilation pour un projet QT ? (je pense avoir mal compris quelque chose...)
A un tel niveau, c'est claire que l'optimisation de temps de compilation, en s'en fout () complètement.
Heureusement que c'est pas comme ça pour tout les projets non plus...
gbdivers a écrit:
N'utilises pas les streams.
Je vais devoir tout modifier . J'étais bien content avec mon seekg et mon peek moi... M'enfin, je pense que, dans un premier temps, je garderai tout de même std::ifstream pour la phase "teste", et ensuite, si c'est vraiment trop handicapent, bas j'utiliserai une fonction C (probablement pas système car non portable).
Tokenizer une dizaine de fichier de seulement quelques centaines de ligne, ca ne me prend qu'une petite seconde, alors bon...
Mais, pour reprendre l'exemple de koala avec QT : il faut plus de 20 heurs de compilation pour un projet QT ? (je pense avoir mal compris quelque chose...)
Non, il parle de la compilation de Qt lui meme.
Geralt de Riv a écrit:
J'étais bien content avec mon seekg et mon peek moi...
La, ce n'est pas un probleme de C vs C++, c'est un probleme de comprehension du fonctionnement des ordinateurs. Il faut que tu lises un cours sur le sujet.
Chaque memoire d'un ordi (disque, RAM, cache, registres, etc) ont des temps d'acces (latence) et des debits. Les disques ont des temps de latences de plusieurs centaines de millisecondes. Chaque acces au disque ajoute donc a chaque fois pluiseurs centaines de millisecondes d'attente. C'est aussi simple que ca.
Pour resoudre ce probleme, une seule solution : faire qu'un seul acces (on est oblige d'en faire au moins un). Et donc TOUT lire d'un coup (si la taille du fichier le permet.)
Mais, pour reprendre l'exemple de koala avec QT : il faut plus de 20 heurs de compilation pour un projet QT ? (je pense avoir mal compris quelque chose...)
Oui, tu as mal compris ce que je voulais dire
A l'heure actuelle, c'est la version 5.11.1 qui est la "dernière version en date" de Qt.
Elle est fournie, sous windows, pour
VisualStudio 2011
VisualStudio 2017
VisualStudio 2018 et
MinGW ... 32 bits (avec Gcc 5.?.? je ne connais plus les numéros de version par coeur).
Pas de bol: la dernière version stable de Gcc (disponible au travers de MinGW) est la version... 8.1.0, disponible aussi bien en 32bits qu'en 64 bits.
Et moi, j'aimerais donc pouvoir utiliser Qt-5.11.1 avec le compilateur que j'utilise habituellement pour tout le reste, à savoir : Gcc-8.1.0 en 64 bits.
Comme cela ne correspond absolument pas à la version de Gcc supportée pour MinGW par Qt, je n'ai pas d'autre choix que de... compiler l'intégralité du projet Qt afin de pouvoir utiliser mon compilateur "natif"
Hé bien, quand je récupère toutes les sources du projet pour pouvoir générer toutes les dlls spécifiques à Qt, cela correspond à +/- 220 000 fichiers pour à peu près 2Gb de code source.
Et quand je lance le processus de compilation pour obtenir les différentes dlls propres à qt à partir de ces 220 000 fichiers, j'en ai pour à peu près 36 heures avant qu'il ne m'ait généré tout ce qu'il devait
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
J'en ai pour à peu près 36 heures avant qu'il ne m'ait généré tout ce qu'il devait
Mais tu ne le fais qu'une seule fois, alors ça va
gbdivers a écrit:
Pour resoudre ce probleme, une seule solution : faire qu'un seul acces (on est oblige d'en faire au moins un). Et donc TOUT lire d'un coup
Mais c'est ce que je fais, ne t'inquiète pas
Si tu veux vraiment savoir comment je fais, voici les étapes :
Ouvrir le fichier, s'assurer qu'il est bon, pas vide, ...
Lire le fichier en continu jusqu'à ce qu'il rencontre un délimiteur (point, virgule, point-virgule, espace, parenthèse, ...) Il y a des symboles de ma grammaire qui s'étalent sur 3 caractères, les deux premiers caractères étant eux aussi un symbole et également le premier et le dernier (voici le jeton s'a ira plus vite : "-->" pour ne pas que le lexer se dise "Tiens ! Le signe moins ! C'est forcément un délimiteur, donc j'arrête ici et je le renvoie"). L'utilisation de seekg + peek me permet de déterminer les 2 prochains caractères en plus de celui actuellement traité, ce qui est utile pour déterminer si on ne coupe pas trop tôt dans le flux afin de ne pas récupéré ceci : [-][-][>] à la place de [-->].
Lorsque le jeton est déterminé du flux, on lui attribue une identité lexicale ainsi que les informations de sa position (ligne, column, fichier) dans une structure proche de celle-ci :
Et ce, pour chaque jetons. Evidemment, cela met plus de temps qu'une lecture classique, mais cela permet de récupérer tout ce dont nous avons besoin pour ensuite continuer. (pour un fichier de 13 octets sans tout ça, il prend environs 0.014 secondes, avec tout ça, il prend environs 0.02 secondes).
Quand je dis lire en une seule fois, ca veut dire lire en un seule fois. Pas de seek, pas de peek, pas d'acces sequentiel. (Tout ca fait que tu as un temps de latence a chaque fois - modulo la bufferisation, mais c'est complexe). Donc cela veut dire que tu as une latence de plusieurs centaines de millisecondes a chaque fois !
Lire en 1 seule fois, ca veut dire lire en une seule ! C'est a dire faire :
const int size_of_file = get_file_size(file_name);
string content(size_of_file); // on cree une chaine de la taille du fichier
content = file.read(size_of_file); // on lit la totalite du fichier !!!
Et ensuite on travaille sur les donnees qui sont en memoire, pas sur le disque.
Donc, il faudrait sauvegarder tout le contenu de tous les fichiers à analyser dans une seule chaine de caractère ?
Mais ca voudrait dire que l'on "retarde" le travail qui pourrait être effectué en "une seule fois", non ?
Je me souviens avoir fait ça pour une VM Just In Time une fois, j'enregistrais tout le contenu du fichier asm-like pour le traiter par la suite, mais le problème, c'est que le temps entre la compilation du bytecode asm-like et l'exécution de celui-ci pouvait prendre un long moment. Depuis, je n'utilise plus jamais ce type de lecture et de traitement de donnée, je le lie directement dans le fichier. Ma VM traitait tout en temps réel dès l'exécution du programme. Mais peux-être est-ce différent la manière de procéder pour un compilateur...
Bonjour Geralt de Riv, j'ai un peu lu les réponses des intervenants e j'ai découvert avec vous cette notion d'AST. on ne s'imagine pas tout ce qui passe décidément.
Ensuite viennent les étapes d'optimisation de l'AST, et d'un potentiel multi-passe, puis vient la compilation en code assembleur via la lecture dudit arbre, avec la gestion de la mémoire (pointeurs, tableaux, allocation dynamique, pile et tas, ...), du système, des bibliothèques externes ainsi que des DLLs, des exceptions, ...
C'est vrai qu'on ne s'en rend pas toujours compte...
Pour moi, le plus difficile, c'est justement cette notion de parsing et d'AST. Autant lire des données et leurs attribuer une identité lexical, c'est simple, mais concevoir un arbre qui représente le programme de façon à pouvoir être analyser de manière logique et non-linéaire, c'est plus compliqué. En plus il existe plusieurs sorte d'AST, et celle qui est utilisé par les compilateurs / interprètes est très complexe et nécessite pas mal de travail.
Raison pour laquelle je m'en tiens déjà à bien intégrer C/C++ et Qt en soi.
Car ce que tu fais avec l'AST, c'est du très très bas niveau et je trouve que ça demande un peu de recul, même si lire ce fil de discussion m'est intéressant, car ça donne des idées.
Mais ca voudrait dire que l'on "retarde" le travail qui pourrait être effectué en "une seule fois", non ?
Tu ne comprends pas le probleme de la latence.
Imagine que tu veux lire un fichier de 10 octets sur un disque dur de latence 1ms et de debit 1Mo/s (*). Avec une seule lecture, tu as 1 ms + 10 /1000000 ms = 1,000001 ms.
La meme chose pour lire octet par octet : 1 * 1 ms + 10 * 1/10000000 ms = 10,000001 ms.
Donc la seconde approche est 10 fois plus lente !
(*) je me suis trompe, un disque dur a une latence de l'ordre de la milliseconde, ce sont les disques optiques (CD, DVD) qui ont une latence de l'ordre de la centaine de milliseconde.
A chaque fois que tu fais un accès, tu ajoutes le temps de latence ! Donc non. Travailler directement sur le disque, ce n'est pas faire les choses en une seule fois. C'est pire !
Maintenant, pour bien comprendre le probleme de la latence, je vais en rajouter une couche...
Tout ce que tu sais sur les performances d'un ordinateur, c'est du bullshit. Seule la latence est importante pour les performances !!!
Ok, il faut des explications.
Imagines si ton CPU n'avait que ton disque dur pour travailler (pas de RAM, pas de registre, rien). Dans ce cas, a chaque fois qu'il veut faire la moindre opération, il devra accéder au disque et donc il y aura une latence de plusieurs millisecondes. Ca serait extrêmement lent !
Un règle générale (valide même hors informatique) : dans une chaîne de processus, la vitesse de la chaîne sera limite par la vitesse de l’élément le plus lent.
Sur ton ordinateur sans RAM, peut importe si ton CPU tourne a 1 Mhz, 1 GHz ou 100000 GHz, il ne pourra pas travailler plus vite que la latence du disque.
Comment régler ce probleme de latence ? La solution est simple : on va utiliser une mémoire intermédiaire qui sera plus rapide. (Et en général, plus cher, donc plus petite). Par exemple, au lieu des 10 ms pour lire 10 octets un par un depuis le disque, on va copier un bloc de données depuis le disque sur la mémoire intermédiaire, puis lire les octets un par un sur cette mémoire. Et le temps de lecture sera alors : 1 ms (latence disque) + 10 * 1/1M (temps de copie) + 10 * 1 ns (latence RAM) ~ 1 ms. 10 fois plus rapide !
C'est le concept de mise en cache des donnees. C'est un concept fondamental en informatique moderne. On utilise ce concept PARTOUT dans un ordinateur !
dans un disque dur a plateau, tu vas avoir de la mémoire flash pour mettre en cache
la RAM met en cache les données du disque
les GPU utilisent des caches pour les données qui viennent de l'ordi
la mémoire cache L3 met en cache les données de la RAM
la mémoire cache L2 met en cache les données de L3
L1 met en cache L2
les registres CPU mettent en cache L1
j'en oublie surement
De nos jours, un code est performant parce qu'il utilise correctement les caches. Les micro-optimisations que certains s'amusent a faire vont faire gagner quelques cycles CPU. Une erreur de gestion des caches, ça a être plusieurs milliers de cycles CPU perdus.
C'est pour cela qu'on passe note temps a dire de ne pas optimiser sans profiler. C'est pour ça que std::vector est plus rapide que std::list. C'est pour cela que les pointeurs peuvent bouffer les performances. C'est pour cela que l'on est généralement plus mauvais que le compilateur pour optimiser le code. Et c'est pour ca que beaucoup d'anciens cours d'info bas niveau ne sont plus valides (ou des cours d'embarque qui ne sont pas applicable sur un ordi de bureau). C'est pour ca que souvent, ecrire des routines en assembleur n'est pas plus performant. C'est pour ca que beaucoup de pratiques qu'on conseillait avant ne sont plus valide.
Geralt de Riv a écrit:
Et ça, ce n'est que le début
J’espère que tu réalises que bosser sur les compilateurs, c'est une spécialité a part entière ? Ceux qui bossent dans ca on généralement eu des cours sur les compilateurs, les langages, etc. pendant des années. C'est un tres tres gros boulot. Tu as des dizaines de livres sur le sujet, il y a des conferences sur ca, etc.
Ce n'est pas du tout un truc qu'on fait entre 2 cafes.
Et tout ce que je te racontes n'est qu'un survol très large du domaine. Je ne suis pas du tout spécialiste des compilateurs (et je pense que koala01 non plus).
Si tu veux voir comment Clang fonctionne en interne, tu as les LLVM conferences sur YouTube : https://www.youtube.com/channel/UCv2_41bSAa5Y_8BacJUZfjQ Mais je te previens, il y a du niveau et du boulot. (Perso, c'est trop complexe pour moi).
YES, man a écrit:
C/C++
moi : "Et c'est pour ca que beaucoup d'anciens cours d'info bas niveau ne sont plus valides". Tant que tu ne comprendras pas ca, tu continueras de faire n'importe quoi et ne pas progresser.
Je comprends ce que tu veux dire, mais -- sans profiler -- j'ai toujours l'impression qu'a l'exécution, c'est la lecture sans enregistrement des données à lire qui va plus vite que si on mettait tout dans une variable justement...
Bon, et bien je vais réviser mon code en conséquence, merci pour les informations
YES, man a écrit:
Car ce que tu fais avec l'AST, c'est du très très bas niveau
Il y a bas-niveau, et programmes natifs. Un AST est justement quelque chose qui a pour but d'abstraire les donnée sous une autre forme, si on le fait nous même, c'est juste de la programmation native j'ai envie de dire (donc sans bibliothèques); un AST qui est bas niveau, c'est justement de l'assembleur : il représente les donnée avec un opérateur et une ou deux valeurs à traitées :
Oui. Mais un opérateur en assembleur, c'est pas la même chose qu'un opérateur en C++.
En assembleur, un opérateur c'est littéralement un moyen d'opérer sur les données qui suivent (il ne peut y en avoir que 2 maximums : la valeur affectée, et la valeur affectant).
× 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.
Discord NaN. Mon site.
Discord NaN. Mon site.
Discord NaN. Mon site.
Discord NaN. Mon site.