Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.
Oznaka asemblerskog jezika
|
|
Ova stranica je uglavnom namenjena osobama koje su već upoznate sa asemblerom i sa C implementacijom da bi videle zašto je često veoma korisno da se koristi direktna asemblerska
implementacija u odnosu na primenu čiste C implementacije. Postoje, po mom mišljenju, previše programera koji jednostavno ne znaju koju razliku čine ručno kodirani asembleri. Nadam se da ću
pomoći da se popravi ova situacija. Ako imate druge primere, ili ulazne jedinice (ili izazove) koje se tiču ove stranice, ne oklevajte da me - GCD
Na comp.lang.asm.x86, Jon Kirwan je zatražio izlazni kompajler za "najveći zajednički delilac" funkciju iz sledeće C implementacije:
unsigned int gcd (unsigned int a, unsigned int b)
{
if (a == 0 &&b == 0)
b = 1;
else if (b == 0)
b = a;
else if (a != 0)
while (a != b)
if (a <b)
b -= a;
else
a -= b;
return b;
}
Ovo je moj omiljeni C kompajler sa /OS/s opcijama (optimizacija za veličinu, ne koristite nikakvu proveru steka, druge optimizacione opcije nisu mnogo pomogle) naspram ljudske (tj. mene) implementacije:
; WATCOM C/C++ v10.0a output
gcd: mov ebx,eax
mov eax,edx
test ebx,ebx
jne L1
test edx,edx
jne L1
mov eax,1
ret
L1: test eax,eax
jne L2
mov eax,ebx
ret
L2: test ebx,ebx
je L5
L3; cmp ebx,eax
je L5
jae L4
sub eax,ebx
jmp L3
L4: sub ebx,eax
jmp L3
L5: ret; Author: Paul Hsieh
gcd: neg eax
je L3
L1: neg eax
xchg eax,edx
L2: sub eax,edx
jg L2
jne L1
L3: add eax,edx
jne L4
inc eax
L4: ret
Posebna slabost ovog kompajlera je da nije sigurno sa kakvim registratorima treba početi. Ali uprkos tome fali veliki broj optimizacionih mogućnosti kada se uporedi sa ljudskom implementacijom. Nema poređenja da li je u pitanju brzina ili veličina. Naravno, kao čovek, imam ogromnu prednost, jer vidim matematičke odnose koji su izgubljeni od strane svih C kompajlera.
Iako xchg nije posebno brzo Intelovo uputstvo, pomaže da ga uradite veoma dobro, i verovatno ne zahteva više od off ciklusa za optimalno obavljanje. Glavna petlja rutine pronalazi se u potpunosti preko instrukcije pre-fetch buffer (16 bajtova).
Koliko god želeo, besmisleno je pokušati i opisati tačne performanse iznad datih algoritama. Oni gotovo u potpunosti imaju ograničene performanse od strane branch mis-prediction penalties and branch taken clocks.
Ažuriranje: Sa pojavom modernih procesora kao što su Alpha, Pentium-II ili Athlon koji imaju duboke kanale i odgovarajuće kazne za loše predviđanje grananja, logično je ukloniti grane preko "predviđanja". U ovom slučaju možemo koristiti min() i max() funkcije da uklonimo unutrašnji most if() iskaz u originalnoj petlji:
x = min (a,b);
y = max(a,b);
while( y!= 0 ) {
x = min(x,y-x); // min (x,y-x)
y - = x; // (y-x)+(x) - min(x,y-x)
}
Ali na 32-bitnoj mašini:
min(x,y) = y+((x-y)>>31)&(x-y)
Tako stavljajući odgovarajuću zamenu i pojednostavljajući po potrebi dolazimo do:
int gcd(int x, int y) {
int t;
y += x;
if(y==0)
y=1;
else do {
x += x;
t = y- x; // (y-x) - (x)
x >>= 1;
x += (t>>31)&t; // min(y-x,x)
y - = x; // (y-x)+(x)-min(x,y-x) == max(x,y-x)
} while(x!=0);
return y;
}
Ponovo, uzimamo Pepsi izazov i dobijamo:
; WATCOM C/C++ v10.0a output
gcd: add edx,eax
jne L1
mov eax,1
jmp L2
L1: mov ebx,edx ; 1 dep: edx
add eax,eax ; 1
sub ebx,eax ; 2 dep: eax
mov ecx,ebx ; 3 dep: ebx
sar ecx,1fH ; 4 dep: ecx
sar eax,1 ; 4/5 shifters
and ebx,ecx ; 5 dep: ecx
add eax,ebx ; 6 dep: ebx
sub edx,eax ; 7 dep: eax
test eax,eax ; 7
jne L1 ; 7
mov eax,edx
L2:; Author: Paul Hsieh
gcd: add edx,eax
jne L1
mov eax,1
jmp L2
L1: mov ebx,edx ; 1 dep: edx
add eax,eax ; 1
sub ebx,eax ; 2 dep: eax
shr eax,1 ; 2
mov ecx,ebx ; 3 dep: ebx
sar ebx,1fH ; 3
and ebx,ecx ; 4 dep: ecx
add eax,ebx ; 5 dep: ebx
sub edx,eax ; 6 dep: eax
test eax,eax ; 6
jne L1 ; 6
mov eax,edx
L2:
Ja sam još uvek ispred, ali u teoriji prilično dobar kompajler bi trebalo da je dobio jednake rezultate. Za razliku od prve petlje, performansa ove petlje je karakterizovana
Ažuriranje: Čuvena knjiga od Michael Abrash "The Zen of Code Optimization" zapravo govori da je metod prostog oduzimanja prespor (ovo je u suprotnosti sa testom koji sam ja izveo). Takođe sam dobio povratnu informaciju od ljudi koji insistiraju da je deljenje bolje za specifične slučajeve ili velike brojeve. I konačno šlag na torti je da u "Priručniku primenjene kriptografije" (ISBN 0-8493-8523-7), se nudi "divide out powers of two" algoritam koji izgleda kao da je dobar kompromis (ali još uvek pati od kazni za pogrešno predviđena grananja) Ja ću morati da istražim ovo malo dublje, i možda ću morati da pregledam ove rezultate. Dodatna analiza je dobrodošla.
Ažuriranje: Samo kao pitanje potpunosti, ja vam predstavljam šta sam pronašao do sada. Korišćenje onog što je očigledno klasičan pristup, radije nego korišćenjem deljenja ili oduzimanja, mi oduzimamo powers of 2 puta manju vrednost od veće. Pored toga, umesto da sledimo GCD algoritam celim putem, kada budemo imali dovoljno male vrednosti za a i b, samo radimo pronalaženje tabela (popunjavanja tabela nisu pokazana ovde.)
#define SLIM (64)
static unsigned smallGcds[SLIM][SLIM];
static unsigned uintGcd (unsigned a, unsigned b) {
unsigned c, d;
/* Divide out low powers of 2 if we can (to decrease a, b) */
d = 1;
while (((a|b) & 1) == 0) {
a >>= 1;
b >>= 1;
d <<= 1;
}
goto start;
do {
/* Find largest 2^t*b, less than a */
c = b;
do { c += c; } while (c <= a);
/* a -= 2^t*b */
a -= (c >> 1);
start:;
/* Make sure a > b, and b != 0 */
if (a < b) {
if (a == 0) return d * b;
c = a; a = b; b = c;
}
} while (a >= SLIM);
/* Return with precalculated small gcds */
return d * smallGcds[a][b];
}
Očigledno, neki slučajevi (a,b) inputa moraju biti provereni (a=0, b=0 šalje program u beskonačnu petlju.)
Verujem da je moguće da se ovo poboljša tako što se obavi pronalaženje tabela na nekoliko bitova od svakog operanda odjednom što bi trebalo da obezbedi glavne linearne faktore koji bi mogli da se iskoriste da bi se smanjili operandi za nekoliko koraka u jednom pokušaju. Tako da se suzdržavam od obavljanja analize jezičkog asemblera dok ne rešim ovo.
Ažuriranje: Postoje brojni podnesci koji su mi privukli pažnju. Prvi je iz Pat D:
; int gcdAsm(int a, int b)
;
; computes gcd(a,b) according to:
; 1. a even, b even: gcd(a,b) = 2 * gcd(a/2,b/2),
; and remember how often this happened
; 2. a even, b uneven: gcd(a,b) = gcd(a/2,b)
; 3. a uneven, b even: gcd(a,b) = gcd(a,b/2)
; 4. a uneven, b uneven: a>b ? a -= b : b -= a,
; i.e. gcd(a,b) = gcd(min(a,b),max(a,b) - min(a,b))
; do 1., repeat 2. - 4. until a = 0 or b = 0
; return (a + b) corrected by the remembered value from 1.
BITS 32
GLOBAL _gcdAsm
SECTION .text
_gcdAsm:
push ebp
mov ebp,esp
push ebx
push ecx
push edx
push edi
mov eax,[ebp + 8] ; eax = a (0 <= a <= 2^31 - 1)
mov ebx,[ebp + 12] ; ebx = b (0 <= b <= 2^31 - 1)
; by definition: gcd(a,0) = a, gcd(0,b) = b, gcd(0,0) = 1 !
mov ecx,eax
or ecx,ebx
bsf ecx,ecx ; greatest common power of 2 of a and b
jnz notBoth0
mov eax,1 ; if a = 0 and b = 0, return 1
jmp done
notBoth0:
mov edi,ecx
test eax,eax
jnz aNot0
mov eax,ebx ; if a = 0, return b
jmp done
aNot0:
test ebx,ebx
jz done ; if b = 0, return a bsf ecx,eax ; "simplify" a as much as possibleshr eax,cl
bsf ecx,ebx ; "simplify" b as much as possibleshr ebx,cl
mainLoop:
mov ecx,ebx
sub ecx,eax ; b - a
sbb edx,edx ; edx = 0 if b >= a or - 1 if a > b
and ecx,edx ; ecx = 0 if b >= a or b - a if a > b
add eax,ecx ; a-new = min(a,b)
sub ebx,ecx ; b- new = max(a,b)
sub ebx,eax ; the difference is >= 0
bsf ecx,eax ; "simplify" as much as possible by 2
shr eax,cl
bsf ecx,ebx ; "simplify" as much as possible by 2
shr ebx,cl
jnz mainLoop ; keep looping until ebx = 0
mov ecx,edi ; shift back with common power of 2 shl eax,cl
done:
pop edi
pop edx
pop ecx
pop ebx
mov esp,ebp
pop ebp
ret ; eax = gcd(a,b)
Drugi podnesak je od Ville Miettinen koji radi (ili je radio) za hybrid graphics koristeći uputstva cmovCC:
/*---------------------------------------------------//*!
* brief Computes GCD of two 32- bit unsigned integers
* param x First unsigned integer
* param y Second unsigned integer
* return gcd(x,y)
* note gcd(x,0) -> x, gcd(0,y) -> y
* note Implemented in x86 assembler (PentiumPro and
* above only as cmov instructions are used)
* note Send all comments/whines to wili@hybrid.fi
* todo [wili 021026] Implement another version that
* uses sbb trickery rather than cmov
* instructions
*-----------------------------------------------------*/
#pragma warning(disable:4035) // no missing return value
inline unsigned int gcd (Uint32 x, Uint32 y) {
__asm {
mov ecx, dword ptr [y]
mov edx, dword ptr [x]
test ecx, ecx
mov eax, edx
je done ;// if (y = 0) -> return x
test eax, eax
mov eax, ecx
je done ;// if (x = 0) -> return y
push edi
bsf ebx, eax ;// ebx = trailingZeroes(y)
bsf ecx, edx ;// ecx = trailingZeroes(x)
cmp ebx, ecx
mov edi, ecx
cmovl edi, ebx ;// edi = min(ebx,ecx)
shr edx, cl ;// x >>= trailingzeroes (x)
mov ecx, ebx
shr eax, cl ;// y >>= trailingzeroes (y)
align 8
mainloop: ;// for (;;)
cmp eax, edx
mov ecx, eax
je skiploop ;// if (x == y) - > break
cmovb eax, edx
cmovb edx, ecx ;// if (y > x) swap(x,y)
sub eax, edx ;// x -= y
bsf ecx, eax
shr eax, cl ;// x >>= trailingzeroes (x)
jmp mainloop
align 8
skiploop:
mov ecx, edi
shl eax, cl ;// return x<<finalShiftLeft
pop edi
done: ;// return value&n bsp;in eax
}
}
#pragma warning(default:4035)
- Opseg skeniranja strukture pakovanja za ključ bez nule
Pretpostavimo da želimo da skeniramo niz struktura kako bi ustanovili da li neka ima vrednosti bez nule kao poseban unos. To jest, pretpostavimo da želite da implementirate sledeću funkciju:
unsigned int existnzkey (struct foobar * table, unsigned int tablelength)
{
int i;
for(i=0;i<tablelength;i++)
if( table[i].key !=0 ) return table[i].key;
return 0;
}
U svom sadašnjem obliku, ovaj kod pati od previše problema potrebnih za neodložnu analizu na asemblerskom nivou. Primenjujući genijalnosti i neke standardne trikove kao što je opisano na mojoj optimizovanoj strani dolazim do:
static unsigned int existnzkey (unsigned int tablelength, struct foobar * table)
{
int i,c,d;
d=i=0;
c=tablelength;
goto Start;
do {
d = table[i].key;
if( d !=0 ) return d;
i++;
c--;
Start:;
} while( c!=0 );
return d;
}
Iako deluje znatno duže i izgleda da dodaje nepotrebnu kompleksnost, zapravo pomaže kompajleru praktično dajući mu promenljivu da bi registrovao mapu. Sada mnogi mogu komentarisati da je upotreba idi na i oznaka loša i da dovodi do toga da kompajleri gase optimizacije ili šta god. Pa, moj kompajler ne izgleda da ima problem sa tim, što je razlog zašto sam ga koristio.
Pod pretpostavkom da imamo:
struct foobar { unsigned int key; void * content; };
ovde je asemblerski izlaz kompajlera naspram mog ručnog kodiranja
; compiler
xor eax,eax
test ecx,ecx
je L2
L1: mov eax,[esi] ; 1 U -
test eax,eax ; 2 U
jne L2 ; 2 V
add esi,8 ; 3 U
dec ecx ; 3 V
jne L1 ; 5 - V +1brt
L2:; by Pisen Chiang and Paul Hsieh
xor eax,eax
test ecx,ecx
je L2
sub esi,8
L1: add esi,8 ; 1 U
sub ecx,1 ; 1 V
sbb eax,eax ; 2 U -
or eax,[esi] ; 3 U
jz L1 ; 4 V +1brt
mov eax,[esi]
L2:
Kompajler osvaja takmičenje u veličini, ali moje je mnogo brže, jer sam izbegao dodatni test i grane u unutrašnjoj petlji. Kao što je prikazano u komentarima, moja petlja štedi vreme (na Pentium-u.)
Impresionirani? Pa, nemojte biti previše impresionirani. U izvesnom smislu sve ovo bi trebalo da bude akademsko. Pravi problem ovde je da mi pristupamo raspoređenim elementima pored niza upakovanih struktura. Ako je niz značajan u veličini, onda na kraju gubimo sve dodatno unete podatke (keš može samo da unese susedne linije podataka.) Cepanje strukture na paralelne nizove podataka, koji imaju lokalitet reference (npr. svi elementi su učitani/upisani u odgovarajućim unutrašnjim petljama) će težiti da učini više za performansu od ovih vrsta optimizacije. Ali čak i u toj situaciji ne mislim da će većina kompajlera koristiti repz scasd.
Ipak, u ovim situacijama u kojima se pridržavate lošeg dizajna niza strukture (kao što je vertex buffer korišćen u microsoft's Direct 3D API) iznad pomenuti kod je primenjiv. - 63 bitni LFSR
Jeste tipičan cyclic redundancy check algoritam kalkulacija. To je u suštini deterministički korak iteracija funkcije koja koristi 63-bitni ulaz, skrembluje bitove na neki ravnomerni pseudo-slučajni način, i zatim vraća te 63 bitove. Takvi algoritmi mogu biti korišćeni za šifrovanje visokih performansi (ali niske bezbednosti), pseudo-slučajnih brojeva, za testiranje integriteta podataka ili hash funkcija.
typedef unsigned long UINT;
void TestC(UINT &b0, UINT &b1)
{
UINT L1, L2, L3;
UINT H1, H2;
// x = (x>>31)^(x>>30)^(x<<32) (mod 2^63)
L1 = (b1<<1)|(b0>>31);
L2 = (b1<<2)|(b0>>30);
H1 = (b1>>31);
H2 = (b1>>30);
b1 = H1^H2^b0 &0x7FFFFFFF;
b0 = L1^L2;
}
Ja sam implementirao ovo pomoću 63 od 64 bita u paru od 32 bitnih poziva promenljivih referenci. (Moj kompajler ne podržava 64-bitni tip.)
; compiler
lea esi,[edx*2] ; 1 U -
shr ebx,31 ; 2 U -
or esi,ebx ; 3 U -
mov ebx,eax ; 4 U -
lea ecx,[edx*4] ; 5 U
shr ebx,30 ; 5 V
or ebx,ecx ; 7 U - +agi
mov ecx,edx ; 8 U -
shr ecx,31 ; 9 U -
shr edx,30 ;10 U -
xor edx,ecx ;11 U -
xor edx,eax ;12 U -
mov eax,esi ;13 U
and edx,07FFFFFFFh ;13 V
xor eax,ebx ;14 U; by Paul Hsieh and Pisen Chiang
mov esi,edx ; 1 U
xor cl,cl ; 1 V
shld edx,eax,1 ; 5 NP +4c*
shld esi,eax,2 ; 9 NP +4c
adc cl,0 ;10 U
xor edx,esi ;10 V
xchg eax,edx ;12 NP +2c
xor dl,cl ;13 U
Ovde ciklusni broj je blizu onom na Pentium MMX (*zapravo pre-MMX CPUs procesori dovode ova dva do nerešenog rezultata s tim da prvi SHLD koristi dodatni sat da bi dekodirao.) Ovo je uglavnom zbog iznenađujuće sporih SHLD instrukcija. Na Pentium Pro/II, K6 and 6x86MX procesorima, SHLD ima značajno poboljšana performanse što ovo čini još ubedljivijem rešenjem baziranom na veličini i brzini.
On je optimizovan samo za rad na Pentium procesorima
; by hand for Pentiums
mov esi,edx ; 1 U
xor cl,cl ; 1 V
shl esi,2 ; 2 U
mov ebx,eax ; 2 V
adc cl,0 ; 3 U
lea edx,[edx*2] ; 3 V
shr ebx,30 ; 4 U
xor edx,esi ; 4 V
xor edx,ebx ; 5 U
xor al,cl ; 5 V
shr ebx,1 ; 6 U -
xchg eax,edx ; 8 NP +2c
xor eax,ebx ; 9 U - Brzo i dirty bubble sortiranje
Andrew Howe, iz Core Designs (proizvođači Tomb Raider-a), poslao mi je izuzetno kratko sortiranu petlju. Prevashodno napisana za WATCOM C/C++, ja sam uklonio cruft da bi vi mogli da vidite to ovde u njenom najoptimalnijem obliku.
; by Andrew Howe
outerloop: lea ebx,[edi+ecx*4]
mov eax,[edi]
cmploop: sub ebx,4
cmp eax,[ebx]
jle notyet
xchg eax,[ebx]
notyet: cmp ebx,edi
jnz cmploop
stosd
loop outerloop
Obratite pažnju na upotrebu xchg, stosd, i petlje, jer je to nešto što nećete videti od C kompajlera. Nisam se trudio da razradim vremenski raspored ove rutine. Imajte na umu da za neke aplikacije, balon sortiranje će nadmašiti neke od sofisticiranijih algoritama za sortiranje. Na primer, 3D aplikacije kojima je potrebno Z-sortiranje, ali koje mogu da se oslone na temporalno lokaliranje da bi uvek održavali uglavnom sortiranu listu. (Za drugo zanimljivo odstupanje duž ove linije vidite <<Sortiranje sa manje od svih činjenica >>) - Brza implementacija strlen-a ()
Nedavno, neko mi je pisao i poslao komentar da strlen() se obično naziva funkcijom, i kao takav je bio zainteresovan za eventualna poboljšanja performansi za njega. U početku, bez mnogo razmišljanja o tome, nisam video da postoji mogućnost da se značajno poboljša algoritam. Bio sam u pravu, ali dokle god je nizak nivo kontrole algoritama u pitanju, postoje mnogobrojne mogućnosti. U osnovi, algoritam je baziran na bajt skeniranju, i kao tipična stvar koju će C verzija da uradi pogrešno je da propusti priliku da smanji teret redundancije.
; compiler
mov edx,ebx
cmp byte ptr [ebx],0
je l2
l1: mov ah,[ebx+1] ; U
inc ebx ; V
test ah,ah ; U
jne l1 ; V +1brt
l2: sub ebx,edx; by Paul Hsieh
lea ecx,[ebx-1]
l1: inc ecx
test ecx,3
jz l2
cmp byte ptr [ecx],0
jne l1
jmp l6
l2: mov eax,[ecx] ; U
add ecx,4 ; V
test al,al ; U
jz l5 ; V
test ah,ah ; U
jz l4 ; V
test eax,0ff0000h ; U
jz l3 ; V
test eax,0ff000000h ; U
jnz l2 ; V +1brt
inc ecx
l3: inc ecx
l4: inc ecx
l5: sub ecx,4
l6: sub ecx,ebx
Ja sam ovde žrtvovao veličinu u korist performanse, tako što sam suštinski odvio petlju 4 puta. Ako su ulazne veze dovoljno duge (tada će performanse biti bitne) na Pentium-u, ASM kod će to izvršiti po stopi od 1,5 klokova po bajtu, dok je C kompajleru potrebno 3 klokova po bajtu. Ako veze nisu dovoljno duge, slabo predviđanje grananja može učiniti ovo rešenje gorim nego ono napred.
Ažuriranje!
Prilikom rasprave o sprite kopiranju podataka (pogledajte sledeći primer) shvatio sam da postoji značajno poboljšanje za 32-bit x86's koji imaju sporo grananje (P-IIs and Athlon.)
; by Paul Hsieh
lea ecx,[ebx-1]
l1: inc ecx
test ecx,3
jnz l3
l2: mov edx,[ecx] ; U
mov eax,07F7F7F7Fh ; V
and eax,edx ; U
add ecx,4 ; V
add eax,07F7F7F7Fh ; U
or eax,edx ; U
and eax,080808080h ; U
cmp eax,080808080h ; U
je l2 ; V +1brt
sub ecx,4
l3: cmp byte ptr [ecx],0
jne l1
sub ecx,ebx
Mislim da će ovaj kod raditi bolje u celini za sve 32 bitne x86s zbog manjeg grananja. 16 bitni k 86 očigledno mogu da iskoriste sličnu ideju, ali treba da bude veoma jasno da će biti najmanje duplo sporiji. (Stvarno počinjem da mi se sviđa ovaj trik maskiranja bitova! Videti sledeći primer) Hvala Zi Bin Yang koji je ukazao na grešku u mom kodu.
Ovde je C verzija iste stvari:
int fstrlen(char *s) {
char *p;
int d;
#define M1 (0x7f7f7f7f)
#define M2 (0x80808080)
#define SW (sizeof(int)/sizeof(char))
p=s-1;
do {
p++;
if( (((int)p)&(SW-1))==0 ) {
do {
d = *((int *)p);
p += SW;
d = (((d&M1)+M1)|d) &M2;
} while( d==M2 );
p -= SW;
}
} while( *p!=0 );
return p-s;
}
Ona sastavlja suštinski istu stvar (na P6 bi trebalo da ima isti učinak) ali ima nekih problema sa njim. Nije previše prenosiv u druge veličine int-a (brojevi 0x7f7f7f7f i0x80808080 trebaju biti skraćeni ili produženi, i bacanje p sa pokazivača na skalar nije garantovano da će raditi) i nije ništa više razumljivije od skupljanja.
Obratite pažnju da iako ravnanje tumačenja nije potrebno na modernim x86's ovde je izvršeno, kao sredstvo da se izbegne neuspeh učitavanja memorije. To se može desiti kao rezultat čitanja na kraju niske, ali pod pretpostavkom da se dodela memorije poravnava barem u DWORD granicama.
Ažuriranje!
Rajan Mek je poslao verziju MMX verziju ovog grananja:
; MMX version by Ryan Mack
; Roughly 13 + 3n + BRANCH clocks on a P-II
const unsigned __int64 STRINGTBL[8] = {0, 0xff,
0xffff, 0xffffff, 0xffffffff, 0xffffffffff,
0xffffffffffff, 0xffffffffffffff}
/* ... */
pxor mm1, mm1
mov ecx, eax
mov edx, eax
and ecx, -8
and eax, 7
movq mm0, [ecx]
por mm0, [STRINGTBL+eax*8]
MAIN:
add ecx, 8
pcmpeqb mm0, mm1
packsswb mm0, mm0
movd eax, mm0
movq mm0, [ecx]
test eax, eax
jz MAIN
bsf eax, eax
shr eax, 2
lea ecx, [ecx+eax-8]
sub ecx, edx
Individualne petlje iteracija ne zavise jedne od drugih, tako da na modernom pokvarenom procesoru ovo je samo ograničen upitni problem. Na P-II imamo 6 ALU microops + 1 load microop, koji bi trebalo da prebaci na 3 klokova po 8 bajtova protoka. Na AMD procesorima postoje 7 riscops što je 3 klokova na jednom Athlon-u i 4 klokova na K6 po 8 bajtova protoka.
Merenja performansi na Athlon-u pokazuju (ignorisanjem lošeg predviđanja grananja) da za duge veze ovaj 64 bitni metod je do 55% brži od prethodnog 32-bitnog metoda (koji je, opet, 22% brže od WATCOM clib implementacije.) Međutim, za veoma kratke veze, ovaj metod je čak 3 puta sporiji od prethodnog metoda (koji je otprilike iste brzine kao i WATCOM clib implementacija). Ali zapamtite da ako su vaše veze su kraće, the branch mispredicts (koji nisu bili na mojim testovima) iskoristiće znatno više vremena. Međutim, ako nameravate da koristite jednu od ovih alternativa, trebalo bi da procenite njihove performanse da vidite koja je najbolja za vaše aplikacije.
Ažuriranje!
Norbert Juffa mi je pisao da me obavesti o starom triku koji predstavlja značajno poboljšanje u odnosu na uređaje koje sam otkrio:
Nakon nekoliko minuta istraživanja ispalo je da je početno otkrivanje nultog bajta od strane Alan Mycroft-a superiornije u odnosu na formulu na jednom vašem sajtu jer ima kratke lance zavisnosti. Na PIII, strcpy() performanse su skočile skoro 20% nakon zamene jednog sa drugim. Mycroft's macro je
#define has_nullbyte_(x) ((x - 0x01010101) & ~x & 0x80808080)
prikazao ovo kao:
mov edx, eax
not eax
sub edx, 0x01010101
and eax, 0x80808080
and eax, edx
; cycle 1
; cycle 2
; cycle 3
Uostalom, jedna od originalnih poruka Mycroft-a o ovom macro se može naći na Deja. Poruka datira iz 27-04-1987!
Uradio sam malu pretragu i zaista možete naći staru nit diskusije o ovome na google grupama. Evo implementacije u C:
#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))
int xstrlen (const char *s) {
const char *p;
int d;
p = s - 1;
do {
p++;
if ((((int) p) & (SW - 1)) == 0) {
do {
d = *((int *) p);
p += SW;
} while (!hasNulByte (d));
p -= SW;
}
} while (*p != 0);
return p - s;
}
Upoređeno sa drugim rešenjima na Athlon-u, ovo je zaista najbrže rešenje za veze do 32 karaktera (MMX rešenje je brže za duže veze). Ova funkcija uveliko nadmašuje strlen većine biblioteka. - Sprite kopiranje podataka
Često pitanje koje se postavlja programerima koji su zainteresovani za renderovanje sprite grafike (npr. programeri video igara) je kako da naprave sprite blitter visokih performansi. U nedavnom razgovoru na rec.games.programmer, ispitivač je imao uslov da niz piksela iz jednog niza bude kopiran u odredišni niz osim ako je vrednost piksela nula (predstavlja transparenciju). Kod za pokretanje izgleda otprilike ovako:
char * scrptr;
char * destptr;
/* ... */
/* copy scanline except where transparent. */
for(x=x0;x<xl;x++) {
if( srcptr[x]!=0 ) destptr[x]=srcptr[x];
}
Naravno, ovaj kod ima nekoliko problema: (1) Sadrži predviđanje grananja unutrašnje petlje koji će verovatno da propada vrlo često i (2) Memorija se učitava jedan po jedan bajt i pri tom troši memorijski propusni opseg i previše povećava petlju.
S tim rečeno, ovo rešenje je zapravo dobro ako memorijska jedinica ima "write combine" i "write mask" mogućnosti i ako memorija upisuje pristup do odredišta koje je više prepreka nego predviđanje grananja, preveliko povećanje petlje ili izvor učitavanja. (Ovo je tačno ukoliko je odredište VRAM, ili je procesor veoma klokovani P-II).
Međutim, ukoliko učitavanje destinacije nije problem (ako je odredište sistemski memorijski buffer), onda učitavanje 4 bajta odjednom i izgradnja maske nije loše rešenje, pod uslovom da možete izgraditi jedan bez korišćenja uslovnih grananja (inače ne bi ste ništa dobili). Russ Williams je smislio direktno orijentisan pristup koristeći carry flag (koji je optimizovan za Pentium):
; by Russ Williams
pushad
mov esi,[pbSrc]
mov ecx,[w]
shr ecx,2
mov edi,[pbDest]
sub edi,esi
looptop:
xor ebx,ebx
mov eax,[esi]
add esi,4
mov edx,eax
ror edx,16
add al,255 ; cf = 1 if al!=0 or 0 if al==0
sbb bl,0 ; bl = -1 if al!=0 or 0 if al==0
add ah,255
sbb bh,0
mov eax,edx
shl ebx,16
add al,255
sbb bl,0
add ah,255
sbb bh,0
mov eax,[edi]
ror edx,16
and eax,ebx ; dest &bg.mask (P6: PRS)
or eax,edx ; merge with src
dec ecx
mov [edi+esi],eax
jnz looptop
popad
Petlja iznad funkcioniše odlično za Pentium-e i nije dostupna za C kompajlere zbog upotrebe carry flag-a. Međutim P-II ne voli delimičan registarski pristup (a non-overlappable 7 clock penalty). Posle kraće diskusije motivisane komentarom Christer Ericson-a, sledeći trik je primenjen:
(((D &0x7F7F7F7F) + 0x7F7F7F7F) | D) &0x80808080
Izraz iznad će generisati bitmasku pri visokim bitovima svakog bajta, 00h ukazuje na nulti bajt, i 80h ukazuje na bez-nulti bajt. Sa direktnim trikovima možete da okrenete ovo u 00h za nulti i FFH za bez-nulti, dajući nam željenu masku. Ovde je kod u asemblerskom jeziku:
; by Paul Hsieh
sub esi,edi
looptop:
mov eax,[esi+edi] ; read sprite source bits
mov ebx,7f7f7f7fh
and ebx,eax
add ebx,7f7f7f7fh
or ebx,eax ; 80808080 bits have non-zero status of bytes.
and ebx,80808080h
shr ebx,7 ; move to 01010101 bits.
add ebx,7f7f7f7fh ; 80==on or 7f==off values in each byte.
and ebx,7f7f7f7fh ; 00==on or 7f==off masks.
lea eax,[ebx+ebx] ; eax has 00==on or fe==off masks. (P5: AGI stall)
or eax,ebx ; eax has 00==on or ff==off masks.
mov ebx,eax
not ebx ; ebx has 00==off or ff==on masks.
and eax,[edi] ; background bits
or eax,[esi+edi] ; merge with sprite bits for final result
mov [edi],eax ; draw!
add edi,4
dec ecx
jnz looptop
Naravno navedena petlja nije posebno pogodna za Pentium-e jer praktično cela petlja je zavisna od podataka, a tu je AGI stall. Ovi problemi mogu biti rešeni odmotavanjem petlje jednom i korišćenjem običnih dodataka umesto Lea (EDKS i EBP registri su vam na raspolaganju za ovo).
Ipak, P-II će pokušati da "prirodno" odmota ovu petlju, i neće patiti od AGI stall-ova i stoga će daleko manje da ima koristi od ručnog planiranja ove petlje (mada verovatno neće smetati). Međutim, pošto je petlja je 22 mikro-OPS (što je za 2 više od P-II preuređivačkog bafer limita) ne može u potpunosti da bude odmotana.
K6 takođe mogu delimično da "odmotaju" ovu petlju jer sadrži više od 6 dekodirajućih klokova.
Zapravo, sa pravim izvorom, C kompajleri bi trebalo da imaju malo poteškoća u dodiru sa izvorom iznad (ili sa nečim veoma sličnim), Ali nisam siguran kako da ubedite svoj C kompajler da treba da se odmota jednom.
Ažuriranje:Nakon nekog razmišljanja, očigledno je da algoritam iznad može i treba da se vrši pomoću MMX i neki novih SSE instrukcija (movntq posebno). Možda ovo i implementiram kasnije.
Druga ideja, koja dolazi od Terje Mathisen, je da koristite P-II kombinovanih upisnih funkcija u vezi sa minimiziranjem kazni za loše predviđanje grananja. Ideja je da koristite masku da bira između dve odredišne adrese za upisne bajtove:
; Idea from Terje Mathisen, implemented by Sean T. Barrett
sub esi,edi
mov edx,temp
sub edx,edi ; edx = (temp-edi)
...
loop:
mov al,[esi+edi] ; al=src
cmp al,1 ; cf = 1 if src==0, 0 if src!=0
sbb ebx,ebx ; ebx = -1 if src==0, 0 if src!=0
and ebx,edx ; ebx = (temp-edi) if src==0, 0 if src! =0
mov [ebx+edi],al ; store to dest (edi) or garbage (temp)
inc edi
dec ecx
jnz loop ; well predicted branch
Naravno, temp je reiskorišćena sistemska matrica namenjena samo kao kanta za transparentnosti upisa. Spoljašnja petlja postaje komplikovana, ali u idealnim situacijama, to će omogućiti bolje iskorišćenje P-II čipset funkcija bez posledica od kazni za loše predviđanje grananja. Carry flag trik još uvek izmiče modernim C kompajlerima. (Naravno, ova petlja bi trebalo da se malo odmota da bi poboljšali performanse).
Ipak, kao i problem gore navedenog skeniranja ključa svi ove može biti akademsko. Za većinu sprajtova koji su renderovani jednom korišćeni iznova i iznova, transparencije i čvrsti izvorni pikseli obično traju dugo. Dakle korišćenjem alternativnog dekodiranja koji daje transparenciju nasuprot ne-transparenciji pokretanja će biti mnogo efikasnija. Blitting transparencija bi došla do toga da dodaje konstante pokazivačima, i blitting čvrstih boja bi bio trenutan bez vršenja ispitivanja izvora.
Ažuriranje: Paolo Bonzini je upisao sa mnogo efikasnijom unutrašnjom petljom Ideja je da se primeni maska na xor razlici izvora i destinacije.
; by Paolo Bonzini
mov eax, [esi+edi] ; read sprite source
mov ebx, [edi] ; source
mov ecx, eax
and ecx, 7f7f7f7fh
add ecx, 7f7f7f7fh ; set bit 7 set if bits 6-0 nonzero
or ecx, eax ; set bit 7 if byte nonzero
and ecx, 80808080h ; 80 == on or 00 == off
xor eax, ebx ; eax = dest ^ source
shr ecx, 7 ; 01010101 bits set if byte nonzero
add ecx, 7f7f7f7fh ; 80 == on or 7f == off
xor ecx, 7f7f7f7fh ; ff == on or 00 == off
and eax, ecx ; d^s== on or 00 == off
xor ebx, eax ; set to source if on
mov [edi], ebx ; set to source if on
Paolo je takođe poslao jednu banalnu MMX petlju
movq mm1, [esi+edi]
pxor mm0, mm0
movq mm2, [edi]
pcmpeqb mm0, mm1 ; mm0 = 0 if on, ff if off
pand mm2, mm0 ; mm2 = 0 if on, d if off
por mm2, mm1 ; mm2 = s if on, d if off
movq [edi], mm2
- Sada je vreme za MMX
Na sandpile DS je pitao kako da uradimo sledeće:
64-bitni MMX reg ima korisne vrednosti samo na byte7 and byte3 (AXXXBXXX, gde A/B-korisno, X-beskorisno). Želim da kopiram byte7 u byte6, byte5, byte4; i da kopiram copy byte3 u byte2, byte1, byte0.
Smislio sam dva načina:
psrld mm0, 24 ; 0 0 0 A 0 0 0 B
packssdw mm0, mm0 ; 0 A 0 B 0 A 0 B
punpckhwd mm0, mm0 ; 0 A 0 A 0 B 0 B
pmullw mm0, Const_0101010101010101 ; A A A A B B B B
ili
psrld mm0, 24 ; 0 0 0 A 0 0 0 B
packssdw mm0, mm0 ; 0 A 0 B 0 A 0 B
packuswb mm0, mm0 ; A B A B A B A B
punpcklbw mm0, mm0 ; A A B B A A B B
punpcklbw mm0, mm0 ; A A A A B B B B
Prvo ima manje instrukcija, ali veću latenciju što je idealno za procesore kao što je Athlon. Drugi ima više instrukcija ali kraću latenciju, što je korisno za procesore kao što su K6, Cyrix or P55C. Nisam siguran koja je petlja bolja za P6 arhitekture.
Naravno kada uđemo u oblast MMX-a, siromašni C kompajler nema ništa da ponudi. - .Generalizovana promena
Norbert Juffa je proučavao Compaq Visual Fortran kompajler i mislio je da bi generalized shift mogla da bude poboljšana. U Fortran jeziku generalized shift je uvek levi shift, ali može da uzme negativnu promenu vrednosti (što je desni shift) i shift vrednosti izvan veličine reči (u bilo kom smeru) u bitovima iznosi 0. Ovde je algoritam koji sam smislio:
unsigned long gensh(unsigned long v, int x) {
int a, b;
a = (v << x) & -(((unsigned int)x) < 32);
x = -x;
b = (v >> x) & -(((unsigned int)x) < 32);
return a| b;
}
ANSI C standard, zahteva da koristimo unsigned int kada koristimo desni shift zbog neodređenog "definisane implementacije" statusa ili korišćenjem desnog shifta na dodeljenim brojevima. Ako se pitate zašto ovo pominjem - to je zato što ovo nije dovoljno poznato, i može da dovede do pogrešnih rezultata. Ovaj put sam uključio i microsoft Visual C++:
; by Paul Hsieh
mov ebx, eax ; 1
shl eax, cl ; 1
cmp ecx, 32 ; 1
sbb edx, edx ; 2 dep: CF
neg ecx ; 2 issue
and eax, edx ; 3 dep: edx
cmp ecx, 32 ; 3 dep: ecx
sbb edx, edx ; 4 dep: CF
shr ebx, cl ; 3 dep: ecx
and ebx, edx ; 5 dep: edx
or eax, ebx ; 6 dep:
; Microsoft Visual C++
cmp ecx, 32 ; 1
mov esi, eax ; 1
sbb edx, edx ; 2 dep: CF
shl esi, cl ; 2 dep: esi
neg edx ; 3 dep: edx ??
neg edx ; 4 dep: edx ??
neg ecx ; 1
and edx, esi ; 5 dep: edx
cmp ecx, 32 ; 2 dep: ecx
sbb esi, esi ; 3 dep: CF
sar eax, cl ; 3 issue (ANSI)
neg esi ; 4 dep: esi ??
neg esi ; 5 dep: esi ??
and eax, esi ; 6 dep: esi
or eax, edx ; 7 dep:
; WATCOM C/C++
cmp edx, 32 ; 1
setb cl ; 2 dep: CF
mov ebx, ecx ; 4 dep: ecx, size
mov esi, eax ; 1
and ebx, 255 ; 5 dep: ebx
mov cl, dl ; 1 rename cl
neg ebx ; 6 dep: ebx
shl esi, cl ; 2 dep: esi,cl
neg edx ; 2 issue
mov ecx, esi ; 3 dep: esi
and ebx, esi ; 7 dep: ebx
cmp edx, 32 ; 3 dep: edx
setb dh ; 4 dep: CF
xor ecx, esi ; 4 dep: ecx ??
mov cl, dh ; 5 dep: dh
mov esi, ecx ; 7 dep: ecx, size
mov cl, dl ; 3 dep: edx
neg esi ; 8 dep: esi
sar eax, cl ; 5 issue (ANSI)
and eax, esi ; 9 dep: esi
or eax, ebx ; 10 dep:
Zapažanja ukazuju na klok na kojem bi idealna 3-way out-of-order x86 mašina (na primer, Athlon) mogao da izvršava ova uputstva. Obratite pažnju da pitanje stoji za svaku od ovih kodovnih sekvenci. To znači da bi mogao da postoji slučaj kada bi x86 procesori išli sa 4-smernim instrukcijama dekodiranja i pitanja u budućnosti. U svakom slučaju, MSVC++ izgleda da se snalazi prilično dobro u pogledu konačnog učinka, ali nije u mogućnosti da se pojednostavi back to back neg reg0 instrukcije. Standardna softversko registraciono preimenovana tehnika za izbegavanje zavisnosti stall-a (posle mov esi, eax ulogu dva registra može i treba da se zameni - dva registra će biti identična posle ove instrukcije osim što je jedan od njih dostupan jedan klok kasnije) se takođe nekoristi. WATCOM C/C++ ima problema sa registrom pogrešne veličine, i nijje svestan standardnog sbb reb, reg trika. - 64-bitni BCD dodatak
Norbert Juffa mi je dao đavolski pametan kod za upotrebu 64 bit BCD dodatka.
; by Norbert Juffa
mov eax, dword ptr [x] ; x (lo)
mov ebx, dword ptr [y] ; y (lo)
mov edx, dword ptr [x+4] ; x (hi)
mov ecx, dword ptr [y+4] ; y (hi)
; here: EDX:EAX = augend, ECX:EBX = addend
mov esi, eax ; x
lea edi, [eax+66666666h] ; x + 0x66666666
xor esi, ebx ; x ^ y
add eax, ebx ; x + y
shr esi, 1 ; t1 = (x ^ y) >> 1
add edi, ebx ; x + y + 0x66666666
sbb ebx, ebx ; capture carry
rcr edi, 1 ; t2 = (x + y + 0x66666666) >> 1
xor esi, edi ; t1 ^ t2
and esi, 88888888h ; t3 = (t1 ^ t2) & 0x88888888
add eax, esi ; x + y + t3
shr esi, 2 ; t3 >> 2
sub eax, esi ; x + y + t3 - (t3 >> 2)
sub edx, ebx ; propagate carry
mov esi, edx ; x
lea edi, [edx+66666666h] ; x + 0x66666666
xor esi, ecx ; x ^ y
add edx, ecx ; x + y
shr esi, 1 ; t1 = (x ^ y) >> 1
add edi, ecx ; x + y + 0x66666666
;;sbb esi, esi ; capture carry
rcr edi, 1 ; t2 = (x + y + 0x66666666) >> 1
xor esi, edi ; t1 ^ t2
and esi, 88888888h ; t3 = (t1 ^ t2) & 0x88888888
add edx, esi ; x + y + t3
shr esi, 2 ; t3 >> 2
sub edx, esi ; x + y + t3 - (t3 >> 2)
; here EDX:EAX = sum
mov edi, z
mov [edi], eax
mov [edi+4], edx
Upotreba carries and rcr instrukcija nasuprot njihovim C ekvivalentima (otprilike) pokazuje da su ogromna pojednostavljenja moguća u asemblaciji koja nije ponuđena u C.
Možete naći više informacija na BCD aritmetici ovde na sajtu Douglas W. Jones-a - Piksel "bashing"
“Gordi" je radio na softverski zasnovanoj grafičkoj biblioteci i zatražio preko USENET-a optimizovane putanje za više zajedničkih pixel bashing rutina. Ovde su neka od rešenja koje sam ja predstavio.
Prva je MMX rutina za kompresovanje 4 bita po pikselu do 1 bita po pikselu po određenom redu. Prevod piksela jednostavno uzima donji bit od svakog zalogaja. Redosled originalnih zalogaja za datu qword je: 21436587 (ne pitajte me - to je Gordy-jeva biblioteka). Pretpostavljamo da su zalogaji bitova zamaskirani (na primer, drugi bitovi su 0).
MagicConst dd 48124812h,48124812h
;....
movq mm7, MagicConst
pcmpeqb mm6, mm6 ; 1111111111111111
psllw mm6, 12 ; 1111000000000000
@quads:
movq mm0, [esi] ; 0006000500080007
movq mm1, mm6 ; XXXX000000000000
pmullw mm0, mm7 ; 8765705800870070
pand mm1, mm0 ; 8765000000000000
psrld mm0, 28 ; 0000000000004321
psrlw mm1, 8 ; 0000000087650000
por mm0, mm1 ; 0000000087654321
packuswb mm0, mm0 ; [?B?A?B?A]
packuswb mm0, mm0 ; [BABABABA]
movd eax, mm0
mov [edi],ax
add esi, 8
add edi, 2
dec ecx
jnz @quads
Pošto su bitovi izolovani, niz promena i ors-a mogu biti zamenjeni sekvencom promena i dodataka. Ali sekvenca promena i dodataka može da se pretvori u jednu možinu. Sa tačke gledišta performanse ovo je dobar kompromis pošto je pmullw potpuno kanalisana instrukcija i u modernom x86, mnoge unutrašnje instance ove petlje bi trebalo da budu u stanju da se izvršavaju paralelno. Ovo rešenje koristi 64 bajtovni izvor u samo nekoliko klokova - obrasci zasnovani na C verovatno ne bi ni bili blizu.
Drugi je bio za prosečne tokove bajtova zajedno (i zaokruživanje naniže). Gordi je tražio rešenje za pre-K6-2 MMX/3DNow! (koji nije imao pavgusb ili pavb instrukcije) kao i pravo rešenje. Ovde su rešenja koja sam ja predložio: Ova rešenja koriste sledeća posmatranja:
; Integer Solution by Paul Hsieh
LTop:
mov eax, [esi]
mov ebx, [edx]
mov ebp, eax
and eax, ebx
xor ebx, ebp
shr ebx, 1
and ebx, 7F7F7F7Fh
add eax, ebx
mov [edi], eax
dec ecx
jnz LTop; MMX Solution by Paul Hsieh
LTop:
movq mm0, [esi]
movq mm1, [edx]
movq mm2, mm0
pand mm0, mm1
pxor mm1, mm2
psrlb mm1, 1
paddb mm0, mm1
movq [edi], mm0
dec ecx
jnz LTop
Ova resenja upotrebite za pracenje :
A + B = (A and B) * 2 + (A xor B)
And therefore:(A + B)/2 = (A and B) + (A xor B)/2
Dok originalni (A + B) dodatak se može prepuniti, dodatak (A i B) + (A xor B)/2 ne može.
Treća rutina je bila potrebna za izvođenje saturacionog dodatka. Koristeći MMX koji je samo trivijalna aplikacija paddusb instrukcije. (kako je "Gordi" naglasio), ali šta je celom rezervnom rutinom? Smislio sam sledeću celu rutinu:
; Integer solution by Paul Hsieh
mov eax, [esi] ; src0
mov ebx, [edi] ; src1
mov ecx, eax
mov edx, ebx
and ecx, ebx ; first bit carry
xor edx, eax ; first bit add (mod 2)
and eax, 0xFEFEFEFE
and ebx, 0xFEFEFEFE
add eax, ebx ; Add top 7 bits (A&0xFE)+(B&0xFE)
sar eax, 1 ; >>= 1 to capture carry bits
and ecx, 0x01010101 ; Is there a carry to the second bit?
add eax, ecx ; (...)>>1
mov ecx, eax
and edx, 0x01010101 ; first bit
and eax, 0x7F7F7F7F
shr ecx, 7
shl eax, 1 ; (...)&0xFE
and ecx, 0x01010101 ; overflows
or eax, edx ; ((...)&0xFE) + (((A&0x01)+(B&0x01))&1)
xor ecx, 0x81818181 ; blockers
sub ecx, 0x01010101 ; 0->80, 1->7F
and ecx, 0x7F7F7F7F ; 0->00, 1->7F
or eax, ecx
shl ecx, 1
or eax, ecx
Ovaj put odvajamo donje bite da bi smo bili sigurni da možemo izvršiti paralelne dodatke sa samo 8 bita radnog opsega u jednom trenutku.
A = (A&0xFE) + (A&0x01)
B = (B&0xFE) + (B&0x01)
SoA + B = ((A&0xFE)+(B&0xFE)) + ((A&0x01)+(B&0x01)) = ((A&0xFE)+(B&0xFE)) + ((A&B&0x01)*2 + ((A xor B)&0x01))
Prenošenje u 9 bit je prevedeno u 0x00 ili 0x7F masku. Od or-ing u maski u destinaciju zatim pomeren u levo za jedan, to postiže isti efekat kao da maska sadrži 0x00 ili 0xFF vrednosti.
Ovog puta, pošto je carry flag zarobljen i korišćen u prvom dodatku, C kompajler ne može duplirati ovu rutinu.
Ažuriranje: Oliver Weichhold je istaknuo zanimljivo pitanje u comp.lang.asm.x86: duplicate this routine.
Update: Oliver Weichhold posted an interesting question in comp.lang.asm.x86:
Moram da konvertujem vrednost boja (u stvari tekel preuzet iz A4R4G4B4 teksture) u A15R15G15B15 vrednost boje održane u MMX registrima.
Iako neko može instiktivno da traži pametnije načine vršenja brojnih promena i maskiranja koje mogu izgledati da su potrebne, to zaista nije potrebno. Uzmite u obzir da što stvarno želite jeste mapiranje 16 ulaznih bitova koje želite da postavite u neke izlazne pozicije, gde svaki ulazni bit je nezavisan od drugih.
To samo vrišti "Potražite tabele" i stvarno to vodi do nekih jednostavnih kodova:
movzx eax, word ptr input_A4R4G4B4
movzx ebx, al
shr eax, 8
movd mm0, dword ptr Table_G4B4_to_G15B15 [ebx*4]
movd mm1, dword ptr Table_A4R4_to_A15R15 [eax*4]
punpckldq mm0, mm1
Tabele se mogu konfigurisati sa jednostavnim C kodom u vreme inicijalizacije. - Konvertovanje Velikih slova
Konvencionalna mudrost kaže da bi brzo konvertovali ASCII vezu u velika slova, treba da koristite tabelu za konverziju svakog slova. Problem je što adresa režima x86 procesora zahteva 32 (ili 16) bitne registre, pa neka vrsta bajt -> DVORD (ili reč) konverzija se dešava. To dovodi do delimične konverzije registra koja je kažnjena na AMD procesorima i razorna je po Intel procesore.
Dakle šta je naša alternativa? Pa, ako možemo da amortizujemo naše performanse pomoću SIMD-a, onda šta mi u stvari pokušavamo da uradimo jeste da prevedemo interval [61h, 7Ah] u [41h,5AH]. Pristup koji sam smislio je bio da iskoristim činjenicu da je ASCII definisan dobro samo u intervalu [00h, 7Fh] okretanjem intervala i maskiranja, zatim rotiranjem i hvatanjem srednjeg intervala u 5-om bitu i oduzimajući to od 4 ulaznih bajtova:
; Integer SIMD uppercase(string) by Paul Hsieh mov eax, src[esi]
mov ebx, 7f7f7f7fh
mov edx, 7f7f7f7fh
and ebx, eax ; 61-7a | 00-60,7b-7f
add ebx, 05050505h ; 66-7f | 05-65,80-84
and ebx, edx ; 66-7f | 00-65
add ebx, 1a1a1a1ah ; 80-99 | 1a-7f
shr ebx, 2
and ebx, 20202020h ; 20 | 00
sub eax, ebx ; 41-5a | 00-60,7b-7f
Ova rutina se nalazi u opsegu svih modernih C kompajlera. (Ostanite nakačeni na C verziju). Letimičan pogled, međutim, pokazuje da se ova rutina lako konvertuje u MMX.
Ažuriranje: Potreba da bude u stanju da podrži ne-ASCII (npr. uključuje interval [80h, FFh]) mi je pala na pamet. Jedan od bonusa koji se dobija kada je u stanju da uradi kompletan interval je da UTF-8 encoded unicode može da se direktno prevede na ovaj način. U svakom slučaju, to je samo mala promena, koja nažalost košta ciklus na kritičnom putu.
; Integer SIMD uppercase(string) on UTF-8 data by Paul Hsieh mov eax, src[esi]
mov ebx, 0x7f7f7f7f
mov edx, 0x7f7f7f7f
and ebx, eax ; 61-7a | 00-60,7b-7f
mov ecx, eax
add ebx, 0x05050505 ; 66-7f | 05-65,80-84
not ecx ; flip top bits
and ebx, edx ; 66-7f | 00-65
add ebx, 0x1a1a1a1a ; 80-99 | 1a-7f
and ebx, ecx ; turn off top bit for non-ASCII
shr ebx, 2
and ebx, 0x20202020 ; 20 | 00
sub eax, ebx
Ažuriranje: Norbert Juffa mi je pisao da me obavesti da kao deo Sun otvaranja iz Solaris izvornog koda su upotrebili neke od njegovih izvora koršćenih za neke C string funkcije, uključujući poređenja i tolower-a dostupnih javnosti. Možete da vidite izvor ovde.
Ažuriranje: Ja sam dizajnirao alternativnu funkciju koja se bavi sa celim UTF-8 opsegom, ali je takođe više paralelan i samim tim treba da se izvrši nešto brže:
; Integer SIMD uppercase(string) on UTF-8 data v2 by Paul Hsieh mov eax, src[esi]
mov ebx, 0x80808080
mov edx, eax ; src
or ebx, eax ; (0x80808080 | src)
mov ecx, ebx
sub ebx, 0x7b7b7b7b ; (0x80808080 | src) - 0x7b7b7b7b
sub ecx, 0x61616161 ; c = (0x80808080 | src) - 0x61616161
not ebx ; d = ~((0x80808080 | src) - 0x7b7b7b7b)
not edx ; ~src
and ebx, ecx ; c & d
and edx, 0x80808080 ; ~src & 0x80808080
and ebx, edx ; e = (c & d) & (~src & 0x80808080)
shr ebx, 2 ; e >> 2
sub eax, ebx ; src - (e >> 2);
C kod je sasvim uporediv:
; Integer SIMD uppercase(string) on UTF-8 data v2 by Paul Hsieh uint32_t upperCaseSIMD (uint32_t x) {
uint32_t b = 0x80808080ul | x;
uint32_t c = b - 0x61616161ul;
uint32_t d = ~(b - 0x7b7b7b7bul);
uint32_t e = (c & d) & (~x & 0x80808080ul);
return x - (e >> 2);
} - Premeštanje bitova
Norbert Juffa nastavlja da proučava Compaq Visual Fortran kompajler (uskoro će postati Intel Fortran kompajler) ovaj put gledajući na MVBITS komandu. Opis funkcije može se naći Ovde .
MVBITS (FROM, FROMPOS, LEN, TO, TOPOS)
Opis: Kopira sekvencu bitova (bit polje) sa jedne lokacije na drugu.
Klasa: Elementarna podrutina
Argumenti: Postoje pet argumenata:
FROM Može biti bilo koji celoviti tip; Predstavlja lokaciju sa koje je bit polja premešteno. FROMPOS Može biti bilo koji celoviti tip; Ne sme da bude negativan. On identifikuje prvu poziciju bita u polju prebačenom iz FROM. FROMPOS + LEN mora biti manji ili jednak BIT_SIZE (FROM. LEN Može biti bilo koji celoviti tip; Ne sme da bude negativan. Ovo identifikuje dužinu polje premeštenog iz FROM. TO Može biti bilo koji celoviti tip, ali mora da ima iste vrste parametara kao FROM. Predstavlja lokaciju gde je bit polje prenešeno. TO je postavljeno kopiranjem niza bitova dužine LEN, sa početkom u poziciji FROMPOS of FROM do pozicije TOPOS of TO. Nijedan drugi bit iz TO nije izmenjen. Po njegovom povratku, LEN bitovi iz TO (koji počinju u TOPOS) su jednaki vrednosti koju LEN bitovi iz FROM (startuju iz FROMPOS) imaju na ulazu. TOPOS Može biti bilo koji celoviti tip; ne sme biti negativan. On identifikuje startnu poziciju (u okviru TO) za bitove koji se prenose. TOPOS + LEN mora biti manji ili jednak BIT_SIZE (TO).
; Solution by Norbert Juffa
mov ecx, [LEN] ; len
mov eax, [FROM] ; from
cmp ecx, 32 ; (len < 32) ? CY : NC
sbb edx, edx ; (len < 32) ? ~0 : 0
shl edx, cl ; (len < 32) ? ((~0) << len) : 0
mov ecx, [FROMPOS]; frompos
not edx ; mask = (len < 32) ? ~((~0) << len) : ~0
shr eax, cl ; from >> frompos
mov ecx, [TOPOS] ; topos
and eax, edx ; (from >> frompos) & mask
shl edx, cl ; mask << topos
shl eax, cl ; bits << topos
not edx ; ~(mask << topos)
and edx, [TO] ; to & ~(mask << topos)
or eax, edx ; to=(to&~(mask<<topos)|((from>>frompos)&mask)
- Slajdovanje registara, promena registara
Norbert Juffa, koji je gledao neki 64-bitni kod za promene (za 32bitne x86 registre) smanjio je problem pronalaženjem dobrog rešenja:
if (ECX == 0) {
EAX = EDX
EDX = 0
} else { /* ECX == 0xFFFFFFFF */
EAX = EAX
EDX = EDX
}
pod pretpostavkom da ecx je 0 ili FFFFFFFF. Nakon što smo oboje petljali oko toga i išli u pogrešnom pravcu, Norbert je dobio odličnu ideju:
; Solution by Norbert Juffa
sub eax, edx ; a - d
and eax, ecx ; c ? a - d : 0
add eax, edx ; c ? a : d
and edx, ecx ; c ? d : 0
Norbert je umesto toga potržio prosto rešenje zasnovano na grananju, kombinovano sa cmovcc rešenjem za novije procesore koji imaju ovu instrukciju:
; Solution by Norbert Juffa
__declspec (naked) __int64 __stdcall
MYLSHIFT64 (const __int64 *i, const int *sh)
{
__asm {
mov ecx, [esp+8] ; &sh
mov eax, [esp+4] ; &i
mov ecx, [ecx] ; sh
mov edx, [eax+4] ; i_hi
mov eax, [eax] ; i_lo
shld edx, eax, cl ; sll (i,sh & 0x1f)
shl eax, cl ;
#if (CPU == i386)
test ecx, 32 ; sh >= 32 ?
jz $lshift_done ; nope, done
mov edx, eax ; sll (i,32)
xor eax, eax ;
$lshift_done:
cmp ecx, 64 ; (sh>=64)||(sh<0)
sbb ecx, ecx ; (sh>=64)||(sh<0) ? 0 : 0xffffffff
and eax, ecx ; (sh>=64)||(sh<0) ? 0 : sll (i,sh)
and edx, ecx ;
#else /* Athlon, P6+ */
test ecx, -64 ; (sh>=64)||(sh<0) ? NZ : ZR
ror ecx, 6 ; (64>sh>=32) ? CY : NC(ZF safe)
mov ecx, 0 ; 0
cmovc edx, eax ; i=(64>sh>=32) ? sll(i,32) : i
cmovc eax, ecx ;
cmovnz edx, ecx ; (sh>=64)||(sh<0) ? 0 : sll (i,sh)
cmovnz eax, ecx ;
#endif
ret 8 ; pop two DWORD parms and ret
}
}
SHLD, cmovcc, i ror nije verovatno da će se pojaviti u izlazu bilo kog poznatog kompajlera. - Pitanje 64 bitno celih brojeva
Phil Carmody (poznati haker za pretragu primarnih brojeva) poslao je na alt.lang.asm sledeće pitanje:
Imam 2 64-bitna (nikad iznad 2^40, za napomenu) celih brojeva u C, radim sledeće:
/* multiply tpow (in 1..p-1) by 2, modulo p */
tpow <<= 1;
if (tpow > p) { tpow -= p; }
Kompajler sada okreće promenu u SHL i SHLD, sa kojim nemam problem. Međutim, if izjava je renderovana korišćenjem cmps i jumps, koja, pošto je vrednost veoma nepredvidiva, me izaziva da uzmem malo od performanse.
Šta će predložena 64-bitna bez granata bit vrteška da uradi gore? Znam da je 32-bitni ekvivalent neka fanki kombinacija subs, sbbs, ands, drugih i stvari, ali da li se konvertujei u 64 -bita? Da li postoji uopšte verzija cmovcc?
Dao sam sledeći odgovor:
Pa, to izgleda kao da želiš nešto ovako:
tpow <<= 1;
tpow -= p & -(tpow > p);
Dakle, kako da uradimo to - (tpow > p) u potpuno predikatnom načinu? Da vidimo ovo je isto kao -(p - tpow < 0), tako da želimo da izvršimo 64 bita oduzimanje od tpow od p i da uhvatimo carry, i onda ga iskoristimo kao masku i protiv p i zatim oduzmemo od tpow.
mov esi, tpow[0]
mov edi, tpow[4]
add esi, esi
adc edi, edi ; tpow << 1; -- Don't use SHLD.
mov eax, p[0]
mov edx, p[4]
sub eax, esi
sbb edx, edi ; p - tpow
sbb ebx, ebx ; -(p - tpow < 0)
mov eax, negp[0]
mov edx, negp[4]
and eax, ebx
and edx, ebx ; p & -(p - tpow < 0)
sub esi, eax
sbb edi, edx ; tpow - (p & -(p - tpow < 0))
mov tpow[0], esi
mov tpow[4], edi ; tpow -= p & -(p - tpow < 0)
Voila! U redu, mislim da bi cmovCC trebalo da bude još lakši.Vaš kod je ekvivalentan:
tpow <<= 1;
tpow = (tpow - p >= 0) ? tpow - p : tpow;
Tako da ćemo samo izračunati samo tpow - p, uhvatiti CF zastave, zatim uslovno zameniti tpow:
mov esi, tpow[0]
mov edi, tpow[4]
add esi, esi
adc edi, edi ; tpow << 1; -- Don't use SHLD.
mov eax, esi
mov edx, edi ; Annoying dependency.
sub eax, p[0]
sbb edx, p[4] ; tpow - p
cmovnb esi, eax
cmovnb edi, edx ; (tpow - p >= 0) ? tpow - p : tpow
mov tpow[0], esi
mov tpow[4], edi ; tpow = (tpow - p >= 0) ? tpow - p : tpow
- 63 bitni atomski brojač
Na comp.lang.asm, Matt Taylor je poslao da je u potrazi za "lockless 63-bit counter" koristeći 32 bitni kod (naravno korišćenje AMD-ovog novog AMD64 seta instrukcija bi učinilo ovo nevažnim, ali Matt je ograničen na 32-bitni kod). Npr., samo lokacija memorije i sekvenca koda koja može da izvrši povećanje i da učitava čak i u multiprocesorskim situacijama. Jedno od problema je činjenica da su većina memorijskih operacija prekinuta duž magistrale jer individualno učitava i upisuje tako da ALU + memorijska operacije neće biti atomska - međutim to se može tretirati sa kodnom bravom. Pravi problem je što je nemoguće napraviti dva 32-bitni memorijska pristupa da budu zaista atomska.
Prvo iskoristimo vreme da pokažemo rešenje koje ne funkcioniše:
mov eax, 1
lock add [counter], eax ; [[1]]
mov eax, 0
lock adc [counter+4], eax ; [[2]]
Problema je što između [[1]] i [[2]] vaša nit može biti predupređena sa drugom niti koja pokušava da primeni isti kod. To znači da bilo koji dati ciklus 64-bitne vrednosti [brojač] može lako da bude neprecizan, pa čak i tako puno. To je ono što je poznato kao race condition. Postoji beskonačan broj netačnih pokušaja da se da zakrpi ovaj tip koda, što može zahtevati analize za otkrivanje mana. Ja ću preskočiti sve što možete/i treba da naučite o njima na nivou časova na koledžu.
; Eighth generation (64bit) x86 code.
mov rax, 1
lock xadd [counter], rax
inc rax
Ovo opisuje semantiku koju tražimo -- želimo da povećamo i da se vratimo sa povećanom vrednošću poštujući lokalni kontekst. Dakle, ne samo da moramo da uradimo to za 64-bita, već moramo da dobijemo učitavanje iza brojača na način koji odražava tu vrednost pre nego što bilo koja druga tema poveća brojač. Naravno, uzimajući da je AMD64 nov set instrukcija, trebalo bi da prođe malo vremena pre nego što budemo mogli da implementiramo ovo rešenje naširoko.
Ali startujući sa Pentium Pro setom instrukcija, čak 32 bit x86s imaju bitk86s imaju pristup 64-bitnom testu i setu instrukcija: CMPXCHG8B:
retry: mov eax, dword ptr [counter] ; [[1]]
mov edx, dword ptr [counter+4] ; [[2]]
mov ebx, eax
mov ecx, edx
add ebx, 1
adc ecx, 0
lock cmpxchg8b qword ptr [counter] ; [[3]]
jnz retry
Dakle ideja je da se spekulativno nadamo da će brojač ostati netaknut od strane drugih tema iz [[1]] do [[3]]. CMPXCHG8B instrukcija nam omogućava da proverimo ovo pre angažujemo operaciju povećanja. prirastu Ako postoji bilo koja nedoslednost (uključujući neslaganja između [[1]] i [[2]] kao rezultat interventnih operacija povećanja) onda se vraćamo na kraj reda čekajućih povećavanja i ponovo pokrećemo operaciju.
Već možemo da vidimo da sa ovim rešenjem smo ušli u prostor gde teorija počinje da se mršti na naše pretpostavke. Ne postoji garancija da će bilo koja tema na kraju da se završi zato što može da se zaglavi u ovoj ponovo pokušanoj petlji za određeno vreme. U stvari, kada je Matt ovo merio benchmark-u (verovatno je mislio da će zaista pobediti mnoge teme i višestruke procesore) saznao je da su performanse ovog koda bile veoma nezadovoljavajuće iz jednog razloga -- dakle ima praktičnih posledica takođe.
"63-bitni brojač", dolazi od ideje da koristeći jedan od bita kao nekakvu zastavu koja ukazuje da se obmotavanje desilo. Možemo pretpostaviti da većinu vremena, povećanje će uticati na samo nekoliko, otprilike 30-bitova, i da samo treba da se konkretno bavimo konkretnim slučajevima obmotavanja. Uz malu pomoć Terje Mathisen i Matt Taylor, smislio sam sledeći kod (baziranim na XADD instrukciji koji je dostupan još od 80486 procesora):
; by Paul Hsieh, Matt Taylor and Terje Mathisen
incrementCounterAndRead:
mov eax, 1
;;cli
mov edx, [counter+4] ; [[1]]
lock xadd [counter], eax
cmp eax, 07FFFFFFFh
jne incrDone
inc edx
mov [counter+4],edx ; [[2]]
mov ebx, 080000000h
lock add [counter], ebx ; [[3]]
;;sti
jmp readDone
incrDone:
;;sti
jb noLockBit
retry:
cmp edx, [counter+4] ; Early correction.
jne topIsUpToDate
mov ebx, [counter]
cmp ebx, 07FFFFFFFh
ja retry ; Wait for "lock bit"&nb sp;to reset.
topIsUpToDate:
mov edx, [counter+4]
jmp readDone
noLockBit:
mov ebx, [counter+4]
cmp edx, ebx
je readDone
cmp eax, 040000000h ; bit 30 on -> before wrap.
jae readDone
mov edx, ebx ; after wrap.
readDone:
lea eax, [2*eax+1] ; previous low + 1.
shrd eax, edx, 1
shr edx, 1
Glavna ideja je da su niži 31 bitovi samo nižii 31 bitovi brave, 31 bit pokazuje da se odmotavanje desilo, i 30 bit takođe može da ukaže ukoliko se neka protivrečnost u visokim 32 bitovima desila zbog odmotavanja.
Sa pretpostavkom.da će se ne više od 30 bitova od (oko milijardu) povećanja desiti tokom spora mi se ne nalazimo više u nečemu sličnome teorijskoj teritoriji. Na primer, postoji očigledna uslovna trka između [[1]] i [[2]] ako, ustvari, postoji 4.3 milijardi povećanja iz prethodnih tema između dve operacije zbog prisvojenja. Međutim, imajući milijardu teme koje preduzimaju akciju između nekoliko instrukcija nije realan scenario, pa bi ovo u praksi trebalo da radi prilično dobro.
Atomic primitives koji vole ovo su uvek lukavi, pa vredi probati videti zašto radi. (Rečeno na drugi način, ne treba verovati ovom kodu, ili bilo čijem, osim ako ne razumete kako radi).
Ok, korišćenjem XADD na nižim 32 bitovima, zaista ne postoji mogućnost da će niži 31 bitovi krenuti naopako. I kada se 31 bitno obmotavanje desi, tačna nit gde se obmotavanje desilo predstavlja jedinu nit koja pokušava da ispravi visoku reč. Kada je visoka reč netačna, to je samo jedna manje od njene tačne vrednosti i "lock bit" (31 bit od niže reči) biće postavljen. Tako možete videti da akcija uvećavanja drži bitove u stanju dobro definisanom i determinističkom stanju.
O specifičnom slučaju čitanja ormara obmotavanja se vodi posebno računa, pa pretpostavimo da smo mi jedan od drugih tema. Kada se učitava, ako je viša polovina u skladu sa nižom polovinom (na primer, ubacivanjem niže polovinu učitavanja između dve visoke polovine učitavanja) i ne postoji set brava bitova, onda smo spremni. Ako postoji bilo koja nedoslednost to je zato što su neke druge teme umotane. Mi onda možemo ispitati naš 30 bit da vidimo da li treba budemo poruka ili unapred obmotavanje koje nam govori da li treba da izvršimo kasnije ili ranije čitanje više polovine.
Konačno, ako je brava bitova spremna, znamo smo posle povećanja, i samo čekamo da se brava ukloni ili da se viša polovine promeni i onda samo ponovo učitamo višu polovinu.
Prokomentarisne CLI i STI instrukcije pokazuju gde bi ove instrukcije trebalo da idu da pokušaju da smanje izloženu regiju neizvesnosti u zaključanoj vrednosti (navodeći druge teme da se okreću). U sistemu jednog procesora one su dovoljne da spreče bilo kakavo zadržavanje, a u multiprocesorskom sistemu bi dale neku vrstu garancije koja se tiče iznosa vremena u kojem brojač ne bi bio u trivijalnom stanju. Ali naravno potreban vam je prsten 0 pristup da izvrši ove instrukcije, i one nisu neophodne za funkcionalnu ispravnost.
A u C? Nije neki igrač bojim se. Čak i sa podrškom operativnog sistema, jezik ne može da se takmiči sa ovim tipom pristupa niskog nivoa.
Ostanite priključeni za više ...
Published (Last edited): 16-09-2012
, source:
http://www.azillionmonkeys.com/qed/asmexample.html