» »

[C++ & asm] najhitrejša inicializacija 2D matrike

[C++ & asm] najhitrejša inicializacija 2D matrike

snow ::

Mene zanima kako najhitreje postavit vse elemente v matriki na 0?

Zaenkrat mam trotl ziher varianto:
for(int x=0;x<iNodes;x++)
{
    for(int y=0;y<iNodes;y++)
    {
        conntaken[x][y]=0;
    }
}



Bi šlo z memset?

Kaj pa recimo sse? A se tam 128 bitov enako hitro prenese kot če prenašaš 32 bitne podatke iz registra v mem?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
  • spremenilo: snow ()

BigWhale ::

Memset bi bil najbrz kar prava izbira.

Ali pa ce celo stvar alociras z calloc na heapu...

Gundolf ::

Za dynamic memory ne moreš nič rečt kake vrednosti bojo notri po defaultu, tako da ko nekaj alociraš vsebina ni nujno 0, ne vem od kje ti taka ideja BigWhale.

Če imaš matriko kot statičen C++ array potem lako poskusiš nekaj takega:
int conntaken[10][10] = {0};
in pustiš prevajalniku da se spomni čimhitrejšega načina da to izvede. Ampak to gre le ob initializaciji, ko definiraš matriko. Zelo verjetno bi pa res bilo hitreje če uporabiš malo assemblerja. Mislim da se celo dela tako, da nastaviš en 128biten register na 0 in ga potem kopiraš v RAM. Morda celo obstaja 128 bitni STOS ukaz. Mislim da se ti splača pogledat, sem nekje bral da se to obnese (ali pa to morda velja le za kopiranje podatkov, ne vem točno).

Thomas ::

Najboljš je delat z dirty matriko. Ki jo sploh ni treba inicializirati.

Kako pa veš, kdaj je notri nova, kdaj pa še prejšnja vrednost?

V principu tkole: 5555 je od zdej. 555 je od prej, 55 še od prej in 5 še od malo prej.

Te vrednosti pa rolaš v MMX in podobnih registrih.
Man muss immer generalisieren - Carl Jacobi

snow ::

Aha sem pogledal mal po manualu in ugotovil da gre takole:
PXOR xmm1,xmm1
MOVDQA mem,xmm1
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

BigWhale ::

> Za dynamic memory ne moreš nič rečt kake vrednosti bojo
> notri po defaultu, tako da ko nekaj alociraš vsebina ni
> nujno 0, ne vem od kje ti taka ideja BigWhale.

Emm?

man calloc

DESCRIPTION
calloc() allocates memory for an array of nmemb elements of size bytes
each and returns a pointer to the allocated memory. The memory is set to
zero.


Nevem no.

BigWhale ::

PS: To je javendar bistvena razlika med malloc() in calloc()

Gundolf ::

Aha, sori BigWhale. :8) C ni moje področje pa sem fajn v temo brcnil.

dodatek:
Sem preizkusil tole kodo (sicer je premikanje podatkov, ne initializacija ampak bi moralo biti v principu isto) in dobil zanimive rezultate. Namreč navadna for zanka, ki premika inte je enako hitra kot movdqa. Uporabil sem pa VC++ 2005 express edition, prevajal sem v release mode, procesor je pa Athlon 64 v 32 bitnih windowsih. Tudi če očitno patetično asm kodo še malo pofriziram je rezultat popolnoma isti. Očitno jaz tu že krepko butnem ob max prepustnost pomnilnika. Tako da karkoli boš že ti izumil, se ti splača preverit, če morda standardna C++ rešitev ni približno enako hitra.

Zgodovina sprememb…

  • spremenil: Gundolf ()

Tutankhamun ::

int conntaken[Y][X];
    
int *p;
p = &conntaken[0][0];

for(i = 0; i < Y * X; i++)
      *(p + i) = 0;
AMD Phenom QUAD 9950 Black Edition, 8GB

Gundolf ::

