Foto per gentile concessione di Kol Tregaskes
Nel primo articolo di questa serie abbiamo visto come awk potrebbe essere utilizzato (o riprodotto) per qualcosa di più della semplice elaborazione del testo. Il semplice script ha dimostrato l'uso di array associativi, la ricorsione e come potremmo usare più array (più del necessario per rappresentare i dati) per velocizzare l'elaborazione. Alla fine erano rimaste alcune idee teaser se stavi cercando qualcosa di più veloce.
Quando avresti bisogno di qualcosa di più veloce? Un lettore ha sottolineato che risolvere gli enigmi è facile. E se stessi progettando un sistema per generare puzzle? Uno degli strumenti di cui avresti bisogno è un programma che assicuri che ci sia una sola soluzione per un puzzle. (Un altro lettore, Milos, ha suggerito lievi modifiche per trovare tutte le soluzioni.) Oppure, se volessimo aumentare le dimensioni dei puzzle a 16×16 o 25×25?
La traduzione dello script in un linguaggio compilato velocemente potrebbe essere d'aiuto e in questo articolo esamineremo uno dei principali vantaggi di awk con la facilità di tradurre in C quando necessario.
Traduzione del primo taglio
Nella nostra prima fase di traduzione del programma mostreremo frammenti di codice fianco a fianco per dimostrare le piccole differenze richieste. Esamineremo le tre funzioni principali che vengono maggiormente colpite; inuse(), mark() e la funzione ricorsiva search(). Il codice è così vicino che è stata utilizzata una copia del programma awk per iniziare la modifica per la conversione in C.
In primo luogo, per eliminare alcune delle definizioni. Utilizzeremo anche la pre-compilazione della regione poiché cerchiamo più velocità. La prima differenza che deve essere affrontata è che gli indici dell'array awk erano uno relativo e per impostazione predefinita gli indici dell'array C sono zero relativi. Per i nostri scopi e per semplificare le cose, continueremo a utilizzare gli indici relativi e ad allocare gli array con elementi aggiuntivi.
#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 ;
} Il confronto tra Awk e C
Ora per approfondire le tre funzioni principali per vedere le somiglianze e le lievi differenze. Le versioni awk originali delle funzioni vengono lasciate come commenti. Ecco alcune delle differenze:
- C richiede dichiarazioni di funzioni, parametri e tipi di variabili
- awk non richiede separatori di istruzioni punto e virgola se è presente una sola istruzione per riga
- awk "falsa" gli array multidimensionali utilizzando array associativi e separando gli indici con il carattere SUBSEP rappresentato con una virgola
- in awk, le dichiarazioni di variabili locali vengono semplicemente inserite con i parametri per la funzione, di solito con spazi extra per separarli per la leggibilità
- i delimitatori dei commenti sono diversi
- le funzioni sono dichiarate in modo diverso
- C usa zero indici relativi per gli array
Tuttavia, puoi vedere una corrispondenza uno-a-uno diretta e tradurre da awk a C è quasi banale in questo esempio.
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
} // }
Bitmap
Una delle chiavi per la velocità a cui si è accennato nell'articolo precedente era l'utilizzo di bitmap per gli array R, C e Q. Poiché ciascuno di questi array viene utilizzato solo per verificare l'appartenenza a un elemento o meno, è rigorosamente una funzione binaria che potrebbe essere rappresentata da un singolo bit anziché da un int. Questo ci ha permesso di verificare se una voce era valida o meno (una delle funzioni più colpite) in pochissimi cicli macchina rispetto ad altri metodi di ricerca.
Ecco alcuni frammenti di codice per mostrare come assomiglia al nostro prototipo awk originale. Le dichiarazioni obbligatorie sono leggermente cambiate rispetto alla versione C originale sopra; abbiamo perso una dimensione per gli array C, R e Q e useremo gli int come array di bit.
----------------------------------------------------------------------------- #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]; -----------------------------------------------------------------------------
Le funzioni mark() e inuse() vengono chiamate molte volte ed è qui che abbiamo bisogno delle ricerche dirette veloci. La funzione mark() è un po' più complessa rispetto alle versioni awk e C originali a causa della manipolazione dei bit che dobbiamo fare. Tuttavia, la funzione inuse() è molto semplice.
-----------------------------------------------------------------------------
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 funzione search() rimane virtualmente invariata rispetto alla versione awk ed è identica alla nostra versione C originale sopra. Abbiamo usato l'occultamento delle informazioni per nascondere il fatto che le altre funzioni usano bitmap per la ricerca.
Linea inferiore
I risultati sui tempi sono interessanti. Entrambe le versioni C sono per mille iterazioni, poiché una singola iterazione era troppo piccola per essere misurata in modo affidabile. Sul nostro sistema otteniamo in media i seguenti risultati per un file di esempio:
- Script awk originale – reale:10.9s, utente:10.2s
- Prima versione C – 1000 iterazioni, reale:21.2s, utente:19.7s
- Seconda versione C con bitmap – 1000 iterazioni, reale:16.4s, utente:15.1s
La versione originale di awk ( solve.awk ) è circa 500 volte più lenta della prima versione C e forse 675 volte più lenta della versione bitmap (usando i tempi dell'utente).
Lo script awk era certamente abbastanza veloce per la maggior parte degli scopi e questo sarà spesso il caso degli script del mondo reale. Quando è necessaria una maggiore velocità, awk può comunque essere utilizzato come strumento di prototipazione efficace. La somiglianza con C in qualche modo rende abbastanza semplice tradurre in questa lingua quando se ne presenta la necessità, il che è un altro grande vantaggio per awk sulle alternative. Tuttavia, non puoi sempre presumere che sarà molto meglio in C. Questo è stato un esempio forzato abbastanza intensivo per la CPU. L'elaborazione del testo, dove awk brilla davvero, è un'altra questione.
Se usato con attenzione, awk a volte può sorprenderci per la sua velocità. Ad esempio, la "saggezza consolidata" è che se puoi fare qualcosa con grep o sed, sarà più veloce di awk. Non necessariamente vero. Uno script sed per l'analisi dei log è stato recentemente sostituito con una versione scritta in awk che era circa 40 volte più veloce e molto più flessibile. Questo fa una grande differenza quando si analizzano decine o centinaia di gigabyte di file di registro. Se c'è interesse, sarà incluso in un prossimo articolo.