Optymalizacja operacji arytmetycznych

Nie raz juz na forum spotkalem sie z pewnymi niejanosciami jesli chodzi o zastepowanie pewnych operacji arytmetycznych operacjami bitowymi dlatego postaram sie to tutaj krotko wyjasnic kiedy je mozna stosowac:

zapis 2^x jakby ktos nie wiedzial jest to nic innego jak 2 do potegi x

Ponizsze dzialania mozna stosowac wylacznie dla liczb dodatnich

1. Mnozenie(*) i dzielenie(/)

a) dzialanie a * b mozna zastapic poprzez szybsza operacje przesuniecia bitowego w lewo: a << x jezeli b = 2^x.
Wiadomo ze mnozenie jest przemienne takze jezeli a = 2^x dzialanie mozna zastapic przez: b << x
Przykladowo:

w = a * 32; 

poniewaz liczbe 32 mozna zapisac jako 2^5 powyzsza operacje mozna zapisac uzywajac operacji bitowej <<:

w = a << 5; 

b) dzialanie a / b mozna zastapic poprzez szybsza operacje przesuniecia bitowego w prawo: a >> x jezeli b = 2^x
Przykladowo:

w = a / 8; 

poniewaz liczbe 8 mozna zapisac jako 2^3 powyzsza operacje mozna zapisac uzywajac operacji bitowej >>:

w = a >> 3; 

2. Operacja modulo(%)
dzialanie a % b mozna zastapic przez operacje bitowa AND: a & (b-1) jezeli b = 2^x
Przykladowo:

w = a % 4; 

poniewaz 4 mozna zapisac jako 2^2 powyzsze dzialanie mozna zapisac uzywajac operacji bitowej &:

w = a & 2; 

Na koniec moze nie dzialanie arytmetyczne ale znana kazdemu a jak nie na pewno sie przyda optymalizacja tzw. operacji swap z pol. zamiana uzywajac operacji bitowej XOR(^)
zamiast:
w C:

void swap(int *a, int *b)
{
int x = *a;
*a = *b;
*b = x;
}

w C++:

void swap(int &a, int &b)
{
int x = a;
a = b;
b = x;
}

mozna to wykonac bez dodatkowej zmiennej uzywajac wlasciwosci operatora XOR:
w C:

void swap(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

w C++:

void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}

Kategoria: FAQ

Ostatnia modyfikacja	05-09-2007 17:06	Ostatni autor	tilius
Ilość wyświetleń	4358	Wersja	2

lmmilewski dnia 08-09-2007 14:07

Pewnie się ze mną część osób nie zgodzi ale... to jest jakiś bełkot. Od takiego "optymalizowania" należy się trzymać z daleka. Zmniejsza to czytelność kodu i zwiększa podatność na błędy, utrudnia rozbudowę, nie wyraża wprost tego co chcemy aby było wykonane (przez co kompilator nie może optymalizować)..... Takie "triki" robią początkujący (nie wiem po co - pamiętam, że też tak pisałem).

Przestałem gdy mój qsort nie chciał działać przez zastosowanie super metody z xor. Problem w tym, że jeżeli a == b ; to taka operacja wcale nie zamienia miejscami tych wartości!!
Wtedy też testowałem efektywność i wyszło na to, że motyw z operacją xor jest dużo wolniejszy.

Co do innych metod: klasyczne (a + b) >> 1; Ile razy autor pomylił się pisząc (a+b)>>2; ?? co ciekawe to zadziała (tylko) dla liczb dodatnich (sic!). Co jeszcze ciekawsze kompilator sam to ( (a+b) / 2 ) zoptymalizuje o ile będzie miał pewność, że wynik jest ok (nie ma głupot z liczbami ujemnymi).

Pytanie: co robi ta funkcja:
void foo(int& x, int& y) {
   x = x + y;
   y = x - y;
   x = x - y;
}

Ciekawe ile osób (nieznających wcześniej tej głupoty jaką jest foo) od razu widzi co foo robi.
Myślę, że autor właśnie napisał jak _nie_ należy programować.
Warto to zaznaczyć.

fr3 dnia 05-09-2007 20:53

>Ponizsze dzialania mozna stosowac wylacznie dla liczb dodatnich
Miałeś chyba na myśli liczby całkowite - zapewniam cię że na ujemnych też można.

Powyższe optymalizacje (mnozenie, dzielenie, modulo) mają sens TYLKO jeśli b jest zmienne i kompilator nie może w żaden sposób wydedukować, że and będzie działać.
Aczkolwiek wtedy kod traci na czytelności... nie widzę zastosowania takich mikrooptymalizacji, ew. w jednej najczęściej wykonywanej pętli w całym programie... (ale to i tak tak dużo na zmieni, na dzisiejszych prockach...)

Modulo - tam chyba miało być a & 3 ...

Swap - wersja z xorem będzie zazwyczaj wolniejsza - optymalizacje tego typu najlepiej zostawić kompilatorowi.

Wbrew pozorom (?) największy wpływ na szybkość programu (poza nielicznymi wyjątkami - jakieś aplikacje numeryczne) ma fragmentacja pamięci (wykorzystanie cache) a nie powolność dzielenia.

necrokris dnia 07-11-2005 18:04

http://www.borland.pl/tech/optymalizacja_wydajnosci.shtml - tu macie cos podobnego, tylko dla delphi.

Spine dnia 07-11-2005 12:50

no, ale jeśli chcesz aby kod był mniej czytelny to powinno się tak pisać

a tak na serio to RESPEKT

mi się ta wskazówka podoba

Maker dnia 31-10-2005 11:41

wolverine pisalem to okolo 2 w nocy mala pomylka ale zaraz to poprawie foflik ten FAQ nie mial rozwazac nad tym czy to bedzie zawsze szybsze ale gdyby tak bylo jak mowisz juz w wiekszosci zrodel tych operacji nikt by nie zastepowal lecz nadal tak robia poniewaz tutaj nie masz pewnosci jaki kompilator Tobie te operacje zoptymalizuje a nikt nie bedzie wertkowal manuali poza tym jestem ciekaw jak w petli liczba bedzie zmieniala swoje wartosci i akurat beda to wartosci 2^n to czy kompilator tez bedzie wiedzial ze mozna dzialanie arytmentyczne przez to liczbe zoptymalizowac

a FAQ ma byc tylko wskazowka kiedy mozna je zastepowac i wszystko.
Co do operacji % i & tak tutaj foflik ma racje ale to nie tylko te operacje bitowego przesuniecia rowniez zapomnialem po prostu nadmienic ale dla liczb ujemnych nie mozna tego zastosowac po prostu wyniki zawsze beda sie roznily

Wolverine dnia 31-10-2005 10:16

poniewaz 2 mozna zapisac jako 2^2

serio?

foflik dnia 31-10-2005 07:48

Szybsze to to znowu tak bardzo nie bedzie. Wiekszosc kompilatorow (nawet bez optymalizacji) i tak w wiekszosci przypadkow zamieni to na to samo. Co do operacji % i & to tez nie dla wszystkich kompilatorow bedzie ten sam wynik (liczby ujemne).

więcej »

więcej »