<f...@N...gazeta.pl> napisał(a):
> swego czasu opisywalem jak to podmienienie literalnie czterech
> instancji floatow na inty przyspieszyla mi program 2 razy
Pamietam że pisałeś. Jednak Ty na floatach robiles troche jakis obliczen, a
ja robie tylko coś takiego:
tablica[ wybierz_adres() ] ++ ;
Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-04-01 15:07, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> W dniu 2012-04-01 13:58, M.M. pisze:
>>
>>>
>>> Raczej tak:
>>> double x[1000];
>>> for( i=0 ; i<1000000 ; i++ )
>>> x[rand()%size] ++;
>>>
>>> Na:
>>
>> tutaj jeszcze konwersja w drugą stronę.
>>
>>> int tmp[1000];
>>> for( i=0 ; i<1000000 ; i++ )
>>> tmp[rand()%size] ++;
>>>
>>> double x[1000];
>>> for( i=0 ; i<1000 ; i++ )
>>> x[i] = (double)tmp[i];
>>>
>>> Dłuższe obliczenia na intach i potem jedna konwersja na doubla.
>>> Problem w tym że obliczenia na intach są trywialne, tylko inkrementacja.
>>
>> I co Cię powstrzymuje przed odpaleniem tego z pomiarem czasu;)
>>
>> BTW, http://www.youtube.com/watch?v=gENVB6tjq_M
>>
>> Chcesz rozdać milion kulek w tysiąc otworków.
>> To tego wystarczy ~1000 losowań i tyle dodawań
>> (+ coś tego rzędu obliczeń związanych z rozkładem
>> Poissona), a pewnie da się i lepiej.
>>
>> Podpowiadać dalej?
>
> Chyba zakręciłem totalnie jaka jest istota problemu i nikt
> nie zrozumiał, sorry :D
>
> Chyba mogłem zapytać prościej: czy inkrementacja intów jest
> szybsza od inkrementacji doubli? Dane są wybierane w przybliżeniu
> z losowych adresow w pamięci, czyli nie chodzi o inkrementację jednej
> zmiennej ktora jest ciagle w rejestrze procesora. Tablice z danymi

Ależ rozumiem. Za to nie zrozumiałeś odpowiedzi:(

> mieszcza sie w L2, ale nie mieszcza sie w L1.


@pytanie o szybkość: Mówiłem, sprawdź.

int:1.682000 i2f:0.000000 double:1.766000 f2i:0.000000
int:1.688000 i2f:0.000000 double:1.794000 f2i:0.000000
int:1.696000 i2f:0.000000 double:1.773000 f2i:0.000000
int:1.691000 i2f:0.000000 double:1.765000 f2i:0.000000

W praktyce nie ma znaczenia. Przypadek sferyczniesymetryczny
sugeruj, że mozesz tak zyskać kilka %, ale w prawdziwym
programie niekoniecznie wyjdzie to na zdrowie.


A co do meritum, chcesz rozdać milion "+1" dla 1000 obiektów.
Dokładnie to robi Twój kod. Możesz to zrobić rząd lub dwa szybciej
używając 'matematyki' zamiast brutalnie siły. Teraz jasne?

pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> A co do meritum, chcesz rozdac milion "+1" dla 1000 obiektow.
> Dokladnie to robi Twoj kod. Mozesz to zrobic rzad lub dwa szybciej
> uzywajac 'matematyki' zamiast brutalnie sily. Teraz jasne?
No wlasnie to nie bylo meritum, to byl tylko program przykladowy.

W meritum chodzilo o to czy proste operacje arytmetyczne (jak
np. x = x + 1) na typie double sa istotnie wolniejsze niz na
typie int, albo long.

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-04-01 16:39, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> A co do meritum, chcesz rozdac milion "+1" dla 1000 obiektow.
>> Dokladnie to robi Twoj kod. Mozesz to zrobic rzad lub dwa szybciej
>> uzywajac 'matematyki' zamiast brutalnie sily. Teraz jasne?
> No wlasnie to nie bylo meritum, to byl tylko program przykladowy.

To nie dawaj złych przykładów;)


