Hirdetés

2019. augusztus 22., csütörtök

Hozzászólások

(#1) P.H.


P.H.
(Topikgazda)

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 ˙˙˙

(#2) P.H.


P.H.
(Topikgazda)

A Write-Combining pufferekből privát cache-be csak a rendszermemórián kereszül kerülhet adat, oda és vissza egyaránt, közvetlen kapcsolat nincs ~ olvasott cache-line felülírása non-termporal módon tilos.

@SSE2rewriteALPHA:
add ebp,ebx
jns @retirePERFORM
cmp [esi+ebp],eax
jz @SSE2rewriteALPHA
movd xmm2,[esi+ebp]
movd xmm3,[edi+ebp]
punpcklbw xmm2,xmm7
punpcklbw xmm3,xmm7
punpcklwd xmm2,xmm7
punpcklwd xmm3,xmm7
cvtdq2ps xmm2,xmm2
mov [esi+ebp],eax <<<----
cvtdq2ps xmm3,xmm3
mulps xmm2,xmm0
mulps xmm3,xmm1
addps xmm2,xmm3
cvtps2dq xmm2,xmm2
packssdw xmm2,xmm2
packuswb xmm2,xmm2
movd [edi+ebp],xmm2
jmp @SSE2rewriteALPHA

K8 lefutás ~2 megapixeles képen 5% layer-kitöltöttség mellett 9M órajel, mov [esi+ebp],eax utasítás helyett movnti [esi+ebp],eax írva 11M órajel.

Vajon
- ez igaz a hardware prefetch-elt cache-vonalakra is?
- az L3-mak jelenléte változtat a dolgon K10 és főleg Nehalem (inclusive) esetén?
- ez csak az DL1-re igaz, vagy a VIA-féle prefetch cache tartalmára is?

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

(#3) P.H.


P.H.
(Topikgazda)

A 32 bites non-temporal store-ok K8-as megvalósítása hagy némi kívánnivalót, a sima x86 tárolássorozat gyorsabb (VectorPath REP STOSD kizárt).

@unpackSSE2:
movnti [edi],eax
add edi,04h
add ebp,ecx
jnz @unpackSSE2
@unpckSSE2:
add ebx,04h
mov eax,edx
mov ebp,[esi+ebx]
jg @fenceUNPACK
and eax,ebp
and ebp,ecx
jmp @unpackSSE2
@@UNPACKBMP: <<- entry
lea eax,{tömörített adatra mutató pointer}
cmp dword ptr [eax],00h
jz @exitUNPACK
pushad
mov edi,{célkép}
mov esi,[eax]
mov ecx,0FF000000h
mov ebx,[esi-04h]
lea esi,[esi+ebx-04h]
neg ebx
cmp {van_SSE2?},cl
jnz @unpckSSE2
jmp @unpck
@unpack:
mov [edi],eax
add edi,04h
add ebp,ecx
jnz @unpack
@unpck:
add ebx,04h
mov eax,edx
mov ebp,[esi+ebx]
jg @returnUNPACK
and eax,ebp
and ebp,ecx
jmp @unpack
@fenceUNPACK:
sfence
@returnUNPACK:
popad
@exitUNPACK:
ret 00h

8 megapixeles kép esetén:
K8:
- előkészített REP STOSD: 153M órajel
- @unpackSSE2 (movnti [edi],eax): 68M órajel
- @unpack (mov [edi],eax): 62M órajel
Netburst (Prescott):
- előkészített REP STOSD: 410M órajel
- @unpackSSE2 (movnti [edi],eax): 110M órajel

64 byte-os cache-line jutó 3-nál több ugró utasítás hatása elhanyagolható, a code-padding befolyása jelentősebb nála.

kérdés: esetleges téves elágazásbecslés miatt lefutott sfence-eknek van teljesítményvisszafogó hatásuk, vagy el kell távolítani az ágat a critical path közeléből?

[ Szerkesztve ]

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

(#4) P.H.


P.H.
(Topikgazda)

32->8 bit signed szaturált érték létrehozása ugrással hatékonyabb, mint anélkül. A

{input:EAX output:AL}
mov edx,000000FFh
cmp eax,edx
jc @done
shr eax,1Fh
add al,cl
@done:

kód gyorsabb K8-on és Netburst-on egyaránt, mint a

{input:EAX output:DL}
mov ecx,000000FFh
cmp eax,ecx
mov edx,ecx
sbb ebx,ebx
adc dl,cl
and ebx,eax
add eax,eax
adc dl,bl

Netburst-ön érthető, hogy miért gyorsabb, de K8-on? Ott 5 órajel lenne az utóbbi.

MMX nélkül nehéz az élet.

Az előző kérdésre a válasz: nincs, az sfence sorbarendező utasítás.

[ Szerkesztve ]

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

(#5) P.H. válasza P.H. (#3) üzenetére


P.H.
(Topikgazda)

Update:

K8:
- előkészített REP STOSD: 153M órajel
- @unpackSSE2 (movnti [edi],eax): 68M órajel
- @unpack (mov [edi],eax): 62M órajel
Netburst (Prescott):
- előkészített REP STOSD: 410M órajel
- @unpackSSE2 (movnti [edi],eax): 110M órajel
- @unpack (mov [edi],eax): 150M órajel

Ez némi gondolkodnivalót ad a VectorPath, illetve úgy általában a microcode alapú utasításokról. A REP STOSD legrosszabb esetben is egyenértékű a

@stosd:
jcxz @done
dec ecx
mov [edi],eax
lea edi,[edi+04h]
jmp @stosd
@done:

sorozattal akár micro-op szinten is: a "service pending interrupts (if any);" lépést és (a debugger-ek tanulsága szerint) ESP-t befolyásoló ugrást mindkettő tartalmaz. A microcode-on alapuló utasítások micro-opjai a microarchitecture szélességére optimalizáltak, de mennyi az az ismétlésmennyiség, aminél a REP STOSD gyorsabb, mint a klasszikus legalapvetőbb egyszerű ciklus? Van egyáltalán ilyen eset?

[ Szerkesztve ]

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

(#6) P.H.


P.H.
(Topikgazda)

Két PCHAR vagyis null-terminated karaktersorozat kisbetű/nagybetű azonosságú összehasonlítására Windows alatt az lstrcmpi utasítás helyett (ami Windows NT-k alatt a lokalizáció miatt a natív unicode-formátumára konvertálja belül a két forrás string-et az összehasonlításhoz minden hívás alkalmával, ehhez előtte végigmegy rajtuk a hosszuk meghatározásához, stb.) célszerűbb a következő:

1. valahol a program indításakor elhelyezni egy 256 elemű _uppercase karakterbömtöt, feltölteni a 256 karakterrel, majd rá kiadni a

CHARUPPERBUFF(@_uppercase,256) ;

utasítást,

2. a programban elhelyezni a következő függvényt:

{ EAX: src0 string address
EDX: src1 string address }
pushad
xor esi,esi
xor edi,edi
mov ebx,offset(_UPPERCASE)
add esi,eax
jz @finalize
add edi,edx
jz @finalize
@compare:
xor eax,eax
xor edx,edx
xor ecx,ecx
add al,[esi]
lea esi[esi+01h]
mov dl,[edi]
mov al,[ebx+eax]
jz @final
add cl,[ebx+edx]
lea edi,[edi+01h]
jz @finalize
cmp al,cl
jz @compare
@finalize:
cmp eax,edx
popad
setz al ; elhagyható ASM szinten
ret

- procedure STREQUAL(src1,src2: PCHAR): boolean; magas szinten
- csak a string egyenlőséget/nemegyenlőséget adja vissza BOOL formában, viszont a kisebb/nagyobb relációt is az EFLAGS-ben
- a NULL pointer mindig a legkisebb a relációban
- ha egyik bemenő paramétere NULL, a másik egy 00h byte-ra mutató érvényes pointer, akkor nem egyenlőek, a NULL kisebb

[ Szerkesztve ]

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

(#7) P.H. válasza P.H. (#6) üzenetére


P.H.
(Topikgazda)

hotfix:

{ EAX: src0 string address
EDX: src1 string address }
pushad
xor esi,esi
xor edi,edi
mov ebx,offset(_uppercase)
add esi,eax
jz @finalize
add edi,edx
jz @finalize
@compare:
xor eax,eax
xor edx,edx
xor ecx,ecx
add al,[esi]
lea esi[esi+01h]
mov dl,[edi]
mov al,[ebx+eax]
jz @final
add cl,[ebx+edx]
lea edi,[edi+01h]
jz @finalize
cmp al,cl
mov dl,cl
jz @compare
@finalize:
cmp eax,edx
popad
setz al ; elhagyható ASM szinten
ret

A "viszont a kisebb/nagyobb relációt is az EFLAGS-ben" törölve (_uppercase átszerkesztés kell hozzá, mert z<ő)

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

(#8) P.H.


P.H.
(Topikgazda)

Minő örömmel töltheti el a felhasználót, hogy amennyiben a Microsoft nem unicode-os API-hívásokkal fordítja saját software-eit (pl. a Windows Explorer, Live Messenger, ...cmd.exe), úgy néha megáll az élet 256 hosszú path-ok felett...

Eset: Windows Live Messenger, Shared Folder-be jönne egy file, ez először egy ideiglenes helyre kerül, majd a teljes átvitel után kerül a valós Shared Folder-be, aminek útvonala ezen a gépen a


H:\Documents and Settings\Administrator\Local Settings\Application Data\Microsoft\Messenger\ph2000@axelero.hu\Sharing Folders\xxxxxxxx@xxxxxxxx.hu

Ám a Windows kellemetlen szokása, hogy szereti az ideiglenes file-okat kvázi véletlenszerűen elnevezett vagy class ID-t tartalmazó mappákban/file-okban tárolni, jelen esetben a


H:\Documents and Settings\Administrator\Local Settings\Application Data\Microsoft\Messenger\ph2000@axelero.hu\SharingMetaData\xxxxxxxx@xxxxxxxx.hu\DFSR\Staging\CS{CA0CF46C-3723-B71A-CE04-F0655DF3F9BE}\48\

mappa alatti


48-{B287AD73-60BB-4C0A-9DD7-E10CE71C4C9D}-v48-{B287AD73-60B8-4C0A-9DD7-E10CE71C4C9D}-v48-Partial.frx

nevű file lenne az. Mivel a mappa neve még 256 karakternél rövidebb, viszont a file-névvel együtt az útvonal már messze hosszabb, ezzel maga a Live Messenger sem tud mit kezdeni az átvitel után, egyszerűen nem tudja áttenni a végleges helyére, pedig a partner szerint 100% feltöltöttséget mutat. A file-on sem Cut/Paste, sem Rename, sem Delete nem segít, sem az, ha a partner törli a Shared Folder-éből, csak a következő utasítássorozat:


subst z: H:\Documents and Settings\Administrator\Local Settings\Application Data\Microsoft\Messenger\ph2000@axelero.hu\SharingMetaData\xxxxxxxx@xxxxxxxx.hu\DFSR\Staging\CS{CA0CF46C-3723-B71A-CE04-F0655DF3F9BE}\48

del *.*

subst z: /d

[ Szerkesztve ]

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

(#9) P.H.


P.H.
(Topikgazda)

Under investigation: 2D gráfpont koordinátaszámítás (nagyítás + eltolás) és vágás több százezer ponton.

- x87-es kiindulási megoldás (extended precision):

@init:
fldz
@coor:
movzx eax,word ptr [edi+STRUCTURE.RSIZE]
mov cx,[LIMIT]
sub edx,01h
lea edi,[edi+eax+STRUCTURESIZE]
fstp st(0)
jle @sections
or byte ptr [edi+STRUCTURE.BITFIELD],$80
cmp [edi+STRUCTURE.RSIZE],cx
fld dword ptr [edi+STRUCTURE.X]
jle @coor
fmul st,st(3)
mov al,[BITFILTER]
fld dword ptr [edi+STRUCTURE.Y]
xor ecx,ecx
mov [esi],edi
fmul st,st(4)
fxch
test [edi+STRUCTURE.BITFIELD],al
fsub st,st(3)
mov eax,[IMAGEWIDTH]
fistp dword ptr [edi+STRUCTURE.XCOOR]
mov ebp,[IMAGEHEIGHT]
fsub st,st(1)
mov [esi+04h],ecx
fist dword ptr [edi+STRUCTURE.YCOOR]
jnz @coor
sub eax,[edi+STRUCTURE.XCOOR]
mov ecx,[edi+STRUCTURE.YCOOR]
or eax,[edi+STRUCTURE.XCOOR]
sub ebp,ecx
or eax,ecx
or eax,ebp
js @coor
and byte ptr [edi+STRUCTURE.BITFIELD],$7F
add esi,04h
jmp @coor
@sections:
...

- SSE2 (double precision):

@initSSE:
mov bp,[LIMIT]
mov cl,[BITFILTER]
mov bl,[edi+STRUCTURE.BITFIELD]
@coorSSE:
movzx eax,word ptr [edi+STRUCTURE.RSIZE]
sub edx,01h
mov [edi+STRUCTURE.BITFIELD],bl
movapd xmm3,xmm4
lea edi,[edi+eax+STRUCTURESIZE]
mov bl,$80
jle @sectionSSE
cvtps2pd xmm0,[edi+STRUCTURE.X]
or bl,[edi+STRUCTURE.BITFIELD]
cmp [edi+STRUCTURE.RSIZE],bp
mulpd xmm0,xmm2
jle @coorSSE
subpd xmm0,xmm1
cvtpd2dq xmm0,xmm0
test bl,cl
psubd xmm3,xmm0
movq [edi+STRUCTURE.XCOOR],xmm0
jnz @coorSSE
por xmm3,xmm0
pmovmskb eax,xmm3
test al,88h
jnz @coorSSE
and bl,$7F
movnti [esi],edi
add esi,04h
jmp @coorSSE
@sectionSSE:
xor eax,eax
sfence
mov [esi],eax
...

- 3DNow! (single precision):

@init3DNow:
mov bp,[LIMIT]
mov cl,[BITFILTER]
mov bl,[edi+STRUCTURE.BITFIELD]
@coor3DNow:
movq mm0,mm2
movzx eax,word ptr [edi+STRUCTURE.RSIZE]
sub edx,01h
mov [edi+STRUCTURE.BITFIELD],bl
movq mm3,mm4
lea edi,[edi+eax+STRUCTURESIZE]
mov bl,$80
jle @section3DNow
pfmul mm0,[edi+STRUCTURE.X]
or bl,[edi+STRUCTURE.BITFIELD]
cmp [edi+STRUCTURE.RSIZE],bp
pfsub mm0,mm1
jle @coor3DNow
pf2id mm0,mm0
test bl,cl
psubd mm3,mm0
movq [edi+STRUCTURE.XCOOR],mm0
jnz @coor3DNow
por mm3,mm0
pmovmskb eax,mm3
test al,88h
jnz @coor3DNow
and bl,$7F
mov [esi],edi
add esi,04h
jmp @coor3DNow
@section3DNow:
xor eax,eax
emms
mov [esi],eax
...

A sorrend (TSC alapján):
- K8: 1.SSE2 2:3DNow! 3:x87 (kb. 5% eltéréssel)
- Netburst: 1:x87 2.SSE2 (elhanyagolható eltéréssel)

:F

[ Szerkesztve ]

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

(#10) P.H.


P.H.
(Topikgazda)

A korábbi pár munkaórás skiccek után egy valódi nagypálya, amelyben már több 10 munkaóra fekszik: a következő kódnak 100 megapixeles képeket kellene kezelnie 1 másodpercen belüli időhatárral; jelenleg 32 megapixeles képen tesztelve bőven megvan az 1 másodperc, de gyorsabbnak érződik 2.26 GHz-es CeleronD-n, mint 2.2 GHz-es Opteron-on. Első lépésben a kép erőteljesen tömörítve lesz, és talán vissza lesz az algoritmus írva integer alapra (MMX/SSE2), a színhelyesség megtartásával.

A kiindulási kód:

@decode:
movd esi,mm5
movd edx,mm4
movd ecx,mm7
movd ebx,mm6
movss xmm0,[ebp]
@temprow:
movzx eax,byte ptr [esi]
add esi,01h
shl eax,04h
sub edx,01h
movaps xmm3,[ecx+eax]
movaps [ebx],xmm3
lea ebx,[ebx+20h]
jg @temprow
add esi,[esp+_SROW]
mov ecx,edi
movd mm5,esi
mov edx,[ebp+08h]
@zoomvertSSE:
and edi,-32
movd esi,mm6
add edi,20h
shufps xmm0,xmm0,00000000b
movd eax,mm4
movaps xmm1,[edi]
@prevHpixelSSE:
movaps xmm4,[esi-00h]
movlps xmm2,[esi-10h]
mov ebx,[esi-10h+08h]
mulps xmm4,xmm0
shufps xmm2,xmm2,01000000b
movaps xmm3,xmm4
@pixelSSE:
test ebx,ebx
mulps xmm4,xmm2
@1pixelSSE:
addps xmm1,xmm4
jz @nextHpixelSSE
movaps [edi],xmm1
js @stepHelementSSE
add edi,10h
movaps xmm4,xmm3
sub ebx,01h
movaps xmm1,[edi]
jnz @1pixelSSE
@nextHpixelSSE: { EBX = 0 }
shufps xmm2,xmm2,11111111b
cmp [esi-10h+04h],ebx
lea ebx,[ebx-01h]
jnz @pixelSSE
@stepHelementSSE: { EBX = -1 }
add eax,ebx
lea esi,[esi+20h]
jnz @prevHpixelSSE
mov edi,ecx
@moreVrowsSSE: { EAX = 0 és EBX = -1 }
add edx,ebx
jns @cvtROW
cmp edx,ebx
jnz @stepVelementSSE
add eax,[ebp+04h]
movd xmm0,eax
jnz @zoomvertSSE
@stepVelementSSE:
add [esp+_VSIZE],ebx
lea ebp,[ebp+20h]
jnz @decode
mov edx,ebx
@cvtROW:
mov esi,ecx
mov eax,[esp+_INCREASE]
and esi,-32
sub edi,eax
@cvtRGB:
add esi,20h
cvtps2dq xmm0,[esi+00h]
movaps [esi+00h],xmm5
cvtps2dq xmm1,[esi+10h]
movaps [esi+10h],xmm5
packssdw xmm0,xmm1
packuswb xmm0,xmm1
movq [edi+eax],xmm0
add eax,08h
js @cvtRGB
test edx,edx
mov ecx,edi
jz @moreVrowsSSE
divss xmm0,xmm0
jns @zoomvertSSE

[ Szerkesztve ]

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

(#11) P.H.


P.H.
(Topikgazda)

Alakulgat:

@copyarraySSE:
pshufd xmm0,[eax],01010101b
@zoomvertSSE:
mov [esp+_DESTROW],edi
mov esi,[esp+_STRROWS]
xor ebx,ebx
and edi,-32
sub edx,[esp+_STRLEFT]
movd ebp,mm4
movd ecx,mm6
lea edi,[edi+20h]
mov esi,[esi]
movaps xmm1,[edi]
jge @newpixelSSE
@sourceLEFT:
mov bl,[esi]
add esi,02h
add edx,ebx
js @sourceLEFT
mov bl,[esi-01h]
jnz @initpixelSSE
@newpixelSSE:
movzx edx,word ptr [esi]
add esi,02h
movzx ebx,dh
@initpixelSSE:
shl ebx,04h
add ebx,[esp+_STRCOLORS]
movaps xmm7,[ebx]
jmp @nxpixelSSE
@prevHpixelSSE:
sub dl,01h
jz @newpixelSSE
@nxpixelSSE:
movaps xmm4,xmm7
movlps xmm6,[ecx+04h]
mov ebx,[ecx+00h]
mulps xmm4,xmm0
pshufd xmm2,xmm6,01000000b
shufps xmm6,xmm6,01010101b
movaps xmm3,xmm4
@pixelSSE:
test ebx,ebx
mulps xmm4,xmm2
@1pixelSSE:
addps xmm1,xmm4
jz @nextHpixelSSE
movaps [edi],xmm1
js @stepHelementSSE
add edi,10h
movaps xmm4,xmm3
sub ebx,01h
movaps xmm1,[edi]
jnz @1pixelSSE
@nextHpixelSSE:
cmp ebx,[ecx+08h]
movaps xmm2,xmm6
lea ebx,[ebx-01h]
jnz @pixelSSE
@stepHelementSSE:
add ebp,ebx
lea ecx,[ecx+10h]
jnz @prevHpixelSSE
mov edi,[esp+_DESTROW]
xor edx,edx
@moreVrowsSSE:
add [eax+00h],ebx
jns @cvtROW
cmp [eax+00h],ebx
jnz @stepVelementSSE
cmp ebp,[eax+08h]
pshufd xmm0,[eax],10101010b
jnz @zoomvertSSE
@stepVelementSSE:
add dword ptr [esp+_STRROWS],04h
add [esp+_VSIZE],ebx
lea eax,[eax+10h]
jnz @copyarraySSE
sub eax,10h
mov [eax+00h],ebx
@cvtROW:
mov esi,edi
mov ebp,[esp+_INCREASE]
and esi,-32
sub edi,ebp
@cvtRGB:
add esi,20h
cvtps2dq xmm3,[esi+00h]
movaps [esi+00h],xmm5
cvtps2dq xmm1,[esi+10h]
movaps [esi+10h],xmm5
packssdw xmm3,xmm1
packuswb xmm3,xmm1
movq [edi+ebp],xmm3
add ebp,08h
js @cvtRGB
cmp [eax+00h],edx
jz @moreVrowsSSE
divps xmm0,xmm0
jns @zoomvertSSE

x87:

fldz
@copyarray:
fadd dword ptr [eax+04h]
@zoomvert:
mov edi,[esp+_DESTROW]
mov ecx,[esp+_STRVAR+_ECX]
xor ebx,ebx
mov esi,[esp+_STRROWS]
mov ebp,[ecx-04h]
fld dword ptr [edi+00h]
mov esi,[esi]
fld dword ptr [edi+04h]
add ecx,[esp+_XADD]
xor edx,edx
sub ebx,[esp+_STRLEFT]
fld dword ptr [edi+08h]
jge @newpixelx86
@sourceLEFTx86:
mov dl,[esi]
add esi,02h
add ebx,edx
js @sourceLEFTx86
mov dl,[esi-01h]
jnz @initpixelx86
@newpixelx86:
movzx ebx,word ptr [esi]
add esi,02h
movzx edx,bh
@initpixelx86:
mov [esp+_TMPCOLOR],bl
shl edx,04h
add edx,[esp+_STRCOLORS]
jmp @nxpixelx86
@prevHpixel:
sub byte ptr [esp+_TMPCOLOR],01h
jz @newpixelx86
@nxpixelx86:
fld dword ptr [ecx+04h]
mov ebx,[ecx+00h]
@HANDLEPIXEL:
fmul st,st(4)
test ebx,ebx
fld dword ptr [edx+00h]
fmul st,st(1)
faddp st(4),st
fld dword ptr [edx+04h]
fmul st,st(1)
faddp st(3),st
fmul dword ptr [edx+08h]
fadd
js @stepHelement
fld1
jz @nextHpixel
fxch st(3)
fstp dword ptr [edi+00h]
fstp dword ptr [edi+08h]
fstp dword ptr [edi+04h]
add edi,0Ch
sub ebx,01h
fld dword ptr [edi+04h]
fld dword ptr [edi+08h]
fld dword ptr [edi+00h]
fxch st(3)
jnz @HANDLEPIXEL
@nextHpixel:
cmp [ecx+08h],ebx
lea ebx,[ebx-01h]
fmul dword ptr [ecx+08h]
jnz @HANDLEPIXEL
fstp st(0)
@stepHelement:
add ebp,ebx
lea ecx,[ecx+10h]
jnz @prevHpixel
fstp dword ptr [edi+08h]
fstp dword ptr [edi+04h]
fstp dword ptr [edi+00h]
@moreVrows:
add [eax+00h],ebx
fsub st,st(0)
mov edi,[esp+_DESTROW]
jns @cvtROWx86
@nextVrow:
cmp [eax+00h],ebx
jnz @stepVelement
cmp ebp,[eax+08h]
fadd dword ptr [eax+08h]
jnz @zoomvert
@stepVelement:
add dword ptr [esp+_STRROWS],04h
add eax,10h
add [esp+_VSIZE],ebx
fsub st,st(0)
jnz @copyarray
sub eax,10h
mov [eax+00],ebx
@cvtROWx86:
mov ecx,[esp+_INCREASE]
mov esi,edi
lea edx,[edi+ecx]
mov [esp+_DESTROW],edx
@cvtRGBx86:
fld dword ptr [esi+08h]
mov [esi+00h],ebp
fld dword ptr [esi+00h]
mov [esi+08h],ebp
fld dword ptr [esi+04h]
mov [esi+04h],ebp
fistp word ptr [esp+_TMPCOLOR]
add esi,0Ch
fistp word ptr [edi+00h]
mov dl,[esp+_TMPCOLOR]
sub ecx,04h
fistp word ptr [edi+02h]
mov [edi+01h],dl
lea edi,[edi+04h]
jnz @cvtRGBx86
fld1
cmp [eax+00h],ebp
fadd
jz @moreVrows
js @removeTEMP
jmp @zoomvert

[ Szerkesztve ]

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

(#12) P.H.


P.H.
(Topikgazda)

Under investigation: K8 utasítássorrend

ad 1:

@rewrite:
xor eax,eax
sub ecx,01h
js @finished
mov dl,[ebx+ecx]
add eax,[edi+ecx*04h]
mov ebp,[esi+edx*04h]
cmovz eax,ebp
test dl,dl
cmovz ebp,eax
mov [ebx+ecx*04h],ebp
jmp @rewrite

ad 2:
@rewrite:
xor eax,eax
sub ecx,01h
mov dl,[ebx+ecx]
js @finished
add eax,[edi+ecx*04h]
mov ebp,[esi+edx*04h]
cmovz eax,ebp
test dl,dl
cmovz ebp,eax
mov [ebx+ecx*04h],ebp
jmp @rewrite

ECX = 2 853 960 bemeneti értékkel az első ciklus lefutása 25M clock (~9 clock/pixel), a 2. ciklusé 30M clock (~10-11 clock/pixel). Az első cmovz általi átírás sosem fut le, a másodiké 90%-ban.

Ennek ellentmod, hogy a

test eax,eax
cmp eax,[eax-04h]

kód abban az esetben, ha EAX = 0, védelmi hibával leáll, tehát a cmovcc függ mindhárom bemeneti értékétől.

A referencia x86 kód 32M órajel:

@rewrite:
xor eax,eax
sub ecx,01h
mov dl,[ebx+ecx]
js @finished
add eax,[edi+ecx*04h]
mov ebp,[esi+edx*04h]
jz @store
test dl,dl
xchg ebp,eax
jz @store
mov ebp,eax
@store:
mov [ebx+ecx*04h],ebp
jmp @rewrite
@finished:

[ Szerkesztve ]

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

(#13) P.H. válasza P.H. (#12) üzenetére


P.H.
(Topikgazda)

hotfix:

Ennek ellentmond, hogy a (dinamikusan allokált tömb méretének lekérdezése, ha a tömb nem NULL):

test eax,eax
cmovnz eax,[eax-04h]

kód EAX = 0 esetben védelmi hibával leáll, tehát a cmovcc függ mindkét bemeneti értékétől.

[ Szerkesztve ]

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

(#14) P.H.


P.H.
(Topikgazda)

Harmadik felvonás, az előző már érdemes volt egy gyors első generációs Netburst port issue elemzésre és TSC-mérésekre.

Előző (Prescott CeleronD): 735M clock
Az alábbi (Prescott CeleronD): 670M clock (-10%)
Az alábbi (K8 Opteron): 565M clock

movd xmm0,[eax+04h] // 6+6/2 p1+1+2 MMX_MSC+MMX_SH+LOAD
@zoomvertSSE: //
mov [esp+_DESTROW],edi // 2/d p3 STORE
xor ebx,ebx // d/d p0/1 ALU 0/1
mov esi,[esp+_STRROWS] // 2+d/d p0/1+2 ALU 0/1+LOAD
and edi,-64 // d/d p0/1 ALU 0/1
sub edx,[esp+_STRLEFT] // 2+d/d p0/1+2 ALU 0/1+LOAD
movd ebp,mm4 // 10/1 p0+1 FP_MOV+FP_MISC
pshufd xmm0,xmm0,00000000b // 4/2 p1 MMX_SH
movd ecx,mm6 // 10/1 p0+1 FP_MOV+FP_MISC
lea edi,[edi+40h] // d/d p0/1 ALU 0/1
mov esi,[esi] // 2+d/d p0/1+2 ALU 0/1+LOAD
cmovge edx,ebx //
movaps xmm1,[edi] // 6+6/1 p0+2 FP_MOV+LOAD
@sourceLEFT: //
mov bl,[esi] // 2+d/d p0/1+2 ALU 0/1+LOAD
add esi,02h // d/d p0/1 ALU 0/1
add edx,ebx // d/d p0/1 ALU 0/1
jle @sourceLEFT // -/d p0 ALU 0
mov bl,[esi-01h] // 2+d/d p0/1+2 ALU 0/1+LOAD
jmp @initpixelSSE // -/d p0 ALU 0
@newpixelSSE: //
movzx edx,word ptr [esi] // 2+d/d p0/1+2 ALU 0/1+LOAD
add esi,02h // d/d p0/1 ALU 0/1
movzx ebx,dh // d/d p0/1+2 ALU 0/1
@initpixelSSE: //
movaps xmm3,xmm0 // 6/1 p0 FP_MOV
shl ebx,04h // 4/1 p1 CMPXALU
add dl,01h // d/d p0/1 ALU 0/1
add ebx,[esp+_STRCOLORS] // 2+d/d p0/1+2 ALU 0/1+LOAD
mulps xmm3,[ebx] // 6+6/2 p1+2 FP_MUL+LOAD
@prevHpixelSSE: //
sub dl,01h // d/d p0/1 ALU 0/1
jz @newpixelSSE // -/d p0 ALU 0
pshufd xmm2,[ecx+00h],10010101b // 6+4/2 p1+2 MMX_SH+LOAD
movaps xmm4,xmm3 // 6/1 p0 FP_MOV
mov ebx,[ecx+00h] // 2+d/d p0/1+2 ALU 0/1+LOAD
@pixelSSE: //
mulps xmm4,xmm2 // 6/2 p1+2 FP_MUL
test ebx,ebx // d/d p0/1 ALU 0/1
@1pixelSSE: //
addps xmm1,xmm4 // 4/2 p1 FP_ADD
jz @nextHpixelSSE // -/d p0 ALU 0
movaps [edi],xmm1 // 6+6/1 p0+3 FP_STR+STORE
js @stepHelementSSE // -/d p0 ALU 0
add edi,10h // d/d p0/1 ALU 0/1
movaps xmm4,xmm3 // 6/1 p0 FP_MOV
sub ebx,01h // d/d p0/1 ALU 0/1
movaps xmm1,[edi] // 6+6/1 p0+2 FP_MOV+LOAD
jnz @1pixelSSE // -/d p0 ALU 0
@nextHpixelSSE: //
cmp ebx,[ecx+08h] // 2+d/d p0/1+2 ALU 0/1+LOAD
pshufd xmm2,xmm2,11111111b // 4/2 p1 MMX_SH
lea ebx,[ebx-01h] // d/d p0/1 ALU 0/1
jnz @pixelSSE // -/d p 1 ALU 0
@stepHelementSSE: //
add ebp,ebx // d/d p0/1 ALU 0/1
lea ecx,[ecx+10h] // d/d p0/1 ALU 0/1
jnz @prevHpixelSSE // -/d p0 ALU 0
mov edi,[esp+_DESTROW] // 2+d/d p0/1+2 ALU 0/1+LOAD
xor edx,edx // d/d p0/1 ALU 0/1
@moreVrowsSSE: //
add [eax+00h],ebx // 2+2+d/d p0+2+3 ALU 0/1+LOAD+STORE
jns @cvtROW // -/d p0 ALU 0
cmp ebx,[eax+00h] // 2+d/d p0/1+2 ALU 0/1+LOAD
jnz @stepVelementSSE // -/d p0 ALU 0
add ebp,[eax+08h] // 2+d/d p0/1+2 ALU 0/1+LOAD
movd xmm0,ebp // 6/2 p1 MMX_MSC+MMX_SH
jnz @zoomvertSSE // -/d p0 ALU 0
@stepVelementSSE: //
add dword ptr [esp+_STRROWS],04h // 2+2+d/d p0+1+3 ALU 0/1+LOAD+STORE
add [esp+_VSIZE],ebx // 2+2+d/d p0+1+3 ALU 0/1+LOAD+STORE
lea eax,[eax+10h] // d/d p0/1 ALU 0/1
jnz @copyarraySSE // -/d p0 ALU 0
sub eax,10h // d/d p0/1 ALU 0/1
mov [eax+00h],ebx // 2/d p3 STORE
@cvtROW: //
mov esi,edi // d/d p0/1 ALU 0/1
mov ebp,[esp+_INCREASE] // 2+d/d p0/1+2 ALU 0/1+LOAD
and esi,-64 // d/d p0/1 ALU 0/1
sub edi,ebp // d/d p0/1 ALU 0/1
@cvtRGB: //
add esi,40h // d/d p0/1 ALU 0/1
cvtps2dq xmm1,[esi+00h] // 6+5/1 p1 FP_ADD+LOAD
cvtps2dq xmm2,[esi+10h] // 6+5/1 p1 FP_ADD+LOAD
cvtps2dq xmm3,[esi+20h] // 6+5/1 p1 FP_ADD+LOAD
cvtps2dq xmm4,[esi+30h] // 6+5/1 p1 FP_ADD+LOAD
movaps [esi+00h],xmm5 // 6+6/1 p0+3 FP_STR+STORE
movaps [esi+10h],xmm5 // 6+6/1 p0+3 FP_STR+STORE
movaps [esi+20h],xmm5 // 6+6/1 p0+3 FP_STR+STORE
movaps [esi+30h],xmm5 // 6+6/1 p0+3 FP_STR+STORE
packssdw xmm1,xmm2 // 2/1 p1 MMX_SHF
packssdw xmm3,xmm4 // 2/1 p1 MMX_SHF
packuswb xmm1,xmm3 // 2/1 p1 MMX_SHF
movups [edi+ebp],xmm1 // 6/1 p0 FP_MOV
add ebp,10h // d/d p0/1 ALU 0/1
js @cvtRGB // -/d p0 ALU 0
cmp [eax+00h],edx // 2+d/d p0/1+2 ALU 0/1+LOAD
jz @moreVrowsSSE // -/d p0 ALU 0
divss xmm0,xmm0 // 23/23 p1 FP_DIV
jns @zoomvertSSE // -/d p0 ALU 0

[ Szerkesztve ]

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

(#15) P.H.


P.H.
(Topikgazda)

Azt hiszem, elérhetetlen céljaim egyike, hogy a Netburst-öt megértsem...

Prescott CeleronD: 630M clock (-4%)
K8 Opteron: 585M clock (+4%)

Csupán két utasítás sorrendjének felcserélésével (melynek mellékhatásaként a memóriaparaméteres PSHUFD 3 millió helyett 6 milliószor fut le).

K8 analízis (túl sok a VectorPath):

@copyarraySSE: //
movd xmm0,[eax+04h] // 9/- FPUvector
@zoomvertSSE: //
mov [esp],edi // 3/1 p0/1/2 ALU 0/1/2
xor ebx,ebx // 1/1 p0/1/2 ALU 0/1/2
mov esi,[esp+_STRROWS] // 3/1 p0/1/2 ALU 0/1/2
and edi,-64 // 1/1 p0/1/2 ALU 0/1/2
sub edx,[esp+_STRLEFT] // 4/1 p0/1/2 ALU 0/1/2
movd ebp,mm4 // 4/- FPUvector
pshufd xmm0,xmm0,00000000b // 4/- FPUvector
movd ecx,mm6 // 4/- FPUvector
lea edi,[edi+40h] // 1/1 p0/1/2 ALU 0/1/2
mov esi,[esi] // 3/1 p0/1/2 ALU 0/1/2
cmovge edx,ebx // 1/1 p0/1/2 ALU 0/1/2
movaps xmm1,[edi] // 4/- p5 FSTORE
@sourceLEFT: //
mov bl,[esi] // 4/1 p0/1/2 ALU 0/1/2
add esi,02h // 1/1 p0/1/2 ALU 0/1/2
add edx,ebx // 1/1 p0/1/2 ALU 0/1/2
jle @sourceLEFT // 1/1 p0/1/2 ALU 0/1/2
mov bl,[esi-01h] // 4/1 p0/1/2 ALU 0/1/2
jmp @initpixelSSE // 1/1 p0/1/2 ALU 0/1/2
@newpixelSSE: //
movzx edx,word ptr [esi] // 1/1 p0/1/2 ALU 0/1/2
add esi,02h // 1/1 p0/1/2 ALU 0/1/2
movzx ebx,dh // 1/1 p0/1/2 ALU 0/1/2
@initpixelSSE: //
movaps xmm3,xmm0 // 2/1 p3/4 FADD/FMUL
shl ebx,04h // 1/1 p0/1/2 ALU 0/1/2
add dl,01h // 1/1 p0/1/2 ALU 0/1/2
add ebx,[esp+_STRCOLORS] // 4/1 p0/1/2 ALU 0/1/2
mulps xmm3,[ebx] // 7/2 p4 FMUL
@prevHpixelSSE: //
sub dl,01h // 1/1 p0/1/2 ALU 0/1/2
pshufd xmm2,[ecx+00h],10010101b // 4/- FPUvector
jz @newpixelSSE // 1/1 p0/1/2 ALU 0/1/2
movaps xmm4,xmm3 // 2/1 p3/4 FADD/FMUL
mov ebx,[ecx+00h] // 4/1 p0/1/2 ALU 0/1/2
@pixelSSE: //
mulps xmm4,xmm2 // 7/2 p4 FMUL
test ebx,ebx // 1/1 p0/1/2 ALU 0/1/2
@1pixelSSE: //
addps xmm1,xmm4 // 5/2 p3 FADD
jz @nextHpixelSSE // 1/1 p0/1/2 ALU 0/1/2
movaps [edi],xmm1 // 3/- p5 FSTORE
js @stepHelementSSE // 1/1 p0/1/2 ALU 0/1/2
add edi,10h // 1/1 p0/1/2 ALU 0/1/2
movaps xmm4,xmm3 // 2/1 p3/4 FADD/FMUL
sub ebx,01h // 1/1 p0/1/2 ALU 0/1/2
movaps xmm1,[edi] // 4/- p5 FSTORE
jnz @1pixelSSE // 1/1 p0/1/2 ALU 0/1/2
@nextHpixelSSE: //
cmp ebx,[ecx+08h] // 4/1 p0/1/2 ALU 0/1/2
pshufd xmm2,xmm2,11111111b // 4/- FPUvector
lea ebx,[ebx-01h] // 1/1 p0/1/2 ALU 0/1/2
jnz @pixelSSE // 1/1 p0/1/2 ALU 0/1/2
@stepHelementSSE: //
add ebp,ebx // 1/1 p0/1/2 ALU 0/1/2
lea ecx,[ecx+10h] // 1/1 p0/1/2 ALU 0/1/2
jnz @prevHpixelSSE // 1/1 p0/1/2 ALU 0/1/2
mov edi,[esp] // 4/1 p0/1/2 ALU 0/1/2
xor edx,edx // 1/1 p0/1/2 ALU 0/1/2
@moreVrowsSSE: //
add [eax+00h],ebx // 4/1 p0/1/2 ALU 0/1/2
jns @cvtROW // 1/1 p0/1/2 ALU 0/1/2
cmp ebx,[eax+00h] // 4/1 p0/1/2 ALU 0/1/2
jnz @stepVelementSSE // 1/1 p0/1/2 ALU 0/1/2
add ebp,[eax+08h] // 4/1 p0/1/2 ALU 0/1/2
movd xmm0,ebp // 9/- FPUvector
jnz @zoomvertSSE // 1/1 p0/1/2 ALU 0/1/2
@stepVelementSSE: //
add dword ptr [esp+_STRROWS],04h // 4/1 p0/1/2 ALU 0/1/2
add [esp+_VSIZE],ebx // 4/1 p0/1/2 ALU 0/1/2
lea eax,[eax+10h] // 1/1 p0/1/2 ALU 0/1/2
jnz @copyarraySSE // 1/1 p0/1/2 ALU 0/1/2
sub eax,10h // 1/1 p0/1/2 ALU 0/1/2
mov [eax+00h],ebx // 3/1 p0/1/2 ALU 0/1/2
@cvtROW: //
mov esi,edi // 1/1 p0/1/2 ALU 0/1/2
mov ebp,[esp+_INCREASE] // 4/1 p0/1/2 ALU 0/1/2
and esi,-64 // 1/1 p0/1/2 ALU 0/1/2
sub edi,ebp // 1/1 p0/1/2 ALU 0/1/2
@cvtRGB: //
add esi,40h // 1/1 p0/1/2 ALU 0/1/2
cvtps2dq xmm1,[esi+00h] // 7/2 p5 FSTORE
cvtps2dq xmm2,[esi+10h] // 7/2 p5 FSTORE
cvtps2dq xmm3,[esi+20h] // 7/2 p5 FSTORE
cvtps2dq xmm4,[esi+30h] // 7/2 p5 FSTORE
movaps [esi+00h],xmm5 // 3/- p5 FSTORE
packssdw xmm1,xmm2 // 2/- p3/4 FADD/FMUL
movaps [esi+10h],xmm5 // 3/- p5 FSTORE
packssdw xmm3,xmm4 // 2/- p3/4 FADD/FMUL
movaps [esi+20h],xmm5 // 3/- p5 FSTORE
packuswb xmm1,xmm3 // 2/- p3/4 FADD/FMUL
movaps [esi+30h],xmm5 // 3/- p5 FSTORE
movups [edi+ebp],xmm1 //
add ebp,10h // 1/1 p0/1/2 ALU 0/1/2
js @cvtRGB // 1/1 p0/1/2 ALU 0/1/2
cmp [eax+00h],edx // 4/1 p0/1/2 ALU 0/1/2
jz @moreVrowsSSE // 1/1 p0/1/2 ALU 0/1/2
divss xmm0,xmm0 //16/- p4 FMUL
jns @zoomvertSSE // 1/1 p0/1/2 ALU 0/1/2

Nem látom Netburst-ön tovább az utat: a 19 clock/forráspixeles globális sebességet PSHUFD-MOVAPS-MULPS-ADDPS kvartett kifeszíti, a többi utasítás futását szinte teljesen elrejti.

Most már kíváncsi vagyok, hogy egy P3-on mit lehet kihozni.

[ Szerkesztve ]

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

(#16) P.H.


P.H.
(Topikgazda)

.

[ Szerkesztve ]

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

(#17) P.H.


P.H.
(Topikgazda)

.

[ Szerkesztve ]

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

(#18) P.H.


P.H.
(Topikgazda)

A dolog befejettnek tekinthető, végső stat:

- SSE2-kód Prescott CeleronD + DDR: 630M clock
- SSE2-kód Northwood Celeron + SDRAM: 635M clock
- SSE2-kód K8 Opteron + DDR2: 585M clock
- SSE1-kód P3 Coppermine + SDRAM: 670M clock
- x87-kód Prescott CeleronD + DDR: 950M clock
- x87-kód K8 Opteron + DDR2: 590M clock

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

(#19) P.H.


P.H.
(Topikgazda)

Perfmonitor: x87-kód - K8 - végtelen ciklusban

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Instructions per cycle (IPC) (átlag: 1.6 IPC)
Counter 2 : Retired x87 instructions
Counter 3 : Retired uops (átlag: 1.67 uop/cycle)

T(ms) c0(M/s) c1(i/c) c2(M/s) c3(M/s)
50 2147.3 1.7 1764.7 3557.5
100 2144.6 1.7 1789.1 3574.9
150 2148.1 1.6 1743.1 3523.0
200 2144.3 1.6 1737.0 3516.0
250 2145.9 1.6 1749.0 3534.2
300 1951.9 1.5 1518.6 3068.6
350 1951.9 1.5 1518.6 3068.6
400 2166.6 1.6 1784.2 3573.8
450 2145.0 1.6 1740.0 3515.3
500 2148.4 1.6 1739.3 3521.1
550 2080.0 1.7 1728.9 3469.3
600 2080.0 1.7 1728.9 3469.3
650 2174.7 1.7 1815.4 3625.6
700 2146.9 1.6 1735.7 3510.5
750 2153.0 1.6 1739.5 3522.5
800 2146.5 1.7 1776.5 3573.7
850 2146.5 1.7 1776.5 3573.7
900 2161.3 1.7 1810.6 3611.2
950 2145.1 1.6 1735.2 3509.7
1000 2143.9 1.6 1736.8 3513.5
1050 2149.8 1.7 1766.1 3560.8
1100 1901.3 1.4 1373.4 2820.3
1150 1901.3 1.4 1373.4 2820.3
1200 2170.7 1.6 1773.8 3565.8
1250 2149.7 1.6 1745.0 3526.8
1300 2146.6 1.6 1754.7 3542.4
1350 1917.8 1.4 1437.8 2919.8
1400 1917.8 1.4 1437.8 2919.8
1450 2175.2 1.7 1794.4 3596.8
1500 2143.4 1.6 1739.3 3513.9
1550 2146.2 1.6 1739.8 3521.4
1600 2007.6 1.6 1621.3 3281.0
1650 2007.6 1.6 1621.3 3281.0
1700 2168.2 1.7 1806.2 3609.1
1750 2147.8 1.6 1742.8 3521.1
1800 2146.3 1.6 1732.0 3508.8
1850 2148.4 1.7 1782.0 3582.2
1900 1912.0 1.4 1362.6 2799.5
1950 1912.0 1.4 1362.6 2799.5
2000 2173.2 1.6 1776.2 3570.1

Perfmonitor: SSE2-kód - K8 - végtelen ciklusban
(ott fut a kód, ahol a counter 2 oszlop 0.0)

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Instructions per cycle (IPC) (átlag: 1.2 IPC)
Counter 2 : Retired x87 instructions
Counter 3 : Retired uops (átlag: 1.89 uop/cycle)

T(ms) c0(M/s) c1(i/c) c2(M/s) c3(M/s)
50 2144.4 1.2 0.0 3937.9
100 2124.2 1.2 0.0 3932.0
150 2124.2 1.2 0.0 3932.0
200 2163.4 1.3 0.0 4087.8
250 2151.2 1.2 0.0 3928.3
300 2148.1 1.2 0.0 3949.5
350 2150.4 1.3 0.0 4026.4
400 2150.4 1.3 0.0 4026.4
450 2113.7 1.3 0.0 3985.9
500 2145.0 1.2 0.0 3944.8
550 2140.1 1.2 0.0 3936.2
600 1997.1 1.2 91.2 3642.2
650 1997.1 1.2 91.2 3642.2
700 2169.1 1.2 0.0 4043.4
750 2145.4 1.2 0.0 3945.1
800 2145.3 1.2 0.0 3987.8
850 1915.7 1.1 269.3 3111.7
900 2146.0 1.3 0.0 4045.9
950 2146.0 1.3 0.0 4045.9
1000 2170.9 1.2 0.0 4005.7
1050 2141.6 1.3 0.0 4013.2
1100 1906.3 1.1 269.3 3077.8
1150 2148.3 1.3 0.0 4031.8
1200 2148.3 1.3 0.0 4031.8
1250 2170.4 1.2 0.0 3984.1
1300 1972.1 1.2 140.0 3523.7
1350 2086.6 1.2 129.3 3613.1
1400 2144.9 1.2 0.0 3973.6
1450 2144.9 1.2 0.0 3973.6
1500 2163.4 1.2 0.0 4044.9
1550 1376.2 1.1 128.3 2225.5
1600 2077.9 1.2 141.0 3582.1
1650 2149.2 1.2 0.0 3983.2
1700 2150.4 1.2 0.0 3957.1
1750 2150.4 1.2 0.0 3957.1
1800 1931.8 1.1 269.2 3197.0
1850 2151.3 1.3 0.0 4054.5
1900 2148.0 1.2 0.0 3947.1
1950 2142.7 1.2 0.0 3929.8
2000 2142.7 1.2 0.0 3929.8

[ Szerkesztve ]

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

(#20) P.H.


P.H.
(Topikgazda)

Perfmonitor: x87-kód - K10.5 - végtelen ciklusban

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Instructions per cycle (IPC) (átlag: 2.1 IPC)
Counter 2 : Retired x87 instructions
Counter 3 : Retired uops (átlag: 2.16 uop/cycle)

T(ms) c0(M/s) c1(i/c) c2(M/s) c3(M/s)
50 3285.4 2.2 3529.4 7076.8
100 3063.2 2.0 3099.1 6264.5
150 3284.3 2.2 3543.0 7099.7
200 3188.5 2.1 3319.6 6680.5
250 3272.3 2.1 3450.2 6938.7
300 3255.9 2.2 3497.3 7011.3
350 3173.4 2.0 3247.4 6558.3
400 3285.2 2.1 3496.2 7020.2
450 3133.1 2.0 3214.7 6477.7
500 3241.0 2.1 3432.2 6899.0
550 3162.5 2.1 3294.7 6630.9
600 3282.7 2.1 3463.3 6967.7
650 3143.3 2.0 3247.2 6534.4
700 3279.9 2.1 3463.5 6966.5
750 3168.5 2.1 3330.2 6697.5
800 3160.7 2.1 3303.5 6645.5
850 3257.3 2.1 3398.0 6837.9
900 3286.2 2.1 3517.0 7055.1
950 3156.7 2.0 3244.1 6546.1
1000 3286.9 2.1 3495.6 7020.8
1050 3147.3 2.0 3259.4 6566.0
1100 3284.1 2.1 3478.9 6992.5
1150 3157.7 2.0 3279.2 6601.2
1200 3282.2 2.1 3461.4 6964.0
1250 3142.5 2.0 3248.9 6537.4
1300 3248.4 2.1 3428.5 6896.7
1350 3168.8 2.0 3285.2 6617.9
1400 3276.6 2.1 3488.3 7006.2
1450 3160.6 2.0 3217.0 6490.4
1500 3283.6 2.2 3526.5 7071.4
1550 3164.2 2.0 3229.8 6524.4
1600 3280.5 2.2 3538.5 7090.2
1650 3160.1 2.0 3219.3 6506.2
1700 3277.7 2.2 3538.4 7089.3
1750 3227.3 2.1 3442.4 6909.4
1800 3140.5 2.0 3214.9 6486.7
1850 3284.8 2.1 3499.9 7027.2
1900 3164.0 2.0 3272.6 6594.4
1950 3246.3 2.1 3346.8 6746.4
2000 3283.9 2.2 3539.6 7093.4

Perfmonitor: SSE2-kód - K10.5 - végtelen ciklusban
(ott fut a tisztán kód, ahol a counter 2 oszlop 0.0)

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Instructions per cycle (IPC) (átlag: 1.7 IPC)
Counter 2 : Retired x87 instructions
Counter 3 : Retired uops (átlag: 1.67 uop/cycle)

T(ms) c0(M/s) c1(i/c) c2(M/s) c3(M/s)
50 3110.8 1.7 0.0 5212.7
100 3119.8 1.6 219.1 5110.6
150 3138.6 1.6 195.4 5217.6
200 3280.6 1.6 23.5 5409.9
250 3163.5 1.6 219.1 5193.5
300 3291.7 1.7 0.0 5519.1
350 3125.2 1.6 219.4 5141.1
400 3299.2 1.7 0.0 5514.0
450 3175.4 1.6 218.8 5266.7
500 3279.5 1.7 0.0 5465.3
550 3145.7 1.6 219.0 5146.2
600 3296.9 1.7 0.0 5542.1
650 3172.3 1.6 218.8 5205.1
700 3172.6 1.6 218.7 5211.1
750 3275.5 1.7 0.0 5503.3
800 3167.4 1.6 220.0 5211.2
850 3296.8 1.7 0.0 5519.2
900 3146.2 1.6 219.0 5161.8
950 3299.9 1.7 0.0 5507.0
1000 3157.2 1.6 218.6 5227.3
1050 3300.9 1.7 0.0 5518.8
1100 3175.5 1.6 218.9 5230.2
1150 3200.4 1.6 141.9 5361.2
1200 3227.2 1.6 77.2 5275.1
1250 3167.0 1.6 218.9 5195.1
1300 3294.7 1.7 0.0 5516.8
1350 3159.2 1.6 218.8 5212.8
1400 3298.6 1.7 0.0 5512.2
1450 3169.7 1.6 218.9 5254.5
1500 3300.2 1.7 0.0 5509.1
1550 3089.0 1.6 216.1 5077.3
1600 3297.4 1.7 0.0 5527.0
1650 3173.8 1.6 219.0 5221.7
1700 3137.5 1.6 217.2 5211.7
1750 3293.4 1.7 1.6 5442.9
1800 3157.7 1.6 218.7 5185.6
1850 3292.4 1.7 0.0 5518.1
1900 3142.9 1.6 219.0 5171.3
1950 3298.1 1.7 0.0 5506.7
2000 3174.0 1.6 218.8 5261.2

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

(#21) P.H.


P.H.
(Topikgazda)

SSE2-kód AMD-re egy kicsit kevesebb utasítással, kis utasítássorrend-módosítással (körvonalazódik, hogy VectorPath célszerűen feltételes ugrás után vagy ugrás céljaként rendezendő)

K8 Opteron: 517M clock (-10%), átlagosan 1.3 IPC

@copyarraySSE:
movd xmm0,[eax+04h]
@zoomvertSSE:
mov [esp],edi
xor ebx,ebx
mov esi,[esp+_STRROWS]
and edi,-64
sub edx,[esp+_STRLEFT]
movd ebp,mm7
pshufd xmm0,xmm0,00000000b
movd ecx,mm6
lea edi,[edi+40h]
mov esi,[esi]
cmovge edx,ebx
movaps xmm1,[edi]
@sourceLEFT:
mov bl,[esi]
add esi,02h
add edx,ebx
jle @sourceLEFT
mov bl,[esi-01h]
jmp @initpixelSSE
@newpixelSSE:
movzx edx,word ptr [esi]
add esi,02h
movzx ebx,dh
@initpixelSSE:
movaps xmm3,xmm0
shl ebx,04h
add dl,01h
add ebx,[esp+_STRCOLORS]
mulps xmm3,[ebx]
@prevHpixelSSE:
sub dl,01h
jz @newpixelSSE
pshufd xmm2,[ecx+00h],10010101b
movaps xmm4,xmm3
mov ebx,[ecx+00h]
@pixelSSE:
mulps xmm4,xmm2
sub ebx,01h
@1pixelSSE:
addps xmm1,xmm4
jz @nextHpixelSSE
movaps [edi],xmm1
js @stepHelementSSE
add edi,10h
movaps xmm4,xmm3
sub ebx,01h
movaps xmm1,[edi]
jnz @1pixelSSE
@nextHpixelSSE:
pshufd xmm2,xmm2,11111111b
cmp ebx,[ecx+08h]
jnz @pixelSSE
not ebx
@stepHelementSSE:
add ebp,ebx
lea ecx,[ecx+10h]
jnz @prevHpixelSSE
mov edi,[esp]
xor edx,edx
@moreVrowsSSE:
add [eax+00h],ebx
jg @cvtROW
jl @stepVelementSSE
add ebp,[eax+08h]
movd xmm0,ebp
jnz @zoomvertSSE
@stepVelementSSE:
add dword ptr [esp+_STRROWS],04h
add [esp+_VSIZE],ebx
lea eax,[eax+10h]
jnz @copyarraySSE
sub eax,10h
mov [eax+00h],ebx
@cvtROW:
mov esi,edi
mov ebp,[esp+_INCREASE]
and esi,-64
sub edi,ebp
@cvtRGB:
add esi,40h
cvtps2dq xmm1,[esi+00h]
cvtps2dq xmm2,[esi+10h]
cvtps2dq xmm3,[esi+20h]
cvtps2dq xmm4,[esi+30h]
movaps [esi+00h],xmm5
packssdw xmm1,xmm2
movaps [esi+10h],xmm5
packssdw xmm3,xmm4
movaps [esi+20h],xmm5
packuswb xmm1,xmm3
movaps [esi+30h],xmm5
movups [edi+ebp],xmm1
add ebp,10h
js @cvtRGB
cmp dword ptr [eax+00h],01h
jz @moreVrowsSSE
divss xmm0,xmm0
jg @zoomvertSSE

[ Szerkesztve ]

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

(#22) P.H.


P.H.
(Topikgazda)

Valamiért a K8 is jobban szereti, ha az utasítások konstans paramétere nem azonnali érték, hanem regiszter, az előforduló függőségek ellenére is; talán az utasításhossz-csökkenés miatt? (a Netburst-ön még jobban kijön a plusz, ennek a trace-cache felépítése lehet az oka)

K8-on még 1% van benne, egy-egy felesleges, de csak ritkán lefutó utasítás eltávolításával és egy ugráscél áthelyezésével: 513M clock

gépi kód:

@copyarraySSE:
movd xmm0,[eax+04h] 660F6E4004
@zoomvertSSE:
mov [esp],edi 893C24
xor ebx,ebx 31DB
mov esi,[esp+_STRROWS] 8B74242C
and edi,-64 83E7C0
sub edx,[esp+_STRLEFT] 2B542430
movd ebp,mm7 0F7EFD
pshufd xmm0,xmm0,00000000b 660F70C000
movd ecx,mm6 0F7EF1
lea edi,[edi+40h] 8D7F40
mov esi,[esi] 8B36
cmovge edx,ebx 0F4DD3
movaps xmm1,[edi] 0F280F
@sourceLEFT:
mov bl,[esi] 8A1E
add esi,02h 83C602
add edx,ebx 01DA
jle @sourceLEFT 7EF7
mov bl,[esi-01h] 8A5EFF
jmp @initpixelSSE EB09
@newpixelSSE:
movzx edx,word ptr [esi] 0FB716
add esi,02h 83C602
movzx ebx,dh 0FB6DE
@initpixelSSE:
movaps xmm3,xmm0 0F28D8
shl ebx,04h C1E304
add ebx,[esp+_STRCOLORS] 035C2428
mulps xmm3,[ebx] 0F591B
@prevHpixelSSE:
sub dl,01h 80EA01
jc @newpixelSSE 72E5
pshufd xmm2,[ecx+00h],10010101b 660F701195
movaps xmm4,xmm3 0F28E3
mov ebx,[ecx+00h] 8B19
@pixelSSE:
mulps xmm4,xmm2 0E59E2
sub ebx,01h 83EB01
@1pixelSSE:
addps xmm1,xmm4 0F58CC
jz @nextHpixelSSE 7413
movaps [edi],xmm1 0F290F
js @stepHelementSSE 781A
add edi,10h 83C710
movaps xmm4,xmm3 0F28E3
sub ebx,01h 83EB01
movaps xmm1,[edi] 0F280F
jnz @1pixelSSE 75E8
@nextHpixelSSE:
pshufd xmm2,xmm2,11111111b 660F70D2FF
cmp ebx,[ecx+08h] 3B5908
jnz @pixelSSE 75D8
not ebx F7D3
@stepHelementSSE:
add ebp,ebx 01DD
lea ecx,[ecx+10h] 8D4910
jnz @prevHpixelSSE 75C0
mov edi,[esp] 8B3C24
xor edx,edx 31D2
add [eax+00h],ebx 0118
jg @cvtROW 7F26
jl @stepVelementSSE 7C0F
@moreVrowsSSE:
mov [eax+00h],edx 8910
add ebp,[eax+08h] 036808
movd xmm0,ebp 660F6EC5
jnz @zoomvertSSE 0F855CFFFFFF
@stepVelementSSE:
add dword ptr [esp+_STRROWS],04h 8344244C04
add [esp+_VSIZE],ebx 015C2414
lea eax,[eax+10h] 8D4010
jnz @copyarraySSE 0F8545FFFFFF
sub eax,10h 83E810
@cvtROW:
mov esi,edi 89FE
mov ebp,[esp+_INCREASE] 8B6C2418
and esi,-64 83E6C0
sub edi,ebp 29EF
@cvtRGB:
add esi,40h 83C640
cvtps2dq xmm1,[esi+00h] 660F5B0E
cvtps2dq xmm2,[esi+10h] 660F5B5610
cvtps2dq xmm3,[esi+20h] 660F5B5E20
cvtps2dq xmm4,[esi+30h] 660F5B6630
movaps [esi+00h],xmm5 0F290E
packssdw xmm1,xmm2 660F6BC6
movaps [esi+10h],xmm5 0F296E10
packssdw xmm3,xmm4 660F0BCD
movaps [esi+20h],xmm5 0F296E20
packuswb xmm1,xmm3 660F67CB
movaps [esi+30h],xmm5 0F296E30
movups [edi+ebp],xmm1 0F110C2F
add ebp,10h 83C510
js @cvtRGB 78C6
add ebx,[eax+00h] 0318
jz @moreVrowsSSE 7493
divss xmm0,xmm0 F30F5EC0
jg @zoomvertSSE 0F8FF4FEFFFF

[ Szerkesztve ]

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

(#23) P.H.


P.H.
(Topikgazda)

Többszálú pufferkezelési kód. Lehetne jobb is... (?)

function _WAITTHREADS: DWORD;
asm test eax,eax
pushad
mov ebx,esp
jz @return
xor ebp,ebp
@threadarray:
shr eax,01h
lea edx,[edx+TBUFFERSIZE]
jnc @threadarray
lea ebp,[ebp+01h]
push dword ptr [edx+TBUFFER.THREAD]
jnz @threadarray
mov edx,esp
push INFINITE; push ecx; push edx; push ebp; call WINDOWS.WAITFORMULTIPLEOBJECTS
mov esp,ebx
@return:
popad
test eax,eax end;
procedure _RESTARTBUFFERS;
asm pushad
mov edx,offset(BUFFERS)
mov bl,cBUFFER
xor ebp,ebp
mov eax,[PENDINGS]; mov ecx,01h; sub edx,TBUFFERSIZE; call _WAITTHREADS
mov esi,edx
mov edi,eax
@init:
sub bl,cl
lea esi,[esi+TBUFFERSIZE]
js @return
shr edi,cl
jc @init
mov edx,esi; call _BUF0
jmp @init
@return:
mov [PENDINGS],ebp
mov [LOCKBITS],ebp
popad end;
procedure _ZEROBUFFER(Blank,Buffer:pointer);
asm cmp byte ptr [_INSSET+__CPUS],01h
mov ecx,[edx+TBUFFER.BIT]
ja @moreCPU
xor ecx,-1
and [LOCKBITS],ecx
jmp _BUF0
@moreCPU:
push ebx
lea ebx,[edx+TBUFFER.THREAD]
lock or [PENDINGS],ecx
push ebx; push 00h; push edx; push offset(@ZTHREAD); push 60h; push 00h; call CREATETHREAD
mov [ebx],eax
pop ebx
ret
@ZTHREAD:
{ ESP+04h: TBUFFER structure
mov edx,[esp+04h]
or ecx,-1
xor ecx,[edx+TBUFFER.BIT]
call _BUF0
lock and [LOCKBITS],ecx
lock and [PENDINGS],ecx
ret 04h end;
procedure _FREEBUFFER(Value:pHGLOBAL);
asm mov edx,eax
xor ecx,ecx
mov eax,[eax]
mov [edx],ecx
test eax,eax
mov edx,offset(BUFFERS)
jz @return
@search:
cmp eax,[edx+TBUFFER.ADDR]
jz _ZEROBUFFER
add ecx,01h
add edx,TBUFFERSIZE
cmp ecx,cBUFFER
jb @search
mov eax,[_NOFREE]
jmp ERRORFORM
@return: end;
function _GETBUFFER(Dest:pHGLOBAL): HGLOBAL;
asm pushad
mov esi,offset(BUFFERS)
mov edi,_hINV
sub esi,TBUFFERSIZE
@testbuffers:
mov ebp,[LOCKBITS]
mov ebx,00000001h
mov edx,esi
mov cl,cBUFFER
mov eax,[PENDINGS]
@search:
test ebp,ebx
lea edx,[edx+TBUFFERSIZE]
jz @lock
sub cl,01h
lea ebx,[ebx+ebx]
jg @search
xor ecx,ecx; call _WAITTHREADS
jnz @testbuffers
popad
mov eax,[_NOGET]; call ERRORFORM
xor eax,eax
ret
@lock:
mov esi,[esp+_EAX]
mov eax,[edx+TBUFFER.ADDR]
mov ecx,[edx+TBUFFER.THREAD]
mov [edx+TBUFFER.THREAD],edi
mov [esi],eax
lock or [LOCKBITS],ebx
push ecx; call WINDOWS.CLOSEHANDLE
popad
mov eax,[eax] end;

[ Szerkesztve ]

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

(#24) P.H.


P.H.
(Topikgazda)

Pufferenként 1-1 előre elindított végtelenített szál + pufferenként 2 event:
- Erase: automatikusan resetelt, 0 kezdőértékkel
- Ready: kézileg resetelt, 0 kezdőértékkel

procedure _ZTHREAD;
{ [ESP+04h]: TBUFFER address
asm mov edx,[esp+04h]
pushad
mov edi,[edx+TBUFFER.BIT]
mov esi,edx
mov ebp,[edx+TBUFFER.ERASE]
mov ebx,offset(BUFFERS)
xor edi,-1
@loop:
push INFINITE; push ebp; call WINDOWS.WAITFORSINGLEOBJECT
mov eax,[esi+TBUFFER.ADDR]; mov edx,[esi+TBUFFER.SIZE]; call _ZEROMEM
push dword ptr [esi+TBUFFER.READY]; call WINDOWS.SETEVENT
lock and [ebx+_LOCKBITS],edi
lock and [ebx+_PENDINGS],edi
jmp @loop
popad
ret 04h end;
procedure _FREEBUFFER(Value:pHGLOBAL);
asm mov edx,eax
xor ecx,ecx
mov eax,[eax]
mov [edx],ecx
mov cl,cBUFFER
test eax,eax
mov edx,offset(BUFFERS)
jz @return
@search:
sub cl,01h
lea edx,[edx+TBUFFERSIZE]
js @error
cmp eax,[edx+TBUFFER.ADDR]
jnz @search
@freebuffer:
cmp byte ptr [_INSSET+__CPUs],01h
mov ecx,[edx+TBUFFER.BIT]
jbe @oneCPU
lock or dword ptr [BUFFERS+_PENDINGS],ecx
push dword ptr [edx+TBUFFER.ERASE]; call WINDOWS.SETEVENT
ret
@oneCPU:
xor ecx,-1
mov eax,[edx+TBUFFER.ADDR]; mov edx,[edx+TBUFFER.SIZE]
and dword ptr [BUFFERS+_LOCKBITS],ecx
jmp _ZEROMEM
@error:
mov eax,[_NOFREE]
jmp ERRORFORM
@return: end;
procedure _RESTARTBUFFERS;
asm pushad
mov edx,offset(BUFFERS); or ecx,-1
xor edi,edi
mov eax,[edx+_PENDINGS]; call _WAITFORBUFFER
mov esi,edx
mov ebp,[edx+_LOCKBITS]
mov bl,cBUFFER
mov [edx+_LOCKBITS],edi
mov [edx+_PENDINGS],edi
add edi,01h
@search:
sub bl,01h
lea esi,[esi+TBUFFERSIZE]
js @return
test ebp,edi
lea edi,[edi+edi]
jz @search
mov eax,[esi+TBUFFER.ADDR]; mov edx,[esi+TBUFFER.SIZE]; call _ZEROMEM
jmp @search
@return:
popad end;
function _WAITFORBUFFER: DWORD;
asm test eax,eax
pushad
mov edi,ecx
mov ebx,esp
jz @return
xor ebp,ebp
@threadarray:
shr eax,01h
lea edx,[edx+TBUFFERSIZE]
jnc @threadarray
lea ebp,[ebp+01h]
push dword ptr [edx+TBUFFER.READY]
jnz @threadarray
mov edx,esp
push INFINITE; push edi; push edx; push ebp; call WINDOWS.WAITFORMULTIPLEOBJECTS
mov esp,ebx
@return:
popad
test eax,eax end;
function _GETBUFFER(Dest:pHGLOBAL): HGLOBAL;
asm pushad
mov esi,offset(BUFFERS)
mov edi,eax
@testbuffers:
mov ebp,[esi+_LOCKBITS]
mov ebx,00000001h
mov edx,esi
mov cl,cBUFFER
mov eax,[esi+_PENDINGS]
@search:
test ebp,ebx
lea esi,[esi+TBUFFERSIZE]
jz @lock
sub cl,01h
lea ebx,[ebx+ebx]
jg @search
cmp ebp,[edx+_LOCKBITS]
mov esi,edx
jnz @testbuffers
xor ecx,ecx; call _WAITFORBUFFER
jnz @testbuffers
@error:
mov eax,[_NOGET]; call ERRORFORM
xor ebx,ebx
mov edx,esi
@lock:
mov eax,[esi+TBUFFER.ADDR]
lock or [edx+_LOCKBITS],ebx
mov [edi],eax
push dword ptr [esi+TBUFFER.READY]; call WINDOWS.RESETEVENT
popad
mov eax,[eax] end;

[ Szerkesztve ]

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

(#25) P.H.


P.H.
(Topikgazda)

Közismert és általános algoritmushoz tartozó kód legalább 6-7 éve és ma

Első rész, a főciklus előtti inicializációs részek:

Régen:
mov ecx,[MTXDBLSIZE]
mov edi,[MARKS]
xor eax,eax
mov ebp,[MTXSIZE]
mov edx,ecx
rep stosd
lea edi,[tempmarks]
mov ecx,edx
rep stosd

@reduce_rows_with_minimum:
mov edi,[mtx]
mov edx,ebp
mov esi,00FFFFFFh
@row_minimum:
mov ecx,ebp
mov ebx,edi
mov eax,esi
mov ch,cl
@find_row_minimum:
scasd
jb @after_row_test
mov eax,[edi-04h]
@after_row_test:
dec cl
jnz @find_row_minimum
@start_reduce_row:
test eax,eax
jnz @force_reduce_row
dec edx
jnz @row_minimum
jmp @reduce_columns_with_minimum
@force_reduce_row:
cmp eax,esi
jz @abnormal_exit
@reduce_row_elements:
cmp [ebx],esi
ja @after_row_reduction
sub [ebx],eax
@after_row_reduction:
add ebx,04h
dec ch
jnz @reduce_row_elements
dec edx
jnz @row_minimum

@reduce_columns_with_minimum:
mov esi,[mtx]
mov ebx,ebp
lea edi,[ebp*04h]
@column_minimum:
mov ecx,ebp
mov eax,00FFFFFFh
mov edx,esi
mov ch,cl
@find_column_minimum:
cmp [esi],eax
ja @after_column_test
mov eax,[esi]
test eax,eax
jz @next_decrease_column
@after_column_test:
add esi,edi
dec cl
jnz @find_column_minimum
@start_reduce_column:
cmp eax,00FFFFFFh
jz @abnormal_exit
mov esi,edx
@reduce_column_elements:
cmp dword ptr [esi],00FFFFFFh
ja @after_column_reduction
sub [esi],eax
@after_column_reduction:
add esi,edi
dec ch
jnz @reduce_column_elements
@next_decrease_column:
lea esi,[edx+04h]
dec ebx
jnz @column_minimum

@determine_start0_system:
mov [sys0],ebx
mov edi,[marks]
mov ebx,ebp
mov eax,0102h
mov esi,[mtx]
xor ecx,ecx
dec ebx
push esi
xor edx,edx
@start_0system:
lea esi,[esi+ebx*04h]
@find_free0:
test [edi+edx],al
jnz @check_next_item
cmp [esi],ecx
jnz @check_next_item
or [edi+edx],al
or [edi+ebx],ah
or [esi+03h],ah
inc [sys0]
jmp @next_column
@check_next_item:
inc edx
lea esi,[esi+ebp*04h]
cmp edx,ebp
jnz @find_free0
@next_column:
mov esi,[esp]
xor edx,edx
dec ebx
jns @start_0system
pop ebx

cmp ebp,[sys0]
jz @count_result
mov eax,01010101h
mov ecx,[MTXDBLSIZE]
@clearrowmark:
and [edi],eax
sub ecx,01h
lea edi,[edi+04h]
jnz @clearrowmark
pushad
jmp @@2nd_step

Mai termés (kb. 10% gyorsulás a teljes lefutásra vetítve)
mov ebp,[MTXSIZE]
@reduce_rows_with_minimum:
mov esi,00FFFFFFh
mov edi,[MTX]
mov edx,ebp
@rowmin:
mov eax,esi
mov ebx,edi
mov ecx,ebp
@findrowmin:
cmp eax,[ebx]
jb @nxrowmin
mov eax,[ebx]
@nxrowmin:
sub ecx,01h
lea ebx,[ebx+04h]
jnz @findrowmin
cmp eax,esi
mov ecx,ebp
jz @abnormal_exit
@decrow:
cmp [edi],esi
sbb ebx,ebx
and ebx,eax
sub [edi],ebx
sub ecx,01h
lea edi,[edi+04h]
jnz @decrow
sub edx,01h
jnz @rowmin

@reduce_columns_with_minimum:
mov ebx,ebp
shl ebp,02h
mov edi,[MTX]
@colmin:
mov ecx,ebp
mov eax,esi
@findcolmin:
cmp [edi],eax
ja @nxcolmin
mov eax,[edi]
@nxcolmin:
sub ecx,04h
lea edi,[edi+ebp]
jnz @findcolmin
neg ebp
cmp eax,esi
mov ecx,ebp
jz @abnormal_exit
@deccol:
add edi,ebp
cmp [edi],esi
sbb edx,edx
and edx,eax
sub [edi],edx
add ecx,04h
jnz @deccol
neg ebp
sub ebx,01h
lea edi,[edi+04h]
jnz @colmin
shr ebp,02h

imul ecx,[MTXDBLSIZE],BYTE(4)
xor eax,eax
mov edi,[MARKS]
mov edx,offset(TEMPMARKS)
mov esi,[MTX]
@clrmark:
sub ecx,04h
mov [edi+ecx],eax
mov [edx+ecx],eax
jg @clrmark

@determine_start0_system:
lea ebx,[ebp-01h]
add eax,01h
push esi
@start0system:
lea esi,[esi+ebx*04h]
xor edx,edx
@findfree0:
cmp dword ptr [esi],00h
jz @markitem
@nxrow:
add edx,eax
lea esi,[esi+ebp*04h]
cmp edx,ebp
jnz @findfree0
jmp @nxcol
@markitem:
bts [edi+edx],eax
jc @nxrow
or [edi+ebx],al
add ecx,eax
or [esi+03h],al
@nxcol:
sub ebx,eax
mov esi,[esp]
jns @start0system
pop ebx
mov [SYS0],ecx

cmp ebp,ecx
mov eax,01010101h
jz @count_result
mov ecx,[MTXDBLSIZE]
@clearrowmark:
and [edi],eax
sub ecx,01h
lea edi,[edi+04h]
jnz @clearrowmark
pushad
jmp @@2nd_step

[ Szerkesztve ]

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

(#26) P.H.


P.H.
(Topikgazda)

Magyar módszer, legfejlebb 126x126-os mátrixokra, a mátrixelemek nagysága legfeljebb 00FFFFFFh. A sebességkülönbség kb. 3-szoros az új kód javára úgy, hogy a mátrix teljesen belefér (és belefért régen is) az L1D-be.

Jelenlegi kód:
pushad
@@REDUCE_ROWS:
mov esi,00FFFFFFh
mov edi,eax
mov edx,ebp
@rowmin:
mov eax,esi
mov ebx,edi
mov ecx,ebp
@findrowmin:
cmp eax,[edi]
cmova eax,[edi]
sub ecx,01h
lea edi,[edi+04h]
jnz @findrowmin
cmp eax,esi
mov ecx,ebp
jz @@ABNORMAL_EXIT
@decrow:
xor edi,edi
cmp [ebx],esi
cmovbe edi,eax
sub [ebx],edi
sub ecx,01h
lea ebx,[ebx+04h]
jnz @decrow
sub edx,01h
mov edi,ebx
jnz @rowmin
jmp @@REDUCE_COLUMNS
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@@REDUCE_COLUMNS:
mov ebx,ebp
mov edi,[esp+__MTX]
@colmin:
mov eax,esi
mov ecx,ebp
@findcolmin:
cmp eax,[edi]
cmova eax,[edi]
sub ecx,01h
lea edi,[edi+ebp*04h]
jnz @findcolmin
neg ebp
cmp eax,esi
mov ecx,ebp
jz @@ABNORMAL_EXIT
@deccol:
lea edi,[edi+ebp*04]
xor edx,edx
cmp [edi],esi
cmovbe edx,eax
sub [edi],edx
add ecx,01h
jnz @deccol
neg ebp
sub ebx,01h
lea edi,[edi+04h]
jnz @colmin
@@INITMARKS:
mov ebx,offset(MARKS)
lea ecx,[ebp+ebp]
xor eax,eax
lea edi,[ebx+ebp]
mov esi,[esp+__MTX]
@clrmark:
sub ecx,04h
mov [ebx],eax
lea ebx,[ebx+04h]
jg @clrmark
@@START0_SYSTEM:
xor ebx,ebx
lea esi,[esi+ebp*04h]
add eax,01h
xor ecx,ecx
@start0system:
sub esi,04h
xor edx,edx
sub ebx,eax
push esi
sub edx,ebp
@findfree0:
cmp [esi],eax
jb @markitem
@nxrow:
add edx,eax
lea esi,[esi+ebp*04h]
jnz @findfree0
jmp @nxcol
@markitem:
bts dword ptr [edi+edx],01h
jc @nxrow
add edx,ebp
mov [esi+03h],al
add ecx,eax
mov [edi+edx],bl
or [edi+ebx],al
@nxcol:
lea edx,[ebx+ebp]
pop esi
test edx,edx
jnz @start0system
mov [esp+__SYS0],ecx
@@CLEARROWMARKS:
cmp ebp,ecx
jz @count_result_MTX
@clear_row_mark:
and [edi+ebx],al
add ebx,eax
jnz @clear_row_mark
sub esp,_SAVE
jmp @@2ND_STEP
@@3RD_STEP:
mov byte ptr [esi+03h],02h
and byte ptr [edi+edx],11111110b
@@2ND_STEP:
xor ebx,ebx
mov esi,[esp+_SAVE+__MTX]
xor ecx,ecx
mov edx,00FFFFFFh
sub ebx,ebp
@free0:
sub ecx,ebp
@freerow:
test byte ptr [edi+ebx],02h
jz @zeroinrow
add ebx,01h
lea esi,[esi+ebp*04h]
jnz @freerow
jmp @@5TH_STEP
@zeroinrow:
test byte ptr [edi+ecx],01h
jnz @handlecol
cmp edx,[esi]
jbe @handlecol
mov edx,[esi]
test edx,edx
jz @@DECIDE_NEXT_STEP
add esp,_SAVE
pushad
@handlecol:
add ecx,01h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,01h
jnz @free0
@@5TH_STEP:
xor ecx,ecx
mov esi,[esp+_SAVE+__MTX]
sub ebx,ebp
@nx5row:
sub ecx,ebp
test byte ptr [edi+ebx],02h
jz @decrease_row_free
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
sbb eax,eax
and eax,edx
add [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @increase_double_markeds
jmp @step5row
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @decrease_row_free
@step5row:
add ebx,01h
jnz @nx5row
popad
sub esp,20h
@@DECIDE_NEXT_STEP:
mov edx,0FFFFFF00h
lea eax,[ebx+ebp]
or byte ptr [edi+ebx],02h
add dl,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+_SAVE+__MTX]
add dword ptr [esp+_SAVE+__SYS0],01h
@0colon:
mov [edi+eax],cl
add ecx,ebp
mov byte ptr [esi+03h],01h
xor eax,eax
lea esi,[edx+ecx*04h]
shl ecx,02h
sub eax,ebp
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
add eax,01h
lea esi,[esi+ebp*04h]
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
add eax,ebp
sub esi,ecx
xor ecx,ecx
mov byte ptr [edi+eax],00h
sub ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @0colon
add ecx,01h
lea esi,[esi+04h]
jnz @search_colon_in_row
@error:
nop
@@1ST_STEP:
cmp ebp,[esp+_SAVE+__SYS0]
jz @count_result_STACK
lea edx,[edx+ebp*04h]
push ebp
@remove_row_marks_set_cols:
lea esi,[edx-04h]
sub edi,01h
xor bl,bl
mov ecx,ebp
sub edx,04h
@chkstarmark:
mov al,[esi+03h]
and al,11111101b
mov [esi+03h],al
and al,01h
or bl,al
sub ecx,01h
lea esi,[esi+ebp*04h]
jnz @chkstarmark
sub dword ptr [esp],01h
mov [edi],bl
jnz @remove_row_marks_set_cols
pop ebx
add edi,ebp
jmp @@2ND_STEP
@count_result_STACK:
add esp,_SAVE
@count_result_MTX:
xor ecx,ecx
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
@results:
movsx edx,byte ptr [edi+ecx]
mov byte ptr [edi+ecx],00h
add ecx,01h
add edx,ebp
add eax,[esi+edx*04h]
cmp ecx,ebp
mov [ebx],dl
lea esi,[esi+ebp*04h]
lea ebx,[ebx+01h]
jnz @results

6-7 évvel ezelőtti kód:
mov ecx,[mtxdblsize]
mov edi,[marks]
xor eax,eax
mov ebp,[mtxsize]
mov edx,ecx
rep stosd
lea edi,[tempmarks]
mov ecx,edx
rep stosd

@reduce_rows_with_minimum:
mov edi,[mtx]
mov edx,ebp
mov esi,00FFFFFFh
@row_minimum:
mov ecx,ebp
mov ebx,edi
mov eax,esi
mov ch,cl
@find_row_minimum:
scasd
jb @after_row_test
mov eax,[edi-04h]
@after_row_test:
dec cl
jnz @find_row_minimum
@start_reduce_row:
test eax,eax
jnz @force_reduce_row
dec edx
jnz @row_minimum
jmp @reduce_columns_with_m
@force_reduce_row:
cmp eax,esi
jz @abnormal_exit
@reduce_row_elements:
cmp [ebx],esi
ja @after_row_reduction
sub [ebx],eax
@after_row_reduction:
add ebx,04h
dec ch
jnz @reduce_row_elements
dec edx
jnz @row_minimum

@reduce_columns_with_minimum
mov esi,[mtx]
mov ebx,ebp
lea edi,[ebp*04h]
@column_minimum:
mov ecx,ebp
mov eax,00FFFFFFh
mov edx,esi
mov ch,cl
@find_column_minimum:
cmp [esi],eax
ja @after_column_test
mov eax,[esi]
test eax,eax
jz @next_decrease_column
@after_column_test:
add esi,edi
dec cl
jnz @find_column_minimum
@start_reduce_column:
cmp eax,00FFFFFFh
jz @abnormal_exit
mov esi,edx
@reduce_column_elements:
cmp dword ptr [esi],00FFFF
ja @after_column_reduction
sub [esi],eax
@after_column_reduction:
add esi,edi
dec ch
jnz @reduce_column_element
@next_decrease_column:
lea esi,[edx+04h]
dec ebx
jnz @column_minimum

@determine_start0_system:
mov [sys0],ebx
mov edi,[marks]
mov ebx,ebp
mov eax,0102h
mov esi,[mtx]
xor ecx,ecx
dec ebx
push esi
xor edx,edx
@start_0system:
lea esi,[esi+ebx*04h]
@find_free0:
test [edi+edx],al
jnz @check_next_item
cmp [esi],ecx
jnz @check_next_item
or [edi+edx],al
or [edi+ebx],ah
or [esi+03h],ah
inc [sys0]
jmp @next_column
@check_next_item:
inc edx
lea esi,[esi+ebp*04h]
cmp edx,ebp
jnz @find_free0
@next_column:
mov esi,[esp]
xor edx,edx
dec ebx
jns @start_0system
pop ebx

cmp ebp,[sys0]
jz @count_result
mov ecx,[mtxdblsize]
mov eax,01010101h
@clear_line_marks:
and [edi],eax
add edi,04h
dec ecx
jnz @clear_line_marks
pushad
jmp @@2nd_step
@@1st_step:
mov edi,[marks]
cmp ebp,[sys0]
jz @count_result_with_POPA
mov ebx,ebp
add edi,ebp
mov al,0FDh
lea edx,[edx+ebx*04h-01h]
dec edi
@remove_line_marks_set_cols:
mov esi,edx
mov [edi],bh
mov ecx,ebp
@check_star_mark:
and [esi],al
jz @marks_tested
mov ah,[esi]
and ah,01h
or [edi],ah
@marks_tested:
lea esi,[esi+ebp*04h]
dec ecx
jnz @check_star_mark
@star_next_column:
sub edx,04h
dec edi
dec ebx
jnz @remove_line_marks_set
@@2nd_step:
mov esi,[mtx]
mov ecx,ebp
mov ebx,[marks]
mov edx,00FFFFFFh
@search_free0:
mov edi,[marks]
xor eax,eax
mov ch,byte ptr [mtxsize]
@search_free0_prev_marked:
test byte ptr [ebx],02h
jz @look_for_zero
inc ebx
dec cl
jz @@5th_step
lea esi,[esi+ebp*04h]
jmp @search_free0_prev_mar
@look_for_zero:
test byte ptr [edi],01h
jnz @handle_column_counter
cmp edx,[esi]
jle @handle_column_counter
mov edx,[esi]
test edx,edx
jz @decide_next_step
add esp,20h
pushad
jmp @step_next_item
@handle_column_counter:
test byte ptr [esi+03h],01
jz @step_next_item
mov eax,edi
@step_next_item:
add esi,04h
inc edi
dec ch
jnz @look_for_zero
inc ebx
dec cl
jnz @search_free0
jmp @@5th_step
@decide_next_step:
mov edx,0102h
or [ebx],dl
test eax,eax
jz @continue_search
@@3rd_step:
and byte ptr [eax],0FEh
mov [esi+03h],dl
jmp @@2nd_step
@continue_search:
mov ebx,ecx
lea eax,[esi+03h]
dec ch
jz @@4th_step
add esi,07h
inc edi
@search_0star:
test [esi],dh
jz @next_0star_test
and byte ptr [edi],0FEh
or [eax],dl
jmp @@2nd_step
@next_0star_test:
add esi,04h
inc edi
dec ch
jnz @search_0star
@@4th_step:
or [eax],dh
xor ecx,ecx
xor edx,edx
inc [sys0]
mov cl,bl
mov edi,ebp
mov dl,bh
sub edi,ecx
mov ecx,ebp
mov eax,[mtx]
lea ebx,[ebp*04h]
sub ecx,edx
mov dl,01h
push eax
@check_column:
shl ecx,02h
lea esi,[eax+ecx+03h]
xor eax,eax
@search_star_in_column:
test [esi],dl
jz @prepare_for_next_item
cmp eax,edi
jnz @found_0_star
@prepare_for_next_item:
inc eax
add esi,ebx
cmp ebp,eax
jnz @search_star_in_column
pop edx
jmp @@1st_step
@found_0_star:
mov byte ptr [esi],00h
sub esi,ecx
mov edi,eax
xor ecx,ecx
mov eax,0102h
@search_colon_in_row:
test [esi],al
jnz @found_0_colon
inc ecx
add esi,04h
cmp ecx,ebp
jnz @search_colon_in_row
@found_0_colon:
mov [esi],ah
mov eax,[esp]
mov dl,01h
jmp @check_column
@@5th_step:
mov esi,[mtx]
sub ebx,ebp
mov ecx,ebp
mov al,01h
mov ebp,ebx
add esi,03h
@decrease_next_row:
mov ch,[esp+08h]
mov edi,ebp
test byte ptr [ebx],02h
jz @start_decrease_current
mov ah,0FCh
@increase_double_markeds:
test [edi],al
jz @step_next_element
test [esi],ah
jnz @step_next_element
add [esi-03h],edx
@step_next_element:
add esi,04h
inc edi
dec ch
jnz @increase_double_marke
inc ebx
dec cl
jnz @decrease_next_row
popad
pushad
jmp @decide_next_step
@start_decrease_current_row:
mov ah,0FFh
@decrease_current_row:
test [edi],al
jnz @jump_next_element
test [esi],ah
jnz @jump_next_element
sub [esi-03h],edx
@jump_next_element:
add esi,04h
inc edi
dec ch
jnz @decrease_current_row
@step_on_next_row:
inc ebx
dec cl
jnz @decrease_next_row
popad
pushad
jmp @decide_next_step
@count_result_with_POPAD:
add esp,20h
@count_result:
mov esi,[save]
shl ebp,02h
mov ebx,edi
xor ecx,ecx
mov edi,[mtx]
mov eax,01000000h
push edi
mov edx,[sys0]
@count_optimum:
@test_elements:
scasd
jnz @test_elements
@increase_optimum:
sub edi,04h
sub edi,[esp]
add [esp],ebp
add ecx,[esi+edi]
add esi,ebp
shr edi,02h
mov [ebx],edi
inc ebx
dec edx
mov edi,[esp]
jnz @count_optimum
@store_optimum:
pop eax
shr ebp,02h
mov eax,ecx

[ Szerkesztve ]

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

(#27) P.H.


P.H.
(Topikgazda)

Algoritmusban felhasználásra kihegyezve (több 100000 lefutás); Shanghai-on 1.4 IPC, ezredmásodpercenként legalább 20 db 25x25-ös mátrix megoldása.

pushad
mov ebx,offset(MARKS)
lea ecx,[ebp+ebp]
xor edx,edx
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub ecx,04h
mov [ebx],edx
lea ebx,[ebx+04h]
jg @mark0
@@REDUCE_ROWS:
mov [esp+__SYS0],ebp
mov ebx,ebp
@rowmin:
mov esi,01000000h
xor edx,edx
mov ecx,ebp
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,01h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,01000000h
jz @specific
lea eax,[eax+ebp*04h]
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,01h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
test byte ptr [edi+edx],01h
jz @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
or byte ptr [edi+ebx],10h
add ecx,ebx
or byte ptr [edi+edx],01h
add dword ptr [esp+__SYS0],01h
mov [edi+ecx],dl
@reducenxrow:
add ebx,01h
jnz @rowmin
@@REDUCE_COLUMNS:
mov ebx,ebp
mov esi,[esp+__MTX]
@colmin:
mov ecx,ebp
xor eax,eax
mov edx,01000000h
neg ebp
@findcolmin:
cmp edx,[esi]
cmovz eax,ecx
cmova edx,[esi]
add ecx,01h
lea esi,[esi+ebp*04h]
jnz @findcolmin
neg ebp
cmp edx,01000000h
mov ecx,ebp
jb @subcol
test eax,eax
jz @@ABNORMAL_EXIT
@subcol:
lea esi,[esi+ebp*04h]
xor eax,eax
cmp byte ptr [esi+03h],00h
cmovz eax,edx
sub [esi],eax
add ecx,01h
jnz @subcol
add ebx,01h
lea esi,[esi+04h]
jnz @colmin
mov eax,00000001h
neg ebp
@@START0_SYSTEM:
xor ecx,ecx
sub esi,04h
sub ebx,eax
sub ecx,ebp
mov edx,esi
@findfree0:
cmp [esi],eax
jb @markitem
@nxrow:
add ecx,eax
lea esi,[esi+ebp*04h]
jnz @findfree0
jmp @nxcol
@markitem:
bts dword ptr [edi+ecx],04h
jc @nxrow
add ecx,ebp
mov [esi+03h],al
add [esp+__SYS0],eax
mov [edi+ecx],bl
or [edi+ebx],al
@nxcol:
lea ecx,[ebx+ebp]
mov esi,edx
test ecx,ecx
jnz @@START0_SYSTEM
cmp [esp+__SYS0],ecx
jz @count_result_MTX
sub esp,_SAVE
jmp @@2ND_STEP
@@3RD_STEP:
mov byte ptr [esi+03h],02h
and byte ptr [edi+edx],11111110b
@@2ND_STEP:
xor ebx,ebx
mov esi,[esp+_SAVE+__MTX]
xor ecx,ecx
mov edx,00FFFFFFh
sub ebx,ebp
@free0:
sub ecx,ebp
@freerow:
test byte ptr [edi+ebx],02h
jz @zeroinrow
add ebx,01h
lea esi,[esi+ebp*04h]
jnz @freerow
jmp @@5TH_STEP
@zeroinrow:
xor eax,eax
test byte ptr [edi+ecx],01h
jnz @nx2col
add eax,[esi]
jz @@DECIDE_NEXT_STEP
cmp edx,eax
cmova edx,eax
jbe @nx2col
add esp,_SAVE
pushad
@nx2col:
add ecx,01h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,01h
jnz @free0
@@5TH_STEP:
xor ecx,ecx
mov esi,[esp+_SAVE+__MTX]
sub ebx,ebp
@nx5row:
sub ecx,ebp
test byte ptr [edi+ebx],02h
jz @decrease_row_free
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
sbb eax,eax
and eax,edx
add [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @increase_double_markeds
jmp @step5row
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @decrease_row_free
@step5row:
add ebx,01h
jnz @nx5row
popad
sub esp,20h
@@DECIDE_NEXT_STEP:
mov edx,0FFFFFF00h
lea eax,[ebx+ebp]
or byte ptr [edi+ebx],02h
add dl,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+_SAVE+__MTX]
@colon_to_star:
mov [edi+eax],cl
add ecx,ebp
mov byte ptr [esi+03h],01h
xor eax,eax
lea esi,[edx+ecx*04h]
shl ecx,02h
and byte ptr [edi+ebx],11111101b
sub eax,ebp
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
add eax,01h
lea esi,[esi+ebp*04h]
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
add eax,ebp
sub esi,ecx
xor ecx,ecx
mov byte ptr [edi+eax],00h
sub ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @colon_to_star
add ecx,01h
lea esi,[esi+04h]
jnz @search_colon_in_row
@error:
nop
@@1ST_STEP:
xor ebx,ebx
xor eax,eax
add dword ptr [esp+_SAVE+__SYS0],01h
jz @count_result_STACK
sub ebx,ebp
mov cl,[edi+00h]
jmp @nxclear
@clear_colon:
and byte ptr [esi+03h],11111101b
add eax,01h
lea esi,[esi+04h]
jnz @clear_colon
@nxclear:
sub eax,ebp
@markedrow:
test byte ptr [edi+ebx],02h
mov esi,edx
mov byte ptr [edi+ebx],00h
jnz @clear_colon
add ebx,01h
lea edx,[edx+ebp*04h]
jnz @markedrow
@markcol:
movsx edx,byte ptr [edi+ebx]
add ebx,01h
add eax,01h
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],cl
jmp @@2ND_STEP
@count_result_STACK:
add esp,_SAVE
@count_result_MTX:
xor ecx,ecx
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
movsx edx,byte ptr [edi+ecx]
add ecx,01h
add edx,ebp
add eax,[esi+edx*04h]
cmp ecx,ebp
mov [ebx],dl
lea esi,[esi+ebp*04h]
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#28) P.H.


P.H.
(Topikgazda)

Utolsó felvonás, két bevezető ciklus összevonása után.

Néhány IPC-mérés a lépések ciklusaira (végtelen ciklusban mérve):
@@REDUCE_ROWS:1.8 IPC
@@REDUCE_COLUMNS:1.6 IPC
@@2ND_STEP: 0.9 IPC (ez a leggyakrabban lefutó ciklus)
@@5TH_STEP: 2.2 IPC
@@1ST_STEP: 1.5 IPC

Úgy tűnik, az AMD-n (a Bulldozer-ig bezárólag) a legjobb stratégia az, ha a ciklusokban az utasítások fele [ ] referenciát tartalmaz, azaz a memóriahivatkozások mellett bizonyos ADD reg,imm és MOV reg,reg utasítások helyett azok LEA reg,[reg+imm] vagy LEA reg,[reg] megfelelőiket használom, ezek méretre ugyanakkorák, viszont a 3 AGU valamelyikében futnak az ALU-k helyett.

pushad
mov ebx,offset(MARKS)
lea edx,[ebp+ebp]
xor ecx,ecx
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx],ecx
lea ebx,[ebx+04h]
jg @mark0
@@REDUCE_ROWS:
mov [esp+__SYS0],ebp
mov ebx,ebp
sub esp,_SAVE
@rowmin:
mov ecx,ebp
mov esi,01000000h
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,01h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,01000000h
jz @specific
lea eax,[eax+ebp*04h]
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,01h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
test byte ptr [edi+edx],01h
jz @mark
@@ABNORMAL_EXIT:
add esp,40h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
or byte ptr [edi+ebx],10h
add ecx,ebx
or byte ptr [edi+edx],01h
add dword ptr [esp+_SAVE+__SYS0],01h
mov [edi+ecx],dl
jz @count_result_STACK
@reducenxrow:
add ebx,01h
jnz @rowmin
@@RECUDE_COLUMNS:
neg ebp
@nxcolmin:
mov edx,ebp
sub ebx,01h
sub eax,04h
add edx,ebx
js @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @nxcolmin
neg ebp
mov edx,01000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add ecx,01h
lea eax,[eax+ebp*04h]
jnz @findcolmin
lea ecx,[ebp-01h]
neg ebp
cmp edx,01000000h
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,01h
jz @nxcolmin
lea eax,[eax+ebp*04h]
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],04h
jc @subcol
bts dword ptr [edi+ebx],00h
lea esi,[ecx+ebp]
jc @subcol
add dword ptr [esp+_SAVE+__SYS0],01h
mov byte ptr [eax+03h],01h
mov [edi+esi],bl
jnz @subcol
jmp @count_result_STACK
@@3RD_STEP:
or byte ptr [edi+ebx],02h
mov byte ptr [esi+03h],02h
and byte ptr [edi+edx],11111110b
@@2ND_STEP:
xor ebx,ebx
mov esi,[esp+_SAVE+__MTX]
xor ecx,ecx
mov edx,00FFFFFFh
sub ebx,ebp
@free0:
sub ecx,ebp
@freerow:
test byte ptr [edi+ebx],02h
jz @zeroinrow
add ebx,01h
lea esi,[esi+ebp*04h]
jnz @freerow
jmp @@5TH_STEP
@zeroinrow:
xor eax,eax
test byte ptr [edi+ecx],01h
jnz @nx2col
add eax,[esi]
jz @@DECIDE_NEXT_STEP
cmp edx,eax
jbe @nx2col
add esp,_SAVE
lea edx,[eax] //mov edx,eax
pushad
@nx2col:
add ecx,01h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,01h
jnz @free0
@@5TH_STEP:
xor ecx,ecx
mov esi,[esp+_SAVE+__MTX]
sub ebx,ebp
@nx5row:
sub ecx,ebp
test byte ptr [edi+ebx],02h
jnz @increase_double_markeds
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @decrease_row_free
jmp @step5row
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
mov eax,00000000h
cmovc eax,edx
add [esi],eax
add ecx,01h
lea esi,[esi+04h]
jnz @increase_double_markeds
@step5row:
add ebx,01h
jnz @nx5row
jmp @@5TH_STEP
popad
sub esp,20h
@@DECIDE_NEXT_STEP:
mov edx,0FFFFFF00h
lea eax,[ebx+ebp]
add dl,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+_SAVE+__MTX]
@colon_to_star:
mov [edi+eax],cl
add ecx,ebp
mov byte ptr [esi+03h],01h
xor eax,eax
lea esi,[edx+ecx*04h]
shl ecx,02h
and byte ptr [edi+ebx],11111101b
sub eax,ebp
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
add eax,01h
lea esi,[esi+ebp*04h]
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
add eax,ebp
sub esi,ecx
xor ecx,ecx
mov byte ptr [edi+eax],00h
sub ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @colon_to_star
add ecx,01h
lea esi,[esi+04h]
jnz @search_colon_in_row
@error:
nop
@@1ST_STEP:
xor ebx,ebx
xor eax,eax
add dword ptr [esp+_SAVE+__SYS0],01h
jz @count_result_STACK
sub ebx,ebp
mov cl,[edi+00h]
jmp @nxclear
@clear_colon:
and byte ptr [esi+03h],11111101b
add eax,01h
lea esi,[esi+04h]
jnz @clear_colon
@nxclear:
sub eax,ebp
@markedrow:
test byte ptr [edi+ebx],02h
mov esi,edx
mov byte ptr [edi+ebx],00h
jnz @clear_colon
add ebx,01h
lea edx,[edx+ebp*04h]
jnz @markedrow
@markcol:
movsx edx,byte ptr [edi+ebx]
add eax,01h
lea ebx,[ebx+01h]
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],cl
jmp @@2ND_STEP
@count_result_STACK:
{ EDI -> MARKS memory end
EBP: row/column quantity
add esp,_SAVE
xor ecx,ecx
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
movsx edx,byte ptr [edi+ecx]
lea ecx,[ecx+01h]
add edx,ebp
add eax,[esi+edx*04h]
cmp ecx,ebp
mov [ebx],dl
lea esi,[esi+ebp*04h]
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#29) P.H. válasza P.H. (#28) üzenetére


P.H.
(Topikgazda)

@@2ND_STEP lecserélve, "kiegyenesítve", így már 0.9 IPC helyett hozza a 2.0 IPC-t, kevesebb utasítással.
A teljes, előzőekben említett algoritmus IPC-je így már (mivel a 2. step lefutása a leggyakoribb) 1.9 körüli.

Carry Flag a programozó legjobb barátja ... legalábbis AMD-n

@@2ND_STEP:
xor ecx,ecx
xor ebx,ebx
mov esi,[esp+_SAVE+__MTX]
mov edx,00FFFFFFh
sub ebx,ebp
@free0:
sub ecx,ebp
@zeroinrow:
bt dword ptr [edi+ebx],01h
setc al
bt dword ptr [edi+ecx],00h
adc al,00h
cmp edx,[esi]
adc al,00h
jnz @nx2col
xor edx,edx
add esp,_SAVE
add edx,[esi]
pushad
jz @@DECIDE_NEXT_STEP
@nx2col:
add ecx,01h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,01h
jnz @free0

[ Szerkesztve ]

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

(#30) P.H. válasza P.H. (#29) üzenetére


P.H.
(Topikgazda)

Lemérve.

Előző:
"Algoritmusban felhasználásra kihegyezve (több 100000 lefutás); Shanghai-on 1.4 IPC, ezredmásodpercenként legalább 20 db 25x25-ös mátrix megoldása."

Az újjal:
"Algoritmusban felhasználásra kihegyezve (több 100000 lefutás); Shanghai-on 1.9 IPC, ezredmásodpercenként legalább 28 db 25x25-ös mátrix megoldása."

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

(#31) P.H.


P.H.
(Topikgazda)

@@2ND_STEP újra módosítva, mostmár az Intel CPU-kon is hozza a 2.0 IPC-t, így a teljes algoritmus is (Intel esetében az ADC és SBB legalább Pentium Pro óta, a CMOVcc legalább Core2 óta 2 micro-op, egészen Nehalem-ig :(( , AMD-nél K7 óta 1 micro-op, 1 órajel lefutási idővel; pedig ezek az ugrásmentesítés és az ILP-kihasználás alapkövei a SETcc mellett).

Mivel az utasításszám is csökkent és a belső ciklustörzsből is kiemelhető pár utasítás, így AMD-n is gyorsabb az előzőnél egy kicsivel.

Az első adandó alkalommal lemér(et)em Bobcat-on is. Ha ott is tudja hozni a 2 körüli IPC-t, akkor mivel nagyon hasonlóak felépítésben - a Bulldozer az emelt órajeleivel valóban speed racer lesz integer-ben - ha marad a legtöbb integer utasítás 1 órajeles lefutási értéke.

@@2ND_STEP:
xor ebx,ebx
xor ecx,ecx
mov esi,[esp+_SAVE+__MTX]
sub ebx,ebp
mov edx,00FFFFFFh
@free0:
bt dword ptr [edi+ebx],01h
setc ah
sub ecx,ebp
@zeroinrow:
mov al,[edi+ecx]
and al,01h
cmp edx,[esi]
adc al,ah
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
pushad
jz @@DECIDE_NEXT_STEP
@nx2col:
add ecx,01h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,01h
jnz @free0

[ Szerkesztve ]

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

(#32) P.H.


P.H.
(Topikgazda)

Kód, még jobban kiegyenesítve, mostmár a teljes mártix egy ciklus, egy-egy sora helyett. AMD-n 2.3 IPC.

@@2ND_STEP:
neg ebp
mov esi,[esp+__MTX]
sub esp,20h
mov ebx,ebp
mov edx,00FFFFFFh
mov ecx,ebp
@zeroinrow:
bt dword ptr [edi+ebx],01h
setc ah
mov al,[edi+ecx]
and al,01h
cmp edx,[esi]
adc al,ah
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
jz @@DECIDE_NEXT_STEP
pushad
@nx2col:
add cl,01h
lea esi,[esi+04h]
cmovz ecx,ebp
adc ebx,00h
jnz @zeroinrow

Most szembesültem először azzal igazán, hogy az AMD féle generális "single cycle execution" + a 2 loads/cycle felépítésre megírt program Intel-en (Core2) fájóan lassabb, mint AMD-n. No ekkor mit lehet csinálni? Az általános gyors vagy AMD-specializált (de az általánosan elterjedt CPU-kon lassabb) megoldás a jobb?

[ Szerkesztve ]

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

(#33) P.H.


P.H.
(Topikgazda)

Kissé átszerkesztve a teljes algoritmust (teljesen 32 bites adatokon dolgozik) az utasításszám csökkent.
Generálisan AMD-re és Intel-re:

pushad
mov ebx,offset(MARKS)
lea edx,[ebp+ebp]
xor ecx,ecx
lea edi,[ebx+ebp*04h]
imul ebp,BYTE(-4)
@mark0:
sub edx,01h
mov [ebx],ecx
lea ebx,[ebx+04h]
jg @mark0
@@REDUCE_ROWS:
mov [esp+__SYS0],ebp
mov ebx,ebp
@rowmin:
mov ecx,ebp
mov esi,01000000h
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,01000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
test byte ptr [edi+edx],01h
jz @mark
@@ABNORMAL_EXIT:
add esp,20h
stc
ret
@mark:
or byte ptr [edi+ebx],10h
add ecx,ebx
or byte ptr [edi+edx],01h
add dword ptr [esp+__SYS0],04h
mov [edi+ecx],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,01000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,01000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],04h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
add dword ptr [esp+__SYS0],04h
mov byte ptr [eax+03h],01h
mov [edi+esi],ebx
jnz @subcol
jmp @count_result_STACK
@@3RD_STEP:
or byte ptr [edi+ebx],02h
mov byte ptr [esi+03h],02h
and byte ptr [edi+edx],11111110b
@@2ND_STEP:
mov esi,[esp+__MTX]
sub esp,20h
mov ebx,ebp
mov edx,00FFFFFFh
@nx2row:
bt dword ptr [edi+ebx],01h
mov ecx,ebp
setc ah
@zeroinrow:
mov al,[edi+ecx]
and al,01h
cmp edx,[esi]
adc al,ah
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
jz @@DECIDE_NEXT_STEP
pushad
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add ebx,04h
jnz @nx2row
@@5TH_STEP:
mov esi,[esp+_SAVE+__MTX]
mov ebx,ebp
@nx5row:
test byte ptr [edi+ebx],02h
mov ecx,ebp
jnz @increase_double_markeds
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @decrease_row_free
jmp @step5row
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
mov eax,00000000h
cmovc eax,edx
add [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @increase_double_markeds
@step5row:
add ebx,04h
jnz @nx5row
popad
xor edx,edx
@@DECIDE_NEXT_STEP:
mov eax,ebx
sub eax,ebp
add edx,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
@colon_to_star:
mov [edi+eax],ecx
sub ecx,ebp
mov byte ptr [esi+03h],01h
lea esi,[edx+ecx]
mov eax,ebp
and byte ptr [edi+ebx],11111101b
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub eax,ebp
sub esi,ecx
mov dword ptr [edi+eax],00000000h
mov ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @colon_to_star
add ecx,04h
lea esi,[esi+04h]
jmp @search_colon_in_row
@@1ST_STEP:
add dword ptr [esp+__SYS0],04h
jz @count_result_STACK
mov ebx,ebp
mov ecx,[edi+00h]
jmp @nxclear
@clear_colon:
and byte ptr [esi+03h],11111101b
add eax,04h
lea esi,[esi+04h]
jnz @clear_colon
@nxclear:
mov eax,ebp
@markedrow:
test byte ptr [edi+ebx],02h
mov esi,edx
mov byte ptr [edi+ebx],00h
jnz @clear_colon
sub edx,ebp
add ebx,04h
jnz @markedrow
@markcol:
mov edx,[edi+ebx]
add eax,04h
lea ebx,[ebx+04h]
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],ecx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#34) P.H.


P.H.
(Topikgazda)

Nem hagy(ott) nyugodni a kisördög. A teljesen 32 bitesre átírással megnyílt pár lehetőség: külön jelölő byte az oszlopnak, külön a sornak, külön a bevezető sorjelölésnek, így sikerült drasztikusan csökkenteni a load-op-store utasításokat, sima store-ral helyettesítve őket.

Kombinálva ezt az AMD 2 load/cycle felépítésével, sikerült elérni a 30 db 25x25-ös mátrix per ezredmásodperc teljesítményt, 2.6 GHz-es Shanghai-on.

Csak Intel-en ne lenne fele ilyen gyors így, 2.5 GHz Core2-n tesztelve... (Sandy Bridge-ig, ami ugyancsak 2 load/cycle felépítésű - lesz -).

Az algoritmuson látható, hogy egyetlen szorzáson kívül összeadás, kivonásnál és bitmanipulációknál bonyolultabb utasítás nincs benne benne (ADC, SBB és CMOVcc viszont elég sok van), a skálázott memóriahozzáférést sem használom már ki, viszont egy pointer-rel két adatterületet is címzek, egyet-egyet a pozitív és a negatív oldalán.

pushad
lea edx,[ebp*08h]
mov ebx,offset(MARKS)
xor ecx,ecx
lea edi,[ebx+ebp*04h]
imul ebp,BYTE(-4)
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,01000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,01000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
bts dword ptr [edi+edx],00h
jnc @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,01000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,01000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],10h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
sub dword ptr [esp+__SYS0],01h
mov byte ptr [eax+03h],01h
mov [edi+esi],ebx
jnz @subcol
jmp @count_result_STACK
@@3RD_STEP:
mov byte ptr [esi+03h],02h
mov byte ptr [edi+ebx+01h],01h
mov byte ptr [edi+edx],00h
@@2ND_STEP:
mov esi,[esp+__MTX]
sub esp,20h
mov eax,ebp
mov edx,00FFFFFFh
@nx2row:
mov bh,[edi+eax+01h]
mov ecx,ebp
@zeroinrow:
mov bl,[edi+ecx]
and bl,01h
cmp edx,[esi]
adc bl,[edi+eax+01h]
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
jz @@DECIDE_NEXT_STEP
pushad
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add eax,04h
jnz @nx2row
@@5TH_STEP:
mov ebx,ebp
mov esi,[esp+_SAVE+__MTX]
@nx5row:
cmp byte ptr [edi+ebx+01h],00h
mov ecx,ebp
jnz @increase_double_markeds
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @decrease_row_free
jmp @step5row
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
mov eax,00000000h
cmovc eax,edx
add [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @increase_double_markeds
@step5row:
add ebx,04h
jnz @nx5row
popad
xor edx,edx
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
@colon_to_star:
mov [edi+eax],ecx
sub ecx,ebp
mov byte ptr [esi+03h],01h
lea esi,[edx+ecx]
mov eax,ebp
mov byte ptr [edi+ebx+01h],00h
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub eax,ebp
sub esi,ecx
mov dword ptr [edi+eax],00000000h
mov ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @colon_to_star
add ecx,04h
lea esi,[esi+04h]
jnz @search_colon_in_row
@error:
nop
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
jz @count_result_STACK
mov ebx,ebp
mov ecx,[edi+00h]
jmp @nxclear
@clear_colon:
and byte ptr [esi+03h],11111101b
add eax,04h
lea esi,[esi+04h]
jnz @clear_colon
@nxclear:
mov eax,ebp
@markedrow:
cmp byte ptr [edi+ebx+01h],00h
mov esi,edx
mov dword ptr [edi+ebx],00000000h
jnz @clear_colon
sub edx,ebp
add ebx,04h
jnz @markedrow
@markcol:
mov edx,[edi+ebx]
add eax,04h
lea ebx,[ebx+04h]
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],ecx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#35) P.H.


P.H.
(Topikgazda)

Korrekció: benne maradt néhány letiltott utasítás.
A @@2ND_STEP így néz ki:

@@2ND_STEP:
mov esi,[esp+__MTX]
sub esp,20h
mov eax,ebp
mov edx,00FFFFFFh
@nx2row:
mov ecx,ebp
@zeroinrow:
mov bl,[edi+ecx]
cmp edx,[esi]
adc bl,[edi+eax+01h]
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
jz @@DECIDE_NEXT_STEP
pushad
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add eax,04h
jnz @nx2row

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

(#36) P.H.


P.H.
(Topikgazda)

- a VectorPath PUSHAD kiváltható 3 tárolással
- a @@2ND_STEP-ben levő, körülugrált kicsi valószínűségű ág máshová került
- plusz 2 utasítás többletadminisztációval 2 keresőciklus feleslegessé vált
- a sorok és oszlopok, valamint a speciális mátrixelemek jelölő byte-értékeinek összehangolása után (mely érték 1, azaz közvetlenül másoható Carry Flag-be BT-vel regiszterhasználat nélkül; mely jelölések összege milyen esetekben pontosan 0) a @@5TH_STEP fele feleslegessé vált

2.0 IPC-vel, 36 25x25 mátrix-ot old meg ezredmásodpercenként.

pushad
shl ebp,02h
mov ebx,offset(MARKS)
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,02000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
bts dword ptr [edi+edx],00h
jnc @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,02000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],10h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
sub dword ptr [esp+__SYS0],01h
mov byte ptr [eax+03h],02h
mov [edi+esi*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK

@@3RD_STEP:
mov byte ptr [esi+03h],08h
mov byte ptr [edi+ebx+01h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
mov eax,ebp
mov edx,00FFFFFFh
mov esi,[esp+__MTX]
@nx2row:
mov ecx,ebp
mov bh,[edi+eax+01h]
@zeroinrow:
cmp edx,[esi]
mov bl,bh
sbb bl,[edi+ecx]
jz @minimum
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add eax,04h
jnz @nx2row
@@5TH_STEP:
mov ebx,ebp
mov esi,[esp+__MTX]
@nx5row:
movsx eax,byte ptr [edi+ebx+01h]
mov ecx,ebp
xor eax,edx
jns @decrease_row_free
neg edx
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,[edi+ebx+01h]
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add esi,04h
add ecx,04h
jnz @decrease_row_free
add ebx,04h
jnz @nx5row
mov eax,[esp+__FREE0ROW]
xor edx,edx
mov ecx,[esp+__FREE0COL]
mov esi,[esp+__FREE0]
jmp @@DECIDE_NEXT_STEP
@minimum:
xor edx,edx
mov [esp+__FREE0ROW],eax
add edx,[esi]
mov [esp+__FREE0COL],ecx
mov [esp+__FREE0],esi
jnz @nx2col
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax*02h+__0STAR]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
jmp @colon_to_star
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub esi,ecx
sub eax,ebp
sub esi,ebp
mov ecx,[edi+eax*02h+__COLON]
lea esi,[esi+ecx]
@colon_to_star:
mov [edi+eax*02h+__0STAR],ecx
sub ecx,ebp
mov byte ptr [esi+03h],02h
lea esi,[edx+ecx]
mov eax,ebp
@search_star_in_column:
test byte ptr [esi+03h],02h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
lea ebx,[edi+__COLON]
mov ecx,ebp
jz @count_result_STACK
@restructure:
mov esi,[ebx]
sub edx,ebp
mov [edi+ecx],eax
and byte ptr [edx+esi+03h],11110111b
add ecx,04h
mov [ebx],eax
lea ebx,[ebx+08h]
jnz @restructure
mov ebx,edi
mov eax,ebp
mov ecx,[edi+00h]
@markcol:
mov edx,[ebx+__0STAR]
add eax,04h
lea ebx,[ebx+08h]
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],ecx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx*02h+__0STAR]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

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

(#37) P.H.


P.H.
(Topikgazda)

Az 5. és az 1. lépés finomhangolása után, valamint a munkaterület címe bemeneti paraméter lett (a hívó algoritmus többszálúsítása okán):

2.0 IPC-vel, 38 25x25 mátrix-ot old meg ezredmásodpercenként.

pushad
shl ebp,02h
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,02000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
bts dword ptr [edi+edx],00h
jnc @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,02000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],10h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
sub dword ptr [esp+__SYS0],01h
mov byte ptr [eax+03h],02h
mov [edi+esi*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK

@@3RD_STEP:
mov byte ptr [esi+03h],08h
mov byte ptr [edi+ebx+03h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
mov eax,ebp
mov esi,[esp+__MTX]
mov edx,00FFFFFFh
@nx2row:
mov bh,[edi+eax+03h]
mov ecx,ebp
@zeroinrow:
cmp edx,[esi]
mov bl,bh
sbb bl,[edi+ecx]
jz @minimum
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add eax,04h
jnz @nx2row
@@5TH_STEP:
mov ebx,ebp
mov esi,[esp+__MTX]
@nx5row:
mov eax,edx
sub ecx,edx
xor eax,[edi+ebx]
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,[edi+ebx+03h]
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add esi,04h
add ecx,04h
jnz @decrease_row_free
add ebx,04h
jnz @nx5row
mov eax,[esp+__FREE0ROW]
xor edx,edx
mov ecx,[esp+__FREE0COL]
mov esi,[esp+__FREE0]
jmp @@DECIDE_NEXT_STEP
@minimum:
xor edx,edx
mov [esp+__FREE0ROW],eax
add edx,[esi]
mov [esp+__FREE0COL],ecx
mov [esp+__FREE0],esi
jnz @nx2col
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax*02h+__0STAR]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
jmp @colon_to_star
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub esi,ecx
sub eax,ebp
sub esi,ebp
mov ecx,[edi+eax*02h+__COLON]
lea esi,[esi+ecx]
@colon_to_star:
mov [edi+eax*02h+__0STAR],ecx
sub ecx,ebp
mov byte ptr [esi+03h],02h
lea esi,[edx+ecx]
mov eax,ebp
@search_star_in_column:
cmp eax,ebx
jz @nxstar
test byte ptr [esi+03h],02h
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
mov ecx,ebp
mov ebx,edi
jz @count_result_STACK
push dword ptr [edi]
@restructure:
mov esi,[ebx+__COLON]
sub edx,ebp
mov [edi+ecx+03h],al
and byte ptr [edx+esi+03h],11110111b
mov esi,[ebx+__0STAR]
add ecx,04h
mov [ebx+__COLON],eax
lea ebx,[ebx+08h]
mov byte ptr [edi+esi],01h
jnz @restructure
pop dword ptr [edi]
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx*02h+__0STAR]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#38) P.H.


P.H.
(Topikgazda)

1 GHz-es Brazos (max. 2 utasítás/órajel micro-arch) az utoljára írt kóddal: átlagosan 1.5 IPC

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Retired uops
Counter 2 : Instructions per cycle (IPC)
Counter 3 : L1 Data cache misses

65950 881.3 1379.8 1.6 0.2
66000 821.5 1163.5 1.4 0.5
66050 820.2 1261.3 1.5 0.3
66100 737.5 994.7 1.3 0.8
66150 737.5 994.7 1.3 0.8
66200 842.2 1192.9 1.4 0.7
66250 801.5 1210.0 1.5 0.3
66300 767.6 994.4 1.3 1.1
66350 840.1 1273.6 1.5 0.3
66400 855.2 1334.0 1.6 0.3
66450 823.4 1196.1 1.4 0.7
66500 733.6 1016.0 1.4 0.7
66550 787.5 1134.9 1.4 0.6
66600 828.6 1204.5 1.4 0.5
66650 909.5 1380.5 1.5 0.4
66700 781.3 1157.5 1.5 0.5
66750 816.6 1163.7 1.4 0.6
66800 805.0 1149.6 1.4 0.6
66850 777.0 1089.3 1.4 0.6
66900 815.3 1205.9 1.5 0.5
66950 804.8 1222.9 1.5 0.4
67000 790.1 1026.5 1.3 0.7
67050 737.5 983.0 1.3 0.8
67100 826.8 1275.2 1.5 0.3
67150 795.9 1153.1 1.4 0.6
67200 760.8 1068.4 1.4 0.6
67250 822.5 1218.7 1.5 0.5
67300 828.5 1223.5 1.5 0.5
67350 817.5 1150.6 1.4 0.4
67400 811.8 1214.2 1.5 0.4
67450 755.6 1051.2 1.4 0.7
67500 858.5 1315.3 1.5 0.4
67550 754.6 1080.0 1.4 0.6
67600 863.4 1195.5 1.4 0.6
67650 750.7 1065.4 1.4 0.6

[ Szerkesztve ]

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

(#39) P.H.


P.H.
(Topikgazda)

SSE1 line algoritmus azonos stílusú vonalak láncolt listájára + 1st gen. Nerburst és K10 port elemzés:
(»port latency (uops) subunit« formában)

K10-en kb. 10%-kal gyorsabb, mint az x87-es megvalósítás, Prescott-on a sebességnövekedés több, mint kétszeres az x87-hez képest.
K10-en 1.6 IPC mérhető (kb. 30000 vonalas tesztadaton 10,5M órajel), Netburst-re visszaszámolva (ugyanazon a tesztadaton 26M órajel) 0.65 IPC.

mov ecx,[esi+_DATA1] // p2 2 (1) load p012 3 (1) AGU
pushad // -vector- -vector-
xorps xmm0,xmm0 // p1 2 (1) mmxalu p34 2 (1) FA/M
lea edi,[esi+DATA2] // p0/1 d (1) alu p012 3 (1) AGU
pcmpeqw xmm7,xmm7 // p1 2 (1) mmxalu p34 2 (1) FA/M
cvtpi2ps xmm3,[edi-...+_TOPLEFT] // p1+2 10 (4) mmx+load 7 (2)
xorps xmm1,xmm1 // p1 2 (1) mmxalu p34 2 (1) FA/M
mov esi,[esi+...DEST] // p2 2 (1) load p012 3 (1) AGU
pslld xmm7,1Fh // p1 2 (1) mmxshf p34 3 (1) FA/M
cvtpi2ps xmm2,[edi-...+_RIGHTBOTTOM] // p1+2 10 (4) mmx+load 7 (2)
xorps xmm5,xmm5 // p1 2 (1) mmxalu p34 2 (1) FA/M
shufps xmm3,xmm2,01000000b // p1 4 (1) mmxshf p34 3 (1) FA/M
sub edi,ecx // p0/1 d (1) alu p012 1 (1) ALU
xorps xmm6,xmm6 // p1 2 (1) mmxalu p34 2 (1) FA/M
shufps xmm3,xmm3,11011000b // p1 4 (1) mmxshf p34 3 (1) FA/M
@nxline:
test ebx,ebx // p0/1 d (1) alu p012 1 (1) ALU
jz @return // p0 2 (1) alu p012 1 (1) ALU
mov eax,[ebx+TRECORD.REF] // p2 2 (1) load p012 3 (1) AGU
pcmpeqw xmm2,xmm2 // p1 2 (1) mmxalu p34 2 (1) FA/M
mov ecx,[ebx+TRECORD.SELF] // p2 2 (1) load p012 3 (1) AGU
mov ebp,[eax+THEADER.YCOOR] // p2 2 (1) load p012 3 (1) AGU
pcmpeqw xmm4,xmm4 // p1 2 (1) mmxalu p34 2 (1) FA/M
mov edx,[ecx+THEADER.YCOOR] // p2 2 (1) load p012 3 (1) AGU
psrld xmm2,01h // p1 2 (1) mmxshf p34 3 (1) FA/M
mov eax,[eax+THEADER.XCOOR] // p2 2 (1) load p012 3 (1) AGU
mov ecx,[ecx+THEADER.XCOOR] // p2 2 (1) load p012 3 (1) AGU
sub ebp,edx // p0/1 d (1) alu p012 1 (1) ALU
movaps xmm6,xmm2 // p0 6 (1) mov p345 3 (1) FANY
sub eax,ecx // p0/1 d (1) alu p012 1 (1) ALU
pslld xmm4,25 // p1 2 (1) mmxshf p34 3 (1) FA/M
cvtsi2ss xmm1,ebp // p1 10 (3) fpmmx 14 (3)
mov ebx,[ebx+TRECORD.NX] // p2 2 (1) load p012 3 (1) AGU
cvtsi2ss xmm0,eax // p1 10 (3) fpmmx 14 (3)
andps xmm6,xmm1 // p1 2 (1) mmxalu p34 2 (1) FA/M
andps xmm2,xmm0 // p1 2 (1) mmxalu p34 2 (1) FA/M
psrld xmm4,02h // p1 2 (1) mmxshf p34 3 (1) FA/M
comiss xmm6,xmm2 // p1 6 (2) fpadd p3 (1) FADD
mov [esp+_EBX],ebx // p0+3 2 (3) alu+store p012 3 (1) AGU
cmovbe ebp,eax // 6 (3) p012 1 (1) ALU
cvtsi2ss xmm6,edx // p1 10 (3) fpmmx 14 (3)
setbe al // p1 5 (3) alu p012 1 (1) ALU
jae @inlineMOVEX // p0 2 (1) alu p012 1 (1) ALU
movaps xmm2,xmm0 // p0 6 (1) mov p345 3 (1) FANY
movaps xmm0,xmm1 // p0 6 (1) mov p345 3 (1) FANY
movaps xmm1,xmm2 // p0 6 (1) mov p345 3 (1) FANY
@inlineMOVEX:
test ebp,ebp // p0/1 d (1) alu p012 1 (1) ALU
cvtsi2ss xmm5,ecx // p1 10 (3) fpmmx 14 (3)
jz @nxline // p0 2 (1) alu p012 1 (1) ALU
divss xmm0,xmm1 // p1 23 (1) fpdiv p4 16 (1) FMUL
mov ebx,[esp+_ECX] // p2 2 (1) load p012 3 (1) AGU
shufps xmm4,xmm0,00000000b // p1 4 (1) mmxshf p34 3 (1) FA/M
jns @inlineSETDIR // p0 2 (1) alu p012 1 (1) ALU
neg ebp // p0 d (1) alu p012 1 (1) ALU
xorps xmm4,xmm7 // p1 2 (1) mmxalu p34 2 (1) FA/M
@inlineSETDIR:
test al,al // p0/1 d (1) alu p012 1 (1) ALU
mov al,[edi+ebx-_ADDER+_DRAWCOLOR] // p2 2 (1) load p012 3 (1) AGU
shufps xmm5,xmm6,00000000h // p1 4 (1) mmxshf p34 3 (1) FA/M
jnz @setpixel // p0 2 (1) alu p012 1 (1) ALU
shufps xmm4,xmm4,00001010b // p1 4 (1) mmxshf p34 3 (1) FA/M
@setpixel:
movaps xmm2,xmm3 // p0 6 (1) mov p345 3 (1) FANY
imul edx,[edi+ebx-_ADDER+_DX] // p1+2 15 (4) fpmul+load p0 6 (1) ALU0+AGU
cmpltps xmm2,xmm5 // p1 4 (1) fpadd p3 (1) FADD
add edx,ecx // p0/1 d (1) alu p012 1 (1) ALU
addps xmm5,xmm4 // p1 4 (1) fpadd p3 4 (1) FADD
movmskps ecx,xmm2 // p1 6 (2) fp p34 3 (1) FA/M
movhlps xmm0,xmm5 // p1 4 (1) mmxshf
cmp cl,05h // p0/1 d (1) alu p012 1 (1) ALU
cvtss2si ecx,xmm5 // p1 8 (2) fp p3+5 8 (2) FADD+FMISC
jnz @continueLINE // p0 2 (1) alu p012 1 (1) ALU
@round:
add edx,[edi+ebx] // p1+2 d (2) alu+load p012 4 (2) ALU+AGU
add ebx,04h // p0/1 d (1) alu p012 1 (1) ALU
mov [esi+edx],al // p0+3 2 (3) store p012 3 (1) AGU
js @round // p0 2 (1) alu p012 1 (1) ALU
mov ebx,[esp+_ECX] // p2 2 (1) load p012 3 (1) AGU
@continueLINE:
sub ebp,01h // p01 d (1) alu p012 1 (1) ALU
cvtss2si edx,xmm0 // p1 8 (2) fp p3+5 8 (2) FADD+FMISC
jge @setpixel // p0 2 (1) alu p012 1 (1) ALU
mov ebx,[esp+_EBX] // p2 2 (1) load p012 3 (1) AGU
jmp @nxline // p1 0 (1) alu p012 1 (2) ALU
@return:
popad // -vector- -vector-

[ Szerkesztve ]

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

(#40) P.H.


P.H.
(Topikgazda)

Gyors o(log n) rendezési algoritmus 64 bites lebegőpontos számokra:

inicializálás:
kimenet:
ESI: az ideiglenes,32 bites elemekből álló munkatömb címe
EDI: a 32 bites munkatömb mérete
bemenet:
EAX: a 64 bites számok tömbjére mutató pointer
EDX: az értékek száma a tömbben
ESI: az ideiglenes,32 bites elemekből álló munkatömb címe
lea edx,[eax+edx*08h]
fldz
mov ecx,esi
xor edi,edi
@insert:
mov [ecx],edx
sub edx,08h
lea ebp,[edi+01h]
cmp edx,[esp+_EAX]
fstp st(0)
jbe @return
add edi,01h
fld qword ptr [edx]
@moveup:
lea ecx,[esi+ebp*04h]
shr ebp,01h
mov ebx,[esi+ebp*04h]
jz @insert
fcom qword ptr [ebx]; fnstsw ax; sahf
jae @insert
mov [ecx],ebx
jmp @moveup
@return:

A következő legkisebb elem lehívása:
kimenet:
EDX: a legkisebb elem pozíciója az eredeti tömmben
EDI: a 32 bites munkatömb új mérete
bemenet:
EAX: a 64 bites számok tömbjére mutató pointer
EDI: a 32 bites munkatömb jelenlegi mérete
ESI: az ideiglenes,32 bites elemekből álló munkatömb címe
or edx,-1
sub edi,01h
js @invalid
pushad
mov edx,[esi+01h*04h]
mov ebp,00000001h
mov ecx,[esi+edi*04h+04h]
fld qword ptr [edx]
sub edx,eax
fld qword ptr [ecx]
mov [esp+_EDX],edx
@down:
mov edx,ebp
lea eax,[esi+ebp*(04h*2)]
add ebp,ebp
cmp ebp,edi
ja @insertdown
mov ebx,[eax+00h]
mov edx,[eax+04h]
jz @child
fld qword ptr [edx]
fcomp qword ptr [ebx]; fnstsw ax; sahf
cmovb ebx,edx {cmovb = cmovc}
adc ebp,00h
@child:
fcom qword ptr [ebx]
mov edx,ebp
fnstsw ax
shr edx,01h
sahf
mov [esi+edx*04h],ebx
ja @down
@insertdown:
fstp st(0)
mov [esi+edx*04h],ecx
popad
sar edx,03h
@invalid:
popad

A rendezés végét a negatív (-1) visszaadott pozíció jelzi, nem szükséges tesztelni a lépések számát.

[ Szerkesztve ]

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

(#41) P.H. válasza P.H. (#39) üzenetére


P.H.
(Topikgazda)

a #39-beli összehasonlításban használt vonalankénti x87 kód:

sub ebp,edx
sub ecx,eax
pushad
lea edi,[esi+...+DATA2]
fild dword ptr [esp+_ECX]
shl eax,10h
fild dword ptr [esp+_EBP]
mov esi,[esi+...DEST]
fld st(1)
mov ebx,[edi-..._DATA1]
fabs
fld st(1)
fabs
fcompp
sub edi,ebx
fnstsw ax
sahf
ja @inlineMOVEX
mov ebp,ecx
fxch
@inlineMOVEX:
test ebp,ebp
fdiv
fld1
jz @return
jns @inlineSETDIR
neg ebp
fchs
@inlineSETDIR:
sahf
fmul st(1),st
jbe @inlineCOORDINATES
fxch
@inlineCOORDINATES:
fild dword ptr [esp+_EDX]
sar eax,10h
fild dword ptr [esp+_EAX]
@setpixel:
cmp edx,[edi-...+_TOPLEFT]
fadd st,st(2)
setl cl
cmp edx,[edi-...+_BOTTOM]
setge ch
imul edx,[edi-...+_DX]
or ch,cl
cmp eax,[edi-...+_RIGHT]
setge cl
add edx,eax
or ch,cl
cmp eax,[edi-...+_TOPLEFT]
mov [esp+_ECX],ebx
setl cl
mov al,[edi+ebx-_ADDER+_DRAWCOLOR]
or cl,ch
jnz @continueLINE
@round:
add edx,[edi+ebx]
add ebx,04h
mov [esi+edx],al
js @round
mov ebx,[esp+_ECX]
@continueLINE:
fxch
fadd st,st(3)
sub ebp,01h
fist dword ptr [esp+_ECX]
fxch
mov edx,[esp+_ECX]
fist dword ptr [esp+_ECX]
mov eax,[esp+_ECX]
jge @setpixel
fcompp
@return:
popad
fcompp

[ Szerkesztve ]

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

(#42) P.H.


P.H.
(Topikgazda)

Ha ilyen nehéz 1.2 IPC fölé menni K10-en (és K10-5-ön is) FPU-ban ([link]) és integerban se nagyon könnyű olyan hasznos kódot írni, ami 2.0 IPC felett van ([link]), ésszerű döntésnek tűnik szálanként ("magonként"?) 2.0 IPC-re maximalizálni az amúgy 4 IPC-re feelkészített hardvert.

Kérdés, hogy ez mennyire használja ki a kész, meglevő software-eket. Hiszen igazán nagyot villlantani kétféleképpen lehet:
- ugyanazt a teljesítményt hozni kisebb termáis kereten belül
- jóval nagyobb terljesítményt mutatni az adott termális keretek közt
Mivel a butított Brazos-on az 1.5 IPC elérhető integerben a korábbi optimalizációs irányvonalak mentén, a minimális elvárás az 1.5 IPC a Bulldozeren is meglevő kódok esetén.

(v.ö. korábbi FPU kódok pl. itt).

[ Szerkesztve ]

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

(#43) P.H.


P.H.
(Topikgazda)

Fél év, Windows XP x64.

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

(#45) P.H.


P.H.
(Topikgazda)

Critital path kitakarítva, avagy egy DIV sok store-t győz.

Counter 0 : Non-halted clock cycles
Counter 1 : Retired instructions
Counter 2 : Instructions per cycle (IPC)
Counter 3 : L1 Data cache refill from RAM

223800 2616.4 5604.4 2.1 0.0
223850 2625.1 5869.5 2.2 0.0
223900 2607.2 5824.5 2.2 0.0
223950 2624.8 5906.3 2.3 0.0
224000 2621.1 5887.6 2.2 0.0
224050 2625.6 5880.5 2.2 0.0
224100 2605.2 5845.0 2.2 0.0
224150 2625.5 5871.4 2.2 0.0
224200 2621.6 5850.6 2.2 0.0
224250 2625.0 5846.2 2.2 0.0
224300 2605.7 5783.7 2.2 0.0
224350 2626.4 5367.4 2.0 0.0
224400 2607.9 5825.7 2.2 0.0
224450 2625.3 5696.0 2.2 0.0
224500 2611.4 5796.3 2.2 0.0
224550 2623.1 5902.6 2.3 0.0
224600 2621.8 5889.7 2.2 0.0
224650 2625.6 5879.4 2.2 0.0
224700 2612.9 5871.2 2.2 0.0
224750 2620.6 5908.6 2.3 0.0
224800 2622.8 5893.5 2.2 0.0

A kód, zárójelben a critical path-ok AMD-s integer port-leosztásával:

mov eax,edi
pushad
shl ebp,02h
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,02000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
bts dword ptr [edi+edx],00h
jnc @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,02000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],10h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
sub dword ptr [esp+__SYS0],01h
mov byte ptr [eax+03h],02h
mov [edi+esi*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK

@@3RD_STEP:
mov byte ptr [esi+03h],08h
mov byte ptr [edi+ebx+03h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
mov eax,ebp
mov esi,[esp+__MTX]
mov edx,00FFFFFFh
@nx2row:
mov bh,[edi+eax+03h]
mov ecx,ebp
@zeroinrow:
{0} cmp edx,[esi]
{1} mov bl,bh
{2} sbb bl,[edi+ecx]
{0} jz @minimum
@nx2col:
{1} add ecx,04h
{2} lea esi,[esi+04h]
{0} jnz @zeroinrow
add eax,04h
jnz @nx2row
@@5TH_STEP:
mov ebx,ebp
mov esi,[esp+__MTX]
@nx5row:
mov eax,edx
sub ecx,edx
xor eax,[edi+ebx]
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
{0} bt dword ptr [edi+ecx],00h
{1} mov al,[esi+03h]
{2} adc al,[edi+ebx+03h]
{0} mov eax,00000000h
{1} cmovz eax,edx
{2} sub [esi],eax
{0} add ecx,04h
{1} lea esi,[esi+04h]
{2} jnz @decrease_row_free
add ebx,04h
jnz @nx5row
mov eax,[esp+__FREE0]
xor edx,edx
mov esi,eax
sub eax,[esp+__MTX]
idiv ebp
neg eax
lea ecx,[ebp+edx]
lea eax,[ebp+eax*04h]
@minimum:
xor edx,edx
mov [esp+__FREE0],esi
add edx,[esi]
jnz @nx2col
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax*02h+__0STAR]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
jmp @colon_to_star
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub esi,ecx
sub eax,ebp
sub esi,ebp
mov ecx,[edi+eax*02h+__COLON]
lea esi,[esi+ecx]
@colon_to_star:
mov [edi+eax*02h+__0STAR],ecx
sub ecx,ebp
mov byte ptr [esi+03h],02h
lea esi,[edx+ecx]
mov eax,ebp
@search_star_in_column:
cmp eax,ebx
jz @nxstar
test byte ptr [esi+03h],02h
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
mov ecx,ebp
mov ebx,edi
jz @count_result_STACK
push dword ptr [edi]
@restructure:
{0} mov esi,[ebx+__COLON]
{1} sub edx,ebp
{2} mov [edi+ecx+03h],al
{0} and byte ptr [edx+esi+03h],11110111b
{1} mov esi,[ebx+__0STAR]
{2} add ecx,04h
{0} mov [ebx+__COLON],eax
{1} lea ebx,[ebx+08h]
{2} mov byte ptr [edi+esi],01h
{0} jnz @restructure
pop dword ptr [edi]
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
{0} mov edx,[edi+ecx*02h+__0STAR]
{1} add ecx,04h
{2} add edx,ebp
{0} add eax,[esi+edx]
{1} shr edx,02h
{2} add esi,ebp
{0} cmp ecx,ebp
{1} mov [ebx],dl
{2} lea ebx,[ebx+01h]
{0} jnz @results

[ Szerkesztve ]

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

(#46) P.H.


P.H.
(Topikgazda)

Szinte minden lépésben többé-kevésbé módosított, működő kód, de még nem végleges.

60 db 25x25 mátrix-ot old meg ezredmásodpercenként.
60x60-as bemeneti mátrixméretnél átlagos 2.4 IPC is mérhető tartósan, ilyen méretnél legalább 2-3x a gyorsulás az előző kódhoz képest..

mov eax,edi
pushad
shl ebp,02h
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
mov byte ptr [edi+00h],01h
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,02000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
add ebx,04h
jnz @rowmin
jmp @columns
@specific:
cmp byte ptr [edi+edx],00h
mov byte ptr [edi+edx],01h
jnz @@ABNORMAL_EXIT
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
add ebx,04h
jnz @rowmin
@columns:
mov [edi+00h],bl
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov esi,02000000h
mov ecx,ebp
@findcolmin:
cmp esi,[eax]
cmova esi,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp esi,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor edx,edx
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp [eax+03h],dl
cmovz edx,esi
sub [eax],edx
jnz @subcol
mov dl,[edi+ecx+02h]
mov byte ptr [edi+ecx+02h],01h
or dl,[edi+ebx]
mov edx,ecx
jnz @subcol
mov byte ptr [edi+ebx],01h
sub edx,ebp
mov byte ptr [edi+ecx+02h],01h
sub dword ptr [esp+__SYS0],01h
mov [edi+edx*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret

@@3RD_STEP:
mov byte ptr [edi+ebx+03h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
mov ecx,ebp
mov esi,[esp+__MTX]
mov edx,00FFFFFFh
@nxcol:
cmp byte ptr [edi+ecx],00h
mov eax,ebp
jnz @check
@zeroinrow:
cmp edx,[esi]
mov bl,[edi+eax+03h]
sbb bl,00h
jz @minimum
@nx2col:
sub esi,ebp
add eax,04h
jnz @zeroinrow
mov esi,ecx
add esi,[esp+__MTX]
sub esi,ebp
@check:
add ecx,04h
lea esi,[esi+04h]
jnz @nxcol
@@5TH_STEP:
lea ebx,[ebp+03h]
mov esi,[esp+__MTX]
@nx5row:
mov eax,edx
sub ecx,edx
xor eax,[edi+ebx-03h]
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,[edi+ebx]
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @decrease_row_free
add ebx,04h
js @nx5row
mov eax,[esp+__FREE0]
xor edx,edx
mov esi,eax
sub eax,[esp+__MTX]
idiv ebp
neg eax
lea ecx,[ebp+edx]
lea eax,[ebp+eax*04h]
@minimum:
xor edx,edx
mov [esp+__FREE0],esi
add edx,[esi]
jnz @nx2col
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax*02h+__0STAR]
jnz @@3RD_STEP
@@4TH_STEP:
sub edx,ebp
jmp @newstar
@0_star:
mov [edi+ebx*02h+__0STAR],ecx
mov ecx,[edi+eax*02h+__COLON]
@newstar:
mov ebx,eax
lea eax,[edx-04h]
@starincol:
cmp [edi+eax*02h+__0STAR],ecx
jz @0_star
sub eax,04h
jns @starincol
mov [edi+ebx*02h+__0STAR],ecx
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
mov ebx,edi
mov ecx,ebp
jz @count_result_STACK
mov edx,[edi]
@restructure:
mov esi,[ebx+__0STAR]
mov byte ptr [edi+ecx+03h],00h
add ecx,04h
lea ebx,[ebx+08h]
mov byte ptr [edi+esi],01h
jnz @restructure
mov [edi],edx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx*02h+__0STAR]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#47) P.H. válasza P.H. (#46) üzenetére


P.H.
(Topikgazda)

Némi módosítással mostmár az elvárható szintet hozza a kód, folyamatosan tartja a 2.4 IPC-t.

PerfMonitor Record file
Counter 0 : Non-halted clock cycles
Counter 1 : Retired instructions
Counter 2 : Instructions per cycle (IPC)
Counter 3 : L1 Data cache refill from RAM

1000 2602.3 6239.3 2.4 0.0
1050 2625.0 6279.9 2.4 0.0
1100 2622.7 6217.2 2.4 0.0
1150 2624.9 6212.2 2.4 0.0
1200 2607.5 6200.2 2.4 0.1
1250 2626.4 6246.8 2.4 0.0
1300 2621.9 6223.3 2.4 0.0
1350 2625.4 6207.1 2.4 0.0
1400 2607.3 6176.2 2.4 0.1
1450 2624.8 6223.7 2.4 0.1
1500 2593.0 6160.8 2.4 0.1
1550 2625.6 6257.4 2.4 0.1
1600 2610.2 6214.2 2.4 0.0
1650 2621.0 6224.5 2.4 0.1
1700 2621.6 6254.4 2.4 0.0
1750 2624.4 6201.1 2.4 0.0
1800 2610.4 6156.3 2.4 0.0
1850 2625.9 6208.6 2.4 0.0
1900 2622.2 6224.9 2.4 0.0
1950 2626.3 6263.7 2.4 0.0
2000 2610.2 6255.1 2.4 0.1
2050 2625.3 6284.7 2.4 0.0
2100 2618.1 6281.4 2.4 0.0
2150 2601.0 6225.6 2.4 0.1
2200 2620.6 6289.6 2.4 0.1

Mivel korábban nem vettem figyelembe, hogy bár a LEA utasítás K10-en és Core2/Nehalem/Sandy Bridge-en 1 órajel, viszont K7/K8-on 2 órajel, Atom-on 4, Prescott-on 2.5, így ezeken nagyon nem egyenértékű a sima összeadással, ezért kivettem a felesleges LEA utasításokat; Prescott-on 10%-kal gyorsult.
Ennek további hozadéka, hogy mivel a Sandy Bridge már az ADD/SUB + Jcc párokat is tudja egyesíteni (macro-fusion), az Atom szintén tudja párosítani ezeket (én pedig korábban minden ilyen pár közé tettem a LEA utasításokat, mert nem szeretem az egymást közvetlenül követő függő integer-kódokat), ezért szinte minden ciklus profitál ebből mindkettőn.

Érdekes lesz a Bulldozer, mivel ahhoz, hogy ez a kód 2.4 IPC felett tudjon futni, a következők kellenek:
1. 3 ALU
2. legalább 2 load/cycle/thread (pl. a @@5ST_STEP 9 utasításos ciklusában 3 load, 1 load+store, 1 ugrás és 4 regiszter-utasítás van)
3. CMOVcc, ADC és SBB utasítások végrehajtása 1 órajel alatt
3. a cikluszáró ADD+Jcc párosok fúziója igencsak gyorsít (szinte minden ciklus így zárul)
4. a teljes kód elfér egy pár 100 elemű uop cache-ben

Jelen pillanatban úgy tudni, az első kettővel a Sandy Bridge és a K7-K10 sorozat rendelkezik, a harmadikkal csak a K7-K10, az utolsó 2 pedig a Sandy Bridge sajátja.
(Elvileg a kód az első 754/939 K8-as generációkon gyorsabb is, mint K10-en, mivel akkor az L1-latency csak 2 órajel volt.)
A Bulldozer 1. generációjában az első kettő kizárt, a 3. szinte biztos, az utolsó kettő lehetséges, de az eddigi információk nem említik őket. Persze ha a maximum 2.0 IPC/thread megfelelő órajellel párosul, akkor nem lehet gond.

mov eax,edi
pushad
shl ebp,02h
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
mov byte ptr [edi+00h],01h
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add eax,04h
add ecx,04h
jnz @findrowmin
sub ecx,ebp
cmp esi,02000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
add eax,04h
sub ecx,04h
jnz @subrow
add ebx,04h
jnz @rowmin
jmp @columns
@specific:
cmp byte ptr [edi+edx],00h
mov byte ptr [edi+edx],01h
jnz @@ABNORMAL_EXIT
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
add ebx,04h
jnz @rowmin
@columns:
mov [edi+00h],bl
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov esi,02000000h
mov ecx,ebp
@findcolmin:
cmp esi,[eax]
cmova esi,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp esi,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor edx,edx
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp [eax+03h],dl
cmovz edx,esi
sub [eax],edx
jnz @subcol
mov dl,[edi+ecx+02h]
or dl,[edi+ebx]
mov edx,ecx
jnz @subcol
mov byte ptr [edi+ebx],01h
sub edx,ebp
mov byte ptr [edi+ecx+02h],01h
sub dword ptr [esp+__SYS0],01h
mov [edi+edx*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret

{ CODE PADDING }

@@3RD_STEP:
mov byte ptr [edi+ebx+03h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
{0} lea ecx,[ebp-04h]
{1} mov edx,00FFFFFFh
{2} jmp @c2col
@zeroincol:
{0} cmp edx,[esi]
{1} mov bl,[edi+eax+03h]
{2} sbb bl,00h
{0} jz @@DECIDE_NEXT_STEP
@nx2mtx:
{1} sub esi,ebp
{2} add eax,04h
{0} jnz @zeroincol
@c2col:
{0} mov esi,ecx
{1} add esi,[esp+__MTX]
{2} sub esi,ebp
@check2col:
{0} add esi,04h
{1} add ecx,04h
{2} jz @@5TH_STEP
{0} cmp byte ptr [edi+ecx],00h
{1} mov eax,ebp
{2} jnz @check2col
{0} jmp @zeroincol
@@5TH_STEP:
lea ebx,[ebp+03h]
mov esi,[esp+__MTX]
@nx5row:
mov eax,[edi+ebx-03h]
sub ecx,edx
xor eax,edx
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
{0} bt dword ptr [edi+ecx],00h
{1} mov al,[esi+03h]
{2} adc al,[edi+ebx]
{0} mov eax,00000000h
{1} cmovz eax,edx
{2} sub [esi],eax
{0} add esi,04h
{1} add ecx,04h
{2} jnz @decrease_row_free
add ebx,04h
js @nx5row
mov eax,[esp+__FREE0]
xor edx,edx
mov esi,eax
sub eax,[esp+__MTX]
idiv ebp
neg eax
lea ecx,[ebp+edx]
lea eax,[ebp+eax*04h]
@@DECIDE_NEXT_STEP:
xor edx,edx
mov [esp+__FREE0],esi
add edx,[esi]
jnz @nx2mtx
mov ebx,eax
sub eax,ebp
add edx,[edi+eax*02h+__0STAR]
jnz @@3RD_STEP
@@4TH_STEP:
sub edx,ebp
jmp @newstar
@0_star:
mov [edi+ebx*02h+__0STAR],ecx
mov ecx,[edi+eax*02h+__COLON]
@newstar:
mov ebx,eax
lea eax,[edx-04h]
@starincol:
cmp [edi+eax*02h+__0STAR],ecx
jz @0_star
sub eax,04h
jns @starincol
mov [edi+ebx*02h+__0STAR],ecx
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
mov ebx,edi
mov ecx,ebp
jz @count_result_STACK
mov edx,[edi]
@restructure:
{0} mov esi,[ebx+__0STAR]
{1} mov byte ptr [edi+ecx+03h],00h
{2} add ebx,08h
{0} mov byte ptr [edi+esi],01h
{1} add ecx,04h
{2} jnz @restructure
mov [edi],edx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
{0} mov edx,[edi+ecx*02h+__0STAR]
{1} add ecx,04h
{2} add edx,ebp
{0} add eax,[esi+edx]
{1} shr edx,02h
{2} add esi,ebp
{0} cmp ecx,ebp
{1} mov [ebx],dl
{2} lea ebx,[ebx+01h]
{0} jnz @results

[ Szerkesztve ]

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

(#48) P.H.


P.H.
(Topikgazda)

Macro-op fusion

The Sandy Bridge can fuse two instructions into one µop in more cases than previous processors can [...].

The decoders will fuse an arithmetic or logic instruction and a subsequent conditional jump instruction into a single compute-and-branch µop in certain cases. The compute-and-branch µop is not split in two at the execution units but executed as a single µop by the branch unit at execution port 5.
The CMP, ADD and SUB instructions can fuse with signed and unsigned branch instructions. INC and DEC can fuse with signed branch instructions, and TEST and AND instructions can fuse with all branch instructions (including useless combinations), [...]
The first instruction can have an immediate operand or a memory source operand, but not both. It cannot have memory destination operand.

Megcsillagoztam azokat az utasításpárokat, amelyek elméletileg egysíthetők, nem véve figyelembe a szükséges 3 utasításos teret köztük (egyrészt az elágazás-tévesztések miatt, másrészt nem nagyon lehet előre kiszámolni, mi tartozik decode-nál ugyanabba a 4-es utasításcsoportba):

The programmer should keep fuseable arithmetic instructions together with a subsequent conditional jump rather than scheduling other instructions in-between; and there should preferably be at least three other instructions between one fuseable pair and the next fuseable pair in order to take advantage of macro-op fusion.

Az ADD és SUB bevonása a Sandy Bridge-nél a macro-op fusion-be igen hatékony lépés volt az Intel-től.

mov eax,edi
pushad
shl ebp,02h
xor ecx,ecx
lea edx,[ebp+ebp*02h]
lea edi,[ebx+ebp]
neg ebp
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
mov byte ptr [edi+00h],01h
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,02000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add eax,04h
* add ecx,04h
* jnz @findrowmin
sub ecx,ebp
* cmp esi,02000000h
* jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
add eax,04h
* sub ecx,04h
* jnz @subrow
* add ebx,04h
* jnz @rowmin
jmp @columns
@specific:
cmp byte ptr [edi+edx],00h
mov byte ptr [edi+edx],01h
jnz @@ABNORMAL_EXIT
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx*02h+__0STAR],edx
jz @count_result_STACK
* add ebx,04h
* jnz @rowmin
@columns:
mov [edi+00h],bl
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
* cmp ebx,ebp
* jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov esi,02000000h
mov ecx,ebp
@findcolmin:
cmp esi,[eax]
cmova esi,[eax]
add eax,ebp
* add ecx,04h
* jnz @findcolmin
cmp esi,02000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor edx,edx
* add ecx,04h
* jz @@RECUDE_COLUMNS
sub eax,ebp
cmp [eax+03h],dl
cmovz edx,esi
* sub [eax],edx
* jnz @subcol
mov dl,[edi+ecx+02h]
mov byte ptr [edi+ecx+02h],01h
or dl,[edi+ebx]
mov edx,ecx
jnz @subcol
mov byte ptr [edi+ebx],01h
sub edx,ebp
mov byte ptr [edi+ecx+02h],01h
sub dword ptr [esp+__SYS0],01h
mov [edi+edx*02h+__0STAR],ebx
jnz @subcol
jmp @count_result_STACK
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret

@@3RD_STEP:
mov byte ptr [edi+ebx+03h],0FFh
mov byte ptr [edi+edx],00h
mov [edi+eax*02h+__COLON],ecx
@@2ND_STEP:
lea ecx,[ebp-04h]
mov edx,00FFFFFFh
jmp @c2col
@zeroincol:
cmp edx,[esi]
mov bl,[edi+eax+03h]
sbb bl,00h
jz @@DECIDE_NEXT_STEP
@nx2mtx:
sub esi,ebp
* add eax,04h
* jnz @zeroincol
@c2col:
mov esi,ecx
add esi,[esp+__MTX]
sub esi,ebp
@check2col:
add esi,04h
* add ecx,04h
* jz @@5TH_STEP
cmp byte ptr [edi+ecx],00h
mov eax,ebp
jnz @check2col
jmp @zeroincol
@@5TH_STEP:
lea ebx,[ebp+03h]
mov esi,[esp+__MTX]
@nx5row:
mov eax,[edi+ebx-03h]
sub ecx,edx
xor eax,edx
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,[edi+ebx]
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add esi,04h
* add ecx,04h
* jnz @decrease_row_free
* add ebx,04h
* js @nx5row
mov eax,[esp+__FREE0]
xor edx,edx
mov esi,eax
sub eax,[esp+__MTX]
idiv ebp
neg eax
lea ecx,[ebp+edx]
lea eax,[ebp+eax*04h]
@@DECIDE_NEXT_STEP:
xor edx,edx
mov [esp+__FREE0],esi
* add edx,[esi]
* jnz @nx2mtx
mov ebx,eax
sub eax,ebp
* add edx,[edi+eax*02h+__0STAR]
* jnz @@3RD_STEP
@@4TH_STEP:
sub edx,ebp
jmp @newstar
@0_star:
mov [edi+ebx*02h+__0STAR],ecx
mov ecx,[edi+eax*02h+__COLON]
@newstar:
mov ebx,eax
lea eax,[edx-04h]
@starincol:
* cmp [edi+eax*02h+__0STAR],ecx
* jz @0_star
* sub eax,04h
* jns @starincol
mov [edi+ebx*02h+__0STAR],ecx
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
mov ebx,edi
mov ecx,ebp
jz @count_result_STACK
mov edx,[edi]
@restructure:
mov esi,[ebx+__0STAR]
mov byte ptr [edi+ecx+03h],00h
add ebx,08h
mov byte ptr [edi+esi],01h
* add ecx,04h
* jnz @restructure
mov [edi],edx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx*02h+__0STAR]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

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

(#49) P.H.


P.H.
(Topikgazda)

Küzdök a 2 GB/32-bit thread kihasználásával régóta: pár KB-énti (egyszerre 1 struktúra) lefoglalással lassú az algoritmus (16 GB memória mellett, x64 OS alatt is), 1000-3000 db struktúra egyszerre lefoglalása esetén 1.0-1.1 GB-ig lehet elmennem (XP x64 alatt), aztán annyira menthetetlenül defragmentálódik a címtér, hogy nem lehet több ilyet egyben lefoglalni. Vajon ezen javítottak Vista/Win7 alatt?

Megoldás lehet:
- unlock-olt (movable) memóriafoglalás, de ennek túl sok költsége lesz minden hozzáféréskor lockolni (és az algoritmus olyan, hogy nem is lehet előre kiszámolni, hogy mit lehet lockolni egyszerre, tehát lock/unlock kellene elemenként)
- külön x64 process-re átírni a programrészt, de ennek felhasználhatósága korlátozott, és nem is elegáns
- egyre csökkenő struktúranagyságú memóriát lefoglalni egyszerre

Valószínűleg a legutolsó az általánosan célravezető. Meglátjuk.

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

(#50) P.H.


P.H.
(Topikgazda)

Két kódrészt az utolsó kódból - ellátva a megfelelő code-padding-gal - lemértem, a következők adódtak:

2ND_STEP: 2.0 IPC
@@2ND_STEP:
lea ecx,[ebp-04h]
mov edx,00FFFFFFh
jmp @c2col
@zeroincol:
cmp edx,[esi]
mov bl,[edi+eax+03h]
sbb bl,00h
jz @@DECIDE_NEXT_STEP
@nx2mtx:
sub esi,ebp
add eax,04h
jnz @zeroincol
@c2col:
mov esi,ecx
add esi,[esp+__MTX]
sub esi,ebp
@check2col:
add esi,04h
add ecx,04h
jz @@5TH_STEP
cmp byte ptr [edi+ecx],00h
mov eax,ebp
jnz @check2col
jmp @zeroincol

5TH_STEP: 2.7 IPC
@@5TH_STEP:
lea ebx,[ebp+03h]
mov esi,[esp+__MTX]
@nx5row:
mov eax,[edi+ebx-03h]
sub ecx,edx
xor eax,edx
cmovs edx,ecx
mov ecx,ebp
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,[edi+ebx]
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add esi,04h
add ecx,04h
jnz @decrease_row_free
add ebx,04h
js @nx5row

Az elsőben elég gyakoriak az (ki)ugrások, a második szinte folyamatos lefutású (mátrixsoronként 1 elágazás-tévesztés van csak)
K10.5-ön mérve:
- az overall IPC 2.4 (nem végtelen ciklusban, ezért az tartalmazza a hívó algoritmus kb. 3x ekkora kódját is), ami 80% kihasználtsága a lehetséges maximumnak
- a @@2ND_STEP 2.0 IPC, ami 66%-os kihasználtság
- a @@5TH_STEP 2.7 IPC, ez 90% kihasználtság
(Vajon ezeket az értékeket mennyiben befolyásolja, hogy a @@2ND_STEP sszámolós ciklusa 7 utasításos, a @@5TH:STEP-é pedig 9, ami passzol a K10.5 3 pipe-jához?)

A @@2ND_STEP-en lehetne javítani, de ahhoz még +1 32 bites regiszter kellene, az meg nincs; 64 biten lesz :)

[ Szerkesztve ]

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

Copyright © 2000-2019 PROHARDVER Informatikai Kft.