AMD64 - CF-t direkt a memóriába

AMD64 - CF-t direkt a memóriába
2011-03-09T20:20:43+01:00
2011-03-11T02:06:21+01:00
2022-11-21T02:55:37+01:00
Argathron
Üdvözlet,

épp egy AMD64 kód méretét akarom a lehető legminimálisabbra csökkenteni. Azt hiszem már mindenhol elértem a minimumot (ha mégse, majd külön topic), egy valami azonban gyanús.
A carry flaget szeretném a memóriába beletenni, a lehető legkevesebb lépéssel. Mivel két lépésben sikerül, ezért értelemszerűen annak örülnék, ha ez menne egy lépéssel is.
Jelenleg (sajnálom, kegyetlen az élet, így AT&T szintaxisban van, de szerintem úgyse az a lényeg):
movl $0, (%rdx,%r12,8) SETB (%rdx,%r12,8)
illetve ugyanez megy még egy két másik módon, azonban reménykedem, hogy valahogy csak sikerülhet ez egy lépésben is.

Hangsúlyoznám, hogy memóriában kell buzerálnom, és mind a 64 bitet (különben SETB-vel is menne, azonban az csak az első 8 bitet buzergálja meg, így ha az adott memóriaterületen van egy nagy) felül kell írnom, az alapérték az adott memóriaterületen pedig random lehet.

Köszönettel,
Argathron
Mutasd a teljes hozzászólást!
Hi!
Hat ezt a kettot osszevonni: szvsz passz :/
Ha sebbessegre gyurod, akkor inkabb regekben rakd ossze az eredmenyt es csak egyszer irj memoriaba.
Ilyesmire gondolok:
xor eax,eax setb al mov [ebx+ecx+8],eax
Asszem, igy a kod is rovidebb lesz, mert xor van az immediate 8byte 0 konstans helyett. Már látom a köv problemat is: kell egy szabad reg ax..dx-bol :D

