Optimizarea programelor folosind operaţii pe biţi

[•Marius]

Comentarii la articolul Optimizarea programelor folosind operaţii pe biţi scris de Cosmin Negruşeri. Îi mulţumim lui Mihai Gheorghe pentru transcrierea acestuia pe site.   

[•Mishu91]

La algoritmul care numără biții unui număr cred că trebuie să faci un do-while sau să începi numărătoarea de la 1, pentru că va returna numărul de biți-1. De exemplu, pentru 2, el când face 2&1 = 0, iese și nu mai incrementează rezultatul.

[•blasterz]

sau returnezi num + 1

[•Marius]

La algoritmul care numără biții unui număr cred că trebuie să faci un do-while sau să începi numărătoarea de la 1, pentru că va returna numărul de biți-1. De exemplu, pentru 2, el când face 2&1 = 0, iese și nu mai incrementează rezultatul.

Mulţumim de observaţie. Eu unul aş anunţa pe forum greşeala şi aş modifica articolul corespunzător. Doar e wiki.

[•alexandru92]

N-ar strica prezentarea  caluclarii minimului si maximului folosind operatii pe bits.

Cod:

inline int min( int x, int y )
{
     return y^( (x^y) & - ( x<y) );
}
inline int max( int x, int )
{
      return x^( (x^y) & -(x<y) );
}

Sa luam y^( (x^y) & -(x<y) );
Daca x < y atunci y^( x^y ) & -0 = y^x^y=x.
Altfel y^( ( x^y) & 0 )=y.

[•blasterz]

Si de ce ai folosi functiile alea de minim / maxim  daca sunt mai lente decat cele normale?
Unde e optimizarea?

Cod:

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


inline int min(int x, int y)
{
return y ^ (( x ^ y) & - (x < y) );
}

inline int min2(int x, int y)
{
if(x < y) return x;
return y;
}

int main()
{
srand(time(0));

double start, end;

start = clock();

int i, n = 20000, j,s = 0;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
s += min(i, j);

printf("%d\n", s);

end = clock();

printf("Time minim: %lf\n", (end - start) /(double)CLOCKS_PER_SEC);


start = clock();

s = 0;

for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
s += min2(i, j);
printf("%d\n", s);

end = clock();

printf("Time minim normal: %lf\n", (end - start) / (double) CLOCKS_PER_SEC);
return 0;
}

[•alexandru92]

La mine is mai rapizi decat algoritmul obisnuit

[•blasterz]

Pai probabil ca nu stii sa testezi calumea  
Testeaza cu sursa mea de mai sus.

[•alexandru92]

Pai probabil ca nu stii sa testezi calumea  
Testeaza cu sursa mea de mai sus.

Am verificat sub linux.  Folosind time din bash

[•blasterz]

Si? (PS. si eu tot pe linux)

Posteaza codul folosit la testare...

[•Mishu91]

La algoritmul care numără biții unui număr cred că trebuie să faci un do-while sau să începi numărătoarea de la 1, pentru că va returna numărul de biți-1. De exemplu, pentru 2, el când face 2&1 = 0, iese și nu mai incrementează rezultatul.

Mulţumim de observaţie. Eu unul aş anunţa pe forum greşeala şi aş modifica articolul corespunzător. Doar e wiki.

Acuma văzui că pot modifica și eu.
Totuși, această facilitate cred că ar trebui eliminată, ca să nu modifice fiecare cum îl taie capul, indiferent dacă este corect sau nu.

[•alexandru92]

Si? (PS. si eu tot pe linux)
Posteaza codul folosit la testare...

Cod:

#include <cstdio>

/*
 *
 */
using namespace std;
inline unsigned int min( unsigned int x, unsigned int y )
{
    if( x < y )
       return x;
    return y;
}
int main()
{
  unsigned int i, j, n=2000000, m=0;
  for( i=0, j=n; i <= n; ++i, --j )
      m+=min( i, j  );
  printf( "%u", m );
  return 0;
}

[•blasterz]

Pai am marit n-ul la 200 000 000 si se simte diferenta... metoda normala ia 0.328 sec iar metoda pe biti 0.578.
:-" Ti-am zis ca nu stii sa testezi.

Si chiar si cu n = 2 000 000
metoda ta ia 0.013 iar cea clasica 0.008.

Testat cu time pe linux

[•wefgef]

La algoritmul care numără biții unui număr cred că trebuie să faci un do-while sau să începi numărătoarea de la 1, pentru că va returna numărul de biți-1. De exemplu, pentru 2, el când face 2&1 = 0, iese și nu mai incrementează rezultatul.

