Avec l'aimable autorisation de Kol Tregaskes
Dans le premier article de cette série, nous avons vu comment awk pouvait être mis au travail (ou jouer) pour plus que le simple traitement de texte. Le script simple a démontré l'utilisation de tableaux associatifs, la récursivité et comment nous pourrions utiliser plus de tableaux (plus que nécessaire pour représenter les données) pour accélérer le traitement. Il restait quelques idées d'accroche à la fin si vous recherchiez quelque chose de plus rapide.
Quand auriez-vous besoin de quelque chose de plus rapide ? Un lecteur a souligné que résoudre les énigmes est facile. Et si vous conceviez un système pour générer des puzzles ? L'un des outils dont vous auriez besoin est un programme qui garantit qu'il n'y a qu'une seule solution à un casse-tête. (Un autre lecteur, Milos, a suggéré de légères modifications pour trouver toutes les solutions.) Ou, et si nous voulions augmenter la taille des puzzles à 16×16 ou 25×25 ?
Traduire le script dans un langage compilé rapidement peut aider et dans cet article, nous examinerons l'un des principaux avantages d'awk avec la facilité de traduction en C si nécessaire.
Première traduction coupée
Dans notre premier essai de traduction du programme, nous montrerons des extraits de code côte à côte pour démontrer les différences mineures requises. Nous examinerons les trois fonctions principales qui sont le plus touchées ; inuse(), mark() et la fonction récursive search(). Le code est si proche qu'une copie du programme awk pour commencer l'édition pour la conversion en C a été utilisée.
Tout d'abord, pour éliminer certaines des définitions. Nous utiliserons également la pré-compilation de la région car nous recherchons plus de vitesse. La première différence à traiter est que les index de tableau awk étaient un relatif et par défaut, les index de tableau C sont zéro relatif. Pour nos besoins et pour simplifier les choses, nous continuerons à utiliser les index relatifs et à allouer des tableaux avec des éléments supplémentaires.
#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 comparaison entre Awk et C
Examinons maintenant les trois fonctions principales pour voir les similitudes et les légères différences. Les versions awk originales des fonctions sont laissées sous forme de commentaires. Voici quelques-unes des différences :
- C nécessite des déclarations de fonction, de paramètre et de type de variable
- awk ne nécessite pas de séparateurs d'instructions point-virgule s'il n'y a qu'une seule instruction par ligne
- awk "faux" des tableaux multidimensionnels en utilisant des tableaux associatifs et en séparant les index avec le caractère SUBSEP représenté par une virgule
- dans awk, les déclarations de variables locales sont simplement insérées avec les paramètres de la fonction, généralement avec des espaces supplémentaires pour les séparer pour plus de lisibilité
- les délimiteurs de commentaires sont différents
- les fonctions sont déclarées différemment
- C utilise des index relatifs nuls pour les tableaux
Néanmoins, vous pouvez voir une correspondance directe et la traduction de awk en C est presque triviale dans cet exemple.
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
} // }
Bitmaps
L'une des clés de la vitesse évoquée dans l'article précédent était l'utilisation de bitmaps pour les tableaux R, C et Q. Étant donné que chacun de ces tableaux n'est utilisé que pour tester l'appartenance ou non à un élément, il s'agit strictement d'une fonction binaire qui pourrait être représentée par un seul bit au lieu d'un int. Cela nous a permis de tester si une entrée était valide ou non (l'une des fonctions les plus durement touchées) en très peu de cycles machine par rapport aux autres méthodes de recherche.
Voici quelques extraits de code pour montrer comment il ressemble à notre prototype awk original. Les déclarations obligatoires ont légèrement changé par rapport à la version C originale ci-dessus ; nous avons perdu une dimension pour les tableaux C, R et Q et nous utiliserons les entiers comme tableaux 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]; -----------------------------------------------------------------------------
Les fonctions mark() et inuse() sont appelées plusieurs fois et c'est là que nous avons besoin des recherches directes rapides. La fonction mark() est un peu plus complexe que les versions awk et C d'origine en raison des manipulations de bits que nous devons faire. Cependant, la fonction inuse() est très 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 fonction search() reste pratiquement inchangée par rapport à la version awk et est identique à notre version C originale ci-dessus. Nous avons utilisé le masquage d'informations pour dissimuler le fait que les autres fonctions utilisent des bitmaps pour la recherche.
Conclusion
Les résultats de chronométrage sont intéressants. Les deux versions C sont pour mille itérations, car une seule itération était trop petite pour être mesurée de manière fiable. Sur notre système, nous obtenons en moyenne les résultats suivants pour un exemple de fichier :
- Script awk d'origine – réel :10,9 s, utilisateur :10,2 s
- Première version C – 1 000 itérations, réel :21,2 s, utilisateur :19,7 s
- Deuxième version C avec bitmaps :1 000 itérations, réel :16,4 s, utilisateur :15,1 s
La version originale de awk ( solve.awk ) est environ 500 fois plus lente que la première version C et peut-être 675 fois plus lente que la version bitmap (en utilisant les temps utilisateur).
Le script awk était certainement assez rapide pour la plupart des utilisations et ce sera souvent le cas dans les scripts du monde réel. Lorsqu'il y a un besoin de plus de vitesse, awk peut toujours être utilisé comme un outil de prototypage efficace. La similitude avec C à certains égards rend assez simple la traduction dans ce langage lorsque le besoin s'en fait sentir, ce qui est un autre gros avantage pour awk par rapport aux alternatives. Cependant, vous ne pouvez pas toujours supposer que ce sera bien mieux en C. Il s'agissait d'un exemple artificiel assez gourmand en CPU. Le traitement de texte, là où awk brille vraiment, est une autre affaire.
Lorsqu'il est utilisé avec précaution, awk peut parfois nous surprendre par sa rapidité. Par exemple, la « sagesse établie » est que si vous pouvez faire quelque chose avec grep ou sed, ce sera plus rapide que awk. Pas nécessairement vrai. Un script sed d'analyse de journal a été récemment remplacé par une version écrite en awk qui était environ 40 fois plus rapide et beaucoup plus flexible. Cela fait une grande différence lors de l'analyse de dizaines ou de centaines de gigaoctets de fichiers journaux. S'il y a un intérêt, il sera inclus dans un futur article.