[avr-gcc] zliczanie modulo

Jest dok³adnie tak jak piszesz - najszybsza jest funkcja & (gdy siê da), potem if, potem %. Je¶li jest to czasowo krytyczne sprawd¼ w listingu kodu wynikowego jak s± kompilowane poszczeglne wersje.

U¿ytkownik "BartekK" snipped-for-privacy@drut.org napisa³ w wiadomo¶ci news:enc996$sdi$ snipped-for-privacy@atlantis.news.tpi.pl...

Je¶li masz masz kawa³ek wolnej pamiêci to deklarujesz tablicê o takiej ilo¶ci elementów jak chcesz liczyæ i potem u¿ywasz funkcji succ lub pred dla elementu tablicy je¶li chcesz liczyæ w ty³, nie znam avr-gcc ale te funkcje powinny byæ tam dostêpne. Nie wiem na ile dobrze kompilator to przet³umaczy, ale w C jest to jedna linijeczka, my¶lê ¿e bêdzie to realizowane szybciej ni¿ to co piszesz. Piotr

Nie bêdzie szybciej. Taka tablica jest szybka dla obliczania reszty (lub innych trudnych funkcji) w przypadku ogólnym dla dowolnej wartoœci wejœciowej. Zrobienie licznika by³oby ma³o efektywne. Samo zaadresowanie elementu tablicy wymaga paru instrukcji.

Przy czym je¶li nie ma istotnych powodów, to nie nale¿y mieszaæ ¶wiata liczb i ¶wiata wektorów bitowych, mimo, ¿e w danej reprezentacji binarnej wyjdzie na to samo. Do operacji na liczbach w tym przypadku s³u¿± operatory %, / i *, które nawet s³aby kompilator powinien umieæ przekszta³ciæ na równowa¿ne operacje logiczne, wiêc nie ma potrzeby zaciemniania kodu poprzez wyrêczanie go. GCC jest bardzo dobry w tego rodzaju przekszta³ceniach.

Owszem, prawo Amdahla:

Pozdrawiam Piotr Wyderski

Piotr Wyderski napisał(a):

Jakos nie chcialo mi sie patrzec w deasemblowany kod po kompilacji, ale jestes pewny ze gcc wie jak to przeksztalcic na if/and ? Po wielkosci kodu wnioskuje ze mimo wszystko uzywa asm-procedurki dzielenia/reszty, moze zalezy to od metody optymalizacji (przewaznie uzywam -Os)

Przyspieszenie jest nie o 100% a chyba pare tysiecy procent (gdy licznik jest np 16bit, i porównujemy & i %), zmiana wielkosci kodu o kilka bajtow przy kazdej operacji, ale dla mnie istotna nie jest predkosc wykonywania kodu, a opoznienie - nawet tylko 50% czas wykonywania fragmentu kodu to 2x szybsza reakcja na zdarzenie wywolujace ten fragment.

Co do AVR, to nie mam pewno¶ci, ale na kilku "wiêkszych" platformach od lat robi to bez problemu. Tego rodzaju transformacje s± w du¿ym stopniu niezale¿ne od docelowej architektury, wiêc i na AVR powinno umieæ zamieniæ % na &, mno¿enie przez sta³± na ci±g dodawañ i przesuniêæ, dzielenie przez sta³± do mno¿enia przez sta³± itp. setki drobnych optymalizacji.

Ej¿e, skoro jako funkcjê kosztu przyj±³e¶ rozmiar kodu, to kompilator bêdzie wykonywa³ powy¿sze transformacje jedynie wówczas, gdy nie zwiêksz± one liczby instrukcji. Je¿eli wywo³anie procedury dzielenia przez sta³± bêdzie choæby o bajt krótsze od wstawienia kodu równowa¿nego, to kompilator wywo³a tê funkcjê bez zbytniego zwracania uwagi na czas jej dzia³ania. Dostaniesz _dok³adnie_ to, o co sam go poprosi³e¶...

W ¶wietle powy¿szego jest to ca³kowicie mo¿liwe. Chcia³e¶ ma³y kod, to dosta³e¶ ma³y kod. Dlaczego wiêc narzekasz na kompilator, który dobrze wykona³ swoje zadanie? Spróbuj przekompilowaæ to z opcj± -O2 i poka¿ listingi. Je¶li dalej kompilator sobie nie poradzi z zamian±, to zg³o¶ autorom b³±d w optymalizatorze wyra¿eñ sta³ych.