Mulţumim de observaţie. Eu unul aş anunţa pe forum greşeala şi aş modifica articolul corespunzător. Doar e wiki.

Acuma văzui că pot modifica și eu.
Totuși, această facilitate cred că ar trebui eliminată, ca să nu modifice fiecare cum îl taie capul, indiferent dacă este corect sau nu.

Pai tocmai asta e ideea la wiki, sa poata modifica oricine, orice. Daca se observa ca a modificat prost, se poate reveni la orice versiune anterioara a paginii.

[•nash]

Uite aici se vede optimizarea Mircea, tu nu faci testarea cum trebuie... rezultatele pe care le ai tu acolo sunt datorate modului in care face compilatorul optimizarile... practic tu ai o secventa constanta... procesorul stie sa optimizeze secventele astea... si rezultatul este acela pe care il vezi... eu am adaugat un vector de elemente pentru minimuri... facut radom... rezultatele sunt :

The Debugger has exited with status 0.
[Session started at 2010-02-11 08:40:33 +0200.]
-1367706278
Time minim: 4.436630
-1367706278
Time minim normal: 5.624118


Practic ar merge mai repede sa faci min/max si daca le-ai face prin adunari si scaderi (ex: min(a,b) = (a+b - abs(a-b) )/2 ) pentru ca if-ul spage intr-un fel secventa de cod... si face niste sarituri la nivel de asamblare in contrast cu metodele aratate ( pe biti, ce am zis eu etc. ) care se sparg in secvente de instructiuni succesive fara salturi... asta e si motivul pentru care merge mai repede ce face acolo pe biti...

Cod:

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


inline int min(int x, int y)
{
return y ^ (( x ^ y) & - (x < y) );
}

inline int min2(int x, int y)
{
if(x < y) return x;
return y;
}

int vec[20001];

int main()
{
srand(time(0));

double start, end;


int i, n = 20000, j,s = 0;

for(int i = 1 ; i <= n ; i++ )
vec[i] = rand();

start = clock();

for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
s += min(vec[i], vec[j]);

printf("%d\n", s);

end = clock();

printf("Time minim: %lf\n", (end - start) /(double)CLOCKS_PER_SEC);


start = clock();

s = 0;

for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
s += min2(vec[i], vec[j]);
printf("%d\n", s);

end = clock();

printf("Time minim normal: %lf\n", (end - start) / (double) CLOCKS_PER_SEC);
return 0;
}

[Editat de moderator]Foloseste tagul [ code ][ /code ] cand postezi secvente de cod.

[•blasterz]

Si la tine e sir constant (practic accesezi aceeasi indici in aceeasi ordine). Si in plus nu spargi cache-ul...de unde stii ca, compilatorul nu optimizeaza mai bine operatiile pe biti cand nu se sparge cache-ul ?

