Se dedica una serie de artículos a describir el enfoque óptimo para implementar herramientas de análisis de código estático, diseñadas para especialistas. El objetivo del trabajo son enfoques, modelos y técnicas para obtener el máximo rendimiento de la herramienta y, al mismo tiempo, minimizar la complejidad del desarrollo y el soporte / cambio de la herramienta. Este artículo analiza una forma de acelerar el analizador y reducir el consumo de memoria. El artículo está estructurado para que el lector lea el manual escrito por Terrence Parr.Usando ANTLR al máximo
ANTLR funciona mejor entre aproximadamente 1 kb y 10 kb; los archivos más grandes no serán analizados por esta biblioteca con la máxima velocidad. También el trabajo de depuración en archivos grandes se vuelve casi imposible. La razón principal por la que necesita mantener los datos de entrada para el analizador dentro de los límites especificados es que los algoritmos de predicción de rama para ANTLR usan activamente la pila, por lo que de cualquier manera debe deshacerse de los ciclos en la gramática cuando una regla se llama a sí misma a través de muchas otras reglas, incluidas ciertas condiciones de activación para dicha conexión, considere un ejemplo:var f = fun a(b) { b = 10; return b; }
Este código se puede describir con la siguiente gramática:start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'
Es fácil ver que stmt se llama dentro de la regla funDecl, que forma un bucle que en aplicaciones reales puede hacer que un archivo de 100 kb requiera 4 GB de memoria RAM para un rendimiento máximo, o incluso la capacidad de trabajar, lo cual es una situación absolutamente inaceptable .Una forma de superar este inconveniente es agregar modificaciones especiales en el proceso de creación de tokens, a saber, la convolución de bloques {} en un token, con el procesamiento de estos tokens más adelante en un nuevo analizador, a la entrada de la cual se transmitirán los tokens colapsados.Para hacer esto, en ANTLR puede anular el método org.antlr.v4.runtime.Lexer # nextToken del lexer, donde puede implementar la funcionalidad de convolución: 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 gramática debe complementarse con:startJavaScript
: HashBangLine? jsFileBody? EOF
;
startFoldBlock
: block EOF
;
block
: LBRACE stmtList? RBRACE
| FoldBlock
// ,
// startFoldBlock
;
Con este enfoque, el contenido de la convolución no se procesará una vez más, ya que el algoritmo recursivo absorberá tokens y los guardará.La velocidad de procesamiento aumenta de 2 a 10 veces, la diferencia se vuelve especialmente notable en los archivos js minificados.El impacto en la operación ANTLR de la optimización propuesta usando varios archivos javascript como ejemplo:Sin optimización, el trabajo se lleva a cabo en un hilo, con la optimización, si es posible, el procesamiento es paralelo.El lanzamiento se llevó a cabo en una máquina con 64 GB de RAM, Intel® Core (TM) i7-9700K CPU @ 3.60GHz, OpenJDK Runtime Environment AdoptOpenJDK (compilación 11.0.4 + 11).Claves de inicio JVM: -Xmx4G -XX: + UseG1GC -XX: MaxHeapFreeRatio = 30 -XX: MinHeapFreeRatio = 10Para el archivo tsserver.js, la clave es -Xmx32G, ¡mientras que el consumo de memoria ha alcanzado 22 GB! Si bien los archivos minimizados de hasta 200 kb con optimización se analizan con un límite de almacenamiento dinámico de 128 mb en modo paralelo sin la necesidad de que el recolector de basura cargue el procesador, ¡un máximo del 2%!Perfilado
ANTLR admite la creación de perfiles del analizador / lexer en tiempo de ejecución. Para habilitarlo, debe llamar al método: org.antlr.v4.runtime.Parser # setProfile antes de que se ejecuten las reglas. Luego puede obtener toda la información, por ejemplo de esta manera: 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("=========================")
}
}
Una ventaja obvia con este método es la reducción en la cantidad de datos que necesita analizar, ya que las convoluciones pueden reemplazarse por {} y siempre funcionan en convolución local, lo que acelera enormemente el proceso de optimización de la gramática.Conclusión
Este artículo propone un método para optimizar el trabajo de las gramáticas formales implementadas utilizando la biblioteca ANTLR, aunque el enfoque en sí mismo puede aplicarse también a otras bibliotecas. Una característica de la optimización es la reducción en el número de transiciones hacia adelante para validar la secuencia de tokens de entrada. También le permite analizar archivos grandes (más de 1 mb) a un costo de memoria de 512 mb para el procesamiento de un solo subproceso, mientras que la falta de optimización requerirá 50 veces más memoria para un trabajo rápido con la misma gramática.Código fuente disponible en github. Este proyecto está hecho para demostrar el trabajo de optimización. El proyecto se simplifica tanto como sea posible, se recomienda comenzar el estudio en la clase GrammarTester, se ha realizado una configuración de lanzamiento, solo tendrá que registrar la ruta a la carpeta de entrada. Preste atención a la clave rscan.tester.cache.dir, los archivos temporales se escribirán en esta carpeta, el análisis de archivos exitoso se repara en esta carpeta y no permitirá que el analizador lo analice por segunda vez, lo cual es conveniente para corregir errores. Por el momento, la gramática se ha probado en 17 mil archivos de node_modules creados para la aplicación core react. Solo se ignoraron los node_modules anidados.En el próximo artículo, consideraremos las opciones para organizar los datos y el modelo R (Reflexión) para la representación óptima de los datos de origen como objetos de análisis con un consumo mínimo de memoria, la capacidad de implementar algoritmos de búsqueda para elementos con complejidad O (1) y poder guardar en el disco en forma serializada. todos los objetos, así como las partes de prueba de la herramienta.