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 ]

Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