> W meritum chodzilo o to czy proste operacje arytmetyczne (jak
> np. x = x + 1) na typie double sa istotnie wolniejsze niz na
> typie int, albo long.

Wyciąłeś test odpowiadający na to pytanie.

pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> To nie dawaj złych przykładów ;)
Oryginalny przykład jest zbyt zagmatwany, chciałem uprościć jakoś :)

> > W meritum chodzilo o to czy proste operacje arytmetyczne (jak
> > np. x = x + 1) na typie double sa istotnie wolniejsze niz na
> > typie int, albo long.
>
> Wyciąłeś test odpowiadają…cy na to pytanie.
Nie wiem jak ten test należy czytać.
int:1.682000 i2f:0.000000 double:1.766000 f2i:0.000000
int:1.688000 i2f:0.000000 double:1.794000 f2i:0.000000
int:1.696000 i2f:0.000000 double:1.773000 f2i:0.000000
int:1.691000 i2f:0.000000 double:1.765000 f2i:0.000000

Czyżby pierwsza kolumna to czas inkrementacji na typie int,
a trzecia kolumna na typie double? To by sugerowało że
nie warto się bawić, bo jeszcze dochodzi czas pętli, indeksowania i
dostępu do pamięci.

Pozdrawiam i dzięki :)


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-04-01 18:06, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> To nie dawaj złych przykładów ;)
> Oryginalny przykład jest zbyt zagmatwany, chciałem uprościć jakoś :)
>
>>> W meritum chodzilo o to czy proste operacje arytmetyczne (jak
>>> np. x = x + 1) na typie double sa istotnie wolniejsze niz na
>>> typie int, albo long.
>>
>> Wyciąłeś test odpowiadają…cy na to pytanie.
> Nie wiem jak ten test należy czytać.
> int:1.682000 i2f:0.000000 double:1.766000 f2i:0.000000
> int:1.688000 i2f:0.000000 double:1.794000 f2i:0.000000
> int:1.696000 i2f:0.000000 double:1.773000 f2i:0.000000
> int:1.691000 i2f:0.000000 double:1.765000 f2i:0.000000
>
> Czyżby pierwsza kolumna to czas inkrementacji na typie int,
> a trzecia kolumna na typie double? To by sugerowało że

Tak.

> nie warto się bawić, bo jeszcze dochodzi czas pętli, indeksowania i
> dostępu do pamięci.

Nie, to czas całego kodu 'testowego'. Pętla, random etc.

Dokłądniej
start=clock();
for (int i=0;i<N;i++) Ti[rand()%M]++;
end = clock();

N jest, jak w Twoim przykładzie, 1000 razy większe niż M.
(dokładniej M=10000)

Czas rand() zasłania praktycznie różnice.

BTW,
wyrzucając random:
start=clock();
for (int i=0;i<N;i++) Ti[i%M]++;
end = clock();

Wyniki są znacznie mniejsze.
int:0.157000 i2f:0.000000 double:0.192000 f2i:0.000000

I mówię na serio. Jeśli w kodzie masz takie losowanko
'na którym klocku zrobić operację', średnio operacji
na klocek jest dużo i są nieżależne, to nie rób tego
w ten sposób. wygwenerpowanie 1000 liczb z penwgo rozkładu,
aby z góry wiedzieć, ile operacji wykonać jest znacznie
szybsze niż milion prostych randomów.


pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> W dniu 2012-04-01 18:06, M.M. pisze:
> > bartekltg<b...@g...com> napisał(a):
> >
> >> To nie dawaj złych przykładów ;)
> > Oryginalny przykład jest zbyt zagmatwany, chciałem uprościć jakoś :)
> >
> >>> W meritum chodzilo o to czy proste operacje arytmetyczne (jak
> >>> np. x = x + 1) na typie double sa istotnie wolniejsze niz na
> >>> typie int, albo long.
> >>
> >> Wyciąłeś test odpowiadają…cy na to pytanie.
> > Nie wiem jak ten test należy czytać.
> > int:1.682000 i2f:0.000000 double:1.766000 f2i:0.000000
> > int:1.688000 i2f:0.000000 double:1.794000 f2i:0.000000
> > int:1.696000 i2f:0.000000 double:1.773000 f2i:0.000000
> > int:1.691000 i2f:0.000000 double:1.765000 f2i:0.000000
> >
> > CzyĹźby pierwsza kolumna to czas inkrementacji na typie int,
> > a trzecia kolumna na typie double? To by sugerowało że
>
> Tak.
>
> > nie warto się bawić, bo jeszcze dochodzi czas pętli, indeksowania i
> > dostępu do pamięci.
>
> Nie, to czas całego kodu 'testowego'. Pętla, random etc.
Ok, czyli sie nie oplaca. Wyglada na to ze dzisiejsze procesory
robia inkrementacje na typie double prawie tak samo szybko jak
na typie int. Moj kod pomiarowy na dole.


> I mówię na serio. Jeśli w kodzie masz takie losowanko
> 'na którym klocku zrobić operację', średnio operacji
> na klocek jest dużo i są nieżależne, to nie rób tego
> w ten sposób. wygwenerpowanie 1000 liczb z penwgo rozkładu,
> aby z góry wiedzieć, ile operacji wykonać jest znacznie
> szybsze niż milion prostych randomów.
Zgadza się.

W oryginalnym kodzie mam coś innego. Mam dane zero-jedynkowe i buduję z nich
układ równań normalnych. Dane mam upakowane. Upakowanie polega
na tym że zamiast zer i jedynek trzymam numery pozycji na których
są jedynki. Dane są trudne, mają znamiona funkcji losowej, dlatego
w przykładzie dałem rand. Mniej/więcej coś takiego:

for( int i=0 ; i<N ; i++ )
for( int j=i ; j<N ; j++ )
macierz[ jedynki[i] * rozmiar_wiersza + jedynki[j] ] ++;

Pozdrawiam



Kod pomiarowy:

#include <cstdio>
#include <cstdlib>
#include <ctime>

#define BASE_SIZE (1000)
#define BASE_ITS (200000000)

int test_int() {
static int data[BASE_SIZE];
for( int i=0 ; i<BASE_ITS ; i++ )
data[rand()%BASE_SIZE] ++ ;
int max = 0;
for( int i=0 ; i<BASE_SIZE ; i++ )
if( max < data[i] )
max = data[i];
return max;
}

double test_double() {
static double data[BASE_SIZE];
for( int i=0 ; i<BASE_ITS ; i++ )
data[rand()%BASE_SIZE] ++ ;
double max = 0;
for( int i=0 ; i<BASE_SIZE ; i++ )
if( max < data[i] )
max = data[i];
return max;
}


int main(int argc, char *argv[]) {
clockid_t start;
srand(123);

start = clock();
int max_i = test_int();
printf("max = %d test int = %d\n" , max_i ,
(int)((clock()-start)/(CLOCKS_PER_SEC/1000)) );

start = clock();
double max_d = test_double();
printf("max = %lf test double = %d\n", (double)max_d,
(int)((clock()-start)/(CLOCKS_PER_SEC/1000)) );

return 0;
}


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-04-01 13:58, M.M. pisze:

> double x[1000];
> for( i=0 ; i<1000000 ; i++ )
> x[rand()%size] ++;

M=1000;
N=1000000;

Załóżmy, że naprawdę chcemy zrobić coś takiego.

do x[i] dodajemy liczbę z rozkładu dwumianowego
B(N,M/N); tyle, że nie są one niezależne.

Mając dobry generator liczb z rozkładu dwumianowego
można napisać:

n = N; //ile kulek jeszcze zostało.
for( i=0 ; i<M ; i++ )
{
int k = generuj_liczbę_losową_B ( n, 1.0/(M-i) );
x[i]+=k;
n-=k;
}

