InfoC adventi naptár

Duff's device

Tegyük fel, hogy egy megadott méretű memóriaterületet kell másolnunk. Példaprogramként szerepeljen itt egyszerűen egy sztring, aminek előre tudjuk a hosszát. count a másolandó bájtok száma; to a cél mutató, from a forrás mutató. Minden bájt átmásolása (*to=*from) után mindkét pointert meg kell növelni eggyel (to++, from++), hogy a következő bájtokra mutassanak. Mindezt annyiszor, amennyi a másolandó bájtok száma:

#include <stdio.h>
#include <string.h>

int main() {
    char f[]="hellohellohellohellohellohellohello", t[40];
    int count;
    char *to=t, *from=f;

    for (count=strlen(f)+1; count>0; count--)
        *to++=*from++;

    printf("%s\n", t);
    return 0;
}

A program „hasznos” részei a ciklus törzsébe, a „haszontalan” részei pedig a fejlécbe kerültek. Egy bájt másolásához a számunka fontos művelet az értékadás, és a két pointer növelése. Tulajdonképp haszontalan a count változó csökkentése, amelyet minden bájt másolása után elvégzünk; ennek maradandó nyoma nem marad a memóriában, csak azért van rá szükség, hogy tudjuk, hányszor kell végrehajtani a ciklus belsejében lévő kódrészletet. Ugyancsak haszontalan az eredmény szempontjából az összehasonlítás (count>0), amelyet úgyszint minden karakter után megcsinálunk; és az ugrás, hogy a ciklus törzse után vissza kell mindig ugrani a feltétel ellenőrzéséhez. Az érdekesség kedvéért álljon itt az optimalizálás nélkül generált assembly kód. Nem olyan vészes, meg lehet érteni a működést, ha megsejtjük, mit jelentenek az utasítások:

        call    strlen              ; strlen hívása (call)
        addl    $1, %eax            ; 1 hozzáadása (addition)
        movl    %eax, -100(%rbp)    ; az eredmény írása a count változóba
        jmp     .L2                 ; ugrás a feltétel ellenőrzéséhez (jump)
.L3:
        movq    -120(%rbp), %rax    ; from pointer a memóriából
        movzbl  (%rax), %edx        ; mutatott bájt beolvasása
        movq    -112(%rbp), %rax    ; to pointer
        movb    %dl, (%rax)         ; bájt írása
        addq    $1, -112(%rbp)      ; to növelése
        addq    $1, -120(%rbp)      ; from növelése
        subl    $1, -100(%rbp)      ; count csökkentése (subtraction)
.L2:
        cmpl    $0, -100(%rbp)      ; count = 0?  (compare)
        jg      .L3                 ; ugrás ha nagyobb (jump if greater)

Valami ilyesmi. Látható, hogy a ciklus megszervezése miatt sok a járulékos művelet minden egyes bájt másolásához. Az ugrás, hogy a ciklustörzs újabb végrehajtásához annak elejére kell lépnie a processzornak, különösen kártékony. A mai processzorok képesek egyszerre több utasítást feldolgozni párhuzamosan; amikor azonban a kódban egy ugrás van, akkor a félig már feldolgozott (memóriából már beolvasott, esetleg már dekódolt) utasításokat el kell dobni.

Ha a ciklus törzsét leírnánk egymás után annyiszor, ahányszor kell, akkor ezeket a járulékos műveleteket meg tudnánk spórolni:

…
*to++=*from++;
*to++=*from++;
*to++=*from++;
*to++=*from++;
*to++=*from++;
…

Ez az assemblyben programozásnál közismert technika (loop unrolling vagy loop unwinding). Ha nem ismerjük előre a másolandó bájtok számát, ez akkor is könnyen megoldható: a bájtmásolások sorozatának közepére ugorva. Érdekes ilyen szempontból a C nyelv, ugyanis ez abban is megvalósítható, ha elhagyjuk a switch()-ből a break-eket, amelyik kiugrana a vezérlési szerkezet közepéből. A switch() lényegében egy táblázatos goto-nak felel meg, ahol az egyes címkéket a case kulcsszavak határozzák meg. A lenti kód count=0…10 értékeire működik helyes adatmásolóként:

switch (count) {
    case 10: *to++=*from++;
    case  9: *to++=*from++;
    case  8: *to++=*from++;
    case  7: *to++=*from++;
    case  6: *to++=*from++;
    case  5: *to++=*from++;
    case  4: *to++=*from++;
    case  3: *to++=*from++;
    case  2: *to++=*from++;
    case  1: *to++=*from++;
    case  0: /* itt mar nem kell semmit */
}

Általánosítás

A C-ben a switch()-case szerkezetet ténylegesen egy táblazatos goto. Olyannyira, hogy a switch() szerkezetesen belül bármilyen, szintaktikailag helyes utasítássorozat szerepelhet, amelyben az egyes utasítások közé szúrhatóak a case-ek. Még azt is megengedi a nyelv, hogy egy ciklus belsejébe beugorjunk egy goto utasítással. És még azt is, hogy egy ciklus belsejébe ugorjunk egy case-es címkével! Tom Duffnak a következő ötlete támadt ezzel kapcsolatban. A fenti, maximum tíz bájtot másolni képes kódrészlet a következő módon általánosítható:

#include <stdio.h>
#include <string.h>

int main() {
    char f[]="hellohellohellohellohellohellohello", t[40];
    int count=strlen(f)+1;

    register char *to=t, *from=f;
    register int n=(count+7)/8;
    switch (count%8) {
        do {
            case 0: *to++=*from++;
            case 7: *to++=*from++;
            case 6: *to++=*from++;
            case 5: *to++=*from++;
            case 4: *to++=*from++;
            case 3: *to++=*from++;
            case 2: *to++=*from++;
            case 1: *to++=*from++;
        } while(--n>0);
    }

    printf("%s\n", t);

    return 0;
}

A fenti kódrészlet úgy működik, hogy a másolásokat 8-as csoportokra osztja. Az n változó tárolja, hogy hányszor kell végrehajtani a 8-as másolást (vagyis hányszor 8 bájtról van szó). Ha a másolandó terület mérete nem osztható 8-cal, akkor pedig a switch(count%8) segítségével a másolás belsejére ugrik; oda, hogy pont annyi bájt kerüljön át pluszba, amekkora a nyolcas csoportokhoz képest a maradék. A register kulcsszóval arra lehet utalni a fordítónak, hogy azt a változót esetleg érdemes a processzor egyik regiszterébe tenni, mivel gyakran használja a program.

Jó ez? Igen is meg nem is. Elvileg gyorsabb, hiszen a másolásokhoz tartozó járulékos műveletek számát nyolcadára csökkentettük. A kód olvashatósága viszont romlott. Továbbá az egyes fordítók eltérő hatékonysággal képesek kezelni a szokatlan kódot. Van, amelyik lassabban futó assembly kódot generál. Legtöbbször jobb ezt éppen ezért a fordítóra bízni: megfelelő optimalizálási beállítások mellett a jó fordítók automatikusan használják az ilyen trükköket.