Une série d'articles est consacrée à la description de l'approche optimale pour l'implémentation d'outils d'analyse de code statique, destinés aux spécialistes. L'objectif du travail est des approches, des modèles et des techniques pour obtenir des performances maximales de l'outil tout en minimisant la complexité de développement et de support / changement de l'outil. Cet article explique comment accélérer l'analyseur et réduire la consommation de mémoire. L'article est structuré de façon à ce que le lecteur lise le manuel écrit par Terrence Parr.Utiliser ANTLR au maximum
ANTLR fonctionne mieux entre environ 1 ko et 10 ko; les fichiers plus volumineux ne seront pas analysés par cette bibliothèque à la vitesse maximale. De plus, le débogage du travail sur des fichiers volumineux devient presque impossible. La raison principale pour laquelle vous devez conserver les données d'entrée pour l'analyseur dans les limites spécifiées est que les algorithmes de prédiction de branche pour ANTLR utilisent activement la pile, donc par tous les moyens vous devez vous débarrasser des boucles dans la grammaire lorsqu'une règle s'appelle à travers de nombreuses autres règles, y compris certaines conditions d'activation d'une telle connexion, considérons un exemple:var f = fun a(b) { b = 10; return b; }
Ce code peut être décrit avec la grammaire suivante:start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'
Il est facile de voir que stmt est appelé à l'intérieur de la règle funDecl, qui forme une boucle qui, dans les applications réelles, peut obliger un fichier de 100 ko à nécessiter 4 Go de mémoire RAM pour des performances maximales, ou même la capacité de travailler, ce qui est une situation absolument inacceptable .Une façon de surmonter cet inconvénient consiste à ajouter des modifications spéciales au processus de création de jetons, à savoir la convolution de blocs {} en un jeton, avec le traitement de ces jetons plus tard dans un nouvel analyseur, à l'entrée desquels les jetons effondrés seront transmis.Pour ce faire, dans ANTLR, vous pouvez remplacer la méthode org.antlr.v4.runtime.Lexer # nextToken du lexer, où vous pouvez implémenter la fonctionnalité de convolution: override def nextToken(): Token = super.nextToken() match {
case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
case x: Token => x
}
def buildFoldToken(start: RScanToken): RScanToken = {
val (token, list) = createFoldBlockBody(
mutable.MutableList[RScanToken]()
++ List(start.asInstanceOf[RScanToken])
)
val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
result.setLine(start.getLine)
result.setCharPositionInLine(start.getCharPositionInLine)
result.setFoldedTokens(list)
result
}
private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
var current: RScanToken = null
while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
current = nextToken().asInstanceOf[RScanToken]
list += current
}
if (current.getType == Token.EOF)
throw new IllegalStateException()
(current, list)
}
La grammaire doit être complétée par:startJavaScript
: HashBangLine? jsFileBody? EOF
;
startFoldBlock
: block EOF
;
block
: LBRACE stmtList? RBRACE
| FoldBlock
// ,
// startFoldBlock
;
Avec cette approche, le contenu de la convolution ne sera plus traité, car l'algorithme récursif absorbera les jetons et les sauvegardera.La vitesse de traitement augmente de 2 à 10 fois, la différence devient particulièrement sensible sur les fichiers js minifiés.L'impact sur le fonctionnement ANTLR de l'optimisation proposée en utilisant plusieurs fichiers javascript comme exemple:Sans optimisation, le travail est effectué dans un seul thread, avec optimisation, si possible, le traitement est parallèle.Le lancement a été effectué sur une machine avec 64 Go de RAM, Intel® Core (TM) i7-9700K CPU @ 3.60GHz, OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.4 + 11).Clés de démarrage JVM: -Xmx4G -XX: + UseG1GC -XX: MaxHeapFreeRatio = 30 -XX: MinHeapFreeRatio = 10Pour le fichier tsserver.js, la clé est -Xmx32G, alors que la consommation de mémoire a atteint 22 Go! Alors que les fichiers minifiés jusqu'à 200 Ko avec optimisation sont analysés avec une limite de tas de 128 Mo en mode parallèle sans que le ramasse-miettes ne charge le processeur, 2% au maximum!Profilage
ANTLR prend en charge le profilage de l'analyseur / lexeur lors de l'exécution. Pour l'activer, vous devez appeler la méthode: org.antlr.v4.runtime.Parser # setProfile avant d'exécuter des règles. Ensuite, vous pouvez obtenir toutes les informations, par exemple de cette manière: private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {
val parseInfo = parser.getParseInfo
val atn = parser.getATN
for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {
val ds = atn.decisionToState.get(di.decision)
val ruleName = parser.ruleName(ds.ruleIndex)
log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)
log.debug("=========================")
log.debug(tokenStream.getText)
log.debug("=========================")
}
}
Un avantage évident de cette méthode est la réduction de la quantité de données que vous devez analyser, car les convolutions peuvent être remplacées par {} et fonctionnent toujours en convolution locale, ce qui accélère considérablement le processus d'optimisation de la grammaire.Conclusion
Cet article propose une méthode pour optimiser le travail des grammaires formelles implémentées à l'aide de la bibliothèque ANTLR, bien que l'approche elle-même puisse également être essayée pour s'appliquer à d'autres bibliothèques. Une caractéristique d'optimisation est la réduction du nombre de transitions vers l'avant pour valider le flux de jeton d'entrée. Il vous permet également d'analyser des fichiers volumineux (plus de 1 Mo) avec un coût de mémoire de 512 Mo pour le traitement monothread, tandis que le manque d'optimisation nécessitera 50 fois plus de mémoire pour un travail rapide en utilisant la même grammaire.Code source disponible sur github. Ce projet est fait pour démontrer le travail d'optimisation. Le projet est simplifié au maximum, il est recommandé de démarrer l'étude dans la classe GrammarTester, une configuration de lancement a été faite pour cela, il suffit d'enregistrer le chemin d'accès au dossier avec les données d'entrée. Faites attention à la clé rscan.tester.cache.dir, les fichiers temporaires seront écrits dans ce dossier, une analyse de fichier réussie est corrigée dans ce dossier et ne permettra pas à l'analyseur de l'analyser une deuxième fois - c'est pratique pour corriger les erreurs. À l'heure actuelle, la grammaire a été testée sur 17 000 fichiers à partir de node_modules créés pour l'application de réaction principale. Seuls les node_modules imbriqués ont été ignorés.Dans le prochain article, nous examinerons les options d'organisation des données et le modèle R (réflexion) pour la représentation optimale des données initiales sous forme d'objets d'analyse avec une consommation de mémoire minimale, la possibilité d'implémenter des algorithmes de recherche pour les éléments de complexité O (1) et de pouvoir enregistrer sur le disque sous forme sérialisée tous les objets, ainsi que les parties de test unitaire de l'outil.