Optymalizacja algorytmu min, maks

Question

Cześć, 

Przerabiam sobie książkę o algorytmach i postanowiłem zoptymalizować szukanie wartości minimalnej i maksymalnej zbioru metodą divide & conquer. Zgodnie z książką, porównuję liczby parami, na indeksach parzystych ustawiam większą z liczb, na nieparzystych indeksach wrzucam mniejszą. Później tradycyjną metodą porównuję liczby z nowych podzbiorów.
Niestety gdzieś popełniłem błąd, bo czasy "zoptymalizowaną" metodą są o wiele większe od osiąganych tradycyjną.

KOD

Answer 1

Zoptymalizowana funkcja dwa razy przegląda całą tablicę, a przesłanie tych wszystkich danych z pamięci do procesora zabiera czas. Już na podstawie tego można by się spodziewać, że będzie dwa razy wolniejsza.

Twoja książka pewnie nie bierze pod uwagę takich zjawisk jak hierarchia pamięci czy potokowość i tego jak potokowości szkodzą nieprzewidywalne skoki warunkowe. W ogóle żeby rozumieć kwestie wydajności, to trzeba dobrze znać sprzęt i wiedzieć jaki kod kompilator wygenerował, sama teoria złożoności obliczeniowej nie wystarczy.

Do samego sposobu przeprowadzenia pomiaru też można się przyczepić. Mierzysz nie tylko czas algorytmu, ale też czas  operacji wejścia-wyjścia (wyświetlania wyniku). Druga funkcja działa na innych danych niż pierwsza, bo pierwsza te dane zmieniła. Funkcja clock to chyba nie jest najlepszy sposób pomiaru czasu. I najważniejsze, czy włączyłeś optymalizację (flaga -O2 albo -O3)?

Comments

-O3 lepiej nie używać.

---

-O3 lepiej nie używać.

Jakieś argumenty? :)

---

Z mojej wiedzy, co do poprawności, owszem były błędy z -O3 ale gdzieś na etapie gcc ~ 2.9/3. Teraz już nie ma powodu bać się -O3 jeśli chodzi o poprawność kodu.

Co do wydajności, powody że może być kiepskie (-O3) to ew. trafienia w cache. Czasem -Os może dawać lepsze wyniki szczególnie na starszych procesorach. Niemniej jednak należy to zmierzyć :-)

---

@monika90,
Faktycznie, nie zwróciłem uwagi, że działamy na zmienionej tablicy, jednak nawet jeśli zamienię kolejność wykonywania się funkcji, to "zoptymalizowany" algorytm nadal działa wolniej. Prawdopodobnie nie włączyłem optymalizacji, przyznam szczerze, że pierwszy raz spotykam się z tym terminem.

---

Jakieś argumenty? :)

http://www.network-theory.co.uk/docs/gccintro/gccintro_49.html

[-O3] This option turns on more expensive optimizations, such as function inlining, in addition to all the optimizations of the lower levels -O2 and -O1. The -O3 optimization level may increase the speed of the resulting executable, but can also increase its size. Under some circumstances where these optimizations are not favorable, this option might actually make a program slower.

It is important to remember that the benefit of optimization at the highest levels must be weighed against the cost. The cost of optimization includes greater complexity in debugging, and increased time and memory requirements during compilation. For most purposes it is satisfactory to use -O0 for debugging, and -O2 for development and deployment.

---

Jpacanowski - źródło pochodzi z 2004 2005 roku, z deczka stare. ;) Zgadzam się, że znajdą się corner-case'y, gdzie optymalizacja poprowadzi do gorszego wyniku, jednak w podręcznikowym sortowaniu, na platformę nie-mikrokontrolerową - nie sądzę.

Oczywiście mokrowski położył tutaj najważniejszą kartę - najpierw zmierzyć, potem podjąć decyzję, co podpowiada prosta inżynierska praktyka. :)