@snow:
_asm {
mov ecx, sizeInBytes;
shr ecx, 4;
jz end;

mov edi, pDest;
mov esi, pSrc;

mov eax, 16;

body:
movdqa xmm1, [esi];
add esi, eax;
movntdq [edi], xmm1; // namesto movdqa daš movntdq in razlika je očitna
add edi, eax;

dec ecx;
jnz body;
end:
}
Tole je pa najbolj optimizirano kar je meni do sedaj uspelo. Tale movntdq uporablja neko magijo s cacheom in rezultati so ene 40% boljši od recimo navadnega memmove, kopiranja v zanki ali istega algoritma z uporabo movdqa ukaza. Da tole pretvoriš v memset, poskrbiš za primere ko začetek kopiranega bloka ne bo alignan na 16 bajtov, ko dolžina bloka ne bo mnogokratnik 16 bajtov itd pa prepuščam tebi.

== Typical Transfer of 10 * 16777216 times of 4 bytes data ==
Time Elapsed = 812 msec

== Optimised Transfer of 10 * 16777216 times of 4 bytes data ==
Time Elapsed = 500 msec

Rerun? (y/n) y

== Typical Transfer of 10 * 16777216 times of 4 bytes data ==
Time Elapsed = 797 msec

== Optimised Transfer of 10 * 16777216 times of 4 bytes data ==
Time Elapsed = 485 msec

Rerun? (y/n)

Fury ::

Na koncu se ti to najverjetneje ne bo poznal (razen ce res skos sam inicializiras matrike 90% cajta) in se ne splaca tok pacat po kodi za zlo mal benefita... al lepo vse memsetas (ne bos verjel kaj dober kompajler zna delat s tem) al pa naredis se en byte (al pa int ce hoces met alignan) "identity" in ga das na 1. Pa ga upostevas pri vseh kalkulacijah... in bos se tam ful profitiral :) Tko smo mel mi neki cajta v enginu sam mislm, da zdej se tega nimamo vec :)

OwcA ::

Če veš dimenzije matrike že za časa prevajanja, bi se verjetno dalo s kalupi skonstruirati podatkovno strukturo ravno prave velikosti in potem pustiš prevajalniku, da jo alocira kakor se mu zdi potrebno.
Otroška radovednost - gonilo napredka.

snow ::

Hvala vsem za nasvete!

Predvsem mi je zanimiva tista od Gundolfa z MOVNTDQ—Store Double Quadword Using Non-Temporal Hint.


@Fury
Vem da se mi zadeva zelo velikokrat izvede... zdej kolk % časa to vzame ne vem.. sem mi pa splača vsako zadevo preštudirat.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

SasoS ::

VS2005, 64-bit target, ne podpira več inline asm-ja. Tak da premisli preden boš šel kodirat veliko asm-ja. Drugače pa, dober kompajler bo maximalno optimiziral memset (bral sem sicer primer za memcpy...ampak bi rekel da je stvar podobna - v VS2005 interno memcpy zbira med 7 ali 8 metodami od rep movsb do mmx in sse metod ki se izberejo dinamično med poganjanjem programa).

CCfly ::

Tale zbirka šablon bi znala biti zanimiva:
http://www.pixelglow.com/macstl/

edit: typo
"My goodness, we forgot generics!" -- Danny Kalev

Zgodovina sprememb…

  • spremenilo: CCfly ()

BigWhale ::

Snow,

Ali lahko sprobas vec variant? Pa kak benchmark sem nalepis?

Me zanima, ce se ASM v resnici splaca.

Thomas ::

Mene pa zanima - kakšne vrednosti shranjuješ v matriko? Koliko bitne?
Man muss immer generalisieren - Carl Jacobi

snow ::

Ubistvu me zanimajo binarne vrednosti... mam pa tabelo intov :) Ja vem lahko bi dal char pa prihranil 30k rama.

Testing... bom izvajal ko pridemo do tja. Prvo moram algoritem potweakat.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

No prov. Povedal nisi, kar sem te vprašal, zato bom vsaj jaz poskušal odgovoriti na tisto, kar si vprašal ti.

Čeprav, približno sem že zgoraj!

Najhitrejši način za reinicializacijo matrike je naslednji. Sploh je ne reinicializiraš vsakič! Samo vsake toliko.

Zdej pa denimo, da shranjuješ v matriko 10 bitne vrednosti. Ob prvem loopu postavljaš notri vrednosti med 0 in 1023. V drugem loopu med 1024 in 2047 ... itd?

