c++ - Minimizando el impulso:: tiempos de compilación del espíritu

boost boost-spirit

Question

¿Alguna idea para reducir boost :: spirit compile time?

Acabo de portar un analizador flexible para impulsar :: espíritu. El EBNF tiene alrededor de 25 reglas.

El resultado funciona bien y el rendimiento del tiempo de ejecución es bueno.

¡El problema es que la compilación toma para siempre! Tarda unos diez minutos y requiere casi un gigabyte de memoria. El analizador flexible original compilado en unos segundos.

Estoy usando la versión de impulso 1.44.0 y Visual Studio 2008.

En el artículo de Joel de Guzman "Mejores prácticas" dice

Las reglas con definiciones complejas perjudican gravemente al compilador. Hemos visto reglas que tienen más de cien líneas y nos toma un par de minutos recopilar

Bueno, no tengo nada cerca de ese tiempo, pero mi compilación todavía lleva más de un par de minutos

Aquí está la parte más compleja de mi gramática. ¿Es un candidato para ser dividido en partes más pequeñas, de alguna manera?

 rule
= ( tok.if_ >> condition >> tok.then_ >> *sequel ) [ bind( &cRuleKit::AddRule, &myRulekit ) ]
| ( tok.if_ >> condition >> tok.and_ >> condition >> tok.then_ >> *sequel ) [ bind( &cRuleKit::AddRule, &myRulekit ) ]
;
condition
= ( tok.identifier >> tok.oper_ >> tok.value ) [ bind( &cRuleKit::AddCondition, &myRulekit, _pass, _1, _2, _3 ) ]
| ( tok.identifier >> tok.between_ >> tok.value >> "," >> tok.value ) [ bind( &cRuleKit::AddConditionBetween, &myRulekit, _pass, _1, _3, _4 ) ]
;
sequel
= ( tok.priority_ >> tok.high_ ) [ bind( &cRuleKit::setPriority, &myRulekit, 3 ) ]
| ( tok.priority_ ) [ bind( &cRuleKit::setPriority, &myRulekit, 2 ) ]
| ( tok.interval_ >> tok.value ) [ bind( &cRuleKit::setInterval, &myRulekit, _2 ) ]
| ( tok.mp3_ >> tok.identifier ) [ bind( &cRuleKit::setMP3, &myRulekit, _2 ) ]
| ( tok.disable_ ) [ bind( &cRuleKit::setNextRuleEnable, &myRulekit, false ) ]
;

Comentando partes de la gramática, descubrí con qué parte el compilador pasaba más tiempo.

 set_reading
= tok.set_reading >> +attribute_reading
;
attribute_reading
= ( tok.name_ >> tok.identifier )
[
bind( &cPackage::Add, &myReadings, _pass, _2 )
]
| ( tok.nmea_ >> tok.identifier )
[
bind( &cPackage::setNextNMEA, &myReadings, _2 )
]
| ( tok.column_ >> tok.integer )
[
bind( &cPackage::setNextColumn, &myReadings, _2 )
]
| ( tok.precision_ >> tok.value )
[
bind( &cPackage::setNextPrecision, &myReadings, _2 )
]
| ( tok.unit_ >> tok.identifier )
[
bind( &cPackage::setNextUnit, &myReadings, _2 )
]
| ( tok.value_ >> tok.identifier )
[
bind( &cPackage::setNextValue, &myReadings, _2 )
]
| ( tok.qualifier_ >> tok.identifier >> tok.qual_col_ >> tok.integer )
[
bind( &cPackage::setNextQualifier, &myReadings, _2, _4 )
]
;

No lo llamaría complejo, pero ciertamente es la regla más larga. Así que pensé en intentar dividirlo, así:

 set_reading
= tok.set_reading >> +attribute_reading
;
attribute_reading
= attribute_reading_name
| attribute_reading_nmea
| attribute_reading_col
| attribute_reading_precision
| attribute_reading_unit
| attribute_reading_value
| attribute_reading_qualifier
;
attribute_reading_name
= ( tok.name_ >> tok.identifier ) [ bind( &cPackage::Add, &myReadings, _pass, _2 ) ]
;
attribute_reading_nmea
= ( tok.nmea_ >> tok.identifier ) [ bind( &cPackage::setNextNMEA, &myReadings, _2 ) ]
;
attribute_reading_col
= ( tok.column_ >> tok.integer ) [ bind( &cPackage::setNextColumn, &myReadings, _2 ) ]
;
attribute_reading_precision
= ( tok.precision_ >> tok.value ) [ bind( &cPackage::setNextPrecision, &myReadings, _2 ) ]
;
attribute_reading_unit
= ( tok.unit_ >> tok.identifier ) [ bind( &cPackage::setNextUnit, &myReadings, _2 ) ]
;
attribute_reading_value
= ( tok.value_ >> tok.identifier ) [ bind( &cPackage::setNextValue, &myReadings, _2 ) ]
;
attribute_reading_qualifier
= ( tok.qualifier_ >> tok.identifier >> tok.qual_col_ >> tok.integer ) [ bind( &cPackage::setNextQualifier, &myReadings, _2, _4 ) ]
;

¡Esto ahorra varios minutos del tiempo de compilación total!

Extrañamente, el requisito de memoria pico sigue siendo el mismo, solo se requiere por menos tiempo

Por lo tanto, me siento un poco más esperanzado de que todos mis esfuerzos en aprender boost :: spirit van a valer la pena.

Creo que es un poco extraño que el compilador deba ser guiado tan cuidadosamente de esta manera. Pensé que un compilador moderno habría notado que esta regla era solo una lista de reglas OR independientes.

He pasado la mayor parte de los siete días aprendiendo boost :: spirit y portando un analizador pequeño, pero real, de flex. Mi conclusión es que funciona y el código es muy elegante. Desafortunadamente, el uso ingenuo simplemente expandiendo el código de ejemplo del tutorial para una aplicación real sobrecarga rápidamente el compilador; la memoria y el tiempo necesario para una compilación se vuelven completamente poco prácticos. Aparentemente hay técnicas para manejar este problema pero requieren conocimiento arcano que no tengo tiempo para aprender. Supongo que me quedaré con flex, que puede ser feo y pasado de moda, pero es relativamente simple y rápido como el rayo.

Answer 1

Tengo que llegar a la conclusión de que el impulso: el espíritu, elegante como es, no es una opción viable para muchos problemas de análisis en el mundo real debido a los largos tiempos de compilación que incluso los expertos no pueden solucionar.

A menudo es mejor apegarse a algo como flexión, que puede ser feo y pasado de moda, pero es relativamente simple y rápido como el rayo.

Como ejemplo de lo que considero un problema del "mundo real" aquí está el diagrama del ferrocarril de la parte más importante de un analizador sintáctico que se compila de forma flexible en un par de segundos, pero aumenta: el espíritu todavía resuena después de diez minutos

Answer 2

Un truco que podría sugerir es separar la compilación de los constructores de ambos, su lexer y su gramática. La forma más fácil de lograr esto es dejar solo la declaración de esos constructores en sus respectivos archivos de encabezado y mover la definición de esas funciones a unidades de traducción separadas. Por ejemplo:

grammar.hpp:

template <typename Iterator>
struct grammar : qi::grammar<Iterator>
{
grammar(); // declaration only
// ...
};

grammar_def.hpp:

// This file should not contain anything else.
#include "grammar.hpp"
// Definition of constructor.
template <typename Iterator>
grammar<Iterator>::grammar()
{
// initialize your rules here
}

grammar.cpp:

// This file should not contain anything else.
#include "grammar_def.hpp"
// Explicitly instantiate the constructor for the iterator type
// you use to invoke the grammar (here, as an example I use
// std::string::const_iterator).
typedef std::string::const_iterator iterator_type;
template grammar<iterator_type>::grammar();

Haz lo mismo con el objeto lexer.

Este enfoque requiere un poco más de trabajo que el método directo, pero permite distribuir los requisitos de memoria y tiempo para la compilación general. Otra ventaja de este enfoque es que cualquier cambio en el constructor de gramática no requiere la recompilación de nada excepto el archivo grammar.cpp .

Otro consejo para el lexer: trate de minimizar el uso de token_def<> instancias tanto como sea posible. Necesita usar token_def<> solo cuando desee acceder al valor del token como un atributo durante el análisis. En todos los demás casos, puede salirse con lex::string o lex::char_ para definir sus tokens.