W dniu piątek, 29 marca 2013 19:04:19 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 29 marca 2013 16:07:55 UTC+1 użytkownik firr kenobi napisał:
>
> > windowsowe ReadFile działa na oko tak samo jak
>
> > fread - aloe nie jestem pewien bo troche trudno
>
> > jest mi porownywac to pierwsze niecacheowane
>
> > wczytanie ;/
>
> > Pozniej sprawdze pwenie jak dziala to asynchroniczne wczytywanie
>
>
>
> A moze jakies inne zadanie? Takie zeby bardziej trafialo w
>
> algorytmike a mniej w szczegoly implementacji, czy dzialania
>
> systemu?
>

a nie wiem, mz to zakurat zadanie jest dsyc
dobre (pod moj gust), nie przepadam za ciezką
algorytmika - lubie za to optymalizowac w ramach
tego co daje maszyna :-/

do góry

W dniu piątek, 29 marca 2013 20:23:19 UTC+1 użytkownik firr kenobi napisał:

> a nie wiem, mz to zakurat zadanie jest dsyc
> dobre (pod moj gust), nie przepadam za ciezką
> algorytmika - lubie za to optymalizowac w ramach
> tego co daje maszyna :-/

Dla mnie optymalizacja w ramach tego co daje maszyna
stanowi pokuse. Czasami gdy widze ze program wolno
dziala, to kusi mnie, zeby go zoptymalizowac. Gdy
ulegne i wykonam optymalizacje liniowe, to wpadam w
pulapke zagmatwanego kodu i... trudno jest optymalizowac
na poziomie algorytmow :/
Pozdrawiam

do góry

W dniu piątek, 29 marca 2013 21:16:24 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 29 marca 2013 20:23:19 UTC+1 użytkownik firr kenobi napisał:
>
>
>
> > a nie wiem, mz to zakurat zadanie jest dsyc
> > dobre (pod moj gust), nie przepadam za ciezką
> > algorytmika - lubie za to optymalizowac w ramach
> > tego co daje maszyna :-/
>
>
>
> Dla mnie optymalizacja w ramach tego co daje maszyna
> stanowi pokuse. Czasami gdy widze ze program wolno
> dziala, to kusi mnie, zeby go zoptymalizowac. Gdy
> ulegne i wykonam optymalizacje liniowe, to wpadam w
> pulapke zagmatwanego kodu i... trudno jest optymalizowac
> na poziomie algorytmow :/
>

a mi nie, po przyoptymalizowaniu kod nie robi
mi sie bardziej zagmatwany, pewnie raczej krotszy
bo wycinam niektore linijki, wyciagam wyrazenia
itp - chyba łacze zreszta przyoptymalizowywanie z
ogolnym poprawianiem bałaganu

do góry

Dnia Thu, 28 Mar 2013 22:12:08 +0100, Michoo wyszeptal:

> On 28.03.2013 16:42, bartekltg wrote:
>> W dniu 2013-03-28 11:27, M.M. pisze:
>>> Bys musial wiedziec na jakim kompie programy beda porownywane.
>>
>> Ostatnio olimpiada informatyczna i potyczki algorytmiczne
>> lecą na czymś w rodzaju wirtualnego procesora x86.
>>
>> http://ripper.dasie.mimuw.edu.pl/~accek/homepage/wp-
content/papercite-data/pdf/acemgr09.pdf

Przebrnąłem...

> Strona 28 - liczenie "prędkości wykonywania instrukcji" za pomocą NOPów,
> które nie wychodzą poza dekoder rozkazów jest poronionym pomysłem. W
> ogóle dlatego się używa benchmarki ze złożonymi operacjami (np.
> dhrystone) bo procesory mają pipeline i np.
> add,add,shr może się wykonać w zauważalnie innym czasie niż add,shr,add.

Autor dość mocno się odsłania zwoimi zdziwieniami poweidziałbym. Te NOPy
to jedno, ale o takich rzeczach jak wykonywanie pętli o małej ilości
mikroopów dekodowanych raz pewnie nie słyszał i dziwi się co ten kompilator
robi z tablicami. Ale nie o tym chciałem, te detale są w tym kontekście
nieistotne.

