Nil Satis Nisi Optimum

Blog.
Magamnak.
Sok dolog elveszett már az elmúlt évek alatt.
Tehát mondjuk online archiválok. Mondjuk ide. Próba szerencse.
Adott egy feladat: talán kétrétegű rajzolás lehetne a neve. Adott egy NxM pixel méretű 32 bites kép, amelyre rajzolni kell, de csak bizonyos mintában, amelyet egy 8x4 bites érték ír le: minden sorhoz egy 8 bites minta tartozik, amely ahol 1, az adott pixelen felül kell írni az eredeti képet a layeren lévő rajzzal, hacsak az nem egy előre kijelölt 'háttérszín'; és minden 4 sorhoz tartozik egy ismétlődő minta.
A megvalósítási ötlet szerint mivel egy kép nem tartalmazhat 32 bites negatív pixel értéket (32 bites megjelenítés megkövetelt, ez alatt nincs értelme a SETDIBITSTODEVICE forrásadatában negatív értéket megadni), így a kisegítő layer (amire első körben a rajzolás történik) háttérszíne tetszőleges negatív szám lehet. A kisegítő layer legyen ugyancsak NxM-es tömb, erre lefutnak a módosítás nélküli rajzolási eljárások a kívánt pixeleket felülírva benne a megfelelő színre, ezután fésüljük össze a két 'képet' az adott minta szerint.
pushad mov ecx,{képszélesség} mov ebx,{rajzolási maszk} mov esi,{layer címe} push {képmagasság} shl ecx,02h mov edi,{célkép címe} mov edx,ecx mov ebp,ebx @inner: sub ecx,04h js @outer ror bl,01h mov eax,[esi+ecx] mov dword ptr [esi+ecx],-1 jnc @inner test eax,eax jl @inner mov [edi+ecx],eax jmp @inner @outer: ror ebp,08h add edi,edx add esi,edx sub dword ptr [esp],01h mov ecx,edx mov ebx,ebp jnz @inner @exit: add esp,04h popad ret
Több ponton is bele lehet kötni a fentiekbe:
- a Core 2 processzorok LSD-je 4x16 byte-nyi utasítást tud tárolni, benne legfejlebb 4 ugró utasítással, ret nélkül; a fenti @inner ciklus az @outer ciklussal együtt is bőven beleférne a 64 byte-ba, viszont 5 ugró utasítás van benne; ha egyet eliminálni lehetne, akkor a szükséges adatok egyszeri beolvasása után sosem kell a teljes kép feldolgozása során az L1 I-cache-hez fordulni.
- a K8 CPU-k optimalizálási leírását bogarászva kitűnik, hogy a hardware prefetcher-e a cache-vonalakat csak növekvő sorrendben tudja előbetölteni, a fenti eljárás viszont egy adott képsoron visszafelé halad, mivel az @inner ciklusban az offszet (ecx) csökken.
pushad mov ecx,{képszélesség} xor edx,edx mov ebx,{rajzolási maszk} mov esi,{layer címe} push {képmagasság} shl ecx,02h mov edi,{célkép címe} not ebx sub edx,ecx mov ebp,ebx @outer: sub edi,edx sub esi,edx sub dword ptr [esp],01h mov ebx,ebp lea ecx,[edx-04h] ror ebp,08h js @exit @inner: or eax,-1 add ecx,04h jns @outer xor eax,[esi+ecx] mov dword ptr [esi+ecx],-1 ror bl,01h jbe @inner not eax mov [edi+ecx],eax jmp @inner @exit: add esp,04h popad ret
A következő változások történtek:
- a korábbi "a layer háttérszíne tetszőleges negatív szám lehet" feltétel szűkült arra, hogy csakis -1 lehet
- az @outer ciklus is elöltesztelős lett: átlép a következő sor elejére, így az @inner 0 felé egyre közelítő negatív offszettel fér a két tömb pixeleihez.
- az @inner ciklusban eggyel kevesebb ugrás található, viszont miután az XOR -1,x utáni ROR reg,01h nem változtatja a ZF-et (sem, csak az OF-et és CF-et), így a JBE (jump if below or equal = jump if CF = 1 or ZF = 1) mindkét feltételt egyszerre kezeli; ehhez viszont bit-negálni kell a maszkot a ciklusok előtt.
Ilyen jellegű megoldás nem létezik magas szintű programozási nyelvekben.
A következőkben nem történt változás:
- a 8 használható regiszter közül csak háromnak változik az értéke az @inner ciklusban, ezért képsoronként egyszer a Core 2 belefut az @outer ciklus elején a registerfile-olvasási korlátjába, mivel EDI, ESI, EDX, ESP és EBP is 'befagyott' register-nek tekinthető.
- ha lenne még egy szabad register, amelyben a -1 konstans tárolható lenne, akkor 1+1+2 byte-tal kisebb lenne a két ciklus kódja, ez x64 alatt megoldható lenne.
Az elméleti nyereség:
- bármilyen egyszerű hardware prefetcher-rel ellátott microarchitecture esetén a két tömbön végigmenni minimális L1/L2 cache-tévesztéssel jár (az is nagyrészt csak a 4 KB-os lapok miatt van)
- teljesen üres layer esetén csakis a jns @outer ugrásánál lehet téveszteni (soronként egyszer)
- teljesen kitöltött layer esetén a ror bl,01h bizonyos, 8 esetenként ismétlődő minta szerint dolgozik, amit a többszintű ugrás-előrejelzőknek illik lekezelni
- az algoritmus jól kezeli a layer folyamatos huzamosabb háttér- ill. előtér sorozatait, viszont a gyakori váltásokat nem (ott jobban teljesít az első algoritmus).
A gyakorlati nyereség: K8 és két, különböző (Kb. 80% és 10%) kitöltöttségű ~2 megapixeles kép+layer esetén TSC-rel kimérve 25M/33M-ról 15M/24M órajel.
[ Szerkesztve ]