Dla Ciebie wa¿ny jest rozmiar kodu. Jesli chcesz mieæ i ma³y kod i szybkie fragmenty krytyczne, to sobie musisz podzieliæ program na kawa³ki i je kompilowac z innymi kryteriami optymalizacji.

Niekoniecznie, bo ten fragment nie jest zawieszony w pró¿ni. Je¿eli procedura obs³ugi sk³ada siê w wiêkszo¶ci z tego kodu, to przyspieszenie czasu reakcji bêdzie du¿e, ale im mniejszy ten udzia³, tym mniej zyskasz w globalnym rozrachunku.

Pozdrawiam Piotr Wyderski

Piotr Wyderski przemówił ludzkim głosem:

Zastępowanie dzielenia modulo operacjami logicznymi (albo porównaniami), to nie zaciemnianie kodu, tylko (celowe) ograniczenie swobody ruchu kompilatorowi. Dzięki temu nie dopuszcza się do sytuacji, w której po zmianie rozmiaru bufora/tablicy, w krytycznym czasowo kawałku kodu pojawia się długotrwała operacja dzielenia (nie każdy procesor ma sprzętowe dzielenie), zamiast operacji logicznej (czy porównania).

Jesli zmienisz rozmiar bufora na taki przy ktorym tylko dzielenie wchodzi w gre to i tak nic nie poradzisz, a jesli da sie go zastapic operacja logiczna to kompilator IMHO ciagle zastapi. Wiec argument malotrafny. BTW. Wlasnie sprawdzilem w avr-gcc dla ATMegi8 operacje typu int zmienna%=16. Kompilator generuje sekwencje: pos=pos%16;

a wiec najkrotszy mozliwy kod. Kompilowane z -Qs.

Je¶li kto¶ potrzebuje ograniczac kompilatorowi swobodê doboru schematu translacji, to powinien pisaæ w asemblerze.

A jakim cudem mia³aby siê tam ona pojawiæ? Zastêpowanie drogich operacji tañszymi odpowiednikami dla specjalnych warto¶ci parametrów nazywa siê redukcj± mocy i jest implementowane w kompilatorach praktycznie od pocz±tku ich istnienia. Jest to przy tym bardzo proste do zrealizowania.

Czy naprawdê s±dzisz, ¿e przekszta³cenia w rodzaju "zamiast x / 4 napisz x >> 2", które na pierwszy rzut oka widzi ju¿ kanapowy optymalizator Zenio, nie zostan± dostrze¿one przez kompilator optymalizuj±cy o co najmniej dwudziestoletnim ¿yciorysie? Wiesz, GCC potrafi m.in. odtwarzaæ przesuniêcia cykliczne z ci±gów operacji logicznych i wektoryzowaæ petle, a Ty chcesz go zagi±æ takimi drobiazgami... :-)

Sensowny kompilator nie u¿yje dzielenia, je¶li bêdzie mia³ inne wyj¶cie. Kolejno¶æ wariantów kodu dzielenia bêdzie nastêpuj±ca:

1. Próba zast±pienia go pojedyncz± prost± operacj± arytmetyczno-logiczn±;
2. Próba zast±pienia go krótkim ci±giem takich operacji;
3. Próba zast±pienia go mno¿eniem przez odpowiedni± sta³± magiczn±;
4. Rezygnacja i u¿ycie prawdziwego dzielenia.

Dzia³a dopóki kto¶ nie u¿yje -Os, zmieniaj±c kryteria optymalno¶ci.

_Tylko_ operacji logicznej. Przenoszenia rzadko wykonywanego kodu do bloków warunkowych zasadniczo nie wolno kompilatorowi robiæ.

Pozdrawiam Piotr Wyderski

T.M.F. przemówił ludzkim głosem:

Zauważ, że w swoim tekście pisałem także o użyciu porównań. Generalnie stosuję zasadę:

1. Jeśli dopuszcza się, że rozmiar tablicy/bufora będzie przyjmował tylko wartości będące potęgą 2, to % zastępuję operacjami logicznymi.
2. W pozostałych przypadkach staram się używać porównań.

Nawiasem mówi±c, to tutaj tylko kompilatorowi wolno zastosowac redukcje mocy wprowadzaj±c± and -- wynik operacji bitowych na typach ze znakiem jest w C(++) nieokre¶lony. Tylko na unsigned wolno ich w przeno¶ny sposób u¿ywaæ, chyba, ¿e kto¶ ¶wiadomie rezygnuje z przeno¶no¶ci.

I choæby¶ pokaza³ jeszcze setki takich przyk³adów, wielu ludzi nie przekonasz o skutecznym dzia³aniu automatycznej redukcji mocy. Ciekawe zjawisko psychologiczne, swoj± drog±.

Pozdrawiam Piotr Wyderski

Nie tyle porównañ, co bloków warunkowych. Samych porównañ mo¿na u¿ywaæ i bez nastêpuj±cych po nich instrukcji skoku, co prowadzi do techniki arytmetyzacji alternatywnych ¶cie¿ek przep³ywu. Masz racjê w tym, ¿e kompilator zazwyczaj nie wprowadzi bloku, choæby z tego wzglêdu, ¿e on w przeciwieñstwie do Ciebie nie zna rozk³adu prawdopodobieñstwa wyboru okre¶lonej ¶cie¿ki, wiêc uznaje, ¿e wprowadzaj±c warunek mo¿e siê pomyliæ, przez co z tego rezygnuje. Niektóre kompilatory maj± mechanizmy do podawania takich cech, np. #pragma execution_frequency w XL, ale to nie jest standardowe C.

Na co odpowiedzieæ nale¿y "skoro Ci to poprawia samopoczucie..."

Je¶li tablica ma rozmiar bêd±cy potêg± np. 3, to jakich porównañ chcesz u¿yæ?

Pozdrawiam Piotr Wyderski

Tylko nie bardzo wiadomo ile z GCC ucieto przy implementowaniu go na tak prosta maszynke.

No i czy aby na pewno na danym procesorku bardziej oplaca sie x>>2 niz x/4 :-)

Eee - robi to. Problem w tym ze skoki zazwyczaj rozwalaja kolejke procesora i wydluzaja kod. Ale .. nie w kazdym :-)

J.

Piotr Wyderski przemówił ludzkim głosem:

W wielu przypadkach indeks do pobierania danych z tablic/buforów nie zmienia się w sposób dowolny, lecz jest sukcesywnie zwiększany/zmniejszany o ściśle określoną wartość (zazwyczaj nie przekraczającą wielkości bufora). Taką sytuację masz w przypadku obsługi wszelkiej maści buforów cyklicznych itp. I w takich przypadkach można zaoszczędzić czas procesora stosując porównanie i warunkowe odejmowanie/dodawanie zamiast równoważnej operacji dzielenia modulo.

Przykład padł już w jednym z wcześniejszych postów. Taki kod na avr wykona się szybciej:

niż: indeks = (indeks + 1) % rozmiar_tablicy;

w przypadku, gdy rozmiar jest np. 27 (twoja potęga 3 :-)

Nic mu nie uciêto. Portowanie GCC polega g³ównie na dodawaniu (generatora kodu, peephole optimizera, modelu maszyny itd.), a nie na ciêciu. :-)

Jak dzielenie bêdzie tañsze, to sobie je zostawi.

Tylko w specjalnych przypadkach, w rodzju robienia referencji ze wska¼nika itp.

Atmelek nie ma pipeliningu, BTB, predyktorów kierunku ani innych cudów znanych z wiekszych architektur. :-)

Pozdrawiam Piotr Wyderski

Piotr Wyderski przemówił ludzkim głosem:

Idąc twoim tokiem rozumowania, to należałoby wyciąć wszystkie opcje kompilacji kodu, bo ogranicza to swobodę translacji. Ja nie widzę nic złego w tym, że próbuję przy pomocy kodu źródłowego wymusić określone zachowanie kompilatora.

Przykładowy kawałek:

a = (a+1) % STALA;

W zależności od wartości stałej kompilator może użyć dzielenia, albo operacji bitowej. Problem polega na tym, że zmiana stałej diametralnie może zmienić czas wykonania kodu, co w kodzie krytycznym czasowo jest niedopuszczalne.

Wiesz, nie samym gcc programista żyje. Zresztą na niektórych platformach gcc też produkuje koszmarny kod. Przykładem niech będzie R8C, gdzie gcc generuje kod jak dla RISCa, marnując potencjał procesora, albo nie potrafi czasem rozpoznać możliwości użycia operacji zerowania/ustawiania pojedynczych bitów i z uporem maniaka stosuje sumę/iloczyn logiczny. Ale stosując odpowiednią sztuczkę składniową można gcc zmusić, do używania instrukcji zapalania/gaszenia bitów. Gdybym musiał użyć gcc na ten procesor, to nie wahałbym się przed używaniem "sztuczek", gdyby tylko pozwoliło to na uzyskanie bardziej zwięzłego kodu.

Jakim cudem doszed³e¶ do takiego wniosku? Kompilator generuje kod korzysaj±c z pewnej funkcji kosztu. Nie istnieje jedna uniwersalna funkcja kosztu, w ró¿nych zastosowaniach mog± byæ w ró¿nym stopniu istotne czynniki takie jak rozmiar lub wydajno¶æ. Do okre¶lania tej funkcji s³u¿± w³a¶nie parametry optymalizacji.

W³a¶nie problem polega na tym, ¿e on sobie doskonale bez takiego wymuszania poradzi, a osoba, która przejmie pó¼niej taki kod nie bêdzie musia³a siê zastanawiaæ, co to s± za maski. Potrzebujesz reszty z dzielenia przez 2^n, to _to_ napisz, kompilator bêdzie wiedzia³, co z tym zrobiæ.

Owszem, ale nie tylko kompilator. Rêcznie tego inaczej nie rozwi±¿esz. BTW, jesli procesor ma wzglêdnie szybkie sprzêtowe mno¿enie, to dla wielu warto¶ci sta³ej sobie poradzi bez dzielenia. Na 32-bitowych maszynach ten sposób optymalizacji to norma.

Ale przecie¿ rêcznie wpisana maska te¿ ci tu w ¿aden sposób nie pomo¿e. Je¶li chcesz mieæ jednakowy czas wykonania niezale¿nie od warto¶ci sta³ej, to wrêcz musisz u¿ywaæ dzielenia w ka¿dym przypadku, bo wersje z maskami bêd± "dramatycznie zmieniaæ czas wykonywania kodu".

Takie rzeczy potrafi± nawet najg³upsze kompilatory, wiêc nieustannie mnie dziwi ¿ywotno¶æ podej¶cia Ja Wiem Lepiej (TM). Czy je¶li napiszesz

x = 1 + 0;

to równie¿ obawiasz siê, ¿e kompilator wygeneruje dodawanie tego zera? Bo redukcja mocy za pomoc± masek bitowych to jest dok³adnie ten sam poziom skomplikowania...

Takie rzeczy siê rozwi±zuje wstawkami asemblerowymi ukrytymi w funkcjach inline, a nie "sztuczkami sk³adniowymi", bo kiedy¶ taka sztuczka mo¿e nie zadzia³aæ. W³a¶nie po to wstawki s±, by mieæ gwarancjê sposobu implementacji.

Kod nie ma byæ zwiêz³y, tylko zrozumia³y i czytelny. Nawet taki z dobrze zaprojektowanymi wstawkami asemblerowymi mo¿e byæ znacznie czytelniejszy ni¿ efekt pracy optymalizatora-majsterklepki w czystym C.

Pozdrawiam Piotr Wyderski

No i w³a¶nie tej informacji o czêsto¶ci wyboru ¶cie¿ek brakuje kompilatorowi, dlatego rêczne wprowadzenie bloku warunkowego pomaga -- i co do tego nie ma dyskusji. Mnie natomiast ca³y czas chodzi o to, ¿e nie ma znaczenia, czy kto¶ sobie napisze & czy %. Automatyczne wykrywanie potêg dwójki w parametrach to tak banalna sprawa, ¿e "(celowe) ograniczenie swobody ruchu kompilatorowi" jest szkodliwe, bo niczego nie przyspiesza, a jedynie sieje zamêt.

Pozdrawiam Piotr Wyderski

Owszem, pierwszy przyklad wykona sie szybciej, ale te dwie instrukcje nie sa rownowazne. Stad druga postac nie moze byc zoptymalizowana. Ergo, przyklad do kitu.