Foto s laskavým svolením:Kol Tregaskes
V prvním článku této série jsme viděli, jak by awk mohl fungovat (nebo hrát) pro více než jen zpracování textu. Jednoduchý skript demonstroval použití asociativních polí, rekurze a toho, jak bychom mohli použít více polí (více, než je nutné k reprezentaci dat), abychom urychlili zpracování. Pokud byste hledali něco rychlejšího, na konci zbyly nápady na upoutávky.
Kdy byste potřebovali něco rychlejšího? Jeden čtenář poukázal na to, že řešení hádanek je snadné. Co kdybyste navrhovali systém pro generování hádanek? Jedním z nástrojů, které byste potřebovali, je program, který zajistí, že existuje pouze jedno řešení hádanky. (Další čtenář, Miloš, navrhl drobné úpravy, aby našel všechna řešení.) Nebo co kdybychom chtěli zvětšit velikost hádanek na 16×16 nebo 25×25?
Překlad skriptu do rychle kompilovaného jazyka může pomoci a v tomto článku prozkoumáme jednu z hlavních výhod awk se snadným překladem do C, když je to nutné.
Překlad prvního střihu
V našem prvním kroku při překladu programu ukážeme úryvky kódu vedle sebe, abychom demonstrovali požadované drobné rozdíly. Prozkoumáme tři hlavní funkce, které jsou nejvíce zasaženy; inuse(), mark() a funkce rekurzivního vyhledávání(). Kód je tak blízko, že byla použita kopie programu awk pro zahájení úprav pro převod do C.
Za prvé, aby některé definice z cesty. Použijeme také předkompilaci regionu, protože chceme vyšší rychlost. První rozdíl, který je třeba řešit, je ten, že indexy pole awk byly jeden relativní a indexy pole C jsou ve výchozím nastavení nulové relativní. Pro naše účely a abychom věci zjednodušili, budeme i nadále používat relativní indexy one a alokovat pole s dalšími prvky.
#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 ;
} Porovnání Awk s C
Nyní se ponořte do tří hlavních funkcí, abyste viděli podobnosti a drobné rozdíly. Původní awk verze funkcí jsou ponechány jako komentáře. Zde jsou některé z rozdílů:
- C vyžaduje deklarace funkcí, parametrů a typů proměnných
- awk nevyžaduje oddělovače příkazů středníkem, pokud je na řádku pouze jeden příkaz
- awk „falšuje“ vícerozměrná pole pomocí asociativních polí a oddělováním indexů znakem SUBSEP reprezentovaným čárkou.
- v awk jsou deklarace lokálních proměnných jednoduše vloženy s parametry funkce, obvykle s mezerami navíc, které je oddělují kvůli čitelnosti.
- oddělovače komentářů se liší
- funkce jsou deklarovány odlišně
- C používá pro pole nulové relativní indexy
Nicméně můžete vidět přímou osobní korespondenci a překlad z awk do C je v tomto příkladu téměř triviální.
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
} // }
Bitmapy
Jedním z klíčů k rychlosti zmiňovaným v předchozím článku bylo použití bitmap pro pole R, C a Q. Vzhledem k tomu, že každé z těchto polí se používá pouze k testování příslušnosti k prvku nebo ne, jedná se výhradně o binární funkci, která by mohla být reprezentována jedním bitem namísto int. To nám umožnilo otestovat, zda je záznam platný nebo ne (jedna z nejhůře zasažených funkcí) ve velmi malém počtu strojových cyklů ve srovnání s jinými metodami vyhledávání.
Zde je několik úryvků kódu, které ukazují, jak se podobá našemu původnímu prototypu awk. Povinná prohlášení se oproti původní verzi C mírně změnila; ztratili jsme dimenzi pro pole C, R a Q a budeme používat ints jako bitová pole.
----------------------------------------------------------------------------- #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]; -----------------------------------------------------------------------------
Funkce mark() a inuse() jsou volány mnohokrát a to je místo, kde potřebujeme rychlé přímé vyhledávání. Funkce mark() je o něco složitější než verze awk a původní verze C, protože musíme dělat bitovou práci. Funkce inuse() je však velmi jednoduchá.
-----------------------------------------------------------------------------
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) ;
}
----------------------------------------------------------------------------- Funkce search() zůstává prakticky nezměněna od verze awk a je identická s naší původní verzí C výše. Použili jsme skrytí informací, abychom zakryli skutečnost, že ostatní funkce používají k vyhledávání bitmapy.
Sečteno a podtrženo
Výsledky načasování jsou zajímavé. Obě verze C jsou pro tisíc iterací, protože jediná iterace byla příliš malá na to, aby se dala spolehlivě změřit. V našem systému dostáváme pro ukázkový soubor v průměru následující výsledky:
- Původní skript awk – skutečný:10,9 s, uživatel:10,2 s
- První verze C – 1000 iterací, skutečné:21,2 s, uživatel:19,7 s
- Druhá verze C s bitmapami – 1000 iterací, reálná:16,4 s, uživatelská:15,1 s
Původní verze awk (solv.awk) je asi 500x pomalejší než první verze C a možná 675x pomalejší než bitmapová verze (s použitím uživatelských časů).
Skript awk byl určitě dostatečně rychlý pro většinu účelů a to bude často případ reálných skriptů. Pokud existuje požadavek na vyšší rychlost, může být awk stále použit jako účinný nástroj pro vytváření prototypů. Díky podobnosti s C v některých ohledech je překlad do tohoto jazyka v případě potřeby poměrně jednoduchý, což je další velké plus pro awk oproti alternativám. Nemůžete však vždy předpokládat, že v C to bude mnohem lepší. Toto byl vymyšlený příklad s poměrně náročným CPU. Zpracování textu, kde awk opravdu září, je věc druhá.
Při opatrném používání nás může awk občas překvapit svou rychlostí. Například „zavedená moudrost“ je, že pokud můžete něco udělat s grep nebo sed, bude to rychlejší než awk. Nemusí to být nutně pravda. Skript sed analýzy protokolu byl nedávno nahrazen verzí napsanou v awk, která byla asi 40krát rychlejší a mnohem flexibilnější. To je velký rozdíl při analýze souborů protokolu v hodnotě desítek nebo stovek gigabajtů. Pokud bude zájem, bude součástí budoucího článku.