[cstex] Rychlejsi implementace mergesortu

[petr-brezina at volny.cz]

Vazeni kolegove,

trosku jsem si pohral se svym konickem a naucil ho behat zase o neco
rychleji. Ve srovnani se svymi predvanocnimi vysledky dokaze nyni zvladnout
Velkou pardubickou (sto tisic ruznych hesel) skoro o dve a pul minuty
rychleji! Muzete vyzkouset; misto zaplaty sort-p.tex se nacte zaplata
sort-p2.tex, dostupna opet na mych strankach, http://www.volny.cz/petr-brezina/

Toto zrychleni spociva v tom, ze jsem vytvoril a do behaciho ustroji
sveho konicka zabudoval vykonnejsi implementaci makra mergesort. Pokusim
se vysvetlit, proc je tato implementace vykonnejsi. Petr Olsak ve sve
implementaci makra mergesort, kterou jsem s malymi upravami prejal pred
Vanoci do prvni zaplaty, pouzil jako buffer pevnou skatulku. Nevyhodou
je, ze doba potrebna pro postupne naplneni takove skatulky roste se
ctvercem poctu polozek. Jestlize pri razeni tisice polozek trva nekolikere
plneni bufferu par desetin vteriny, pri razeni deseti tisic polozek
najednou to uz dela desitky zbytecnych vterin. Tento efekt lze zmirnit
razenim po mensich skupinach (viz registr \bufsize), takove reseni muze
vsak s sebou prinest zpomaleni jineho druhu.

Ve druhe zaplate jsem se proto uchylil k jedne sve myslence z puvodni
verze makra sort: polozky jsou ulozeny v pameti TeXu jednotlive jako
definice s vhodne zvolenymi identifikatory, diky nimz lze polozky vselijak
seskupovat. Mam-li polozky schovany napr. v definicich s identifikatory
\csname entry-1\endcsname
\csname entry-2\endcsname
\csname entry-3\endcsname
a znam-li cislo v poslednim identifikatoru, pak je snadne pomoci prikazu
\let presouvat polozky z bufferu "entry" do bufferu "mentry", a kdyz
se tento naplni, zase zpatky do bufferu "entry" atd. V tomto pojeti
je jeden buffer mnozina definic \csname entry-i\endcsname, kde "i" je
cislo od jedne do cisla, ktere odpovida poctu polozek a je ulozeno v
registru specialne pro tento ucel vyhrazenem; podobne druhy buffer je
mnozina definic \csname mentry-i\endcsname. Protoze je nutne v tomto
systemu identifikatoru udrzovat poradek a take pamatovat si cisla urcitych
pozic v bufferu, kod makra mergesort se stal o neco slozitejsi; vymenou
za to vsak pracuje rychleji, coz ocenime zejmena u delsich rejstriku.

Pri razeni seznamu deseti tisic polozek bylo razeni se druhou zaplatou
o tri vteriny rychlejsi nez s prvni zaplatou. Sto tisic polozek se seradilo,
jak jiz jsem uvadel, skoro o dve a pul minuty rychleji pri srovnani
nejrychlejsich casu prvni a druhe zaplaty. Zde je dobre zastavit se
u registru \bufsize. Druha zaplata snasi dobre vysoke hodnoty tohoto
registru, samozrejme pokud to pametove moznosti TeXu dovoli. Pri razeni
sto tisic polozek bylo s prvni zaplatou vhodne nastavit \bufsize=2000;
pri vyssich hodnotach se celkova doba razeni vyrazne zpomalovala. Druha
zaplata pri \bufsize=2000 jeste zdaleka nedosahla nejvyssi rychlosti;
trideni zde bylo rychlejsi "jen" o necelou minutu a pul. Nejvyssi rychlost
mela asi pri \bufsize=14500, pak rychlost pozvolna klesala.

Registr \bufsize urcuje maximalni pocet polozek, ktere TeX zpracovava
najednou v pameti. Kazda polozka zabere v hlavni pameti TeXu misto odpovidajici
velikosti teto polozky a krome toho jsou pro ni vyhrazeny ctyri identifikatory
ridicich sekvenci. Asi drive nez hlavni pamet prekrocime maximalni povoleny
pocet ridicich sekvenci. V me instalaci TeXu neni povoleno vice nez
asi 260 tisic ridicich sekvenci, takze celych sto tisic polozek nelze
v pameti najednou setridit. To vsak nijak nebrani setridit stotisicovy
nebo jakkoli jinak velky rejstrik. TeX jej setridi po tak velkych skupinach,
jak mu dovolime prostrednictvim registru \bufsize. Jakmile ve sve pameti
setridi jednu skupinu polozek, zaradi ji do vystupniho souboru timto
zpusobem: nejdrive zatridi prvni polozku z teto skupiny, pak druhou,
treti atd.; protoze vsak polozky ve skupine jsou setridene, nemusi pri
zarazovani kazde polozky prochazet vystupni soubor cely znovu od zacatku,
nybrz pokracuje od mista, kam zaradil predchozi polozku. Registr \bufsize
je tedy vyznamny ze dvou hledisek: 1.~diky spojeni "bufferoveho" a "souboroveho"
trideni umoznuje tento registr vykalibrovat celkovou rychlost trideni;
2.~diky trideni po skupinach lze tridit libovolne dlouhe rejstriky treba
i na archaickych strojich s emTeXem.

Na konec makra jsem zaradil prikaz, kterym se po skonceni razeni uvolni
z pameti jiz nepotrebne veci. TeX sice neumi odstranit ze sve pameti
identifikatory ridicich sekvenci, lze vsak odstranit definice, ktere
jsou s temito identifikatory asociovany. Takto uvolnenou cast pameti
muzeme pozdeji vyuzit pro litery tiskoveho materialu nebo pro nove definice,
nikoli vsak pro boxy ani pro jiny tiskovy material nez litery. TeX totiz
pracuje se dvema oblastmi hlavni pameti: "variable-size memory" a "one-word
memory", o nichz nas informuje pri kazdem \shipout, mame-li nastaveno
\tracingstats na hodnotu vyssi nez jedna. Do oblasti "one-word memory"
uklada tokeny a jednotlive litery tiskoveho materialu, zatimco do "variable-size
memory" uklada ostatni tiskovy material. Z dosud nevyuziteho mista v
hlavni pameti prideluje podle potreby misto jedne nebo druhe oblasti.
Jakmile vsak nejake misto prideli, toto misto zustava te ci one oblasti
natrvalo (tedy i kdyz se uvolni).

Olsakovo pojeti bufferu ma tu vyhodu, ze z nej lze snadno vyjmout duplicitni
polozky, takze pri dalsich pruchodech neprekazeji. V mem bufferu to
patrne dost dobre mozne neni, protoze by se tim rozhodil system skupin,
na nemz je mergesort zalozen; proto kdykoli se narazi na dve stejne
polozky, je (po slouceni jejich "textu") jedna z nich oznacena jako
prazdna, aby mohla byt v dalsich pruchodech preskakovana; uloha takove
prazdne polozky spociva jen v tom, ze dorovnava pocet polozek ve skupine.
(U Olsaka jsou jednotlive skupiny rozpoznavany podle oddelovacu (carek),
kdezto u me podle poctu polozek.)

Poznamka o norme abecedniho razeni. Dozvedel jsem se, ze soucasna statni
norma pro ceske abecedni razeni (alespon v interpretaci Ustavu pro jazyk
cesky, viz http://prirucka.ujc.cas.cz/ ) nestanovuje jednoznacne vzajemne
poradi dvou hesel, ktera se lisi pouze velikosti pismen; napr. hesla
"Kniha" a "kniha" muzete v rejstriku radit treba podle sve aktualni
nalady. Takove nejednoznacne normalizovani se mi nejevi jako prilis
stastne. Me makro sort a s nim dodavana tridici tabulka pro cestinu
vychazi ze starsi normy v interpretaci Petra Olsaka, viz Zpravodaj 3/94;
je zde pro rozliseni velkych a malych pismen vyuzito tretiho pruchodu,
pricemz velka pismena se radi az za mala. To neni nikterak v rozporu
se soucasnou normou; pouze se tim do pripadu, kdy soucasna norma pripousti
libovolne poradi, vnasi pevny rad. Lze tedy konstatovat, ze makro sort
(velmi pravdepodobne) radi v souladu s platnou statni normou. Musim
vsak podotknout, ze jsem se detailnim porovnanim obou norem nezabyval.

Na zaver se slusi poznamenat, ze jsem take v prvni zaplate (sort-p.tex)
od jejiho prvniho zverejneni provedl jeste nekolik drobnych uprav.

S pozdravem

Petr Brezina