Uite, eu am facut asa: am declarat un vector int vec[100 000 001]; adica 400 MB. si ii dau min(a[rand() % nr + 1], a[rand() % nr +1]) . Nu este nici sir constant (ii dau srand(time(0)).

Diferite rulari:

-1368030597
Time minim: 3.600000
-282026249
Time minim normal: 3.570000


163207845
Time minim: 3.570000
-1876227552
Time minim normal: 3.380000


1921398278
Time minim: 3.500000
-1700755686
Time minim normal: 3.800000


605368241
Time minim: 4.180000
842137942
Time minim normal: 4.080000

Cod:

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


inline int min(int x, int y)
{
   return y ^ (( x ^ y) & - (x < y) );
}

inline int min2(int x, int y)
{
   if(x < y) return x;
   return y;
}

int vec[100000001];

int main()
{
   srand(time(0));
   
   double start, end;
   
     
   int i, n = 5000, j,s = 0, nr = 100000000;

   
   for(i = 1; i <= nr; ++i)
   vec[i] = rand();

   start = clock();
   for(i = 1; i <= 10000000 ; ++i)
s += min( vec[rand() % nr + 1], vec[rand() % nr + 1]);
   
   printf("%d\n", s);
 

 
   end = clock();
   
   printf("Time minim: %lf\n", (end - start) /(double)CLOCKS_PER_SEC);
   
   
   start = clock();
   
   s = 0;
   
   for(i = 1; i <= 10000000 ; ++i)
s += min2( vec[rand() % nr + 1], vec[ rand() % nr + 1]);
         
   printf("%d\n", s);
   
   end = clock();
   
   printf("Time minim normal: %lf\n", (end - start) / (double) CLOCKS_PER_SEC);
   return 0;
}

[•nash]

   Nu, la mine nu este sir constant pentru ca secventa de operatii nu va fi mereu aceasi cand repornesti programul pentru ca automat nu sunt aceleasi numere cum erau la tine fiind indici de doua for-uri... Toata secventa aia era constnta. ( secventa de instructiuni era constanta ). La mine la fiecare pornire de program era alta si atunci compilatorul nu facea nici o optimizare pentru ca vedea ca nu se poate si ai vazut diferentele .
   In al doilea rand eu nu vb de cache... ci de o chestie mult mai simpla... if-ul este implementat ca o secventa de "goto" la nivel de asamblare ( nu ma intreba de unde stiu asta... citesti/verifici/te informezi si vezi si tu daca nu sti asamblare ) si face operatie de salt. Practic cand se translateaza apoi in cod masina in secventa de 0010101... o sa apara o saritura care face sa mai treaca un timp.
  Sincer nu stiu ce sa zic despre datele tale... tind sa cred ca esti carcotasi


The Debugger has exited with status 0.
[Session started at 2010-02-12 01:58:14 +0200.]
-1905502094
Time minim: 2.019822
-607096570
Time minim normal: 2.179637

The Debugger has exited with status 0.
[Session started at 2010-02-12 01:58:27 +0200.]
183067316
Time minim: 1.998376
-546390122
Time minim normal: 2.137789

The Debugger has exited with status 0.
[Session started at 2010-02-12 01:58:41 +0200.]
-601500509
Time minim: 1.992697
1901982635
Time minim normal: 2.135167

The Debugger has exited with status 0.
[Session started at 2010-02-12 01:59:04 +0200.]
1385362508
Time minim: 1.999421
-1248609482
Time minim normal: 2.137639

The Debugger has exited with status 0.
[Session started at 2010-02-12 01:59:18 +0200.]
920421738
Time minim: 1.987323
856807656
Time minim normal: 2.125442

The Debugger has exited with status 0.

( testele sunt facute exact pe sursa malale de mai sus ... daca vrei sa evidentieti diferentele si mai bine maresc numarul de teste )

( pentru dublu numar de calcul de minimuri )

The Debugger has exited with status 0.
[Session started at 2010-02-12 02:10:36 +0200.]
-2006889069
Time minim: 4.066287
849834287
Time minim normal: 4.247599

The Debugger has exited with status 0.
[Session started at 2010-02-12 02:10:58 +0200.]
812755062
Time minim: 3.995999
1018319365
Time minim normal: 4.268772

The Debugger has exited with status 0.
[Session started at 2010-02-12 02:11:10 +0200.]
1922056890
Time minim: 3.992492
1852173117
Time minim normal: 4.265673

The Debugger has exited with status 0.
[Session started at 2010-02-12 02:11:25 +0200.]
548556780
Time minim: 4.034963
1186260194
Time minim normal: 4.262402

The Debugger has exited with status 0.
[Session started at 2010-02-12 02:11:38 +0200.]
1705988173
Time minim: 3.987084
552722841
Time minim normal: 4.251289

The Debugger has exited with status 0.

[•blasterz]

De ce folosesti Debugger-ul ? "The Debugger has exited with status 0."

Am dublat si eu numarul la 20000000. De data asta am testat pe un computer sub Windows XP pe MingW.  (data trecuta pe laptop in Ubuntu):

-335291704
Time minim: 2.906000
-271732366
Time minim normal: 2.579000

Nu stiu... ma gandesc ca depinde si de platforma, si de procesor... (stiu ca tu ai mac).

Deci pe bune...asa imi arata...

pe linux am incercat sa compilez in 4 moduri distincte, si da acelasi rezultat (adica minim normal mai mic)

g++ -O2 -o x sursa.cpp //g++ 4.3
g++ -o x sursa.cpp
g++-4.2 -O2 -o x sursa.cpp
g++-4.2 -lm -static -Wall -fopenmp -pthread -O2 -o x sursa.cpp

Cel mai mare impact il are cand compilez cu  g++ -O2 -lm -static -o x sursa.cpp (diferente mai mari de o secunda intre ele)



Spune-mi cum compilezi tu...



Iar tu cand faci for-urile alea in sursa ta,

 for i = 1 la n  
    for j = 1 la n


tu practic calculezi min( a[ i ], a[ j ] ) si min( a[ j ], a[ i ] )... la asta ma refeream ca e constant...

Eu nu cred ca 5 operatii pe biti sunt mai rapide decat un jump...

Uite o poza:
http://sandbox.blasterz.net/test.JPG

Si pe linux :

http://sandbox.blasterz.net/Screenshot-1.png

[•blasterz]

Deci... in alta ordine de idei: (da stiu... nu e bine sa postez consecutiv...dar am obosit sa tot dau "modifica")

Pe noi ne intereseaza daca una din cele 2 functii scrise in C++ (nu in asm sau altceva) optimizeaza cu ceva, in special la olimpiade si concursuri...
Raspuns: NU ... nu conteaza pe care le folositi... depinde cum optimizeaza compilatorul, cum se compileaza (daca se compileaza cu -lm -static, cum e la olimpiade si concursuri, se simte diferenta...in anumite cazuri).

Pentru programatori in general... conteaza atunci cand se doreste optimizarea la sange... si cred ca e important sa studiezi care e mai buna din variante... nu cred ca e vreuna din ele strict mai buna.

Eu m-am plictisit de topicul asta...care oricum nu are prea multa importanta.

[•manciu_ion]

 
buna! va scrie un pasionat de informatica din R.Moldova.
M-am apucat de informatica la 27 de ani si acum sunt student (am 29 de ani) la Universitatea Tehnica din Moldova. Referitor la articolul "operatii pe biti... ciurul lui Eratostene"- care de ltfel e un articol destul de interesant! Daca nu gresesc asi vrea sa fac unele corectii ale codului, si anume:
#define maxsize 10000000
02.
03.char at[maxsize / 16];
04.int n;
05.
06.int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 0 ;
09.else return 1 ;
10.else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;
11.}
12.
13.void sieve() {
14.int i, j;
15.memset(at, 0, sizeof(at)) ;
16.for (i = 3; i <= maxsize; i += 2)
17.if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
18.for (j = i * i ; j <= maxsize ; j += i + i)
19.at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;
20.}

