Kompilátory jazyka CMartin Mareš
Pokračování z minulého čísla Finále
Říká se, že to nejlepší nakonec. Na poslední (a snad konečně rozhodující)
test jsme si připravili program, který jako své parametry dostane čísla, ta
setřídí klasickou metodou bublinkového třídění a vypíše setříděná. Vypadá takto: int main(int argc, char **argv)
/* Parametry z příkazové řádky */
{
int *x; /*Pole na mezivýsledky */
int i,j,k,c,a; /* Pomocné proměnné */
c = argc-1; /* Počet čísel */
x = malloc(sizeof(int)*c);
/*Alokujeme pomocné pole */
if (!x) return 10; /* Fuj! Došla paměť. */
for(i=1; i<argc; i++) /* Naplníme pole čísly */
x[i-1] = atol(argv[i]);
i = c-1; /* Horní mez pro porovnávání */
do
{ /* A třídíme... */
k = 0; /* k: došlo k záměně */
for(j=0; j<i; j++) /* Jeden průchod */
if (x[j] > x[j+1]) /* Nesprávné pořadí sousedů? */
{
a = x[j]; /* Prohodíme */
x[j] = x[j+1];
x[j+1] = a;
k = 1; /* Ano, došlo k záměně */
}
i--
}; /* Snížíme horní mez */
while (k); /* A pokračujeme, je-li třeba */
for(i=0; i<c; i++) /* Vypíšeme výsledek */
printf("%d
", x[i]);
return 0; /* A konec */
} A naši finalisté?
Nejprve SAS/C: subq.w #8 sp
movem.l d4-d7/a3-a5,-(sp)
move.l a0,a3 ; A3=argv
move.l d0,d7 ; D7=argc
move.l d7,d6 ; Db=c (argc-1)
subq.l #1,d6
move.l db,d0 ; D0=c
asl.l #2,d0 ; D0=c*sizeof(int)
bsr @malloc ; D0=malloc()
move.l d0,a5
tst.l d0 ; Kontrola
bne.s lab1
moveq #10,d0 ; Došla paměť
bra.s final
lab1: moveq #1,d5 ;Plníme pole, D5=i
moveq #4,d4 ; D4=offset v cílovém poli
bra.s lab3
lab2: move.l (a3,d4.1),a0 ; A0=argv[i]
bsr @atol ; D0=atol()
move.l d0,-4(a5,d4.1) ; x[i-1 ] = atol()
lab3: addq.l #1,d5 ; i++
addq.l #4,d4 ; D4 posuneme na další prvek
cmp.l d7,d5 ; Konec?
blt.b lab2
move.l db,d7 ; D7=i (c-1)
subq.l #1 d7
lab4: moveq #0,dS ; Smyčka do: D5=k
moveq #0,d4 ; D4=j
move.l a5,a3 ; A3=&x[j]
bra.s lab7
lab5: move.l 4(a3),d0 ; Porovnáváme x[j] a x[j+1 ]
move.l (a3),dl
cmp.l d0,d1
ble.s lab6
move.l d0,(a3) ; Prohazujeme
move.l d1,4(a3)
moveq #1,d5 ; k=1
lab6: addq.l #l,d4 ; j++
addq.l #4,a3 ; Posouváme &x[j] na další prvek
lab7: cmp.l d7,d4 ; Ještě dále?
blt.s lab5
subq.l #1,d7 ; Další průchod hlavní smyčkou...
tst.l d5
bne.s lab4
moveq #0,d7 ; A vypisujeme...
bra.s lab9
lab8: move.l (a5)+,-(sp) ; Jedno číslo
pea txt(pc)
bsr _printf
addq.l #8,sp
addq.l #1,d7
lab9: cmp.l d6 d7 ; Další?
blt.b lab8
moveq #0,d0 ; A konec
final: move.l (sp)+,d4-d7/a3/a5
addq.l #8,sp
rts
txt: dc.b %d,10,0 Několik zajímavých pozorování: SAS/C si na začátku rezervovalo 8 bytů na
zásobníku pravděpodobně pro uložení nějakých proměnných, ale ať prohlížíte
program, jak prohlížíte, žádné se tam nikde neukládají. Na druhou stranu je
potěšující, že SAS/C elegantně využilo hodnoty zbylé v registrech po dřívějších
částech programu a že ve smyčkách si mimo indexů polí uchovává i adresy
zpracovávaných prvků, takže je nemusí stále podle indexů počítat. Celková délka
kódu činí 140 bytů. Řešení dle GCC:
movem.l d2-d3/a2-ab,-(sp)
move.l 32(sp),d2 ; D2=argc
move.l d2,a6 ; Ab=argc
subq.l #l,a6 ; A6=c (argc-1)
move.l a6,d0
asl.l #2,d0 ; DO=c*sizeof(int)
move.l d0,-(sp) ; Parametr na zásobník
jsr _malloc ; DO=malloc()
addq.l #4 sp
cmp.w #0,a5 ; Došla paměť?
bne.s L6
moveq #10,40
bra.s L27
L6: move.w #1,a3 ; A3=počáteční hodnota indexu "i"
cmp.l a3,d2 ; Již konec?
ble.s L8
lea 4(a5),a4 ; &x[1]
move.l 36(sp),a2 ; A2=&argv
addq.l #4 a2 ; A2=&argv[1 ]
L10: move.l (a2)+,-(sp) ; Parametr: argv[i]
jsr _atol ; D0=atol()
move.l d0 -4(a4) ; x[i-1 ] = atol()
addq.w #4,sp ; Odstraníme parametr
addq.w #4,a4 ; Další prvek
addq.w #1 a3 ; Další index
cmp.l a3,d2 ; Ještě jeden?
bgt.s L10
L8: lea -1(ab),a3 ; A3=i (c-1)
L12: moveq #0,d0 ; D0=0
moveq #0,d1 ; D1=j
cmp.l d0,a3
ble.s L16 ; Vnitřní cyklus by se neprovedl
move.l a5 a0 ; A0=&x[0]
L18: lea 4(a0),al ; AO=&x[i], A1=&x[i+l ]
move.l (a0),d3 ; Porovnáme sousední prvky
cmp.l (a1),d3
ble.s L17
move.l d3,d0 ; Prohazujeme [*]
move.l (a1),(a0)
move.l d0,(a1)
moveq #1,d0
L17: move.l a1,a0 ; Další prvek...
addq.l #1,d1
cmp.l d1,a3
bgt.s L18
L16: subq.w #1 ,a3 ; Jedeme dál vnějším cyklem...
tst.l d0
bne.s L12
sub.l a3,a3 ; A vypisujeme
cmp.l a3,a6
ble.s L23
move.l a5,a2
L25: move.l (a2)+,-(sp) ; Parametry pro printf
pea txt
jsr _printf
addq.w #8,sp
addq.w #1,a3 ; A další...
cmp.l a3,a6
bgt.s L25
L23: moveq #0,d0 ; Končíme
L27: movem.l (sp)+,d2-d3/a2-a6
rts
txt: dc.b %d,10,0 Tento výpis ukazuje rovněž několik zajímavostí: Jednak GCC porušilo běžné
zvyklosti a uložilo některá numerická data do adresových registrů, což se
ukázalo být užitečným (pěkné použití instrukce LEA pro přiřazení a zároveň
odečtení v jednom kroku), na druhou stranu to však předvedlo, že GCC není
schopno efektivně testovat nulovost adresového registru (elegantně to jde pomocí
MOVE do některého z registrů datových). Rovněž pak v jednom případě (označen
[*]) zcela zbytečně přesunulo data do jiného registru, i když bylo možno použít
hodnotu v registru původním.
Stejně jako u SAS/C, i zde je vidět vcelku efektivní uchovávání adres aktuálních
prvků polí místo jejich stálého počítání z indexů. Sympatické je, že ve vnitřní
smyčce byl pro přechod na další prvek použit pouhý MOVE již předtím používané
adresy dalšího prvku. Navíc GCC elegantně využívá četné adresní módy Motoroly.
Všechny smyčky jsou rozvinuty tak, že se neprovádí skok ze začátku na konec.
Toto rozvinutí program mírně urychluje, ovšem za cenu mírného prodloužení kódu.
Celková délka programu je 172 bytů, což je způsobeno zejména neefektivním
předáváním parametrů přes zásobník a rozvinutím podmínek cyklů. Mezitím stihl
dopsat svůj program i náš favorit, programátor assemblerský (opět s použitím
těchž knihoven): movem.l d2-d5/a2-a3/a5-ab,-(sp)
movem.l 36(sp),a2/a3 ; A2=argc, A3=argv
moveq #-1,d2
add.l a2,d2 ; D2=c
beq.s final ; Nemáme co řešit
move.l d2,d0
subq.l #1,d2 ; D2=c-1
lsl.l #2,d0 ; D0=sizeof(int)*c
bsr @malloc ; Alokujeme paměf tst.l d0
bne.s l1
moveq #10,d0
bra.s done
l1: move.l d0,a2 ; A2=adresa pole x
move.l a2,a6 ; Ab=&x[i] při plnění
move.w d2,d3 ; D3=počitadlo při plnění
addq.l #4,a3 ; Plníme pole...
l2: move.l (a3)+,a0 ; A0=argv[i]
bsr @atol
move.l d0,(ab)+
dbf d3,12
move.w d2,d5 ; D5=c-1
l3: subq.w #1,d2 ; D2=i
bmi.s 16
moveq #0,d3 ; D3=k
move.w d2,d4 ; D4=i-j
move.l a2,a3 ; A3=&x[j]
lea 4(a2),a5 ; A5=&x[j+l ]
l4: move.l (a5)+,d0 ; Porovnáme sousedy
cmp.l (a3)+,d0
bcc.s l5
move.l -(a3),-4(a5) ; Prohodíme
move.l d0,(a3)+
moveq #1,d3
l5: dbf d4,14 ; A další...
tst.l d3
bne.s l3
l6: move.l (a2)+,-(sp) ; Vypisujeme
pea form(pc)
bsr _printf
addq.l #8,sp
dbf d5,l6
final: moveq #0,d0
done: movem.l (sp)+,d2-d5/a2-a3/a5-ab ; Konec
rts
form: dc.b %d,10,0 V tomto programu je použito několik pěkných triků: Jednak se hned na začátku
otestuje, zda je vůbec co řešit, čímž se odstraní testy podmínek na počátku
každého z cyklů a zůstanou pouze ty na jejich koncích. Rovněž se ve všech
případech elegantně využívá instrukce DBF pro realizaci smyček. Zejména samotný
vnitřní cyklus je napsán velice elegantně a je daleko rychlejší než konkurenční
produkty kompilátorů. Velikost kódu dosahuje 124 bytů. (Poznámka autora: Autor
si v žádném případě neodvažuje tvrdit, že v assembleru to lépe napsat nelze.
Jedná se mu pouze o typický příklad z praxe.) Na stupních vítězů
A jak již to u závodů bývá, někteří z účastníků po skončení stanou na
stupních vítězů. V našem případě se tam dostanou všichni, nebol byli pouze tři.
Na prvním místě jásá náš assemblerista (ale ještě že se dneska závodilo na délku
a ne na čas, který byl potřeba na napsání a odladění programu), o místo druhé a
třetí se svorně dělí GCC a SAS/C - oba kompilátory odvedly vcelku dobrý výkon a
předvedly nám, že jejich kód není zase tak mizerný, na druhou stranu se ovšem
ukázaly jejich slabiny, a těch nebylo zrovna málo.
A chcete-li na závěr slyšet nějaké ponaučení, pak vizte, že není všechno zlato,
co se třpytí, a že vskutku dobrý a rychlý, téměř optimální kód asi přes všechny
pokroky computer science získáte pouze úmornou ruční tvorbou v assembleru. Na
druhou stranu se ovšem říká, že účel světí prostředky, a tak není-li v daném
případě na škodu mírně delší a mírně pomalejší program, klidně sáhněte po
kompilátoru "céčka" a ušetřete si tak dost práce. Vytlačiť článok
Pozn.: články boli naskenované ako text a preto obsahujú aj zopár chýb. Taktiež neručíme za zdrojové kódy (Asm, C, Arexx, AmigaGuide, Html) a odkazy na web. Dúfame, že napriek tomu vám táto databáza dobre poslúži.
Žiadna časť nesmie byť reprodukovaná alebo inak šírená bez písomného povolenia vydavatela © ATLANTIDA Publishing
none
|