On Sunday, August 20, 2017 at 10:14:33 AM UTC+2, fir wrote:
> odnosnie optymalizacji to moge jeszcze dodac cos bo widzialm gdzies
> tu jak zwykle te niemal bezdennie glupie klasyczne pseudodyskusje
> czy programista zoptymalizuje kod lepiej niz kompilator itd itd
Dlaczego uważasz te rozmowy za głupie?



> z tego jak ja to widze psrawa wyglada tak ze programista zoptymalizuje
> kod lepiej problem jest jednak w czym innym - dzis - z tego jak to
> mi sie jawi - kody sa memory-bound to nie asembler spowalnia kody
> tylko memory-bandwidth, innymi slowy problem jest w tym ze nawet
> 100-krotne zoptymalizowanie arytmetyki moze spowodowac na przyklad
> powiedzmy jedynie 1% przyspieszenia -
Generalnie masz rację. Ile razy przyspieszy 100-krotne zoptymalizowanie
arytmetyki? To zależy od programu. Ja myślę, że przyspieszyłoby
powiedzmy od 2 do 100 razy.

> Zupelnie inaczej bylo kiedys kiedy to memory bound nie bylo
> widoczne i wszystki liczylo sie predkoscią poszcegolnych instrukcji,
> w danej sytuacji przyspieszenie asemblera 100 razy dawalo przyspeszenie
> 100 razy... dzisiaj (jeli wywalic takie funkcja jak sin sqrt pow exp div)
> kody sa glownie memory bound i dlatego przepisywania asma po prostu
> niewiele daje -
Można skrócić czas wykonania od np. 7% do 50%, zależy od przypadku.


> jak robic optymalizacje tego memory bound?
Ja np. zaimplementowałem tak drzewa czerwono-czarne, żeby wszystkie
dane i meta-dane były w ciągłym obszarze pamięci. Można jeszcze
spróbować tak, aby dane i meta dane trzymać w dwóch osobnych
tablicach - ale ta technika w niektórych przypadkach zaszkodzi.
Wracając, w wyszukiwaniu w drzewie ciągle jest skok pod
(prawdopodobnie) losowy adres. W wyszukiwaniu binarnym w tablicy
skok pod losowy adres jest tylko na początku:
while( max - min > L ) {
middle = (max - min)/2;
[...]
}
while( min < max ) {
[...]
min ++ ;
}


> nie zajmowalem sie tym za duzo ale zdaje sie ze na przyklad unikanie
> malych zmiennych posrednich niewiele przyspiesza (na szczescie - bo
> rownoczesnie to zanczy ze mozna ich uywac tj uzywani ich niewiele
> spowalnia) .. przepisywanie arytmetyki
> jak wspomnialem w sumie sporo daje (mam tu na mysli przepisywanie i >
> upraszcanie raczej na poziomie c a nie asma)
Tak, na jedno wychodzi.

> ale i tak sprawa rozbija sie o memory bound (memory bound jest dzisiaj
> sciana i jesli mozesz zoptymalizowac asma to tylko DO tej sciany a nie
> poza nia - dlatego przepisywanie w asmie nie daje tak jak kiedys
> przyspieszen rzedu 10x 30x i
Hmmm mi kiedyś dawało zazwyczaj 3x. Myślę, że przyczyną jednak było to, że
kompilatory kiedyś były kiepskie.


> dlateo wlasnie nie jest tak wazne jak kiedys) samego memory bound nie
> wiem jak przyspieszyc byc moze sie nie da - podstawowe moemory bound
> liczy sie po prostu wielkoscią inputu i wielkoscia outputu (w megabajtach)
> t co ew mogloby to przyspieszyc to jakies skomplikowane algorytmy
> selekcjonujace input i output
Generalnie się zgadzam z Tobą, ale nie aż tak dosłownie. Przepisanie asma
trochę też daje. Tyle że dziś kompilatory dobrze to robią.


> -- ale to jest skomplikowane i zaciemnia algorytmy
> tak ze ja osobiscie o to zbytnie nie dbam
> jak zwykle na koniec warto wspomniec
> zapewne opencl bo GPU maja mamory bandwidth np 10 razy wiekszy niz
> procki tak ze jak ktos chce robic potezny flow przetwazania to
> pewnie powinien si etego nauczyc ;c
Na xeonphi jest fajnie, po prostu daje się
#pragma omp parallel
Niczego nie trzeba się uczyć i bangla. Ale na pewno podejście od bebechów
przyspieszyłoby dużo więcej.



> (ogolnie to napisalem wyzej to co wiem na ten temat, sam ostatnio
> jednak zaczalem jak wspomnielem mniej interesowac sie optymalizacją -
> choc ciagle interesuje mnie rev-engeenereeng /disasembling, vide
> pisanie asemblera x86)

Od kiedy znalazłem fragment kodu napisany przez kosmitów, też interesuję
się wsteczną inżynierią ;-)

Pozdrawiam

do góry

W dniu niedziela, 20 sierpnia 2017 12:30:14 UTC+2 użytkownik M.M. napisał:
> On Sunday, August 20, 2017 at 10:14:33 AM UTC+2, fir wrote:
> > odnosnie optymalizacji to moge jeszcze dodac cos bo widzialm gdzies
> > tu jak zwykle te niemal bezdennie glupie klasyczne pseudodyskusje
> > czy programista zoptymalizuje kod lepiej niz kompilator itd itd
> Dlaczego uważasz te rozmowy za głupie?
>
>

dlatego ze ktos kto tak dyskutuje kompletnie nie rozumie problemu

>
> > z tego jak ja to widze psrawa wyglada tak ze programista zoptymalizuje
> > kod lepiej problem jest jednak w czym innym - dzis - z tego jak to
> > mi sie jawi - kody sa memory-bound to nie asembler spowalnia kody
> > tylko memory-bandwidth, innymi slowy problem jest w tym ze nawet
> > 100-krotne zoptymalizowanie arytmetyki moze spowodowac na przyklad
> > powiedzmy jedynie 1% przyspieszenia -
> Generalnie masz rację. Ile razy przyspieszy 100-krotne zoptymalizowanie
> arytmetyki? To zależy od programu. Ja myślę, że przyspieszyłoby
> powiedzmy od 2 do 100 razy.
>

raczej przyspieszy od 0 do 10 %
wlasnie dlatego ze kod juz na starcie jest memory bound (dzis chyba trudna napisac az
taki krap ktory bylby az tak bardzo cpu bound bys mogl go przyspieszyc 5 razy co tu
mowic o 100x)

kazdy kod ma swoja naturalna predkosc ktora rowna sie memory bandwidth i powiedzmy ze
jest to 1 ms na 1 MB na rdzen (tak naprawde jest to troche wiecej, na kompach ktore
testowalem bylo to do 10 razy wiecej, ale dla utrzymania uwagi mozna przyjac 1 ms na
1 MB)

poprawne napisany kod wstepnie zoptymalizowany w c bedzie bliski tego

jelsi ta nieprzekraczalna granice uznasz za 100% to arytmatyka moze dodac nie wiem
powiedzmy dodatkowe 30%
i chocbys nie wiem co robic przepisywaniem asma zredukujesz tylko te 30% a 100%
nieprzekraczalnej granicy nie ruszysz innymi slowy max co przyspieszysz nawet
najlepszym recznym samem to 30% - i to nie dlatego dzis nie pisze sie za duzo w asmie
ze kompilatory generuja tako dobry asm tylko wlasnie dlatego ze chocby najlepszy asm
nie da za duzo

(chyba ze kod jest totalnym crapem i nie jest memory bound ale takie kody
rzadko sie widzi sa naprawde malo prawdopodobne)

wiecej chyba nie che mi sie o tym gadac bo albo to rozumiesz albo nie (a ja
powtarzajac w kolko to samo tylko tracilbym swoj czas czego wolalbym uniknac)

(ps mozliwe ze kody ktore sa memory bound mozna dalej zoptymalizowac ale
to raczej jakimis algorytmami w c
ktore beda oszczedzac operacje na pamieci a nie przepisywaniem na asma,
(mozliwe tez ze pewne szczegoly mi unikaja ale ogolna wizja memory-bound raczej jest
prawdziwa)

samo to przepisywanie kodow by unikaly przetwazania pamieci jest raczej co nieco
nieprzyjemna i 'nadbudowana' optymalizacyjna algorytmiką i moim zdaniem niekoniecznie
to trzeba robic bo kody robia sie od tego dluzsze i brzydsze a nie maja dodatkowej
funkcjonalnosci wrecz nabieraja węższej ak ze jest to mocno specjalistyczna dzialka)






> > Zupelnie inaczej bylo kiedys kiedy to memory bound nie bylo
> > widoczne i wszystki liczylo sie predkoscią poszcegolnych instrukcji,
> > w danej sytuacji przyspieszenie asemblera 100 razy dawalo przyspeszenie
> > 100 razy... dzisiaj (jeli wywalic takie funkcja jak sin sqrt pow exp div)
> > kody sa glownie memory bound i dlatego przepisywania asma po prostu
> > niewiele daje -
> Można skrócić czas wykonania od np. 7% do 50%, zależy od przypadku.
>
>
> > jak robic optymalizacje tego memory bound?
> Ja np. zaimplementowałem tak drzewa czerwono-czarne, żeby wszystkie
> dane i meta-dane były w ciągłym obszarze pamięci. Można jeszcze
> spróbować tak, aby dane i meta dane trzymać w dwóch osobnych
> tablicach - ale ta technika w niektórych przypadkach zaszkodzi.
> Wracając, w wyszukiwaniu w drzewie ciągle jest skok pod
> (prawdopodobnie) losowy adres. W wyszukiwaniu binarnym w tablicy
> skok pod losowy adres jest tylko na początku:
> while( max - min > L ) {
> middle = (max - min)/2;
> [...]
> }
> while( min < max ) {
> [...]
> min ++ ;
> }
>
>
> > nie zajmowalem sie tym za duzo ale zdaje sie ze na przyklad unikanie
> > malych zmiennych posrednich niewiele przyspiesza (na szczescie - bo
> > rownoczesnie to zanczy ze mozna ich uywac tj uzywani ich niewiele
> > spowalnia) .. przepisywanie arytmetyki
> > jak wspomnialem w sumie sporo daje (mam tu na mysli przepisywanie i >
> > upraszcanie raczej na poziomie c a nie asma)
> Tak, na jedno wychodzi.
>
> > ale i tak sprawa rozbija sie o memory bound (memory bound jest dzisiaj
> > sciana i jesli mozesz zoptymalizowac asma to tylko DO tej sciany a nie
> > poza nia - dlatego przepisywanie w asmie nie daje tak jak kiedys
> > przyspieszen rzedu 10x 30x i
> Hmmm mi kiedyś dawało zazwyczaj 3x. Myślę, że przyczyną jednak było to, że
> kompilatory kiedyś były kiepskie.
>
>
> > dlateo wlasnie nie jest tak wazne jak kiedys) samego memory bound nie
> > wiem jak przyspieszyc byc moze sie nie da - podstawowe moemory bound
> > liczy sie po prostu wielkoscią inputu i wielkoscia outputu (w megabajtach)
> > t co ew mogloby to przyspieszyc to jakies skomplikowane algorytmy
> > selekcjonujace input i output
> Generalnie się zgadzam z Tobą, ale nie aż tak dosłownie. Przepisanie asma
> trochę też daje. Tyle że dziś kompilatory dobrze to robią.
>
>
> > -- ale to jest skomplikowane i zaciemnia algorytmy
> > tak ze ja osobiscie o to zbytnie nie dbam
> > jak zwykle na koniec warto wspomniec
> > zapewne opencl bo GPU maja mamory bandwidth np 10 razy wiekszy niz
> > procki tak ze jak ktos chce robic potezny flow przetwazania to
> > pewnie powinien si etego nauczyc ;c
> Na xeonphi jest fajnie, po prostu daje się
> #pragma omp parallel
> Niczego nie trzeba się uczyć i bangla. Ale na pewno podejście od bebechów
> przyspieszyłoby dużo więcej.
>
>
>
> > (ogolnie to napisalem wyzej to co wiem na ten temat, sam ostatnio
> > jednak zaczalem jak wspomnielem mniej interesowac sie optymalizacją -
> > choc ciagle interesuje mnie rev-engeenereeng /disasembling, vide
> > pisanie asemblera x86)
>
> Od kiedy znalazłem fragment kodu napisany przez kosmitów, też interesuję
> się wsteczną inżynierią ;-)
>
> Pozdrawiam

do góry

z samego tego ze dzis kody so tak bardzo mamory-speed-bound i ze nie oplaca sie za
bardzo optymalizowac asmanie wiem czy warto sie smucic czy cieszyc (kiedys juz o tym
fakcie pisalem)

pewnjie po prostu nalezy sie zmucis ze sa 'bound' i ze predkosc ramu jest jaka jest
bo moglabybyc wieksza

moim zdaniem jakby zwiekszyli predkosc ramu (np 20 razy) to predkosc programow by
wzrosla blisko 20 razy (o ile mniej to by wlasnie znaczylo ze o tyle sa asm-bound)
bez wiekszania liczby rdzeni i bez zwiekszania taktowania procesora

do góry

On Sunday, August 20, 2017 at 1:01:20 PM UTC+2, fir wrote:
> dlatego ze ktos kto tak dyskutuje kompletnie nie rozumie problemu

Niekoniecznie oznacza to, że ktoś kompletnie nie rozumie problemu.
Może to oznaczać, że ktoś w pośpiechu, sformułował ciekawy problem
właśnie przy pomocy takich słów.

Zawsze szukamy jakiś idealnych odnośników. Programista ręcznie
implementujący dany algorytm w języku assemblera jest odnośnikiem
do najlepszej implementacji, bo dobry programista jak ma bardzo
dużo czasu, to wykona najlepszą implementację. Potem do tej
najlepszej porównujemy możliwości obecnych kompilatorów.

Dla mnie to oznacza kolokwialne sformułowanie problemu, a nie
totalne niezrozumienie.

> [...]
> wiecej chyba nie che mi sie o tym gadac bo albo to rozumiesz albo
> nie (a ja powtarzajac w kolko to samo tylko tracilbym swoj czas
> czego wolalbym uniknac)
Generalnie zrozumiałem od początku. Problem jak zwykle siedzi w
szczegółach. Zobacz jak nieprecyzyjne jest określenie "przyspieszenie
CPU 100 razy". Co to jest CPU? Przyspieszamy tylko arytmetykę, czy
także odczyty z rejestrów (rejestry to zdecydowanie część CPU, ale
pamięć też), czy może także przyspieszamy cache L1, bo to chyba też
integralna część CPU? Przyspieszony 100 razy CPU wraz z rejestrami i
pamięcią cache, wykona dużo programów 30 razy szybciej.

Pytanie, wnosi do naszej rozmowy przytoczenie 100 razy szybszego
CPU, jeśli może być przyspieszony na N sposobów? Myślę że nic, tylko
komplikuje sprawę. Dlatego w porównaniach często powołujemy się na
teoretycznego programistę który napisał kod idealny - niestety z
tym też jest problem, bo zazwyczaj nie mam kodu idealnego pod
ręką. Hmmm my nie mamy, ale twórcy kompilatorów mogą mieć i to
wiele prawie doskonałych kodów.

Powiem w ten sposób. Gdy bez zastanowienia pisałem fragment kodu w
asemblerze na nowsze procesory w czasach gdy kompilatory już
powszechnie uchodziły za dopracowane, to mój kod działał np. o 20%-50%
wolniej niż skompilowany z opcją -O1. Gdy był kompilowany z
opcją -O3, w dodatku z informacjami z profilera, to mój był wolniejsz
jeszcze może o 40%-80%. Przepustowość pamięci się nie zmieniała.
Sposób korzystania z pamięci był taki sam, bo algorytmy za każdym
razem te same. Wniosek dla mnie jest taki, że pisząc nawet
przyzwoity kod w asemblerze można spowolnić wykonanie. Co by było
gdyby kompilator porównać z kodem optymalnym - nie wiem, o to
właściwie ja czasami dopytuję i nie uważam żeby moje pytania
oznaczały totalnie niezrozumienie, co powyżej uzasadniłem.


> samo to przepisywanie kodow by unikaly przetwazania pamieci jest raczej
> co nieco nieprzyjemna i 'nadbudowana' optymalizacyjna algorytmiką i
> moim zdaniem niekoniecznie to trzeba robic bo kody robia sie od tego
> dluzsze i brzydsze a nie maja dodatkowej funkcjonalnosci wrecz
> nabieraja węższej ak ze jest to mocno specjalistyczna dzialka)
Tu się zgadzam, przykładem jest ATLAS. Koszmarek implementacyjny i
zarazem dzieło sztuki implementacyjnej.

Pozdrawiam

do góry

On Saturday, August 19, 2017 at 9:52:57 PM UTC+2, AK wrote:
> Użytkownik "bartekltg" <b...@g...com> napisał:
>
> > Jeśli to jest drzewo, to w dół idzie unique_ptr, a w górę choćby goły
> > wskaźnik. Ten goły zawsze jest ważny, bo obiekt w którym jest istnieje
> > tylko, jesli obiekt nadrzędny istnieje.
>
> Nie goly wskaznik, tylko normalniej: weak_pointer

Dlaczego?
Weak pointer jest do sprawdzania, czy obiekt istnieje.
A obiekt istenije na pewno.


> PS: Najlepiej zapomniec o "zwyklych"/"golych"wskaznikach.
> Doposzczalne winny byc jedynie w narzedziowce i to "on demand; (tak jak to
zrobiono w C#)

Bzdura.

pzdr
bartekltg

do góry

W dniu 2017-08-19 o 23:17, fir pisze:
> W dniu sobota, 19 sierpnia 2017 23:02:17 UTC+2 użytkownik M.M. napisał:
>> On Saturday, August 19, 2017 at 9:52:57 PM UTC+2, AK wrote:
>>> Użytkownik "bartekltg" <b...@g...com> napisał:
>>>
>>>> Jeśli to jest drzewo, to w dół idzie unique_ptr, a w górę choćby goły
>>>> wskaźnik. Ten goły zawsze jest ważny, bo obiekt w którym jest istnieje
>>>> tylko, jesli obiekt nadrzędny istnieje.
>>>
>>> Nie goly wskaznik, tylko normalniej: weak_pointer
>>>
>>> PS: Najlepiej zapomniec o "zwyklych"/"golych"wskaznikach.
>>> Doposzczalne winny byc jedynie w narzedziowce i to "on demand; (tak jak to
zrobiono w C#)
>>>
>>> AK
>>
>> Gdy wydajność nie jest istotna, to trzeba korzystać z wszelkich
>> tego typu udogodnień.
>> Pozdrawiam
>
> gdy wydajnosc jest istotna to nawet zwykle wskazniki nie sa wskazane imo
>
> (kiedys mierzylem ile wolniejszy jest kod gdy dzialasz na tablicy bedacej wynikiem
malloka w stosunku do w pewlni statycznej - i na malloku bylo auwazalnie 10-20%
wolniej
>
> no ale niewazne moze to byla specyficzne sytuacje, podaje jako anegdote, ostatnio
az tak bardzo nie przejmuje sie wydajnoscią - nawet moge
> powiedziec, kiedys stawialem chyba gdzies tu pytanie jak ktos zrobilby trzymanie
zawartosci edytora tekstowego w programie w c i kombinowalem wtedy cos w kierunku
trzymania listy litych kawalkow ramu po powiedzmy okolo 500 kb kazdy - dzis
> raczej chyba zrobilbym przynajmniej na poczatek do testu tak ze kazda linijka w
edytrze po prostu bylaby na odzielnym malloku (realokowany w miare
> edycji itd)
>

Gdybyś się przyłożył bardziej do testów, zauważyłbyś, że jest to zależne
od tego w jakim celu, jak dużą tablicę potrzebujesz. To jest narzędzie,
tak samo jak młotek, czy wkrętak, jak będziesz młotkiem próbował wkręcać
śrubki, a wkrętakiem wbijał gwoździe, to tez będzie raczej nieoptymalne...


--
http://kaczus.ppa.pl

do góry

On Monday, August 21, 2017 at 7:50:33 AM UTC+2, Tomasz Kaczanowski wrote:
> Gdybyś się przyłożył bardziej do testów, zauważyłbyś, że jest to zależne
> od tego w jakim celu, jak dużą tablicę potrzebujesz. To jest narzędzie,
> tak samo jak młotek, czy wkrętak, jak będziesz młotkiem próbował wkręcać
> śrubki, a wkrętakiem wbijał gwoździe, to tez będzie raczej nieoptymalne...

Ja zrozumiałem, że chodzi nie o łączny koszt, lecz w ogóle o operacje na
wskaźniku pochodzącym z malloc. Kiedyś też coś takiego zaobserwowałem, ale
w innych programach to się nie potwierdzało.

Pozdrawiam

do góry