Foto cortesía:Kol Tregaskes
En el primer artículo de esta serie, vimos cómo se podía poner a trabajar (o reproducir) awk para algo más que solo procesar texto. El script simple demostró el uso de arreglos asociativos, la recursividad y cómo podríamos usar más arreglos (más de los necesarios para representar los datos) para acelerar el procesamiento. Quedaron algunas ideas preliminares al final si buscaba algo más rápido.
¿Cuándo necesitaría algo más rápido? Un lector señaló que resolver los acertijos es fácil. ¿Qué pasaría si estuvieras diseñando un sistema para generar rompecabezas? Una de las herramientas que necesitará es un programa que asegure que solo hay una solución para un rompecabezas. (Otro lector, Milos, sugirió ligeras modificaciones para encontrar todas las soluciones). O, ¿qué pasaría si quisiéramos aumentar el tamaño de los rompecabezas a 16×16 o 25×25?
Traducir el script a un lenguaje compilado rápido podría ayudar y en este artículo examinaremos uno de los principales beneficios de awk con la facilidad de traducir a C cuando sea necesario.
Traducción del primer corte
En nuestro primer intento de traducir el programa, mostraremos fragmentos del código uno al lado del otro para demostrar las diferencias menores requeridas. Examinaremos las tres funciones principales que son las más afectadas; inuse(), mark() y la función de búsqueda recursiva(). El código está tan cerca que se usó una copia del programa awk para comenzar a editar para la conversión a C.
Primero, para sacar algunas de las definiciones del camino. También usaremos la precompilación de la región ya que buscamos más velocidad. La primera diferencia que debe tratarse es que los índices de matriz awk eran uno relativo y, por defecto, los índices de matriz C son cero relativos. Para nuestros propósitos y para simplificar las cosas, continuaremos usando los índices relativos uno y asignaremos matrices con elementos adicionales.
#define SUBORDER 3
#define ORDER (SUBORDER * SUBORDER)
#define MARK 1
#define UNMARK 0
int count = 0;
unsigned int regmap[ORDER+1] [ORDER+1];
unsigned int master[ORDER+1] [ORDER+1];
unsigned int C[ORDER+1][ORDER+1];
unsigned int R[ORDER+1][ORDER+1];
unsigned int Q[ORDER+1][ORDER+1];
#define fregmap(r,c) (regmap[r][c])
/* precompile region map for faster lookup
*/
int initregmap()
{
int i,j;
for (i = 0; i < ORDER ; i++)
for (j = 0; j < ORDER ; j++)
regmap[i+1][j+1] = i/SUBORDER*SUBORDER + j/SUBORDER +1 ;
} La comparación de Awk con C
Ahora a profundizar en las tres funciones principales para ver las similitudes y ligeras diferencias. Las versiones awk originales de las funciones se dejan como comentarios. Estas son algunas de las diferencias:
- C requiere funciones, parámetros y declaraciones de tipos de variables
- awk no requiere separadores de declaraciones de punto y coma si solo hay una declaración por línea
- awk "falsa" arreglos multidimensionales usando arreglos asociativos y separando los índices con el carácter SUBSEP representado con una coma
- en awk, las declaraciones de variables locales simplemente se incluyen con los parámetros de la función, generalmente con espacios adicionales para separarlas y facilitar la lectura
- los delimitadores de comentarios son diferentes
- las funciones se declaran de manera diferente
- C usa cero índices relativos para arreglos
Sin embargo, puede ver una correspondencia directa uno a uno y traducir de awk a C es casi trivial en este ejemplo.
inline int inuse(r,c,try) // function inuse(r,c,try) {
int r,c,try; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
return (R[r][try] || C[c][try] || Q[q][try]); // return (C[c,try] || R[r,try] || Q[q,try])
} // }
inline void mark(r,c,try, flag) // function mark(r,c,try, flag, q) {
int r,c,try, flag; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
Q[q][try] = flag; // Q[q,try] = flag
R[r][try] = flag; // R[r,try] = flag
C[c][try] = flag; // C[c,try] = flag
master[r][c] = flag ? try : 0 ; // master[r,c] = flag ? try : 0
} // }
int search(r,c) // function search(r,c, q,i,a,try) {
int r,c; //
{ //
int q,i,a,try; //
count++ ; // count++
//
while (master[r][c]) { // while (master[r,c]) {
if (++c > ORDER) { // if (++c > ORDER) {
c = 1 ; // c = 1
if (++r > ORDER) { // if (++r > ORDER) {
/* then we're done filling */ // # then we're done filling!
return 1 ; // return 1
} // }
} // }
} // }
//
for (try=1; try <= ORDER; try++) { // for (try=1; try <= ORDER; try++) {
if (! inuse(r,c,try)) { // if (! inuse(r,c,try)) {
mark(r,c,try, MARK) ; // mark(r,c,try, 1)
if (search(r,c)) return 1 ; // if (search(r,c)) return 1
/* else zero returned -- unwind, unmark */ // # else zero returned -- unwind
mark(r,c,try, UNMARK) ; // mark(r,c,try, 0) # unmark
} // }
} // }
//
return 0; // return 0
} // }
Mapas de bits
Una de las claves de la velocidad mencionada en el artículo anterior fue el uso de mapas de bits para las matrices R, C y Q. Dado que cada una de estas matrices solo se usa para probar la pertenencia o no del elemento, es estrictamente una función binaria que podría representarse con un solo bit en lugar de un int. Esto nos permitió probar si una entrada era válida o no (una de las funciones más afectadas) en muy pocos ciclos de máquina en relación con otros métodos de búsqueda.
Aquí hay algunos fragmentos de código para mostrar cómo se parece a nuestro prototipo awk original. Las declaraciones obligatorias han cambiado ligeramente con respecto a la versión C original anterior; hemos perdido una dimensión para las matrices C, R y Q y usaremos los enteros como matrices de bits.
----------------------------------------------------------------------------- #define SUBORDER 3 #define ORDER (SUBORDER * SUBORDER) unsigned int regmap[ORDER+1] [ORDER+1]; unsigned int master[ORDER+1] [ORDER+1]; unsigned int C[ORDER+1]; unsigned int R[ORDER+1]; unsigned int Q[ORDER+1]; -----------------------------------------------------------------------------
Las funciones mark() e inuse() se llaman muchas veces y aquí es donde necesitamos las búsquedas directas rápidas. La función mark() es un poco más compleja que las versiones awk y C original debido a la manipulación de bits que necesitamos hacer. Sin embargo, la función inuse() es muy simple.
-----------------------------------------------------------------------------
void mark(r,c,try, flag)
int r,c,try, flag;
{
unsigned bitmap = (1 << try) ;
int q = fregmap(r,c);
if (flag) {
Q[q] |= bitmap ;
R[r] |= bitmap ;
C[c] |= bitmap ;
}
else {
Q[q] &= ~bitmap ;
R[r] &= ~bitmap ;
C[c] &= ~bitmap ;
}
master[r][c] = flag ? try : 0 ;
}
int inuse(r,c,try)
int r,c,try;
{
int q = fregmap(r,c);
unsigned bitmap = 1 << try;
return ((R[r] | C[c] | Q[q]) & bitmap) ;
}
----------------------------------------------------------------------------- La función de búsqueda () permanece prácticamente sin cambios desde la versión awk y es idéntica a nuestra versión C original anterior. Hemos utilizado la ocultación de información para ocultar el hecho de que las otras funciones usan mapas de bits para la búsqueda.
Conclusión
Los resultados de tiempo son interesantes. Ambas versiones de C son para mil iteraciones, ya que una sola iteración era demasiado pequeña para medirla de manera confiable. En nuestro sistema, obtenemos los siguientes resultados en promedio para un archivo de muestra:
- Script awk original:real:10,9 s, usuario:10,2 s
- Primera versión C:1000 iteraciones, real:21,2 s, usuario:19,7 s
- Segunda versión C con mapas de bits:1000 iteraciones, real:16,4 s, usuario:15,1 s
La versión original de awk ( solve.awk ) es aproximadamente 500 veces más lenta que la primera versión C y quizás 675 veces más lenta que la versión de mapa de bits (utilizando los tiempos de usuario).
La secuencia de comandos awk ciertamente fue lo suficientemente rápida para la mayoría de los propósitos y este suele ser el caso en las secuencias de comandos del mundo real. Cuando existe un requisito de mayor velocidad, awk aún puede usarse como una herramienta de creación de prototipos efectiva. La similitud con C en algunos aspectos hace que sea bastante sencillo traducir a este idioma cuando surge la necesidad, lo cual es otra gran ventaja de awk sobre las alternativas. Sin embargo, no siempre se puede suponer que será mucho mejor en C. Este fue un ejemplo artificial bastante intensivo de CPU. El procesamiento de texto, donde awk realmente brilla, es otra cuestión.
Cuando se usa con cuidado, awk a veces puede sorprendernos con su velocidad. Por ejemplo, la "sabiduría establecida" es que si puedes hacer algo con grep o sed, será más rápido que awk. No necesariamente cierto. Recientemente se reemplazó un script sed de análisis de registro con una versión escrita en awk que era unas 40 veces más rápida y mucho más flexible. Esto marca una gran diferencia cuando se analizan decenas o cientos de gigabytes de archivos de registro. Si hay interés, se incluirá en un próximo artículo.