W każdym obrocie pętli kulki mogą wpaść (każda z prawdopodobieństwem
1/długość tablicy) w pierwszy element. Liczymy, ile wpadło,
pozostałe idą dalej, sytuację powtarzamy dla krótszej tablicy.
W ostatnim ruchu prawdopodobieństwo =1, wszystkie pozostałe kulki
lądują w ostatniej szufladce.


Równoważność z kodem MM zapewnia nam ta własność
http://en.wikipedia.org/wiki/Binomial_distribution#C
onditional_binomials


Napisanie... wygoglanie generatora rozkąłdu dwumianowego moze okazać
się męczące. Ale B(n,p) -> N(n*p,m*p*(1-p)) a generator rozkładu
normlanego każdy umie. Ważne jest aby spełnione były warunki
zbieżności rozkładów, poprzedni kod jest do tego celu zły.

n jest duże, rzędu 1000 na szufladkę. Wypadałoby urzymać
p w okolicach 0.5.

Dzielmy więc tablicę na dwie równe części, przydzielając im
wynikającą z rozkładu liczbe kulek.


krok(int tab[], int first;int last, int n )
{
if (first==last)
{
tab[first]+=n;
}else
{
podział = (first + last)/2;
int k = generuj_liczbę_losową_B ( n, ((double)
(podzial-first+1))/(last - first+1) );
// ile kulek w pierwszy podział
krok(tab,first,podzial,k);
krok(tab,podzial+1,last ,n-k);
}
}

Tutaj wyniki będą 'w miarę' nawet jeśli generator będzie
generatorem rozkładu normlanego z zaokrągleniem i obcięciem
brzegów.
powinno się tez w miare przyzwoicie równoległość (na drugim
poziomie podziału puścić w nowych wątkach).

pzdr
bartekltg

do góry

W dniu 2012-04-01 19:37, M.M. pisze:

> W oryginalnym kodzie mam coś innego. Mam dane zero-jedynkowe i buduję z nich
> układ równań normalnych. Dane mam upakowane. Upakowanie polega
> na tym że zamiast zer i jedynek trzymam numery pozycji na których
> są jedynki. Dane są trudne, mają znamiona funkcji losowej, dlatego

Jedna ze standardowych metod zapisu macierzy rzadkich,
dość rozsądnie.

> w przykładzie dałem rand. Mniej/więcej coś takiego:

Ale te indeksy jedynek trzymasz chyba posortowane
po długiej wspołrzednej dla każej 'krótkiej' osobno?

> for( int i=0 ; i<N ; i++ )
> for( int j=i ; j<N ; j++ )
> macierz[ jedynki[i] * rozmiar_wiersza + jedynki[j] ] ++;


'Macierz' to już ta X^t X?
Oznaczenia
http://en.wikipedia.org/wiki/Numerical_methods_for_l
inear_least_squares#The_general_problem


A skompresowane za pomocą indeksów jest samo X?

Coś tu jest nie tak;)

pzdr
bartekltg

do góry

<f...@N...gazeta.pl> napisał(a):