> "Pewnym zaskoczeniem jest prawie dwukrotnie większa szybkość zapisu na
> komputerze Xeon w porównaniu z Core 2 Duo mimo, że oba komputery
> posiadają pamięć DDR2 666 MHz" - ech, a gdzie ilość kości pamięci? A
> gdzie timingi pamięci? Autor słyszał o czymś takim jak dual channel?

Ten kseon nie miał przypadkiem podpiętej buforowanej?

> Jak na mimuw to się zawiodłem...

Ja nie, to ma sens, ale OMG te cytaty z Feynmanna i Jobsa: jak można
chwalić innowacyjność i tępić heurystyki? A już żeby opierać
się na eksperymencie w celu wyciąganięcia wniosku, że teoretycznie
lepsze ale praktycznie gorsze rozwiązania są lepsze to już trzeba
być mocno wrośniętym w świat uczelniany (1). Rozumiem intencje,
ale te cytaty...

Tak na marginesie, jak widzę określenia typu "wydajność względna"
to widzę zderzenie siebie z ludźmi, którzy zostali na uczelni mniej
więcej tak jak zderzenie masywnych galaktyk, są artystycznie
wyglądające pozostałości takich rzeczy daleko w przestrzeni ;)

Z jednej strony rozumiem potrzebę stworzenia uczestnikom olimpiad
jednorodnego środowiska do oceny rozwiązań, a z drugiej nóż mi się
w kieszeni otwiera jak widzę metodę - jak chcą oceniać rozwiązanie
w ten sposób to mogliby poświęcić czas na ocenę przez człowieka.
Jak każde programowanie na kartce. Tu widać pewną rozbieżność
pomiędzy dziedziną Feynmanna a Jobsa - prawa fizyki niektórych
nie obejmują czasami.

Mogliby jednak zapewnić ludziom sprzęt oraz cienkiego klienta
w dowolnym języku i wszystko byłoby jasne. Aż tak biedna polska
nauka nie jest, żeby nie kupić kilkuset Raspberry Pi i na tym
możnaby już oceniać rozwiązania w zasadzie idealnie. Zbudowanie
takiego systemu to nawet niewiele roboty.

> Przy wypełnianiu tablicy - to jest zdaje się[*] kwestia nie tyle cache
> co działania linuxa - strony inicjalizowane 0 są przydzielane jako CoW,
> więc pierwszy zapis do tablicy w losowy sporób robi (robił?) masakrę w mmu.

Są opcje vm.overcommit_* - dzisiaj już chyba domyślnie są 0, co nie znaczy
że to pomoże, nie wiem kiedy faktycznie kernel zaczyna szukać strony.
Ustawianie faulta na pierwszy dostęp jest powszechną praktyką, to nawet
nie jest COW tylko dziura w pamięci. Na długą metę to powinno przyspieszać
system i aplikacje, tylko w pomiarach wydajności przeszkadza. Podobne
akcje robi m.in. NUMA - migruje przy pierwszym dostępie po decyzji.

(1) Gdyby ktoś miał wątpliwości, wiem co to jest złożoność. Na całe
szczęście po przepisaniu algorytmu z kartki jeszcze ratuje mnie kwestia
sprzętu, który też ma swoje właściwości

--
Edek

do góry

On Fri, 29 Mar 2013 11:04:19 -0700 (PDT), "M.M." <m...@g...com>
wrote:
> A moze jakies inne zadanie? Takie zeby bardziej trafialo w
> algorytmike a mniej w szczegoly implementacji, czy dzialania
> systemu?

Proszę bardzo: masz na dysku baardzo duży plik tekstowy (np. 200 GB -
tak duzy, ze nie zmiesci sie caly w pamięci operacyjnej) i chcesz
wybrac z niego losowa linię. Jak to zrobisz nie skanujac zawartosci
pliku dwukrotnie?

RW

do góry

W dniu sobota, 30 marca 2013 10:35:54 UTC+1 użytkownik Roman W napisał:
>
> Proszę bardzo: masz na dysku baardzo duży plik tekstowy (np. 200 GB -
> tak duzy, ze nie zmiesci sie caly w pamięci operacyjnej) i chcesz
> wybrac z niego losowa linię. Jak to zrobisz nie skanujac zawartosci
> pliku dwukrotnie?

Zaindeksuje poczatki linii i zapisze w osobnym pliku. Potem wybiore
losowy indeks i skocze od razu pod losowy wiersz, bez drugiego skanowania.

Przy drugim wyborze losowego wiersza, nie bede musial nawet raz skanowac.

Pozdrawiam

do góry

W dniu sobota, 30 marca 2013 11:17:38 UTC+1 użytkownik M.M. napisał:
> W dniu sobota, 30 marca 2013 10:35:54 UTC+1 użytkownik Roman W napisał:
>
> >
>
> > Proszę bardzo: masz na dysku baardzo duży plik tekstowy (np. 200 GB -
>
> > tak duzy, ze nie zmiesci sie caly w pamięci operacyjnej) i chcesz
>
> > wybrac z niego losowa linię. Jak to zrobisz nie skanujac zawartosci
>
> > pliku dwukrotnie?
>
>
>
> Zaindeksuje poczatki linii i zapisze w osobnym pliku. Potem wybiore
>
> losowy indeks i skocze od razu pod losowy wiersz, bez drugiego skanowania.
>
> Przy drugim wyborze losowego wiersza, nie bede musial nawet raz skanowac.
>
>

a fseek na takim duzym pliku jest szybką
operacją? bo od tego wiele zalezy ;) chyba sam
musze sprawdzic :/

do góry

W dniu sobota, 30 marca 2013 11:49:54 UTC+1 użytkownik firr kenobi napisał:
> a fseek na takim duzym pliku jest szybką
> operacją? bo od tego wiele zalezy ;) chyba sam
> musze sprawdzic :/
Wszystko zalezy od systemu plikow. Mowiac po prawdzie, to nigdy
nie mierzylem czasu funkcji fseek, ale tez na roznych systemach
plikow golym okiem nie zaobserwowalem aby dzialala wolno.

Tutaj jest problem z rozna dlugoscia wiersza. Jesli wylosujemy
sobie offset w pliku i zaczniemy szukac konca linii w
poblizu wylosowanego offsetu, to bedziemy trafiac czesciej w
dluzsze wiersze - czyli nie bedziemy mieli losowo.

Pozdrawiam

do góry

W dniu sobota, 30 marca 2013 12:06:20 UTC+1 użytkownik M.M. napisał:
> W dniu sobota, 30 marca 2013 11:49:54 UTC+1 użytkownik firr kenobi napisał:
>
> > a fseek na takim duzym pliku jest szybką
>
> > operacją? bo od tego wiele zalezy ;) chyba sam
>
> > musze sprawdzic :/
>
> Wszystko zalezy od systemu plikow. Mowiac po prawdzie, to nigdy
>
> nie mierzylem czasu funkcji fseek, ale tez na roznych systemach
>
> plikow golym okiem nie zaobserwowalem aby dzialala wolno.
>
>
>
> Tutaj jest problem z rozna dlugoscia wiersza. Jesli wylosujemy
>
> sobie offset w pliku i zaczniemy szukac konca linii w
>
> poblizu wylosowanego offsetu, to bedziemy trafiac czesciej w
>
> dluzsze wiersze - czyli nie bedziemy mieli losowo.
>
>
zmierzylem (ale niedokladnie bo nei chce mi
sie robic jakiejs kompleksowej testologii

- zwlaszcza ze nie bardzo wiem jak zapodawac
/rozrozniac odczyty z cachem i bez cachea )

i wynik jest u mnie 20 milisekund na
fseek+fgetc (czyli ujdzie - acz nie testowalem zadnych jakichs brzegowych warunkow)

wogole to plugin lister do podgladu plikow w
total komanderze jest dobrze napisany (pewnie
wlasnie na fseeku) bo o ile otworzenie 50MB pdfa
acrobat readerowi u mnie zajmuje z 10 sekund
zamułki 9co prawda nie wiem czy przez wczytywanie
pdf czy plikow samego programu) to lister otwiera
blizej natychmiastowo nawet takie duze pliki

do góry

On Sat, 30 Mar 2013 03:17:38 -0700 (PDT), "M.M." <m...@g...com>
wrote:
> Zaindeksuje poczatki linii i zapisze w osobnym pliku. Potem wybiore
> losowy indeks i skocze od razu pod losowy wiersz, bez drugiego
skanowania.

Czyli jednak bedziesz przetwarzal plik dwukrotnie. Ma byc tylko raz.

RW

do góry