Ker tudi tam v N-tem loopu, kjer testiraš, vzameš vse vrednosti pod N*1024 za 0! Med (N+1)*1024 pa za število med 0 in 1023.

Kapiš?

No, če kapiš, potem boš pri 32 bitnih možnih vrednostih matrike redimenzioniral samo vsakih MILIJON loopov!

Kapiš?

Ja, koda, ki to enostavno dela, je pa seveda MMX (ali GWXH ...) in je ne bom (ne smem) napisal. Dokaj lahko jo pa (eno) napišeš sam.

Se razumemo?
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Ubistvu me zanimajo binarne vrednosti... mam pa tabelo intov :) Ja vem lahko bi dal char pa prihranil 30k rama.
In initializacijo pohitril 4x - brez kakršnegakoli igranja z assemblerjem ;)

Zdej odvisno kaj delaš ampak če matrike veliko filaš z 0/1, kopiraš, premikaš in na njih izvajaš logične operacije, potem se ti splača za en element tabele uporabiti en sam bit.

OwcA ::

So to slučajno razpršene matrike?
Otroška radovednost - gonilo napredka.

Thomas ::

> potem se ti splača za en element tabele uporabiti en sam bit.

Rešitev ki sem jo nakazal, "pobira vsakič" BISTVENO MANJ kot 1 bit v matriki.

Kako je to mogoče? Jah tadrugi konec infota je razpršen v stanju programa v tisti točki.

Kdor ni šokiran, ni razumu. 8-)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> So to slučajno razpršene matrike?

Za veliko večino teh zadev to vse lepo prime. So pa možne matrike in primeri (vsaj extra designed) kjer se ne splača.
Man muss immer generalisieren - Carl Jacobi

OwcA ::

Vem, da je bolj splošno, ampak če ima snow razpršeno matriko je precejšna verjetnost, da se bolj splača to upoštevati.
Otroška radovednost - gonilo napredka.

Thomas ::

No sej. Po moje da ma in da se mu bo kar splačalo.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Rešitev ki sem jo nakazal, "pobira vsakič" BISTVENO MANJ kot 1 bit v matriki.
Ja, ne rabi initializacije, pri premikanju, and-anju itd. mora pa še vedno vse elemente premaknit, and-at, ...

Fury ::

Dej uporab memset k se ti ne bo nc poznal.. s kaksnimi stvarmi se vi sekirate :)

snow ::

Thomas
1 bitne vrednosti. Sem napisal gor binarne - lapsus.

In... ja šokiran sem :) Sem razumel.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

> Ja, ne rabi initializacije,

Super, ane? Sej ne bi verjel da je možno, če ne bi vidu?

> pri premikanju, and-anju itd. mora pa še vedno vse elemente premaknit, and-at, ...

Lahko se zgodi da rabiš, lahko se zgodi da ne rabiš (vsega) tega.

Lahko se zgodi, da je potem še bolj pripravno.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> 1 bitne vrednosti.

Torej boš še vedno reinicializiral na vsake par milijardokrat! ;)


> Dej uporab memset k se ti ne bo nc poznal..

:D
Man muss immer generalisieren - Carl Jacobi

snow ::

> Torej boš še vedno reinicializiral na vsake par milijardokrat!

:D Me happy.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Fury ::

snow ko bos napisal program prosim objavi rezultate tajmingov ene naloge... enkrat nej bo notri thomasov nacin, drugic inicializiraj z memset.. pa da vidmo razliko. Bos?


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Apple se poslavlja od 32 bitov (strani: 1 2 3 )

Oddelek: Novice / Apple iPhone/iPad/iPod
10825072 (20056) AndrejO
»

Naloga z Matrikami v c++

Oddelek: Programiranje
112150 (1937) Tutankhamun
»

[C#] [XNA] Premikanje objekta

Oddelek: Programiranje
6861 (818) furion
»

Matrika- Determinanta

Oddelek: Programiranje
63707 (3552) pro2c
»

vaša sintaksa pri programiranju (strani: 1 2 )

Oddelek: Programiranje
986543 (4346) Thomas

Več podobnih tem