> <f...@N...gazeta.pl> napisał(a):
>
> > =?ISO-8859-2?Q?_genera=B3_kenobi?= <f...@W...gazeta.pl> napisał(a):
> >
> > > ten sposob rysowania rotowanej bitmapy jest fenomenalny
> > > swoja prostota
> > >
> > > for(int j=0; j<sprite_height; j++)
> > > {
> > > for(int i=0; i<sprite_width; i++)
> > > {
> > > SetPixel( x>>20, y>>20, sprite[j][i] );
> > >
> > > x += dxdx; // skosy/ poprawki dla ruchu pixele na fiz ekranie
> > > y += dydx; // dla ruchu po tekselach x++
> > > }
> > >
> > > x += dxdy; // skosy dla y++
> > > y += dydy;
> > > }
> > >
> > > tu raczej nie da sie nic poprawic - ale chcialbym jakos moze
> > > poprawic sama funkcje stawiania pixela
> > >
> > > inline void SetPixelInDibInt(int x, int y, unsigned color)
> > > {
> > >
> > > int yc = CLIENT_Y-y;
> > >
> > >
> > > if(!pBits) return;
> > >
> > > if(yc<0) return;
> > > if(yc>=CLIENT_Y) return;
> > >
> > > if(x<0) return;
> > > if(x>=CLIENT_X) return;
> > >
> > >
> > > int adr = (yc*CLIENT_X+x);
> > >
> > > ((unsigned*)pBits)[adr] = color;
> > >
> > > }
> > >
> > > mam tutaj cala mase warunkow, zabezpieczajacych wprost przed
> > > postawieniem pixela poza pamiecia ekranu - samo filtrowanie
> > > sprite'ow robie bardzo zgrubne (odrzucam sprity o srodku iles tam
> > > dalej poza ekranem ) tak ze przez to przechodzi cala masa
> > > pixeli ze sprite'ow ktore sa tylko czesciowo w ekranie --
> > >
> > > jak przerobic kod tej funkcji by bylo szybciej?
> > >
> > wychodzi na to ze wlasnie nalezaloby odwrocic proces - o ile
> > teraz jake po calej tekturze (a duza tekstura w prog2.exe ma 1000x1000
> > pixeli ) i czestokroc wypadam poza ekran to po obroceniu mozna
> > iterowac bez problemu po obruconej teksturze tylko w tym kawalku
> > ktory lezy w ekranie - tak ze to mogloby nawet przyspieszyc
> >
> > (choc sa dodatkowe koszty albo zapisywania tych krawedzi dla sylwetki
> > albo iterowania po wiekszych kwadratach) - tak ze zarazem moze
przyspieszyc
> > jak i moze zwolnic
> >
>
> troche sie zmeczylem ale wieczorem moze sprobuje (z ciekawosci czy
> przyspieszy) uruchomic prostrsza wersji z odwrotna transformacja
> (tj bez sylwetek)
>
>

napisalem

int from_x = max( min(xAfiz,xBfiz,xCfiz,xDfiz), 0);
int to_x = min( max(xAfiz,xBfiz,xCfiz,xDfiz), CLIENT_X);
int from_y = max( min(yAfiz,yBfiz,yCfiz,yDfiz), 0);
int to_y = min( max(yAfiz,yBfiz,yCfiz,yDfiz), CLIENT_Y);


for(int j=from_y; j<to_y; j++)
{
int fy = j - yAfizInt;

int dxdy_fy = dxdy_ * fy;
int dydy_fy = dydy_ * fy;

for(int i=from_x; i<to_x; i++)
{
int fx = i - xAfizInt;

int logX = ( dxdx_ * fx - dxdy_fy)>>20;
int logY = (-dydx_ * fx + dydy_fy)>>20;

if( logY<0 || logY>=sprite_height || logX<0 ||
logX>=sprite_width );
else
{
unsigned color = sprites_buf_[sprite_bitmap_posy + logY]
[sprite_bitmap_posx + logX];

if(!color==0)
((unsigned*)pBits)[((CLIENT_Y-1-j)*CLIENT_X+i)] = color;

}

}

}


zniknely artefakty (choc one bywaly fajne jak kropki w druku
gazetowym ) i cholerstwo jeszcze troche przyspieszylo - przyspiesza na
wyraznych przypadkach clippingu bo w tę strone jest automatyczny i nie
stawia sie ani nawet jednego pixela poza ekranem,
moglbym jeszcze zrobic te sylwetki i przepisac petle z mnoznej na
dodawczą ale to moze kiedy indziej

martwi mnie teraz inna rzecz - plynnosc jest slaba bo czasy ramek
oscylują jak szum, przy tym nie mam pewnosci czy plynnosc przestrzenna
jest ok - tj np czy obracaniu nie kwantyzuje malych roznic miedzy katami
obrotu - trzebaby sie przyjrzec kodu - ale to tez ew raczej kiedy indziej
- dziala tylko rwie (nie jest oleiscie plynnie)




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry