Hasta la versión 2 hemos venido usando el magnífico producto de Trolltech, QSA. La verdad es que ha funcionado muy bien y se ha portado como un campeón, pero a la hora de desarrollar AbanQ v3 y ver con detenimiento que podríamos mejorar, hemos visto algunas carencias del motor de script que queríamos solventar, así que hemos desarrollado un QSA con asteroides que trae algunas mejoras, veámoslas.
Más rápido y Ahorra memoria = Menos cansino
QSA incorpora su intérprete de ECMAScript (parecido a JavaScript ), no vamos a entrar en detalle de cómo funciona un intérprete, para el caso nos basta saber que existen una serie de reglas gramaticales que se aplican a un código fuente y que mediante reducciones se van creando los nodos de la gramática que almacenan la información necesaria para ejecutar ese código.
La mayoría de la información que almacenan los nodos de la gramática son cadenas de texto, generalmente correspondientes a literales que se asignan a identificadores de variables, funciones, constantes, etc. Es fácil de prever que el número de cadenas de texto que puede llegar a contener un código medianamente grande es significativo y que una manera eficiente de crearlas y almacenarlas determinará la velocidad de ejecución y consumo de memoria. ¿ Cómo hace esto QSA ?, pues vamos a ver:
Si nos fijamos por ejemplo en una regla de reducción de la declaración de una función:
FunctionDeclaration:
FUNCTION IDENT ‘(’ ‘)’ ResultSignature FunctionBody
{ $$ = new QSFuncDeclNode($2, 0L, $5, $6); delete $2; }
IDENT, es efectivamente una cadena de texto ( el nombre de la función que elige el programador ), que se crea en el analizador léxico con este código:
case Identifier:
if ( (token = QSLookup::find( &mainTable, buffer16, pos16 )) < 0 ) {
qsyylval.ustr = new QString( buffer16, pos16 );
return IDENT;
}
Es decir se hace un new QString( buffer16, pos16 ) cada vez que se encuentra un identificador, ese puntero se pasa al nodo y se elimina; new QSFuncDeclNode($2, 0L, $5, $6); delete $2; ( el $2 hace referencia al parámetro 2 de la regla, es decir a IDENT ). Al crear el objeto nodo, este hace copia de la cadena y la almacena como un atributo suyo. Sólo hemos visto el nodo tipo función, pero es similar para muchos otros nodos que reducen identificadores; variables, vectores, constantes, clases, etc.. Por lo tanto resumiendo, cada vez que el intérprete encuentra un identificador, realiza estos pasos:
- Crear una cadena de texto con new QString en la cabecera de la memoria
- Pasarle el puntero de esa cadena al nodo que debe almacenarla
- El nodo hace copia (profunda) de la cadena
- Cuando el nodo ya ha copiado la cadena de texto, esta se elimina de memoria
Podemos ver varios inconvenientes en esta manera de actuar, el que más llama la atención es el hecho de repetir sin cesar new’s seguidos de delete’s. Esto es muy ineficiente tanto en consumo de memoria (en el siguiente apartado se habla sobre otros inconvenientes que tiene esta manera de actuar con la memoria) como en velocidad de ejecución, sobre todo teniendo en cuenta que hay muchos identificadores que son literales exactamente iguales en distintas partes del código y es una pena que no nos acordemos de los creados con anterioridad, y así no tener que volver a crearlos, hacer copia y después destruirlos.
En el caso del código de AbanQ, es especialmente interesante acordarse de los literales de los identificadores ya que debido a su estructura jerárquica y predefinida se reusan constantemente los nombres, por ejemplo ¿cuantos identificadores del tipo “internat_init”, “oficial_beforeCommit..”, “bufferChanged”, etc.. hay en los scripts de AbanQ?, efectivamente, un mogollón.
Pues pensando, pensando, si tuviéramos algún contenedor donde almacenar las cadenas de texto de los identificadores, y cada una de ellas etiquetada con una clave unívoca, podríamos reutilizarlas ¿no?. Pero además si esa clave unívoca es un número, se la puedo pasar a los nodos que ya no tendrán que copiar la cadena, sólo almacenar esa clave y cuando se vaya a usar realmente la cadena de texto hacer una búsqueda por clave en el contenedor.
Con esto conseguimos:
- Ahorrar memoria ya que las cadenas repetidas sólo se almacenan una vez en el contenedor y los nodos sólo deben almacenar los números clave que hacen referencia a ellas.
- Rapidez de ejecución ya que sólo creamos las cadenas nuevas y no se realizan copias profundas de las mismas en los nodos. Estas copias profundas son lentas, mucho más que el hecho de almacenar simplemente un número.
Bien pues ahora sólo queda elegir que tipo de contenedor usamos y cómo generamos esas claves unívocas.
Como contenedor nuestro planteamiento está pidiendo a gritos una tabla Hash ( QHash ) que almacena pares (Clave, Valor), este tipo de contenedor permite realizar búsquedas muy rápidas y optimiza bastante bien la memoria, el contenedor elegido es QHash(quint32,QString) , o lo que es lo mismo claves tipo entero sin signo de 32 bits que identifican a cadenas de texto.
Para crear las claves unívocas lo ideal sería tener una función inyectiva, o uno a uno, que tomando como entrada una cadena de texto devolviera un numero de 32 bits único para ella. Bien, pues esto que parece tan fácil tiene tela si queremos que esa función sea lo suficientemente rápida cómo para que pase desapercibida. Realmente lo que estamos buscando es una función hash perfecta que garantice que no existan colisiones ( en este caso, una colisión se produce cuando para dos cadenas distintas se genera el mismo número de 32 bits ). La buena noticia es que la funciones hash perfectas existen, la mala es que son muy lentas. También tenemos la opción de usar una función hash no perfecta y asumir un mínimo riesgo de colisión. Calculando ese riesgo vemos que es perfectamente asumible con ciertas funciones hash rápidas y no perfectas, por lo que finalmente hemos decidido que merece la pena usar esta opción. La función elegida es esta:
uint QSLexer::hashUstr( const QString & s )
{
int len = s.length();
if ( !len )
return 0;
uint hash = 0;
for ( int i = 0; i < len; ++i ) {
hash += s[ i ].unicode();
hash += ( hash << 10 );
hash ^= ( hash >> 6 );
}
hash += ( hash < < 3 );
hash ^= ( hash >> 11 );
hash += ( hash < < 15 );
return hash;
}
Esta función es muy rápida y la probabilidad media de colisión es de 1 entre 4.294.967.296 ( 2 elevado a 32 ), aunque realmente esa probabilidad de colisión es aún menor, ya que en la practica se maneja un diccionario bastante reducido de palabras. En resumidas cuentas casi podríamos decir que es más fácil que te toque la lotería del niño que tener una colisión de estas.
Lo que hemos hecho al final es modificar QSA para tener una tabla Hash global a todos los nodos y generar claves para las cadenas de texto de los identificadores que van pasando por el analizador léxico. De esta forma los pasos que realiza el intérprete cuando encuentra un identificador son estos:
- Calcula la clave unívoca de la cadena de texto mediante nuestra función hash.
- Si la clave ya existe en la tabla Hash global no hace nada, de lo contrario la almacena en esta tabla.
-
Le pasa esta clave numérica al nodo que debe almacenarla
El primer paso es muy rápido, y en el segundo para muchos casos sólo se realizará una búsqueda en la tabla, ya que hay muchas probabilidades de que la clave ya exista. El tercero también es muy rápido ya que sólo consiste en almacenar un valor numérico. Parece que hemos ganado algo, en el último apartado veremos si es verdad, ahora veamos lo que dejamos pendiente sobre otros problemas que tenía QSA con la memoria.
Fragmentos de mi memoria
Otro problema que solventa la nueva gestión de las cadenas de texto que acabamos de describir, merece mención especial. El problema es la fragmentación de la cabecera de memoria, también conocida como heap o memoria dinámica. En la implementación original de QSA hemos visto que se repiten hasta la saciedad la creación ( new’s ) y destrucción ( delete’s ) de cadenas de texto, tantas veces como identificadores encuentra el analizador léxico.
Ya sabemos que un new reserva memoria y un delete la libera, en este caso las reservas de memoria en general son excesivamente pequeñas al referenciar en la mayoría de los casos a cadenas de texto cortas, unos pocos bytes. Estos trozos pequeños de memoria se crean en el heap de forma dinámica conforme se demandan y no de forma contigua, generalmente intercalados con otros trozos mas grandes que forzosamente se crean durante la ejecución, al liberarlos se marca como libre el trozo que ocupaban, por lo que al final tenemos muchos trozos pequeños libres dispersados por el heap. Tal y como lo hace la implementación original de QSA al realizar un análisis léxico de mucho código deja plagado el heap de mini-trozos no contiguos de memoria libre, en AbanQ se analiza muchísimo código constantemente por lo que en nuestro caso el problema aún es mas grave si cabe.
El segmento heap aumenta su tamaño cuando se pide reservar un nuevo trozo de memoria que no cabe en un trozo liberado. Siempre que se pueda reubicar una reserva de memoria en un trozo de memoria liberado el heap no crecerá, ya que reusa memoria liberada. Cuando tenemos muchos trozos pequeños no contiguos, que en suma son mucha memoria libre pero que por separado son difíciles de reusar al no poder albergar nuevas reservas de memoria mayores, estamos ante un problema de fragmentación. Al crear trozos tan pequeños se obliga a crecer mucho al segmento heap ya que en la práctica aunque esos trozos están libres es como si estuvieran ocupados al no poder reusarse. Como la memoria no es infinita podemos llegar aun desbordamiento y hacer caer a la aplicación cuando en realidad no se necesita tanta memoria.
En los sistemas Unix se soporta mejor este crecimiento de la memoria dinámica y rara vez se produce un desbordamiento, pero los sistemas Windows lo llevan peor, esta es una de la razones por la que Windows da calabazas cuando AbanQ le pide marcha.
En la nueva implementación esto queda resuelto ya que todas las cadenas se crean una sola vez y se almacenan en una tabla hash que internamente compacta y agrupa sus elementos en memoria contigua, es decir, se usa mucha menos memoria y una vez que se libera es reutilizable.
La prueba del algodón
Ahora tenemos que ver si realmente todo esto ha servido para algo o no. La única manera que se me ocurre es ejecutar código y medir tiempos, tampoco vamos a ser muy exigentes, un par de scripts típicos, no sea que al final nos salgan resultados negativos y nos deprimamos.
Probamos con Fibonacci:
function fibonacci(n) {
if (n == undefined)
throw “Try calling the main function…";
if (n == 0)
return 0;
else if (n == 1)
return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
function oficial_fibo( n:Number ):String
{
var d1 = new Date();
var fib;
for (var x = 0; x < = n; ++x) {
fib = fibonacci(x);
print(’Fibonacci number: ‘ + x + ‘, is: ‘ + fib);
}
var d2 = new Date();
var e = d2.getTime() - d1.getTime();
print( ‘Total time : ‘ + e + ‘ms’ );
}
|
fibo( 22 ) - 22 términos
|
QSA viejo
|
QSA nuevo
|
|
ejecución 1
|
4725ms
|
3456ms
|
|
ejecución 2
|
4687ms
|
3511ms
|
|
ejecución 3
|
4737ms
|
3456ms
|
No está mal
Ahora con un script genérico con consulta SQL:
function prueba()
{
var d1 = new Date();
var res:String = “Version ” + this.version();
var cur:AQSqlCursor = new AQSqlCursor( “divisas” );
cur.select();
while( cur.next() )
res += “n
” + cur.valueBuffer( “descripcion” );
var qry:AQSqlQuery = new AQSqlQuery();
qry.setTablesList( “clientes” );
qry.setSelect( “nombre” );
qry.setFrom( “clientes” );
if ( qry.exec() )
while( qry.next() )
res += “n
” + qry.value( 0 );
var bancos;
bancos = [["0030″, “BANESTO"],["0112″, “BANCO URQUIJO"],
["2085″, “IBERCAJA"],["0093″, “BANCO DE VALENCIA"],
["2059″, “CAIXA SABADELL"],["2073″, “CAIXA TARRAGONA"],
["2038″, “CAJA MADRID"],["2091″, “CAIXA GALICIA"],
["0019″, “DEUTSCHE BANK"],["0081″, “BANCO DE SABADELL"],
["0049″, “BANCO SANTANDER CENTRAL HISPANO"],["0072″, “BANCO PASTOR"],
["0075″, “BANCO POPULAR"],["0182″,"BANCO BILBAO VIZCAYA ARGENTARIA"],
["0128″, “BANKINTER"],["2090″, “C.A.M."],["2100″, “LA CAIXA"],
["2077″, “BANCAJA"],["0008″, “BANCO ATLANTICO"],
["0061″, “BANCA MARCH"],["0065″, “BARCLAYS BANK"],
["0073″, “PATAGON INTERNET BANK"],["0103″, “BANCO ZARAGOZANO"],
["2013″, “CAIXA CATALUNYA"],["2043″,"CAJA MURCIA"],
["2103″, “UNICAJA"],["2105″, “CAJA DE CASTILLA LA MANCHA"],
["0042″, “BANCO GUIPUZCOANO"],["0138″, “BANKOA"],
["3056″, “CAJA RURAL DE ALBACETE"]];
for (var i:Number = 0; i < bancos.length; i++)
res += “
” + bancos[i][0] + ” ” + bancos[i][1];
var d2 = new Date();
var e = d2.getTime() - d1.getTime();
print( ‘Total time : ‘ + e + ‘ms’ );
return res;
}
|
|
QSA viejo (tiempo/memoria)
|
QSA nuevo (tiempo/memoria)
|
|
ejecución 1
|
16ms / 51.4 Mb
|
38ms / 8.7 Mb
|
|
ejecución 2
|
12ms / 51.4 Mb
|
6ms / 8.7 Mb
|
|
ejecución 3
|
13ms / 51.6 Mb
|
6ms / 8.8 Mb
|
La primera vez es mas lento porque carga la tabla hash, luego es el doble de rápido. Con la memoria si que se nota de verdad.
Al parecer si que hemos conseguido algo, pero aún se puede conseguir más, ya lo veremos más adelante.
