Forum » Znanost in tehnologija » Digitalna evolucija
Digitalna evolucija
Thomas ::
Nas zanima, kako hitro se izvede nek algoritem.
NE zanima nas, kako hitro se izvede milijonkrat zapored, če to ni natančno milijonkrat več, kot če se enkrat.
Vsaka "diagonalizacija", ko procesor uporablja od prej cacheirane rezultate, ni merodajna za noben benchmark.
Zato trdim, da je algoritem:
if (n>1048576) return 2097152;
if (n>524288) return 1048576;
if (n>262144) return 524288;
if (n>131072) return 262144;
if (n>65536) return 131072;
if (n>32768) return 65536;
if (n>16384) return 32768;
if (n>8192) return 16384;
if (n>4096) return 8192;
if (n>2048) return 4096;
if (n>1024) return 2048;
if (n>512) return 1024;
if (n>256) return 512;
if (n>128) return 256;
if (n>64) return 128;
if (n>32) return 64;
if (n>16) return 32;
if (n>8) return 16;
if (n>4) return 8;
if (n>2) return 4;
if (n>1) return 2;
if (n>0) return 1;
teoretično najhitrejši možni algoritem. Hitrejšega NI.
Katera izvedba, kateri prevod v strojni jezik je najboljši, to je diskutabilno. Ampak nobena tabela ne more biti hitrejša, nič ne more biti hitrejše.
"Žal".
NE zanima nas, kako hitro se izvede milijonkrat zapored, če to ni natančno milijonkrat več, kot če se enkrat.
Vsaka "diagonalizacija", ko procesor uporablja od prej cacheirane rezultate, ni merodajna za noben benchmark.
Zato trdim, da je algoritem:
if (n>1048576) return 2097152;
if (n>524288) return 1048576;
if (n>262144) return 524288;
if (n>131072) return 262144;
if (n>65536) return 131072;
if (n>32768) return 65536;
if (n>16384) return 32768;
if (n>8192) return 16384;
if (n>4096) return 8192;
if (n>2048) return 4096;
if (n>1024) return 2048;
if (n>512) return 1024;
if (n>256) return 512;
if (n>128) return 256;
if (n>64) return 128;
if (n>32) return 64;
if (n>16) return 32;
if (n>8) return 16;
if (n>4) return 8;
if (n>2) return 4;
if (n>1) return 2;
if (n>0) return 1;
teoretično najhitrejši možni algoritem. Hitrejšega NI.
Katera izvedba, kateri prevod v strojni jezik je najboljši, to je diskutabilno. Ampak nobena tabela ne more biti hitrejša, nič ne more biti hitrejše.
"Žal".
Man muss immer generalisieren - Carl Jacobi
OwcA ::
@Thomas: načeloma bi se bolj ali manj strinjal s tistim citatom (lepo bi bilo navesti še vir), ampak ne pa če primerjamo algoritem razvit s Critticallom in "ročno". Kajti Critticall že od vsega začetka optimizira glede na neke vhodne podatke, tako da moramo dobre testne primere tako ali tako pripraviti in ga lahko uporabimo tudi pri primerjanju hitrosti, še celo najbolj pošteno je tako. S tem večina protiargumentov odpade, v kolikor uporabimo enako stopnjo optimizacije in dobre testne primere seve. Nekoč nekdaj si tudi sam priznal, da zagotovo algoritem pravilno deluje le za podane vhodne podatke, glede na katere je tudi izražena pohitritev. Ob izpolnjenih teh predpostavkah je pravzaprav vseeno, četudi je zmagovalec posledica smelega predpomnjenja, kajti to pomeni le, da je ta algoritem bolj skladen z procesorjevim mehanizmom predvidevanja in/ali pomnilniško manj zahteven, to pa sta dve lastnosti, ki bosta prišli prav v vsaki situaciji.
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
Thomas ::
Critticall je k temu algoritmu, ki ga nazadnje lahko napišeš tudi v obliki zanke, konvergiral.
Ni mogel drugače, če je bil le prav vprašan.
> Ob izpolnjenih teh predpostavkah je pravzaprav vseeno, četudi je zmagovalec posledica smelega predpomnjenja, kajti to pomeni le, da je ta algoritem bolj skladen z procesorjevim mehanizmom predvidevanja
Benchmarking je izjema od tega pravila.
Spremljaj naprej zadeve na Gamedev.net.
Ni mogel drugače, če je bil le prav vprašan.
> Ob izpolnjenih teh predpostavkah je pravzaprav vseeno, četudi je zmagovalec posledica smelega predpomnjenja, kajti to pomeni le, da je ta algoritem bolj skladen z procesorjevim mehanizmom predvidevanja
Benchmarking je izjema od tega pravila.
Spremljaj naprej zadeve na Gamedev.net.
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Benchmarking je izjema od tega pravila.
Ja, ko iščeš najboljši algoritem, ne ko rešuješ realni (in povsem konkretni) problem.
Otroška radovednost - gonilo napredka.
noraguta ::
kar se da videti tam je en zmeden osebek ki hoce propagitat nekaj kar nihce noce. napacni rezultati ne zanimajo nikogar uvidi to najprej. potem se loti svoje olike, ni treba ,da prezentiraš neotesanega in neumnega tepca in vsaj da razcistimo glede sortov , benchmarkali smo hitrost sortov in ne pomnilnisko porabo , ako vzamemo to v racun in SUS ovo specificnost je statistika ki jo potrebijemo za triganje dolocenega algoritma nezanemarljiva. glede genericnega komparatorja pa se vedno nismo dobili odgovora . ali pač ?
vseeno je kdo optimizira critical ali compiler, ali je to iz funkionalisticnega pristopa zadosti jasna trditev?
ako je resda da ukolikor jaz dobim iz gamedev benche sta algotima bolj ali manj identicna.
le da je od digitalillusna pravilen le tvoj pa ni.
vseeno je kdo optimizira critical ali compiler, ali je to iz funkionalisticnega pristopa zadosti jasna trditev?
ako je resda da ukolikor jaz dobim iz gamedev benche sta algotima bolj ali manj identicna.
le da je od digitalillusna pravilen le tvoj pa ni.
Pust' ot pobyedy k pobyedye vyedyot!
Zgodovina sprememb…
- spremenilo: noraguta ()
Thomas ::
#include <math.h>
#include <stdio.h>
#include <windows.h>
#include <conio.h>
// define bits. Don't go over 22, since the original code may fail.
#define BITS 20
unsigned NextPow2_Critticall( int n ) {
/*
if (n>1048576) return 2097152;
if (n>524288) return 1048576;
if (n>262144) return 524288;
if (n>131072) return 262144;
if (n>65536) return 131072;
if (n>32768) return 65536;
if (n>16384) return 32768;
if (n>8192) return 16384;
if (n>4096) return 8192;
if (n>2048) return 4096;
if (n>1024) return 2048;
if (n>512) return 1024;
if (n>256) return 512;
if (n>128) return 256;
if (n>64) return 128;
if (n>32) return 64;
if (n>16) return 32;
if (n>8) return 16;
if (n>4) return 8;
if (n>2) return 4;
if (n>1) return 2;
if (n>=0) return 1;
*/
int actions=0;
actions++;if (n>1048576) return actions+1;
actions++;if (n>524288) return actions+1;
actions++;if (n>262144) return actions+1;
actions++;if (n>131072) return actions+1;
actions++;if (n>65536) return actions+1;
actions++;if (n>32768) return actions+1;
actions++;if (n>16384) return actions+1;
actions++;if (n>8192) return actions+1;
actions++;if (n>4096) return actions+1;
actions++;if (n>2048) return actions+1;
actions++;if (n>1024) return actions+1;
actions++;if (n>512) return actions+1;
actions++;if (n>256) return actions+1;
actions++;if (n>128) return actions+1;
actions++;if (n>64) return actions+1;
actions++;if (n>32) return actions+1;
actions++;if (n>16) return actions+1;
actions++;if (n>8) return actions+1;
actions++;if (n>4) return actions+1;
actions++;if (n>2) return actions+1;
actions++;if (n>1) return actions+1;
actions++;if (n>=0) return actions+1;
return actions+1;
}
static const unsigned bit[0x100] =
{
1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256
};
unsigned __stdcall nextpow2_DD3(unsigned x)
{
/* --x;
int shift = 0;
if( x & 0xFFFF0000)
{
x >>= 16;
shift = 16;
}
if( x & 0xFF00)
{
x >>= 8;
shift += 8;
}
return bit[x] << shift;
*/
int actions=0;
--x;actions++;
int shift = 0;actions++;
actions++;actions++;
if( x & 0xFFFF0000)
{
actions++;
x >>= 16;
actions++;
shift = 16;
}
actions++;actions++;
if( x & 0xFF00)
{
actions++;
x >>= 8;
actions++;
shift += 8;
}
actions++;actions++;
//return bit[x] << shift;
return actions+1;
}
int main(int argc, char* argv[])
{
int mode=1;mode<<=BITS+1;
int t=GetTickCount();
LARGE_INTEGER c1;
LARGE_INTEGER c2;
int k;int n;
k = 0;
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
k += nextpow2_DD3(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n DD3 : %d useconds. %d=Actions taken." ,GetTickCount()-t, k);
printf(" %d precise c. ", c2.QuadPart-c1.QuadPart);
k = 0;
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
k += NextPow2_Critticall(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Critticall: %d useconds. %d=Actions taken.",GetTickCount()-t, k);
printf(" %d precise c. ", c2.QuadPart-c1.QuadPart);
printf("\n");
printf("\n");
system("pause");
return 0;
}
Poženi tole.
#include <stdio.h>
#include <windows.h>
#include <conio.h>
// define bits. Don't go over 22, since the original code may fail.
#define BITS 20
unsigned NextPow2_Critticall( int n ) {
/*
if (n>1048576) return 2097152;
if (n>524288) return 1048576;
if (n>262144) return 524288;
if (n>131072) return 262144;
if (n>65536) return 131072;
if (n>32768) return 65536;
if (n>16384) return 32768;
if (n>8192) return 16384;
if (n>4096) return 8192;
if (n>2048) return 4096;
if (n>1024) return 2048;
if (n>512) return 1024;
if (n>256) return 512;
if (n>128) return 256;
if (n>64) return 128;
if (n>32) return 64;
if (n>16) return 32;
if (n>8) return 16;
if (n>4) return 8;
if (n>2) return 4;
if (n>1) return 2;
if (n>=0) return 1;
*/
int actions=0;
actions++;if (n>1048576) return actions+1;
actions++;if (n>524288) return actions+1;
actions++;if (n>262144) return actions+1;
actions++;if (n>131072) return actions+1;
actions++;if (n>65536) return actions+1;
actions++;if (n>32768) return actions+1;
actions++;if (n>16384) return actions+1;
actions++;if (n>8192) return actions+1;
actions++;if (n>4096) return actions+1;
actions++;if (n>2048) return actions+1;
actions++;if (n>1024) return actions+1;
actions++;if (n>512) return actions+1;
actions++;if (n>256) return actions+1;
actions++;if (n>128) return actions+1;
actions++;if (n>64) return actions+1;
actions++;if (n>32) return actions+1;
actions++;if (n>16) return actions+1;
actions++;if (n>8) return actions+1;
actions++;if (n>4) return actions+1;
actions++;if (n>2) return actions+1;
actions++;if (n>1) return actions+1;
actions++;if (n>=0) return actions+1;
return actions+1;
}
static const unsigned bit[0x100] =
{
1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256
};
unsigned __stdcall nextpow2_DD3(unsigned x)
{
/* --x;
int shift = 0;
if( x & 0xFFFF0000)
{
x >>= 16;
shift = 16;
}
if( x & 0xFF00)
{
x >>= 8;
shift += 8;
}
return bit[x] << shift;
*/
int actions=0;
--x;actions++;
int shift = 0;actions++;
actions++;actions++;
if( x & 0xFFFF0000)
{
actions++;
x >>= 16;
actions++;
shift = 16;
}
actions++;actions++;
if( x & 0xFF00)
{
actions++;
x >>= 8;
actions++;
shift += 8;
}
actions++;actions++;
//return bit[x] << shift;
return actions+1;
}
int main(int argc, char* argv[])
{
int mode=1;mode<<=BITS+1;
int t=GetTickCount();
LARGE_INTEGER c1;
LARGE_INTEGER c2;
int k;int n;
k = 0;
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
k += nextpow2_DD3(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n DD3 : %d useconds. %d=Actions taken." ,GetTickCount()-t, k);
printf(" %d precise c. ", c2.QuadPart-c1.QuadPart);
k = 0;
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
k += NextPow2_Critticall(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Critticall: %d useconds. %d=Actions taken.",GetTickCount()-t, k);
printf(" %d precise c. ", c2.QuadPart-c1.QuadPart);
printf("\n");
printf("\n");
system("pause");
return 0;
}
Poženi tole.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Kaj blebetaš? Nisem mislil da ti poženeš. Kdo drug naj. 
Man muss immer generalisieren - Carl Jacobi
noraguta ::
skoda da se ne imenuješ Samo to bi bila šele parodia.
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Če zgornji program poženete, kdor ga je pognal, bo videl, da Švedov algoritem naredi okoli milijardo in 100 milijonov operacij, da najde nextpower of 2.
Critticallov - oziroma optimalni - pa rabi le 300 milijonov operacij.
Zdej bo kdo rekel - pa kako da je potem na nekaterih računalnikih hitrejši?!
Ker ga poganjamo sekvencionalno, nekateri compilerji znajo to dejstvo izkoriščati. Meritev ni pravilna. Če bi lahko merili samo eno operacijo, bi videli, da so v resnici počasnejši.
To smo sicer vzeli že kdaj. NE MERI operacij zaporedno, če ne moreš zagotoviti dekontaminacije registrov in podobnih zadev!
Critticallov - oziroma optimalni - pa rabi le 300 milijonov operacij.
Zdej bo kdo rekel - pa kako da je potem na nekaterih računalnikih hitrejši?!
Ker ga poganjamo sekvencionalno, nekateri compilerji znajo to dejstvo izkoriščati. Meritev ni pravilna. Če bi lahko merili samo eno operacijo, bi videli, da so v resnici počasnejši.
To smo sicer vzeli že kdaj. NE MERI operacij zaporedno, če ne moreš zagotoviti dekontaminacije registrov in podobnih zadev!
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Glede na to, da se razvoj procesorjev preusmerja ravno v dodatne nabore in bodobne izboljšave (večjedrni procesorji, boljše predvidevanje ...) je bodisi nespametno, bodisi sofistično zgovarjati testiranje "optimizirano" takorekoč samo za RICS. Oziroma je veljavno resnično le samo dokler primerjamo algoritme v matematičnem smislu in ne v konkretni situaciji.
Nadalje kaj je zate sploh operacija. Če recimo prevedemo kodo za nVidia NV40 (grafični procesor) kar naenkrat dobimo strojno podporo za kopico računskih operacij, ki jih sicer ni. Niti ne traja vsaka operacija enako procesorskih ciklov.
Nadalje kaj je zate sploh operacija. Če recimo prevedemo kodo za nVidia NV40 (grafični procesor) kar naenkrat dobimo strojno podporo za kopico računskih operacij, ki jih sicer ni. Niti ne traja vsaka operacija enako procesorskih ciklov.
Otroška radovednost - gonilo napredka.
Thomas ::
> je veljavno resnično le samo dokler primerjamo algoritme v matematičnem smislu in ne v konkretni situaciji.
Če so matematično optimalnejši, jih je mogoče tudi hitreje izvesti.
Če bi pa hoteli algoritem, ki samo zaporednim številom določa nextpower2, bi pa lahko naredili samo en if in en set v povprečju. Vendar smo hoteli nekaj drugega. Nextpower2 za katerokoli število iz intervala.
Mogoče bo bolj razumljivo takole:
Če bi nekdo meril učinkovitost cacheja na nespucanem pomnilniku od prejšnjega, bi dobil neke nerelevantne (čeprav navidez zelo ugodne rezultate).
Uporabljaj instruction cache, branch predicting in podobno potem, ko že imaš čist in delujoč algoritem! Sicer bodo tvoji rezultati naključno boljši ali slabši, kot so zares.
No bom videl, kje bodo hitreje zapopadli. Tukaj ali na gamedev.net.
Če so matematično optimalnejši, jih je mogoče tudi hitreje izvesti.
Če bi pa hoteli algoritem, ki samo zaporednim številom določa nextpower2, bi pa lahko naredili samo en if in en set v povprečju. Vendar smo hoteli nekaj drugega. Nextpower2 za katerokoli število iz intervala.
Mogoče bo bolj razumljivo takole:
Če bi nekdo meril učinkovitost cacheja na nespucanem pomnilniku od prejšnjega, bi dobil neke nerelevantne (čeprav navidez zelo ugodne rezultate).
Uporabljaj instruction cache, branch predicting in podobno potem, ko že imaš čist in delujoč algoritem! Sicer bodo tvoji rezultati naključno boljši ali slabši, kot so zares.
No bom videl, kje bodo hitreje zapopadli. Tukaj ali na gamedev.net.
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Če so matematično optimalnejši, jih je mogoče tudi hitreje izvesti.
Ja na idealnem (morda celo le ne-fizikalnem) turinogovem stroju, povsod drugod je potrebno upoštevati tudi kje se bo stvar izvajala, v kolikor nam gre za dejansko hitrost, seve.
porabljaj instruction cache, branch predicting in podobno potem, ko že imaš čist in delujoč algoritem! Sicer bodo tvoji rezultati naključno boljši ali slabši, kot so zares.
Delovanje algoritma ni vprašanje (no občasno je, kot smo lahko videli na gamedev
), optimizacije pa na "čistost" ne vplivajo (no nekateri pristopi vplivajo na berljivost, ampak to je postranskega pomena).Torej je vprašanje le ali je smiselno izbirati nadaljne smernice za razvoj oblike bloida formule 1 na dirki Pariz-Dakar.
No bom videl, kje bodo hitreje zapopadli. Tukaj ali na gamedev.net.
Dopuščaš možnost, da bodo v istem trenutku zapopadla ena stran na obeh forumih?
Otroška radovednost - gonilo napredka.
Thomas ::
Upam, da se bodo ljudje kaj naučili. Tukaj in tam.
p.s.
Kako vam kaže tazadnji program ki sem ga postal?
Kako vam kaže, če zakomentirate actionse in poženete oba algoritma?
Kateri compiler uporabljate?
p.s.
Kako vam kaže tazadnji program ki sem ga postal?
Kako vam kaže, če zakomentirate actionse in poženete oba algoritma?
Kateri compiler uporabljate?
Man muss immer generalisieren - Carl Jacobi
Thomas ::
O napačnem rezultatu si ti nekaj sanjal zgoraj. Kolikor sem razumu, si ga videl pri meni.
Ni napačnega rezultata.
Ni napačnega rezultata.
Man muss immer generalisieren - Carl Jacobi
noraguta ::
// define bits. Don't go over 22, since the original code may fail.
#define BITS 20
vsi ostali algoritmi delujejo na celitnem int območju naj me kdo popravi ako se motim.
seveda pa lahko problem reducviramo na eno samo števko .... in pustimo skokritikalu dan ali dva casa , da evolucija pokaže svojo moč...
#define BITS 20
vsi ostali algoritmi delujejo na celitnem int območju naj me kdo popravi ako se motim.
seveda pa lahko problem reducviramo na eno samo števko .... in pustimo skokritikalu dan ali dva casa , da evolucija pokaže svojo moč...
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Ne, ni res. Začetni algoritem, takoimenovani IEEE trik je navzgor omejen na 22 bitov. Zato smo se na benchmarku omejili na toliko.
Vendar optimalni (Critticall's algoritem) lahhko zlahka razširiš na 256 bitov, če hočeš). Še zmeraj bo čisto lepo tekel in v povprečju izvedel 3 (tri) operacije na število. Najmanj 2 (v polovici primerov) in največ 257, v povprečju pa res 3.
p.s.
Tvoja ironija je nepotrebna, tvoje spakovanje pa pomilovanja vredno.
Vendar optimalni (Critticall's algoritem) lahhko zlahka razširiš na 256 bitov, če hočeš). Še zmeraj bo čisto lepo tekel in v povprečju izvedel 3 (tri) operacije na število. Najmanj 2 (v polovici primerov) in največ 257, v povprečju pa res 3.
p.s.
Tvoja ironija je nepotrebna, tvoje spakovanje pa pomilovanja vredno.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
OwcA ::
Rezultati poganjanja zgoraj priloženega programa:
Sistem: P4 3,34 GHz HT, winXp, v ozadju je teklo še nekaj programov, ampak nič drastičnega
Prevajalnik: Intel C++ Compiler 8 integriran v MS Visual Studio 6
Optimizacije: le "splošne" (samo naklikano v VS brez vseh IC specifičnih, bom jutri poskusil še z bolj agresivnim pristopom, danes sem preveč zaspan).
P.S. koda bi lahko bila brez warningov na L3
DD3 : 360 useconds. 1099975520=Actions taken. 1219266152 precise c. Critticall: 390 useconds. 300664256=Actions taken. 1284670804 precise c. --- DD3 : 359 useconds. 1099975520=Actions taken. 1218853320 precise c. Critticall: 391 useconds. 300664256=Actions taken. 1283509720 precise c. --- DD3 : 360 useconds. 1099975520=Actions taken. 1220342684 precise c. Critticall: 375 useconds. 300664256=Actions taken. 1253343340 precise c.
Sistem: P4 3,34 GHz HT, winXp, v ozadju je teklo še nekaj programov, ampak nič drastičnega
Prevajalnik: Intel C++ Compiler 8 integriran v MS Visual Studio 6
Optimizacije: le "splošne" (samo naklikano v VS brez vseh IC specifičnih, bom jutri poskusil še z bolj agresivnim pristopom, danes sem preveč zaspan
).P.S. koda bi lahko bila brez warningov na L3
Otroška radovednost - gonilo napredka.
noraguta ::
kakorkoli na poskoko in noro bi rekel bedanc
ko zamenjamo vrstni red benchov
(LUT za critical) in primerjamo rezultate je lu zmagovalec. to lahko preveri vsak sam. seveda spakovanje tzarote nerazumjen ,.... samo timing steje. ki pa na zalost dragi moj kolega je preprosto pevedan za tvoj algoritem slab.
ko zamenjamo vrstni red benchov
(LUT za critical) in primerjamo rezultate je lu zmagovalec. to lahko preveri vsak sam. seveda spakovanje tzarote nerazumjen ,.... samo timing steje. ki pa na zalost dragi moj kolega je preprosto pevedan za tvoj algoritem slab.
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Lej OwcA, popolnoma nemogoče je, da bi tvoja mašina izvedla dobri 2 milijardi C operacij v 1/3 sekunde.
Zastopi vendarle, da jih tvoj C compiler popegla na račun tega, da se izvajajo zaporedno. Kar je za program čisto v redu, za meritev algoritma pa ni.
Če bi Critticall optimiziral NextPower2 za sekvenco, bi dobil še dosti hujši rezultat. Ampak v tem zdaj ni point. Izklopi nekatere defaultne optimizacije, prej meritev ni pravilna.
Zastopi vendarle, da jih tvoj C compiler popegla na račun tega, da se izvajajo zaporedno. Kar je za program čisto v redu, za meritev algoritma pa ni.
Če bi Critticall optimiziral NextPower2 za sekvenco, bi dobil še dosti hujši rezultat. Ampak v tem zdaj ni point. Izklopi nekatere defaultne optimizacije, prej meritev ni pravilna.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Za Linux -O0
Za Windowse -Od
Pred benchmarkom algoritma vedno izklopimo optimizacije, ker nam te spačijo sliko. Zoptimizirajo nam v tem primeru računanje k-ja. Kar bi se sicer dalo na vsega par ciklov ob fiksni zgornji meji, ki je zdaj 100 milijonov. Če bi bila ta zgornja meja pa variabilna, pa na morda 100 ciklov.
Če pa bi n-ji uletavali random, bi lahko storili komaj kaj.
Za Windowse -Od
Pred benchmarkom algoritma vedno izklopimo optimizacije, ker nam te spačijo sliko. Zoptimizirajo nam v tem primeru računanje k-ja. Kar bi se sicer dalo na vsega par ciklov ob fiksni zgornji meji, ki je zdaj 100 milijonov. Če bi bila ta zgornja meja pa variabilna, pa na morda 100 ciklov.
Če pa bi n-ji uletavali random, bi lahko storili komaj kaj.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
snow ::
GCC brez optimizacij, ona koda brez štetja actionov:
DD3 : 3375 useconds. 436207632=Actions taken. 1 746 464 320 precise c.
Critticall: 2094 useconds. 436207680=Actions taken. 2 146 167 680 precise c.
Pa še z optimizacijami(glede na to da tu sešteva nima nevem kaj bluzit?):
DD3 : 1563 useconds. 436207632=Actions taken. 495 369 136 precise c.
Critticall: 1687 useconds. 436207680=Actions taken. 854 641 588 precise c.
Sicer tud nevem kako seštevka nista identična.
Glede zadeve na gamedev... c++ operacije?! :) Ok princip mi je jasen, ampak dejansko če še hočete nadaljevat tele debate tam morate it na asm nivo.
Ves trik je pa itak v linearni razporeditvi številk. Meni je jasno da je 50% števil če gledamo 32bitna števila med 232 in 231...potem 25% med 231 in 230... enka bo z verjetnostjo 1/2^32 (10-10).
Pri LUT algoritmu pa je večina (vse razen 10-5 za tista 16bitna števila) števil gre po prvi zanki.
Zdej bi gruntal kak gre tole v asm.. ampak sem bolj lev (mikrokontrolerski asm pa ne vem kolk je podoben s tem, pa tud pozabu sem ga že dost..).
No uglavnem če mamo random linearno razporeditev veljajo zgorne cifre, zdej pa naj si gre računat kolk asm korakov oz. procesorskih ciklov porabi kateri algoritem. Je odvisno od razporeditve seveda...ampak zaenkrat predvidevamo linearno razporeditev.
Tak na moj neuki uč...bi rekel da je critticallova zadeva hitrejša.
Naj pa me nekdo razsvetli in napiše kako tista dva algoritma izgledata v asm.
Da nehamo pol bluzit glede teh smotanih cifer pa gremo rubika reševat. (simulator že mam napisan
)
DD3 : 3375 useconds. 436207632=Actions taken. 1 746 464 320 precise c.
Critticall: 2094 useconds. 436207680=Actions taken. 2 146 167 680 precise c.
Pa še z optimizacijami(glede na to da tu sešteva nima nevem kaj bluzit?):
DD3 : 1563 useconds. 436207632=Actions taken. 495 369 136 precise c.
Critticall: 1687 useconds. 436207680=Actions taken. 854 641 588 precise c.
Sicer tud nevem kako seštevka nista identična.
Glede zadeve na gamedev... c++ operacije?! :) Ok princip mi je jasen, ampak dejansko če še hočete nadaljevat tele debate tam morate it na asm nivo.
Ves trik je pa itak v linearni razporeditvi številk. Meni je jasno da je 50% števil če gledamo 32bitna števila med 232 in 231...potem 25% med 231 in 230... enka bo z verjetnostjo 1/2^32 (10-10).
Pri LUT algoritmu pa je večina (vse razen 10-5 za tista 16bitna števila) števil gre po prvi zanki.
Zdej bi gruntal kak gre tole v asm.. ampak sem bolj lev (mikrokontrolerski asm pa ne vem kolk je podoben s tem, pa tud pozabu sem ga že dost..).
No uglavnem če mamo random linearno razporeditev veljajo zgorne cifre, zdej pa naj si gre računat kolk asm korakov oz. procesorskih ciklov porabi kateri algoritem. Je odvisno od razporeditve seveda...ampak zaenkrat predvidevamo linearno razporeditev.
Tak na moj neuki uč...bi rekel da je critticallova zadeva hitrejša.
Naj pa me nekdo razsvetli in napiše kako tista dva algoritma izgledata v asm.
Da nehamo pol bluzit glede teh smotanih cifer pa gremo rubika reševat. (simulator že mam napisan
) Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Aja sam oni nimajo linearne razporeditve... ker tako velikih tekstur kao ni.
Vejo pa ne povedat kako razporeditev majo, kot sem že rekel... je potrebno vedet za KAJ hočeš ti najhitrejši algoritem.
Glede tajminga critticall algoritmov pa raznih drugih optimizacij je pa treba še preštudirat kaj je boljše.
Recimo: eratostenovo sito(full optimizacije) vs critticall-ova verzija(brez optimizacij).
Alpa kaka bolj problemsko usmerjena naloga, kjer se bi dalo v obeh verzijah skompajlat z optimizacijami. Kar tako eno brezvezno računanje ni najboljši pokazatelj hitrosti po moje. Any ideas?
Vejo pa ne povedat kako razporeditev majo, kot sem že rekel... je potrebno vedet za KAJ hočeš ti najhitrejši algoritem.
Glede tajminga critticall algoritmov pa raznih drugih optimizacij je pa treba še preštudirat kaj je boljše.
Recimo: eratostenovo sito(full optimizacije) vs critticall-ova verzija(brez optimizacij).
Alpa kaka bolj problemsko usmerjena naloga, kjer se bi dalo v obeh verzijah skompajlat z optimizacijami. Kar tako eno brezvezno računanje ni najboljši pokazatelj hitrosti po moje. Any ideas?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Lej OwcA, popolnoma nemogoče je, da bi tvoja mašina izvedla dobri 2 milijardi C operacij v 1/3 sekunde.
Čedalje bolj bluziš:
1) števila C operacij ne meriš pravilno, if je vreden vsaj 2, če ne kar 3, sestavljeni operatorji (+=, --) pa po 2
2) "C operacije" so popolnoma irelevantne, zaradi že omenjenih razlik v arhitekturah (saj že generacija jezika narekuje takšno abstrakcijo)
3) Sodobni (namizni) procesorji zmorejo okoli 10000 MIPS
4) Popolnoma zgrešin način testiranja, ki favorizira Critticallovo kodo pri merjenju časa, ker pri DD3 na vsakem koraku actions povečaš za 1, namesto da bi to naredil samo enkrat na blok, ali še boljše sploh samo enkrat. Zato sem nekoliko spremenil tvojo kodo v (še vedno je Critticall kanček na boljšem, ampak precej manj):
if (n>1048576) return 2;
if (n>524288) return 3;
if (n>262144) return 4;
if (n>131072) return 5;
if (n>65536) return 6;
if (n>32768) return 7;
if (n>16384) return 8;
if (n>8192) return 9;
if (n>4096) return 10;
if (n>2048) return 11;
if (n>1024) return 12;
if (n>512) return 13;
if (n>256) return 14;
if (n>128) return 15;
if (n>64) return 16;
if (n>32) return 17;
if (n>16) return 18;
if (n>8) return 19;
if (n>4) return 20;
if (n>2) return 21;
if (n>1) return 22;
return 23;
---
int actions=9;
--x;
int shift = 0;
if( x & 0xFFFF0000)
{
x >>= 16;
shift = 16;
actions+=2;
}
if( x & 0xFF00)
{
x >>= 8;
shift += 8;
actions+=2;
}
return actions;
Rezultati so več kot zanimivi. Izkaže se, da prevajalnik res je "goljufal" ampak predvsem nad grdo implementacijo merjenja operacij. Novi rezultati so tako:
DD3 : 1329 useconds. 1099975520=Actions taken. 172093068 precise c. Critticall: 1781 useconds. 300664256=Actions taken. 1616946268 precise c.
Pri istih nastavitvah sem s staro kodo dobil:
DD3 : 500 useconds. 1099975520=Actions taken. 1666534880 precise c. Critticall: 250 useconds. 300664256=Actions taken. 831468268 precise c
Opcije sem tokrat nastavljal ročno in sicer:
/D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /Fo"Release/" /W3 - brezpredmetno /MT - static, multi-thread C run time library /G7 /QxN - optimizacije za moj procesor /GA - optimizacije za okensko aplikacijo /Og - global optimizations /Oi - inline expansion of intrinsic functions /Ot - all speed optimizations /Oy - use of the EBP register in optimizations /Gf - string-pooling optimization /Gs4096 - Disables stack-checking for routines with n or more bytes of local variables and compiler temporaries /Gy - Packages functions to enable linker optimization. /Qip - interprocedural optimizations for single file compilation /Qparallel - Detects parallel loops capable of being executed safely in parallel and automatically generates multithreaded code for these loops /Qunroll - the compiler automatically chooses the maximum number of times to unroll a loop /GX- /GR- /vd0 /EHc - izklopljen RTTI, constructor displacement member, exception handling /Qc99 - C99 razširitev
Katere ti sedaj niso všeč?
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
Thomas ::
Ničesar nisi napisal, s čimer se jest ne bi strinjal. Vsaj ne bistveno.
No assemblerski program zgleda takole:
int NextPow2_Critticall_asm( int n ) {
_asm {
mov ecx,100000000
mov ebx,0
cmp ecx, 0
je over1
gor:
mov eax, ecx
and eax, 0x001FFFFF
cmp eax, 1048576
jg e21
cmp eax, 524288
jg e20
cmp eax, 262144
jg e19
cmp eax, 131072
jg e18
cmp eax, 65536
jg e17
cmp eax, 32768
jg e16
cmp eax, 16384
jg e15
cmp eax, 8192
jg e14
cmp eax, 4096
jg e13
cmp eax, 2048
jg e12
cmp eax, 1024
jg e11
cmp eax, 512
jg e10
cmp eax, 256
jg e9
cmp eax, 128
jg e8
cmp eax, 64
jg e7
cmp eax, 32
jg e6
cmp eax, 16
jg e5
cmp eax, 8
jg e4
cmp eax, 4
jg e3
cmp eax, 2
jg e2
cmp eax, 1
jg e1
cmp eax, 0
jg e0
jmp over
e21:
add ebx, 2097152
jmp over
e20:
add ebx, 1048576
jmp over
e19:
add ebx, 524288
jmp over
e18:
add ebx, 262144
jmp over
e17:
add ebx, 131072
jmp over
e16:
add ebx, 65536
jmp over
e15:
add ebx, 32768
jmp over
e14:
add ebx, 16384
jmp over
e13:
add ebx, 8192
jmp over
e12:
add ebx, 4096
jmp over
e11:
add ebx, 2048
jmp over
e10:
add ebx, 1024
jmp over
e9:
add ebx, 512
jmp over
e8:
add ebx, 256
jmp over
e7:
add ebx, 128
jmp over
e6:
add ebx, 64
jmp over
e5:
add ebx, 32
jmp over
e4:
add ebx, 16
jmp over
e3:
add ebx, 8
jmp over
e2:
add ebx, 4
jmp over
e1:
add ebx, 2
jmp over
e0:
add ebx, 1
jmp over
over:
dec ecx
jnz gor
over1:
inc ebx
mov x1, ebx
}
return x1;
}
No assemblerski program zgleda takole:
int NextPow2_Critticall_asm( int n ) {
_asm {
mov ecx,100000000
mov ebx,0
cmp ecx, 0
je over1
gor:
mov eax, ecx
and eax, 0x001FFFFF
cmp eax, 1048576
jg e21
cmp eax, 524288
jg e20
cmp eax, 262144
jg e19
cmp eax, 131072
jg e18
cmp eax, 65536
jg e17
cmp eax, 32768
jg e16
cmp eax, 16384
jg e15
cmp eax, 8192
jg e14
cmp eax, 4096
jg e13
cmp eax, 2048
jg e12
cmp eax, 1024
jg e11
cmp eax, 512
jg e10
cmp eax, 256
jg e9
cmp eax, 128
jg e8
cmp eax, 64
jg e7
cmp eax, 32
jg e6
cmp eax, 16
jg e5
cmp eax, 8
jg e4
cmp eax, 4
jg e3
cmp eax, 2
jg e2
cmp eax, 1
jg e1
cmp eax, 0
jg e0
jmp over
e21:
add ebx, 2097152
jmp over
e20:
add ebx, 1048576
jmp over
e19:
add ebx, 524288
jmp over
e18:
add ebx, 262144
jmp over
e17:
add ebx, 131072
jmp over
e16:
add ebx, 65536
jmp over
e15:
add ebx, 32768
jmp over
e14:
add ebx, 16384
jmp over
e13:
add ebx, 8192
jmp over
e12:
add ebx, 4096
jmp over
e11:
add ebx, 2048
jmp over
e10:
add ebx, 1024
jmp over
e9:
add ebx, 512
jmp over
e8:
add ebx, 256
jmp over
e7:
add ebx, 128
jmp over
e6:
add ebx, 64
jmp over
e5:
add ebx, 32
jmp over
e4:
add ebx, 16
jmp over
e3:
add ebx, 8
jmp over
e2:
add ebx, 4
jmp over
e1:
add ebx, 2
jmp over
e0:
add ebx, 1
jmp over
over:
dec ecx
jnz gor
over1:
inc ebx
mov x1, ebx
}
return x1;
}
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Postam tole sredi noči. Ker z zgornjim so nekateri na gamedev imeli težave. Tole ni problemov z vklapljanjem rutine nekam, tole je instant.
Copy, paste & compile.
No prisoners taken this time.
[nekoliko izboljšal prikaz kode z uporabo st.koda taga -OwcA]
Copy, paste & compile.
// nextpow.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <windows.h>
// define bits. Don't go over 22, since the original code may fail.
#define BITS 20
int tab[]={1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,512};
unsigned int x1=0;
static const unsigned bit[0x100] =
{
1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256,
256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256
};
unsigned __stdcall NextPow2_DD3(unsigned x)
{
--x;
int shift = 0;
if( x & 0xFFFF0000)
{
x >>= 16;
shift = 16;
}
if( x & 0xFF00)
{
x >>= 8;
shift += 8;
}
return bit[x] << shift;
}
unsigned NextPow2( unsigned n ) {
int MantissaMask = (1<<23) - 1;
(*(float*)&n) = (float) n;
n = n + MantissaMask & ~MantissaMask;
n = (unsigned) (*(float*)&n);
return n;
}
inline unsigned __fastcall bsr( unsigned x )
{
_asm
{
mov ecx, x
dec ecx
bsr ecx, ecx
mov x1,ecx
}
return x1;
}
inline unsigned nextpow2_BSR2(unsigned x)
{
//return 2<<bsr(--x); // 0 is a special case ...
return 2<<bsr(x); // 0 is a special case ...
}
unsigned NextPow2_asm( unsigned n ) {
_asm {
mov ecx, n
dec ecx
bsr ecx, ecx
mov n, ecx
}
return n;
}
int NextPow2_Critticall( int n ) {
if (n>1048576) return 2097152;
if (n>524288) return 1048576;
if (n>262144) return 524288;
if (n>131072) return 262144;
if (n>65536) return 131072;
if (n>32768) return 65536;
if (n>16384) return 32768;
if (n>8192) return 16384;
if (n>4096) return 8192;
if (n>2048) return 4096;
if (n>1024) return 2048;
if (n>512) return 1024;
if (n>256) return 512;
if (n>128) return 256;
if (n>64) return 128;
if (n>32) return 64;
if (n>16) return 32;
if (n>8) return 16;
if (n>4) return 8;
if (n>2) return 4;
if (n>1) return 2;
if (n>=0) return 1;
return 0;
}
int NextPow2_Critticall_all( int n ) {
int x=0;int mode=1;mode<<=BITS;int m=0;
for (n=0;n<100000000;n++) {
m=n%mode;
if (m>1048576) {x=2097152;goto ower;}
if (m>524288) {x=1048576;goto ower;}
if (m>262144) {x=524288;goto ower;}
if (m>131072) {x=262144;goto ower;}
if (m>65536) {x=131072;goto ower;}
if (m>32768) {x=65536;goto ower;}
if (m>16384) {x=32768;goto ower;}
if (m>8192) {x=16384;goto ower;}
if (m>4096) {x=8192;goto ower;}
if (m>2048) {x=4096;goto ower;}
if (m>1024) {x=2048;goto ower;}
if (m>512) {x=1024;goto ower;}
if (m>256) {x=512;goto ower;}
if (m>128) {x=256;goto ower;}
if (m>64) {x=128;goto ower;}
if (m>32) {x=64;goto ower;}
if (m>16) {x=32;goto ower;}
if (m>8) {x=16;goto ower;}
if (m>4) {x=8;goto ower;}
if (m>2) {x=4;goto ower;}
if (m>1) {x=2;goto ower;}
if (m>=0) {x=1;goto ower;}
ower:;
}
return 0;
}
int NextPow2_table( int n ) {
n--;
if (n>16777216) {
n=n/16777216;
n=tab[n];
return n*16777216;
}
if (n>65536) {
n=n/65536;
n=tab[n];
return n*65536;
}
if (n>256) {
n=n/256;
n=tab[n];
return n*256;
}
return tab[n];
}
int NextPow2_Critticall_asm( int n ) {
_asm {
mov ecx,100000000
mov ebx,0
cmp ecx, 0
je over1
gor:
mov eax, ecx
and eax, 0x001FFFFF
cmp eax, 1048576
jg e21
cmp eax, 524288
jg e20
cmp eax, 262144
jg e19
cmp eax, 131072
jg e18
cmp eax, 65536
jg e17
cmp eax, 32768
jg e16
cmp eax, 16384
jg e15
cmp eax, 8192
jg e14
cmp eax, 4096
jg e13
cmp eax, 2048
jg e12
cmp eax, 1024
jg e11
cmp eax, 512
jg e10
cmp eax, 256
jg e9
cmp eax, 128
jg e8
cmp eax, 64
jg e7
cmp eax, 32
jg e6
cmp eax, 16
jg e5
cmp eax, 8
jg e4
cmp eax, 4
jg e3
cmp eax, 2
jg e2
cmp eax, 1
jg e1
cmp eax, 0
jg e0
jmp over
e21:
add ebx, 2097152
jmp over
e20:
add ebx, 1048576
jmp over
e19:
add ebx, 524288
jmp over
e18:
add ebx, 262144
jmp over
e17:
add ebx, 131072
jmp over
e16:
add ebx, 65536
jmp over
e15:
add ebx, 32768
jmp over
e14:
add ebx, 16384
jmp over
e13:
add ebx, 8192
jmp over
e12:
add ebx, 4096
jmp over
e11:
add ebx, 2048
jmp over
e10:
add ebx, 1024
jmp over
e9:
add ebx, 512
jmp over
e8:
add ebx, 256
jmp over
e7:
add ebx, 128
jmp over
e6:
add ebx, 64
jmp over
e5:
add ebx, 32
jmp over
e4:
add ebx, 16
jmp over
e3:
add ebx, 8
jmp over
e2:
add ebx, 4
jmp over
e1:
add ebx, 2
jmp over
e0:
add ebx, 1
jmp over
over:
dec ecx
jnz gor
over1:
inc ebx
mov x1, ebx
}
return x1;
}
int main(int argc, char* argv[])
{
int mode=1;mode<<=BITS;
int n=0;
int t=GetTickCount();
LARGE_INTEGER c1;
LARGE_INTEGER c2;
int k=0;
QueryPerformanceCounter(&c1);
NextPow2_Critticall_all(0);
QueryPerformanceCounter(&c2);
printf("\n Time NextPow2_Critticall_all: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
k += NextPow2_DD3(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Time NextPow2_DD3: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
NextPow2(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Time NextPow2: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
t=GetTickCount();
QueryPerformanceCounter(&c1);
k=0;
for (n=0; n<100000000; n++) {
k+=NextPow2_Critticall(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Time NextPow2_Critticall: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
x1=0;
nextpow2_BSR2(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n Time NextPow2_BSR2: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
t=GetTickCount();
QueryPerformanceCounter(&c1);
for (n=0; n<100000000; n++) {
NextPow2_table(n%mode);
}
QueryPerformanceCounter(&c2);
printf("\n nextpow2_table: %d miliseconds. ",GetTickCount()-t);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
dol:;
t=GetTickCount();
QueryPerformanceCounter(&c1);
x1=NextPow2_Critticall_asm(0);
QueryPerformanceCounter(&c2);
printf("\n nextpow2_Critticall_asm: %d miliseconds. %d ",GetTickCount()-t, x1);
printf("%d precise counter. ", c2.QuadPart-c1.QuadPart);
printf("\n");
printf("\n");
system("pause");
return 0;
}
No prisoners taken this time.
[nekoliko izboljšal prikaz kode z uporabo st.koda taga -OwcA]
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenilo: OwcA ()
noraguta ::
zakaj tvoja asemblerska procedura sploh jemlje argument? ali predpostavljamo ,da je klic funkcije brezplačen in vračanje vrednosti lete?
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Zakaj ne poveš časov?
(Tvoje vprašanje je pa brezpredmetno. Lahko bi jemala argument, lahko ga ne bi ... nobene bistvene razlike.)
(Tvoje vprašanje je pa brezpredmetno. Lahko bi jemala argument, lahko ga ne bi ... nobene bistvene razlike.)
Man muss immer generalisieren - Carl Jacobi
noraguta ::
Iz povsem praktičnih razlogov , ce ostale reutine realiziramo kakor so nastavljene tvoje , nijh časi drastično padejo.
Kar pa je še huje ugotovi ,da so dummyi in ji tako tudi tretirajo. ima tvoja asemblerska rutina tedaj precej slab čas.
evo ti z optimizacijo.
Time NextPow2_Critticall_all: 0 miliseconds. 3 precise counter.
Time NextPow2_DD3: 0 miliseconds. 4 precise counter.
Time NextPow2: 0 miliseconds. 4 precise counter.
Time NextPow2_Critticall: 0 miliseconds. 4 precise counter.
Time NextPow2_BSR2: 1969 miliseconds. 7026406 precise counter.
nextpow2_table: 656 miliseconds. 2371780 precise counter.
nextpow2_Critticall_asm: 453 miliseconds. 438304785 1578837 precise counte
r.
Vračane vrednosti iz funkcije pobere vsaj eno kopiranje. tudi klic in vračanje staneta.
Vsoje sodbe o brezplodnosti pa zadrži zase , kajti brezlodno je le tvoje prevarantsko pehanje za bog si ga vedi čim.
Kar pa je še huje ugotovi ,da so dummyi in ji tako tudi tretirajo. ima tvoja asemblerska rutina tedaj precej slab čas.
evo ti z optimizacijo.
Time NextPow2_Critticall_all: 0 miliseconds. 3 precise counter.
Time NextPow2_DD3: 0 miliseconds. 4 precise counter.
Time NextPow2: 0 miliseconds. 4 precise counter.
Time NextPow2_Critticall: 0 miliseconds. 4 precise counter.
Time NextPow2_BSR2: 1969 miliseconds. 7026406 precise counter.
nextpow2_table: 656 miliseconds. 2371780 precise counter.
nextpow2_Critticall_asm: 453 miliseconds. 438304785 1578837 precise counte
r.
Vračane vrednosti iz funkcije pobere vsaj eno kopiranje. tudi klic in vračanje staneta.
Vsoje sodbe o brezplodnosti pa zadrži zase , kajti brezlodno je le tvoje prevarantsko pehanje za bog si ga vedi čim.
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Hja no ... na teoretičnem nivoju algoritmov se večinoma niso hoteli/znali pogovarjat.
Implementacija bi jih morala potem strezniti na čisto praktičnem nivoju ...
??? zanimivo. Legenda o Slovenski nevoščljivosti rula?
Implementacija bi jih morala potem strezniti na čisto praktičnem nivoju ...
??? zanimivo. Legenda o Slovenski nevoščljivosti rula?
Man muss immer generalisieren - Carl Jacobi
snow ::
Hm Thomas a ni ona tabela ki se uporablja za DD3 narobe nastavljena? Bi moralo bit 512 na koncu kot je pri meni, ker ubistvo gre za isti princip ampak jaz prej skačem in programa z returni, ker pač nima smisla gledat a je cifra pa večja od 2^16 če je večja od 2^24
Če gledamo recimo 257 (mora prit 512).
Najprej odšteje 1 dobimo 256.. potem gre mimo obeh if-ov.. potem pa pogleda bit[256] in dobi ven 256? :)
Komentar na tist tvoj zadnji program za merjenje časov.
Bi lahko prosim vsi programi jemali spremenljivko in tudi vračali rezultat, pa da bi bili vsi loopi enaki?
Ker po moje tudi call funkcije šteje nekaj :)
Recimo 2 cikla pri mikrokontrolerjih.
Aja pa tista _table zadeva dela na do 32 bit.
Drugače so mi pa tile tajmingi že brezvezni.. pa še asm ma gcc drugčen format, ki ga ne štekam ravno :)
Jaz sem že naveličan tega nextpow2... sem pa na gamedev napisal kaj je bil tam nesporazum oziroma problem.
Če gledamo recimo 257 (mora prit 512).
Najprej odšteje 1 dobimo 256.. potem gre mimo obeh if-ov.. potem pa pogleda bit[256] in dobi ven 256? :)
Komentar na tist tvoj zadnji program za merjenje časov.
Bi lahko prosim vsi programi jemali spremenljivko in tudi vračali rezultat, pa da bi bili vsi loopi enaki?
Ker po moje tudi call funkcije šteje nekaj :)
Recimo 2 cikla pri mikrokontrolerjih.
Aja pa tista _table zadeva dela na do 32 bit.
Drugače so mi pa tile tajmingi že brezvezni.. pa še asm ma gcc drugčen format, ki ga ne štekam ravno :)
Jaz sem že naveličan tega nextpow2... sem pa na gamedev napisal kaj je bil tam nesporazum oziroma problem.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Time NextPow2_Critticall_all: 0 miliseconds. 1172 precise counter.
Time NextPow2_DD3: 0 miliseconds. 1244 precise counter.
Time NextPow2: 796 miliseconds. -1623845804 precise counter.
Time NextPow2_Critticall: 0 miliseconds. 808 precise counter.
Time NextPow2_BSR2: 407 miliseconds. 1378663696 precise counter.
nextpow2_table: 0 miliseconds. 828 precise counter.
nextpow2_Critticall_asm: 187 miliseconds. 438304785 614541216 precise counter.
V čem je poanta? Način testiranja (klici funkcije v zanki ali zanka v funkciji samo) ne upliva zaradi nasilnega inline-anja, kateri algoritem je v končni fazi najhitrejši pa je takisto brezpredmetno. Vsaj kar se mene tiče je bila poanta v tem katera sredstva so dovoljena za dosego cilja.
Otroška radovednost - gonilo napredka.
Thomas ::
Sem nazaj iz raziskovanja Bohinjskih hudournikov. Impresivno!
Ja, sem videl, da fantje so zmetali praktično vse ven in jim nekako bolj približno dela. Koliko bi imeli povedati, če bi meni delalo približno!
Anyway, uporabil bom iste cute in spremenil svoj assemblerski program tako, da bo še bistveno hitrejši - takoj zdajle. Samo da bo točen.
Meni je že tudi dovolj, ampak naj zaključimo zadevo!
Ja, sem videl, da fantje so zmetali praktično vse ven in jim nekako bolj približno dela. Koliko bi imeli povedati, če bi meni delalo približno!
Anyway, uporabil bom iste cute in spremenil svoj assemblerski program tako, da bo še bistveno hitrejši - takoj zdajle. Samo da bo točen.
Meni je že tudi dovolj, ampak naj zaključimo zadevo!
Man muss immer generalisieren - Carl Jacobi
Sergio ::
Kakšni so torej zaključki? Kaj piše pod črto? Thomas, OwcA?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
kopernik ::
Očitno vsak po svoje razume uporabnost nekega algoritma.
Tako ali tako se je tema na gamedev.net precej oddaljila od začrtane smeri.
Po komentarjih je sicer razvidno, da bi večina uporabila DD3 verzijo in ne critticallove (zato, ker naj bi bila v resničnem svetu precej bolj uporabna (hitrejša)).
Tako ali tako se je tema na gamedev.net precej oddaljila od začrtane smeri.
Po komentarjih je sicer razvidno, da bi večina uporabila DD3 verzijo in ne critticallove (zato, ker naj bi bila v resničnem svetu precej bolj uporabna (hitrejša)).
Zgodovina sprememb…
- spremenil: kopernik ()
snow ::
Ja nekaj takega.. ker bodo meli to za neko določanje velikosti tekstur.
Grem se jaz z Rubikom bost sedaj.
Bom probal critticall nahecat da mi poišče kako hevristično funkcijo, ki bi mi povedala kako blizu rešitve je kocka. :)
Grem se jaz z Rubikom bost sedaj.
Bom probal critticall nahecat da mi poišče kako hevristično funkcijo, ki bi mi povedala kako blizu rešitve je kocka. :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Tole sem hotu spostat na gamedev.net:
"Time NextPow2_Critticall_all: 551 miliseconds. 1971061 precise counter.
Time NextPow2_DD3: 80 iliseconds. 283451 precise counter.
nextpow2_Critticall_asm: 280 miliseconds. 438304785 987642 precise counter."
Yeah, right. Your optimized DD3 runs as fast as an empty loop?
Want to know why? Be cause this "optimization" you love so much, in fact empties it!
Ker se tipčki sploh ne zavedajo, da "Critticall's" oziroma "binary" teče samo 3X bolj počasi od prazne zanke.
Njim je v tem citiranem testu tekla prazna zanka!
Ali pa se bo našel še kdo ki bo trdil, da DD3 v resnici teče "in no time?".
Kdo od naših tule?
"Time NextPow2_Critticall_all: 551 miliseconds. 1971061 precise counter.
Time NextPow2_DD3: 80 iliseconds. 283451 precise counter.
nextpow2_Critticall_asm: 280 miliseconds. 438304785 987642 precise counter."
Yeah, right. Your optimized DD3 runs as fast as an empty loop?
Want to know why? Be cause this "optimization" you love so much, in fact empties it!
Ker se tipčki sploh ne zavedajo, da "Critticall's" oziroma "binary" teče samo 3X bolj počasi od prazne zanke.
Njim je v tem citiranem testu tekla prazna zanka!
Ali pa se bo našel še kdo ki bo trdil, da DD3 v resnici teče "in no time?".
Kdo od naših tule?
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Poskušam, pa stran že pol ure ne dela. Vsaj od koder jo gledam.
Man muss immer generalisieren - Carl Jacobi
snow ::
[annoyed about nextpow2 mode]
Ja, jaz bom!
DD3 je hitrejši kot prazna zanka. Če bi imel možnost merjenje čistega samega algoritma bi dobil negativni čas. Dlje kot bi ga poganjal.. bolj v preteklost bi prišel. Valda je to jasno? :)
[/annoyed about nextpow2 mode]
Kr 0 milisekund dobijo pa trdijo kak hitro je vse skupaj? Hm.
Ja, jaz bom!
DD3 je hitrejši kot prazna zanka. Če bi imel možnost merjenje čistega samega algoritma bi dobil negativni čas. Dlje kot bi ga poganjal.. bolj v preteklost bi prišel. Valda je to jasno? :)
[/annoyed about nextpow2 mode]
Kr 0 milisekund dobijo pa trdijo kak hitro je vse skupaj? Hm.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Aja sej res, tiste 0 so bile men kar mirakolo. Mislil sem, da so nekako disableali algoritme, kateri jih niso toliko zanimali.
Ampak ja, naklopili so vse žive optimizacije, pa jim je compiler vse zmetal ven! RTMFLO! (al kako je že tista kratica?).
Ampak ja, naklopili so vse žive optimizacije, pa jim je compiler vse zmetal ven! RTMFLO! (al kako je že tista kratica?).
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Ampak ja, naklopili so vse žive optimizacije, pa jim je compiler vse zmetal ven!
Če bi res prevajalnik zmetal vse ven, potem bi bil rezultat pri vseh enak, glede na to, da sta input in outpout za vse enaka. Še najbolj po odstranitvi kliče prav NextPow2_Critticall, ki edina vrača konstanto (in hkrati ne sprejema kazalca, ali dela z globalnimi spremenljivkami), ampak se rezultat ne spremeni opazno, če vrača recimo x (ne trdim, da stvar tako postane nepredvidljiva, le po obnašanju enaka ostalim).
Aja sej res, tiste 0 so bile men kar mirakolo.
GetTickCount() ni ravno vrhunec natančnosti, niti niso rezultati povsem primerljivi, ker je odvisen od resolucije sistemske ure. Pri 1000 razlike po QueryPerformanceFrequency() bi moralo preteči 20 ms, torej je na mojem sistemu resolucija manj kot 20 ms.
Po eni strani je toliko govora o nepravilni metodologiji, po drugi strani pa se zadovoljimo z merjenjem časa s "kuhinjsko uro".
Še par opazk glede hitrosti. Upoštevati je potrebno dve stvari. Prva je predvidevanje vejenja. Glede na to, da n-ji naraščajo "zvezno" (kolikor je to mogoče za naravnaštevila) in da je potenc relativno malo, je stage vedno v enem od ektremov (bodisi 0, bodisi 3).
Poleg tega je Critticallov algoritem skorajda preveč preprost (od tod tudi moja trditev, da matematično najboljši algoritem ni nujno najboljši na stroju kjer se izvaja) za današnje procesorje, saj bi lahko postorili v enem ciklu več (še posebaj Athloni). Skoki namreč pogojujejo vzporedno obdelovanje ukazov z večimi dekoderji (vsak ima seveda tudi svoj cevovod) hkrati. Po drugi strani pa so "presežni" ukazi pri DD3 preprosti, poceni (seštevanje, prestavljanje bitov) in še neodvisni drug od drugega (mrcvarimo shift in x) ter tako veliko pridobijo z vzporednim obdelovanjem.
P.S. se mi samo zdi, ali je tvoja asm koda kanček napčna in bi moral biti label "gor" pred cmp ecx, 0?
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
Thomas ::
> se mi samo zdi, ali je tvoja asm koda kanček napčna in bi moral biti label "gor" pred cmp ecx, 0?
Samo zdi se ti. To je zaradi prve 0 v zanki, ko mora izračunana vrednost znašati 1.
> Če bi res prevajalnik zmetal vse ven, potem bi bil rezultat pri vseh enak
Tele agresivne optimizacije ... o tem sem že pisal kako in zakaj. Više.
Samo zdi se ti. To je zaradi prve 0 v zanki, ko mora izračunana vrednost znašati 1.
> Če bi res prevajalnik zmetal vse ven, potem bi bil rezultat pri vseh enak
Tele agresivne optimizacije ... o tem sem že pisal kako in zakaj. Više.
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Tele agresivne optimizacije ... o tem sem že pisal kako in zakaj. Više.
Res je, ampak ker nisi odgovoril katere ti niso povšeči, ko sem naštel, kaj sem uporabljal, sem sklepal, da se strinjaš z vsemi.
Niti ni zaslediti nobene dobre razlage, zakaj se čas izvajanja izmerljivo poveča (1045 proti 1449, zaokroženo na 1, povprečeno po petih zaporednih meritvah), če dopolnimo kodo NextPow2_DD3() z:
int tmp = x%shift; return bit[x] << shift + tmp;
Čeprav recimo, da bi slednje lahko pripisali tudi sistematičnim napakam.
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
Thomas ::
Compiler mora skrbeti za to in samo za to, da NAZADNJE pridejo dobre vrednosti iz zanke.
ČE se jih še potrebuje.
ZATO optimizacije mečejo precej ven. LAHKO bi pa še več, če bi znale.
Da optimizacija hitrosti ne gleda na nič drugega, kot na vrednost vseh spremenljivk po zadnjem dogodku v zanki in z zanko, je zato razumljivo.
ČE se jih še potrebuje.
ZATO optimizacije mečejo precej ven. LAHKO bi pa še več, če bi znale.
Da optimizacija hitrosti ne gleda na nič drugega, kot na vrednost vseh spremenljivk po zadnjem dogodku v zanki in z zanko, je zato razumljivo.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
> če dopolnimo kodo NextPow2_DD3() z
Zato, ker potem ne najde načina, kako vreči ven toliko kot prej, da bi se pa ta zadnji one poznal na izhodu.
Zato, ker potem ne najde načina, kako vreči ven toliko kot prej, da bi se pa ta zadnji one poznal na izhodu.
Man muss immer generalisieren - Carl Jacobi
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Najhitrejši programski jezik? (strani: 1 2 )Oddelek: Programiranje | 7766 (5586) | Senitel |
| » | Funkcija z logičnimi operaterji.... (strani: 1 2 )Oddelek: Programiranje | 5620 (4966) | CaqKa |
| » | Petaflopsu naproti (strani: 1 2 3 )Oddelek: Novice / Procesorji | 8911 (8911) | Marjan |
| » | cene permutacij help pleaseOddelek: Programiranje | 2081 (1688) | Sergio |
| » | kako definirtati prasteviloOddelek: Programiranje | 3805 (3610) | ooux |