ui: movzx sem tud memoriaba irni, pedig az is jo lenne amugy.
Mutasd a teljes hozzászólást!

  • Nekem úgy tűnik, ugyanakkora marad. /lehet valamit elnéztem/
    Végigmentem az egész instruction set-en, de nem találtam semmi olyan dolgot, ami megoldaná egy lépésben (mondjuk az is igaz, hogy nem egy túl gyakran használt dolog)

    Tetszőleges méretű egész számokat összeadó rutint akartam kioptimalizálni és ez igazából a legutolsó lépés, nem egy gyakran lefutó parancs úgyhogy nem olyan lényeges a sebessége.

    Movzx szerintem csak arra lenne jó, hogy a xor-t kikerüljük (lehet te is erre gondoltál).
    De ahogy én tudom, a flageket nem lehet direkt elérni és regiszterként kezelni.

    Még várok egy kicsit valami csodára, aztán ha nem jön, repül a pötyi
    Mutasd a teljes hozzászólást!
  • Elalvás előtt beugrott, hogy a logikából következően van egy mindenképpen nulla értékű eax regiszterem, úgyhogy még a xorra sincs szükség
    Mutasd a teljes hozzászólást!
  • Esetleg sbb eax,0 (0 vagy -1 lesz) vagy sahf (1 byte) valamilyen módon?
    Mutasd a teljes hozzászólást!
  • Ha jól értelek, akkor ennek így nincs sok értelme, akkor már érdemesebb lenne ADC-t használni, mert akkor 0 vagy 1 lesz a kapott érték.
    Azonban a gond az, hogy előtte mindenképpen nulláznom kell a memóriát, mert bármi lehetett azon a helyen előtte.

    A sahf-al nem tudom, mire gondoltál.
    Igazából szerintem
    setb %cl movq %rcx, (%rdx,%rax,8)
    -nél nincsen rövidebb/gyorsabb (eaxot előtte ciklusváltozónak használom, tehát mire ide ér, mindenképpen 0) megoldás.
    Mutasd a teljes hozzászólást!
  • sse-vel meg ossze lehetne hozni 128 bites osszeadast, de nincs unsigned cmp benne

    Ez lenne az elv, csak vektorosan (+ :32bit add):

    sum <- a+b
    carry <-(min(a,b)>sum)and 1

    min/max-al még azert osszedobhato, de nem az igazi igy:
    m <- min(a,b)
    carry <- not(m=max(m,sum)) and 1

    //input: xmm0,xmm1 xmm7=ints(1,1,1,1) movaps xmm2,xmm0 pminud xmm2,xmm0 paddd xmm0,xmm1 pmaxud xmm2,xmm0 pcmpeqd xmm2,xmm0 pandn xmm2,xmm7 //output: xmm0 <- xmm0+xmm1 xmm2<- carry
    Amd K10-en ez csupa olyan utasitas, aminek 1/2-a throughput-ja, szoval még egy ilyen 'szálat' lazán elbírna a proci.

    A SETB-nek is 1/2 szoval ott is lehetne kettot egyszerre csinaltatni.
    Mutasd a teljes hozzászólást!
  • Nézegettem én is az SSE-t, de egyelőre szerintem hagyom AMD64-ben.

    SSE-hez még nem érzem magam elég erősnek
    Mutasd a teljes hozzászólást!
  • Amugy erdekes felallas:
    Egyreszt ott a setb, ami legjobb esetben 3 szalon futhat(na!) de nem futhat, mert a carry flag-et valamivel kozvetlenul elotte frissiteni kellene.
    Az sse-n viszont ugy kell osszebuveszkedni a carry-t, viszont abbol meg leher 2 szal is egymas mellett.

    Mi is a végcél? Két bazinagy integer összeadása, ugye?
    Mutasd a teljes hozzászólást!
  • Két bazinagy integer összeadása, ugye?

    Bizony

    A párhuzamosságra nem feltétlenül van szükségem.
    Vagyis jó lenne, ha az egy adott összeadást két szálon tudnám végezni, de ez szerintem nem lehetséges. Vagy rosszul gondolom?
    Mutasd a teljes hozzászólást!
  • adc ?
    Mutasd a teljes hozzászólást!
  • En is adc-re jutottam, de ugy, hogy a ciklus valtozo inc-el megy, ami bekenhagyja a CF-et. Nem kell kimenteni memoriaba a carryt (vagy az is lehet, hogy valamit nagyon beneztem :D)

    procedure AddBigInt(const a,b,res:pcardinal;const sizeBytes:integer);//1165 asm push edi push esi push ebx mov esi,sizeBytes; shr esi,2 xor edi,edi clc @@1: mov ebx,[eax+edi*4] adc ebx,[edx+edi*4] mov [ecx+edi*4],ebx inc edi dec esi jnz @@1; pop ebx pop esi pop edi end;
    (az sse-s meg nem gyenge puzzle, ott semmi carryval kapcs dolog nincs :D)
    Mutasd a teljes hozzászólást!
  • Végső esetben a CX-szel is lehet ciklust szervezni, lásd a LOOP-nál...
    Mutasd a teljes hozzászólást!
  • Szerintem félreértitek, már kész vagyok a kóddal, csak az utolsó részt akartam még rövidíteni just4fun.
    A legvégén muszáj kimentem a carry-t.
    Közben persze nem akartam.
    Írtam korábban:

    Tetszőleges méretű egész számokat összeadó rutint akartam kioptimalizálni és ez igazából a legutolsó lépés, nem egy gyakran lefutó parancs úgyhogy nem olyan lényeges a sebessége.


    Sajnálom, ha nem volt egyértelmű.


    Az enyém (lényegében mint a tied, csak én rcx-et használok, ha már úgyis abban jön át a tömb mérete (na meg 64bites)):
    .LFB2: xor %rax, %rax jecxz .L3 .L8: movq (%rdi,%rax,8), %r8 adcq (%rsi,%rax,8), %r8 movq %r8, (%rdx,%rax,8) inc %rax loop .L8 .L3: setb %cl movq %rcx, (%rdx,%rax,8) ret

    Még valami:
    A te kódodban az elején a clc-re nincs is szükség, a xor nullázza a CF-et.
    Mutasd a teljes hozzászólást!
  • basszus, miert nem szoltal, hogy a setb nalad nem inner loop? :D:D:D
    Mutasd a teljes hozzászólást!
  • Az nem gáz, micro-op fusion-al összevonja a proci az inc-et meg a jxx-t.
    Mutasd a teljes hozzászólást!
  • Hát abban a hiszemben voltam, hogy egyértelmű, az SSE-t meg csak azért mondod, hátha tudnék a közepén is gyorsítani

    Mindenesetre nemigen hiszem, hogy lesz gyorsabb megoldás a CF mentésére, mint amit az első hozzászólásban javasoltál, úgyhogy köszönöm(na meg a sok fáradozást a többivel ).

    Még annyi érdekelne, hogy van e különbség a regiszterek sebessége között (mondjuk egy rax gyorsabb, mint egy r8)? Esetleg bizonyos műveleteknél?
    Mutasd a teljes hozzászólást!
  • namert kulso looppal nem foglalkozunk, az legyen inkabb attekintheto :D

    Teljesen mindegy, hogy 8bit, 32bit, 64bit vagy 128bites regiszterek kozott mozgatod az adatot, az ilyen tipusi mov-bol orajelenkent 3-at is megbir a proci. Ha memoriabol olvasol, akkor mar -> 1 orajelenkent max 1, mert cimszamitoegyseg csak 1 van. Tokmind1, hogy aligned dword, qword, dqword(128bit)-et olvasol az egysegnyi idoben olvasodik be, azon felul mem/cache-ra kell varni. Ha unaligned (mint nalad) akkor megnagyobb penaltyk vannak, mert a proci csak 16 byteonkent tud olvasni, a tobbit osszebitvadászkodja mikroutasitasokbol (1 unaligned mov=10 uop is lehet)

    Tehat elso lepeskent 16byte aligned memoriahasznalatra kell atterni, ez az adatmennyiseg aranyosan a leghatekonyabb. Ket ilyen olvasas es egy iras koze pedig egy oldalnyi asm is bepakolhato, most hogy mar a nyers memoria savszelesseg lett a botleneck (nálad még az unaligned read/write az).

    Pár pillanat es osszerakom 16byte align read-ekkel, mert en is kivancsi vagyok erre. (most a 32bites adc-hez kepest 4x gyorsabbg, de van egy kis bug benne (lehet a bug miatt haha))
    Mutasd a teljes hozzászólást!
  • Na kicsit megtorpantam Minimum kivalasztas nincs sse-ben 64 bitre, compare viszont van, de az megy sse4.2, amit nem tud a procim.
    Valahogy megkerulom, a vege olyan 3.7szeres lesz a 32bites valtozathoz kepest.

    Aztan majd lehetne csinalni egy benchmarkot a kulonbozo modszerekre.

    Nalam most: 1024 byte adatra (core2 3ghz, cachebol, kb 1sec tesztidotartam)
    32bit: 1165ns
    sse aligned: 340ns //na ez tobb lesz, ha me'g beleirom a hianyzo reszt :D
    64bit: ??
    Mutasd a teljes hozzászólást!
  • Őszintén szólva én még ott vagyok leragadva, hogy a te fenti kódod miért nem unaligned (vagy már az SSE kódodról beszélsz? Akkor értem.), ha az enyém az?

    Annak mennyire van értelme, hogy MOVDQA-val olvasok a memóriából, majd pedig az így beolvasott adatokat már a 64 bites regiszterbe pakolgatom a számoláshoz (majd vissza újra be a 128 bitesbe)?
    Mutasd a teljes hozzászólást!
  • Na jo kis gyakorlas volt ez nekem, ezt a 2xInt64 greater problemat inkább nem feszegetem már :D (!!!!!!!!!!!!!!! jelolve)

    Kiprobaltam azt is: 16byte aligned olvasas/iras, aztan regek kozott muveletvegzes 32bit adc-vel:
    32bit: 1165
    32bit,128bit aligned r/w: 622
    sse 128bit aligned r/w: 365

    Irj majd pls idoket meg configot, erdekelne engem, hogy mukodik a 64bites verzio! (szvsz 2x gyorsabb, mint a 32bites, azaz egy kicsit gyorsabb, a feleannyi memoria eleres miatt. talan 3x?)

    Es itt jegyezném meg, hogy mekkora egy takolas ez az utasitaskeszet már lol -> pl: pcmpGTq sse4.2-tol kezdve van csak, pcmpEQq viszont sse4.0-tol is. Régen a 8bites utasitaskeszletnél még szórták a kodokat mint állat (ja,jae,jb,jbe,jg,jge,jl,jle,je,jne) azt most hogy már prefixekkel egyutt 4 byte folott vannak (64biten meg 5byte, ha uj regiszterek is vannak) most már orulni lehet egy EQ-nek, megy egy kov verziobeli GT-nak, a tobbit meg rakd ossze bitmuveletekkel meg tobb cmp-vel haha. Az uj verzional (256bit sse) meg ugy hallottam, hogy kizarolag a 8xSingle muveleteket valositjak meg. Még 1 8bites utasitast kellene bealdozni es oda egy 16bites teruletet megnyitni, de lehet hogy már nem maradt olyan bealdozhato utasitas...

    ps: Ilyen nagysagrendek vannak core2-n 128bit mosgatasokra:
    movaps (ua, mint movdqa) reg-ek kozott: 1
    movaps, padd reg,mem: 2
    movups reg,mem: 4
    movups mem,reg: 9
    4x 32bit mov mem,reg: 9

    procedure AddBigInt1(const a,b,res:pcardinal;const sizeBytes:integer);//1165 asm push edi push esi push ebx mov esi,sizeBytes; shr esi,2 xor edi,edi clc @@1: mov ebx,[eax+edi*4] adc ebx,[edx+edi*4] mov [ecx+edi*4],ebx inc edi dec esi jnz @@1; pop ebx pop esi pop edi end; procedure AddBigInt2(const a,b,res:pcardinal;const sizeBytes:integer); //a,b,res: align16; sizebytes>0; sizebytes and $f=0 asm push edi push esi push ebx mov esi,1; movd xmm7,esi; pshufd xmm7,xmm7,0+1 shl 2+1 shl 6 //xmm7 <- ints(1,0,1,0) // movaps xmm1,xmm7 psllq xmm1,63 //xmm1: $800000000000 pxor xmm3,xmm3 //carry mov esi,sizeBytes; shr esi,2; xor edi,edi @@1: movaps xmm0,[eax+edi*4] //add a,b, get carry movaps xmm2,xmm0 paddq xmm0,[edx+edi*4] //add a,b pminud xmm4,xmm2 //nincs min uq :/ {q!!!!!!!!!!!!!!!} pcmpeqd xmm4,xmm2 //emiatt 2-2 d-bol kell osszerakni {q!!!} pandn xmm4,xmm7 //xmm4:newcarry //+c0,+cOld movlhps xmm3,xmm4 //xmm3:regi carry,uj carry; xmm4.hi: uj carry accum pxor xmm5,xmm5 paddq xmm0,xmm3 //add oldCarry,lowCarry pcmpeqq xmm5,xmm0 pand xmm5,xmm3 //xmm5:newcarry2 //+c2,0 pshufd xmm3,xmm5,1+1 shl 2+0 shl 4+1 shl 6 pxor xmm6,xmm6 paddq xmm0,xmm3 //add highCarry,lowCarry.Carry pcmpeqq xmm6,xmm0 pand xmm6,xmm3 //xmm5:newcarry2 //accumulate new alpha paddq xmm4,xmm5 paddq xmm4,xmm6 pshufd xmm3,xmm4,2+3 shl 2+3 shl 4+3 shl 6 //output: xmm0 <- xmm0+xmm1 xmm3<- carry movaps [ecx+edi*4],xmm0 add edi,4 sub esi,4 jnz @@1; pop ebx pop esi pop edi end; procedure AddBigInt3(const a,b,res:pcardinal;const sizeBytes:integer); //a,b,res: align16; sizebytes>0; sizebytes and $f=0 asm push edi push esi push ebx push ebp mov esi,1; movd xmm7,esi; pshufd xmm7,xmm7,0+1 shl 2+1 shl 6 //xmm7 <- ints(1,0,1,0) pxor xmm3,xmm3 //carry mov esi,sizeBytes; shr esi,2+2 xor ebp,ebp clc @@1: movaps xmm0,[eax+ebp*8] movaps xmm1,[edx+ebp*8] movd ebx,xmm0 movd edi,xmm1 adc ebx,edi movd xmm2,ebx psrldq xmm0,4 movd ebx,xmm0 psrldq xmm1,4 movd edi,xmm1 adc ebx,edi movd xmm3,ebx pslldq xmm3,4 por xmm2,xmm3 psrldq xmm0,4 movd ebx,xmm0 psrldq xmm1,4 movd edi,xmm1 adc ebx,edi movd xmm3,ebx pslldq xmm3,8 por xmm2,xmm3 psrldq xmm0,4 movd ebx,xmm0 psrldq xmm1,4 movd edi,xmm1 adc ebx,edi movd xmm3,ebx pslldq xmm3,12 por xmm2,xmm3 movaps [ecx+ebp*8],xmm2 inc ebp inc ebp dec esi jnz @@1; pop ebp pop ebx pop esi pop edi end; procedure checkmyAdc; var a,b,carry,res,newCarry:byte; tmp:byte; begin for carry:=0 to 1 do for a:=0 to 255 do for b:=0 to 255 do begin tmp:=a; res:=a+b; newCarry:=byte(min(res,tmp)<>tmp); res:=res+carry; newcarry:=newcarry or byte((res=0)and(carry<>0)); //chk Assert((res+newCarry shl 8=a+b+carry), format('fakkkkk %d+%d+%d <> %d + %d shl 8',[a,b,carry,res,newCarry])); end; end; var a,b,c1,c2:PCardinal; const testlen=1024; const testcount=1000000; procedure TFrmBigNumTest.FormCreate(Sender: TObject); var i:integer;s:ansistring; begin checkmyadc; SetPriorityClass(GetCurrentProcess,REALTIME_PRIORITY_CLASS); SetMinimumBlockAlignment(mba16Byte); GetMem(a,testlen);FillChar(a^,testlen,0); GetMem(b,testlen);FillChar(b^,testlen,0); GetMem(c1,testlen);FillChar(c1^,testlen,0); GetMem(c2,testlen);FillChar(c2^,testlen,0); RandSeed:=0; for i:=0 to 7 do begin pcardinal(psucc(a,i*4))^:=cardinal(RandSeed);random end; for i:=0 to 7 do begin pcardinal(psucc(b,i*4))^:=cardinal(RandSeed);random end; perfStart('A');for i:=1 to testcount do AddBigInt1(a,b,c1,testlen);perfstop; perfStart('B');for i:=1 to testcount do AddBigInt3(a,b,c2,testlen);perfstop; Memo1.Text:=perfReport; if not CompareMem(c1,c2,testlen)then memo1.lines.add('fakk!!!!'); s:='';for i:=0 to 7 do s:=s+IntToHex(pint64(psucc(a,i*8))^,16)+' ';Memo1.Lines.Add(s); s:='';for i:=0 to 7 do s:=s+IntToHex(pint64(psucc(b,i*8))^,16)+' ';Memo1.Lines.Add(s); s:='';for i:=0 to 7 do s:=s+IntToHex(pint64(psucc(c1,i*8))^,16)+' ';Memo1.Lines.Add(s); s:='';for i:=0 to 7 do s:=s+IntToHex(pint64(psucc(c2,i*8))^,16)+' ';Memo1.Lines.Add(s); FreeMem(a);FreeMem(b);FreeMem(c1);FreeMem(c2); end;
    Mutasd a teljes hozzászólást!
  • ÓÓÓ rendesen kitettél magadért

    Most éjjel már nem állok neki átírni AT&T-re (btw, létezik valami fordító, ami 64bites, támogat C/C++ inline asm-et és Intel szintaktikát(ha jól tudom a VS nem tudja ezt, de mivel azt hiszem, hogy jól tudom, nem próbáltam, szóval lehet, hogy rosszul tudom)? Különben sajnos maradnom kell az öreg gcc-nél), majd holnap/hétvégén megcsinálom, aztán mondom az eredményeket

    Sulis nagyszerveren is ki tudnám próbálni a futásidőt, de a pontos konfighoz még majd ki kell bogarásznom, hogy ezt hogyan tudhatnám meg ssh-n keresztül.
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd