Optymalizacja zliczania modulo w AVR: XOR czy dzielenie dla AVR Tiny2313?

Tue Jan 02, 2007 8:33 pm   

J.F. wrote:


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

Tue Jan 02, 2007 8:42 pm   

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.

Tue Jan 02, 2007 9:25 pm   

Zbych wrote:


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

Tue Jan 02, 2007 9:25 pm   

Zbych wrote:


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

Tue Jan 02, 2007 9:36 pm   

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


--
Inteligentny dom - http://idom.wizzard.one.pl
Teraz takze forum dyskusyjne
Zobacz, wyslij uwagi, dolacz sie do projektu.

Tue Jan 02, 2007 9:46 pm   

Alez to jest zle. Chociazby dlatego, ze nie wiesz jak kompilator
przetlumaczy to co napisales na assembler. Skad masz gwarancje, ze zapis
np. x&0x0f nie zostanie przetlumaczony na x%0x0f? Oczywiscie ten
przyklad jest bez sensu, ale w bardziej zlozonych sytuacjach nie masz
zadnego przelozenia pomiedzy skladnia w C/C++ a generowanym kodem
assemblerowym. Tak wiec jesli naprawde chcesz miec kontrole nad
fragmentem kodu to nalezy go napisac w assemblerze, a nie liczyc, ze
kompilator dla danej skladni wygeneruje okreslony kod.


Owszem, ale jesli bedzie mozliwe uproszczenie do operacji wycinania
bitow to kompilator to zrobi, jesli nie bedzie mozliwe to czlowiek tez z
tym nic nie zrobi. IMHO roznica jest wylacznie taka, ze szybciej sie o
tym dowiesz.


Nie jest to zwiazane z promowaniem typow char/uchar na typy 16 bitowe,
dla ktorych ustawianie i zerowanie pojedynczych bitow nie jest
supportowane w assemblerze? Analogiczny problem istnieje w przypadku
AVR, mozna go obejsc w sposob maloelegancki, albo elegancko robiac
wstawke w assemblerze.


Jezeli masz taka krytyczna sekcje to IMHO jedynym eleganckim
rozwiazaniem gwarantujacym otrzymanie oktreslonego kodu jest napisanie
go po prostu w assemblerze. Jaka masz gwarancje, ze nowa wersja
kompilatora ciagle bedzie sie zachowywac tak samo napotykajac na twoja
"sztuczke"?



--
Inteligentny dom - http://idom.wizzard.one.pl
Teraz takze forum dyskusyjne
Zobacz, wyslij uwagi, dolacz sie do projektu.

Tue Jan 02, 2007 10:40 pm   

Piotr Wyderski przemówił ludzkim głosem:


Pokazałem Ci kawałek kodu, w którym to "poradzi" prowadzi do znacznych
różnic w długości wykonywania programu (w zależności od procesora
oczywiście), co nie zawsze jest pożądane.


Ależ można to rozwiązać (na poziomie kodu C) tak, że długość wykonania
będzie z dokładnością do paru instrukcji procesora taka sama, dla każdej
stałej (i to wcale nie przez wymuszenie dzielenia). Pokazałem to w innym
poście w tym wątku.


Nie, mogę tam wsadzić "blok warunkowy" i uzyskam mniej więcej podobny
czas wykonania niezależnie od stałej.


Oczywiście, że ma być zrozumiały. Ale czy to wyklucza pisanie kodu w
taki sposób, który daje przy okazji kod lepiej zoptymalizowany?


Rozumiem, że przytoczonym przeze mnie przykład w innym poście zalicza
się do kategorii "majsterklepka" ?

Tue Jan 02, 2007 10:54 pm   

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


Człowiek może coś z tym zrobić. Jak? Już to pokazywałem.


Akurat problem o którym pisałem nie był związany z sekcjami krytycznym
(choć tu też mógł się objawić), ale z rejestrami obsługi przerwań, na
których rozbicie operacji na odczyt-modyfikację-zapis mogło prowadzić do
"gubienia" przerwań.


Stosuję jedną podstawową zasadę, niezależnie czy używam "sztuczek", czy
też nie: nie zmieniam (wersji) kompilatora w trakcie trwania projektu.

Tue Jan 02, 2007 11:02 pm   

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


Jeśli tylko wartość zmiennej indeks nie przekracza wartości rozmiar
przed wykonaniem powyższych instrukcji, to obydwie postaci są
funkcjonalnie równoważne.

Tue Jan 02, 2007 11:04 pm   

Owszem, ale kompilator nic nie wie o takim zalozeniu, wiec nie moze
zoptymalizowac kodu. Trudno mu z tego czynic zarzut bo musialby czytac w
myslach.


--
Inteligentny dom - http://idom.wizzard.one.pl
Teraz takze forum dyskusyjne
Zobacz, wyslij uwagi, dolacz sie do projektu.

Tue Jan 02, 2007 11:11 pm   

Owszem, pokazales zmieniajac funkcjonalnie algorytm rozwiazania. W
szczegolnosci jesli trzymamy sie przykladow z modulo i alternatywna
operacja logiczna to ten problem nie ma innego rozwiazania.


Czyli miales sekcje krytyczna czasowo. Nakombinowales sie ze sztuczkami,
ktorych pewnie nie da sie przeniesc na inny kompilator lub nawet inna
wersje tego samego zamiast od razu wrzucic pare instrukcji assemblera
majac 100% pewnosci co do uzyskanego kodu i czasu egzekucji.


I rozumiem, ze kazdy projekt zapisujesz z uzytym do jego skompilowania
kompilatorem? A co jesli gotowa procedure chcesz przeniesc do innego
projektu? Za kazdym razem wszystko piszesz od zera?
Sam widzisz, ze powoli dochodzimy do absurdow, bo od poczatku przyjales
absurdalne zalozenia. Po to pisze sie w jezyku wysokiego poziomu, zeby
korzystac z jego dobrodziejstw. Jesli ma sie krytyczny
czasowo/objetosciowo kod to nalezy przejsc do jezyka nizszego poziomu
dajacego w zamian pelna kontrole nad generowanym kodem. Inaczej
dochodzimy wlasnie do absurdow typu jeden projekt jeden kompilator, brak
mozliwosci przeniesienia fragmentow kodu itd.



--
Inteligentny dom - http://idom.wizzard.one.pl
Teraz takze forum dyskusyjne
Zobacz, wyslij uwagi, dolacz sie do projektu.

Tue Jan 02, 2007 11:16 pm   

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


Toć dlatego, od początku, pisałem, że czasem takie "ręczne sterowanie"
czasami jest potrzebne i pozwala wygenerowanie lepszego kodu.

Tue Jan 02, 2007 11:18 pm   

Zbych wrote:


Pokazałeś dwa programy, które robią inne rzeczy.
Dla index = rozmiar_tablicy


zwróci 0, a


zwróci 1. Możesz używać ich zamiennie tylko przy scisłej
kontroli zakresu zmiennej index, więc nie rozumiem próby
"sprzedania" pierwszego jako zamiennika drugiego.


Ale tylko dzięki wiedzy o sposobie zmian parametrów.
Spróbuj z tym:

int fn(int x, int y) {

return array[x*y % STALA];
}


No to wsadzaj, do dzieła. :-)


Przecież nie daje. & i % sprowadzają się do tego samego ciągu instrukcji.


Ale który z nich? Wręczanie kompilatora w zamianie % na &?
Zdecydowanie tak. Korzystanie z dodatkowej wiedzy o sposobie
generowania parametrów? Nie, to się chwali.

Pozdrawiam
Piotr Wyderski

Tue Jan 02, 2007 11:36 pm   

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


Oceniasz to co zrobiłem nie wiedząc nawet jak to zrobiłem i na ile ta
"sztuczka" jest przenośna.


Jeżeli to co napiszę w języku wysokiego poziomu spełnia wymagania, to
nie widzę powodu, by przenosić to na assembler, tylko dlatego że
kiedyś/gdzieś/ktoś może użyć innej wersji kompilatora, albo chcieć
przenieść to na inny procesor. Sprowadzasz sprawę do absurdu.

Tue Jan 02, 2007 11:45 pm   

Zbych wrote:


No ale przecież temu nikt nie zaprzecza. Ja cały czas
odnoszę się tylko do ręcznej redukcji mocy. Jeśli zaś
chodzi o wersję z ifem to na architekturach z drogimi
skokami warto zastosować wersję zarytmetyzowaną,
eliminującą skok:

#include <stdio.h>

inline unsigned int mod_increment(unsigned int v, const unsigned int m) {

__asm__(" addl $1, %0 \n" \
" cmpl %0, %1 \n" \
" sbbl %1, %1 \n" \
" notl %1 \n" \
" andl %1, %0 \n" \
" \n"
: "+r"(v)
: "r"(m - 1U)
: "cc");

return v;
}

inline unsigned int mod_increment_saturated(unsigned int v, const unsigned
int m) {

__asm__(" cmpl %1, %0 \n" \
" adcl $0, %0 \n" \
" \n"
: "+r"(v)
: "r"(m)
: "cc");

return v;
}

int main(int argc, char *argv[]) {

unsigned int v = 0U;

for(unsigned int i = 0; i < 15; ++i) {

v = mod_increment(v, 3U);
printf("%2u: %u\n", i, v);
}

v = 0;

for(unsigned int i = 0; i < 15; ++i) {

v = mod_increment_saturated(v, 2U);
printf("%2u: %u\n", i, v);
}

return 0;
}