AMIGA REVIEW online
  Uvodná stránka     Software     Hry     Obaly     Download     Kniha návštev     Amiga na PC     Amiga Forever  

Kompilátory jazyka C

Martin 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


© ATLANTIDA Publishing Všechna práva vyhrazena.
Žádna část nesmí být reprodukována nebo jinak šířena bez písemného svolení vydavatele.



Amiga na Vašem PC rychle, snadno a zdarma!


none

AMIGA REVIEW

57 ( 11-12 / 2000 )
56 ( 9-10 / 2000 )
55 ( 7-8 / 2000 )
54 ( 5-6 / 2000 )
53 ( 3-4 / 2000 )
52 ( 1-2 / 2000 )
 
51 ( 12 / 1999 )
50 ( 11 / 1999 )
49 ( 10 / 1999 )
48 ( 9 / 1999 )
46-47 ( 7-8 / 1999 )
45 ( 6 / 1999 )
44 ( 5 / 1999 )
43 ( 4 / 1999 )
42 ( 3 / 1999 )
41 ( 2 / 1999 )
40 ( 1 / 1999 )
 
39 ( 12 / 1998 )
38 ( 11 / 1998 )
37 ( 10 / 1998 )
36 ( 9 / 1998 )
35 ( x / 1998 )
34 ( x / 1998 )
33 ( 1-2 / 1998 )
 
32 ( 11-12 / 1997 )
31 ( 9-10 / 1997 )
30 ( 7-8 / 1997 )
29 ( 6 / 1997 )
28 ( 5 / 1997 )
27 ( 4 / 1997 )
26 ( 3 / 1997 )
25 ( 2 / 1997 )
24 ( 1 / 1997 )
 
23 ( 12 / 1996 )
22 ( 11 / 1996 )
21 ( 10 / 1996 )
20 ( 9 / 1996 )
18-19 ( 7-8 / 1996 )
17 ( 6 / 1996 )
16 ( 5 / 1996 )
15 ( 4 / 1996 )
14 ( 3 / 1996 )
13 ( 2 / 1996 )
12 ( 1 / 1996 )
 
11 ( 12 / 1995 )
10 ( 11 / 1995 )
9 ( 10 / 1995 )
8 ( 9 / 1995 )
7 ( 7 / 1995 )
6 ( 5 / 1995 )

ATLANTIDA NEWS

5 ( 3 / 1995 )
4 ( 1 / 1995 )
 
3 ( 11 / 1994 )
2 ( 9 / 1994 )
1 ( 7 / 1994 )
0 ( 5 / 1994 )