in sectiunea 17 in loc de if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
ar trebui de scris if (!(at[((i - 3) >> 1) >> 3] & (1 << (((i - 3) >> 1) & 7))))
sau chiar if 17.if (!(at[i  >> 4] & (1 << ((i  >> 1) & 7))))
astfel evitându-se scăderea repetată (x-3) dar cu prețul pierderii primilor trei biți din primul octet
al char-ului at[], astfel fiind necesar de a rezerva cu un octet mai multă memorie decât este necesar.
A doua observație ar fi ca în secțiunea   19.at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;
la fel aceiași observație , plus că în loc de i trebuie să fie j, adică:
19.at[((j-3) >> 1) >> 3] |= (1 << (((j - 3) >> 1) & 7))) ;
sau cum am mai spus mai sus :19.if (!(at[j  >> 4] & (1 << ((j  >> 1) & 7))))
O a treia observație ar fi cea din funcția :
int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 0 ;
09.else return 1 ;
10.else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;
11.}
și anume :
int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 1 ;
09.else return 0 ;
10.else return ( ! (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) );
11.}

Codul final ar fi:
#include <stdio.h>
#include <memory.h>
#include <conio.h>

#define maxsize 30000

char sita[maxsize / 16 + 1];
int n;

int isPrime(int );
void sieve();

int main()
{
     clrscr();
     sieve();
     printf("\n n= "); scanf("%d", &n);
     for (int i=3; i <= n; i+=2)
   if (isPrime(i)) printf("%d este prim\n", i);
      else printf("%d nu este prim\n", i);
    getch();
    return 0;
}

int isPrime(int x)
{
    if (x <= 1) return 0;
    if (!(x & 1))
       if (x == 2) return 1;
     else     return 0;
       else return ( !(sita[x >> 4] & (1 << ((x >> 1) & 7))) );
}

void sieve()
{
   int i, j;
   memset(sita, 0, sizeof(sita));
   for (i=3; i * i <= maxsize; i+=2)
      if ( !(sita[i >> 4] & (1 << ((i >> 1) & 7))) )
    for (j=i * i; j <= maxsize; j+=i + i)
         sita[j >> 4] |= (1 << ((j >> 1) & 7));
}

De altfel ași vrea să vă mulțumesc pentru acest articol și pentru multe altele, de fapt faceți o treabă foarte bună. Am analizat acestă sursă o zi întreagă și credeți-mă că am avut ce învăța, mai ales subtilitățile -  for (j=i * i; j <= maxsize; j+=i + i). Mult succes în continuare!