W dniu 2013-03-28 21:50, Michoo pisze:

>
> W znanych mi implementacjach tak - jest automat zjadający wejście i
> wypluwający wyjście (pobierając/zapisując kolejne rekordy ze stosu)
> (hmmm, ciekawe, czy printf jest turing complete ;) ).

To nie linuksowy edytor tekstu;-)


>>
>>> No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
>>> jeszcze lepiej mmap
>>
>> W przykładzie który widziałem (właśnie z takich konkursików)
>> gość użył fgets + bufor + własne przerabianie na liczby.
>
> Na potyczkach używałem kiedyś atoi - jest dostatecznie szybkie. fgets ma
> jedną dodatkową wartwę po drodze do read.


O jakim dokładnie read mówisz? w stdio nic takiego nie widzę.


>> U nas tablica mieszająca i tak pewnie zasłoniłaby swoim czasem
>> działania szczegóły wczytywania.
>
> Dla takich problemów dobra funkcja mieszająca to taka, która działa
> możliwie liniowo. Zrobiłbym wektor wskaźników na funkcję do wykrywania
> końca linii i lookup do robienia to_lower - w takiej konfiguracji
> czytanie bajt-po-bajcie kontra czytanie blokami da duuużą różnicę.

"wektor wskaźników do wykrywania końca linii"?


>>> Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w
>>> sumie).
>>
>> O zapomnialem o tym. Tablica na 256 elementów to nie problem,
>
> O ile wejście jest 8-bit/znak - wtedy użyłbym w sumie jumptable.

Nie wyjdzie z grubsza na to samo? A 256 bajtów pewnie ładnie
się blisko procesora zmieści.


>> a dzieki temu za darmo mamy utożsamienie wszystkich białych
>> znaków, interpunkcji etc.
>
> 256*4/8bajty na wskaźnik całkiem nieźle rezyduje w cache. O ile tylko
> jumptable nie zepsuje za bardzo pipeline to powinna wymiatać.

Nadal nie widzę przewagi. Może nie wiem, co dokładnie masz na myśli.


> Tak w ogóle teraz mnie deadline ścigają ale za jakieś 2 tygodnie to może
> skrobnę programik - będzie można zrobić konkurs ;)

Można zrobić. Teraz święta, a 2 tygodnie to i pewnie firowy
konkurs minie. Tylko skoro potępiłeś maszynkę, trzeba będzie
jakoś to sprawiedliwie mierzyć;)

Jakiś zestaw ebooków się znajdzie;)

pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 23:55:08 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-28 21:50, Michoo pisze:
>
>
>
> >
>
> > W znanych mi implementacjach tak - jest automat zjadający wejście i
>
> > wypluwający wyjście (pobierając/zapisując kolejne rekordy ze stosu)
>
> > (hmmm, ciekawe, czy printf jest turing complete ;) ).
>
>
>
> To nie linuksowy edytor tekstu;-)
>
>
>
>
>
> >>
>
> >>> No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
>
> >>> jeszcze lepiej mmap
>
> >>
>
> >> W przykładzie który widziałem (właśnie z takich konkursików)
>
> >> gość użył fgets + bufor + własne przerabianie na liczby.
>
> >
>
> > Na potyczkach używałem kiedyś atoi - jest dostatecznie szybkie. fgets ma
>
> > jedną dodatkową wartwę po drodze do read.
>
>
>
>
>
> O jakim dokładnie read mówisz? w stdio nic takiego nie widzę.
>
>
>
>
>
> >> U nas tablica mieszająca i tak pewnie zasłoniłaby swoim czasem
>
> >> działania szczegóły wczytywania.
>
> >
>
> > Dla takich problemów dobra funkcja mieszająca to taka, która działa
>
> > możliwie liniowo. Zrobiłbym wektor wskaźników na funkcję do wykrywania
>
> > końca linii i lookup do robienia to_lower - w takiej konfiguracji
>
> > czytanie bajt-po-bajcie kontra czytanie blokami da duuużą różnicę.
>
>
>
> "wektor wskaźników do wykrywania końca linii"?
>
>
>
>
>
> >>> Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w
>
> >>> sumie).
>
> >>
>
> >> O zapomnialem o tym. Tablica na 256 elementów to nie problem,
>
> >
>
> > O ile wejście jest 8-bit/znak - wtedy użyłbym w sumie jumptable.
>
>
>
> Nie wyjdzie z grubsza na to samo? A 256 bajtów pewnie ładnie
>
> się blisko procesora zmieści.
>
>
>
>
>
> >> a dzieki temu za darmo mamy utożsamienie wszystkich białych
>
> >> znaków, interpunkcji etc.
>
> >
>
> > 256*4/8bajty na wskaźnik całkiem nieźle rezyduje w cache. O ile tylko
>
> > jumptable nie zepsuje za bardzo pipeline to powinna wymiatać.
>
>
>
> Nadal nie widzę przewagi. Może nie wiem, co dokładnie masz na myśli.
>
>
>
>
>
> > Tak w ogóle teraz mnie deadline ścigają ale za jakieś 2 tygodnie to może
>
> > skrobnę programik - będzie można zrobić konkurs ;)
>
>
>
> Można zrobić. Teraz święta, a 2 tygodnie to i pewnie firowy
>
> konkurs minie. Tylko skoro potępiłeś maszynkę, trzeba będzie
>
> jakoś to sprawiedliwie mierzyć;)
>
>
>
> Jakiś zestaw ebooków się znajdzie;)
>

co do czytania z pliku to mysle ze mozna to
olać bo (jak mysle) czas odczytania tego z dysku
wlasnie bedzie zapewne wiekszy (?) niz czas wykonania
samej kalkulacji

jaki jest 'zamortyzowany' ;) koszt odczytania
jednego bajta/kilobajta/megabajta z dysku ?
dla megabajta (powiedzmy ze ksiazka wejsciowa)
to byloby pewnie rzedu (uwaga grube oszacowanie
bo nie bardzo wiem;) z 1/50 sekundy (= 20 ms)
pewnie w praktyce - ten rozruch glowicy itp
to powodowaloby ze jest to wiecej 50-100, 200 ms?

jesli 200 ms to same obliczenia mz powinny trwac mniej niz tyle (bo ja bym ozacowal
ze te obliczenia
powinny sie chyba wyrobic pod 50 ms - ale tez zgrubne oszacowanie )

do góry

W dniu piątek, 29 marca 2013 11:41:56 UTC+1 użytkownik firr kenobi napisał:
> W dniu czwartek, 28 marca 2013 23:55:08 UTC+1 użytkownik bartekltg napisał:
>
> > W dniu 2013-03-28 21:50, Michoo pisze:
>
> >
>
> >
>
> >
>
> > >
>
> >
>
> > > W znanych mi implementacjach tak - jest automat zjadający wejście i
>
> >
>
> > > wypluwający wyjście (pobierając/zapisując kolejne rekordy ze stosu)
>
> >
>
> > > (hmmm, ciekawe, czy printf jest turing complete ;) ).
>
> >
>
> >
>
> >
>
> > To nie linuksowy edytor tekstu;-)
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > >>
>
> >
>
> > >>> No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
>
> >
>
> > >>> jeszcze lepiej mmap
>
> >
>
> > >>
>
> >
>
> > >> W przykładzie który widziałem (właśnie z takich konkursików)
>
> >
>
> > >> gość użył fgets + bufor + własne przerabianie na liczby.
>
> >
>
> > >
>
> >
>
> > > Na potyczkach używałem kiedyś atoi - jest dostatecznie szybkie. fgets ma
>
> >
>
> > > jedną dodatkową wartwę po drodze do read.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > O jakim dokładnie read mówisz? w stdio nic takiego nie widzę.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > >> U nas tablica mieszająca i tak pewnie zasłoniłaby swoim czasem
>
> >
>
> > >> działania szczegóły wczytywania.
>
> >
>
> > >
>
> >
>
> > > Dla takich problemów dobra funkcja mieszająca to taka, która działa
>
> >
>
> > > możliwie liniowo. Zrobiłbym wektor wskaźników na funkcję do wykrywania
>
> >
>
> > > końca linii i lookup do robienia to_lower - w takiej konfiguracji
>
> >
>
> > > czytanie bajt-po-bajcie kontra czytanie blokami da duuużą różnicę.
>
> >
>
> >
>
> >
>
> > "wektor wskaźników do wykrywania końca linii"?
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > >>> Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w
>
> >
>
> > >>> sumie).
>
> >
>
> > >>
>
> >
>
> > >> O zapomnialem o tym. Tablica na 256 elementów to nie problem,
>
> >
>
> > >
>
> >
>
> > > O ile wejście jest 8-bit/znak - wtedy użyłbym w sumie jumptable.
>
> >
>
> >
>
> >
>
> > Nie wyjdzie z grubsza na to samo? A 256 bajtów pewnie ładnie
>
> >
>
> > się blisko procesora zmieści.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > >> a dzieki temu za darmo mamy utożsamienie wszystkich białych
>
> >
>
> > >> znaków, interpunkcji etc.
>
> >
>
> > >
>
> >
>
> > > 256*4/8bajty na wskaźnik całkiem nieźle rezyduje w cache. O ile tylko
>
> >
>
> > > jumptable nie zepsuje za bardzo pipeline to powinna wymiatać.
>
> >
>
> >
>
> >
>
> > Nadal nie widzę przewagi. Może nie wiem, co dokładnie masz na myśli.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > > Tak w ogóle teraz mnie deadline ścigają ale za jakieś 2 tygodnie to może
>
> >
>
> > > skrobnę programik - będzie można zrobić konkurs ;)
>
> >
>
> >
>
> >
>
> > Można zrobić. Teraz święta, a 2 tygodnie to i pewnie firowy
>
> >
>
> > konkurs minie. Tylko skoro potępiłeś maszynkę, trzeba będzie
>
> >
>
> > jakoś to sprawiedliwie mierzyć;)
>
> >
>
> >
>
> >
>
> > Jakiś zestaw ebooków się znajdzie;)
>
> >
>
>
>
> co do czytania z pliku to mysle ze mozna to
>
> olać bo (jak mysle) czas odczytania tego z dysku
>
> wlasnie bedzie zapewne wiekszy (?) niz czas wykonania
>
> samej kalkulacji
>
>
>
> jaki jest 'zamortyzowany' ;) koszt odczytania
>
> jednego bajta/kilobajta/megabajta z dysku ?
>
> dla megabajta (powiedzmy ze ksiazka wejsciowa)
>
> to byloby pewnie rzedu (uwaga grube oszacowanie
>
> bo nie bardzo wiem;) z 1/50 sekundy (= 20 ms)
>
> pewnie w praktyce - ten rozruch glowicy itp
>
> to powodowaloby ze jest to wiecej 50-100, 200 ms?
>
>
>
> jesli 200 ms to same obliczenia mz powinny trwac mniej niz tyle (bo ja bym ozacowal
ze te obliczenia
>
> powinny sie chyba wyrobic pod 50 ms - ale tez zgrubne oszacowanie )

w zasadzie to mozna tez tego nie olewac tylko
wtedy zrobi sie to ew konkurs na optymalizowanie
operacji wczytywania pliku z dysku - tez bardzo
ciekawa sprawa, w zasadzie to dla mnie wlasnie
nawet ciekawsze tyle ze nie znam sie na tym

do góry

W dniu piątek, 29 marca 2013 11:41:56 UTC+1 użytkownik firr kenobi napisał:
> co do czytania z pliku to mysle ze mozna to
> olać bo (jak mysle) czas odczytania tego z dysku
Moja propozycja jest taka, żeby wczytać plik i N razy
wykonać zadanie w pamięci RAM. Stoper uruchamiamy po
wczytaniu pliku.
Pozdrawiam

do góry

W dniu piątek, 29 marca 2013 11:44:39 UTC+1 użytkownik firr kenobi napisał:
> w zasadzie to mozna tez tego nie olewac tylko
> wtedy zrobi sie to ew konkurs na optymalizowanie
> operacji wczytywania pliku z dysku - tez bardzo
> ciekawa sprawa, w zasadzie to dla mnie wlasnie
> nawet ciekawsze tyle ze nie znam sie na tym
Jest ciekawe, można zrobić dwie kategorie:
a) czas wykonania całego programu
b) czas wykonania bez czasu wczytania
Pozdrawiam

do góry

>
>
> jaki jest 'zamortyzowany' ;) koszt odczytania
> jednego bajta/kilobajta/megabajta z dysku ?
> dla megabajta (powiedzmy ze ksiazka wejsciowa)
> to byloby pewnie rzedu (uwaga grube oszacowanie
>
> bo nie bardzo wiem;) z 1/50 sekundy (= 20 ms)
> pewnie w praktyce - ten rozruch glowicy itp
> to powodowaloby ze jest to wiecej 50-100, 200 ms?
>
>
>
> jesli 200 ms to same obliczenia mz powinny trwac mniej niz tyle (bo ja bym ozacowal
ze te obliczenia
> powinny sie chyba wyrobic pod 50 ms - ale tez zgrubne oszacowanie )






Dokonałem pewnych prostych testów i wyniki mnie zszokowały :U (mam w domu naprawde
starego kompa i stary dysk tak ze to sa dane dla mojego sprzetu, mam nadzieje ze nic
z testem nie zbabrałem ale chyba nie)

wczytanie pilku 1MB przec fgetc - mw 11 milisekund (powtarzane kilka razy, wiec z
cache)


pierwszy szok bo mz jest to nieslychanie szybko, wydawalo mi sie ze to powinno byc z
10 razy wolniej

wczytanie pilku 300 bajtow przec fgetc - mw 0.2 milisekundy



wczytanie pilku 10MB przec fgetc - mw 120 milisekundy (kolene uruchomienia) -
pierwsze uruchomienie 1.2 sekundy


szybko, widac ze z cache działa 10x szybciej niz
bez

wczytanie pilku 1MB przec fread - mw 3 ms (kolene uruchomienia)


kojejny szok, wczytywanie przez fread jest 3-4 razy szybsze niz przez fgetc - w zyciu
bym sie nie spodziewal bo przeciez wydaje sie ze fgetc mozna zrobic jako b lekki
wrapper na fread i powinno byc to samo a tu tymczasem jednak nie :/

wczytanie pilku 10MB przec fread - mw 31 ms (kolene uruchomienia)


[okazalo sie ze przeszacowałem (tj przynajmniej
dla wynikow lecacych z cache jest cholernie
szybko, dla pierwszego wczytania juz jest realistycznie eolniej) akurat przegapilem
wersje dal 1MB bez cache ale pewnie gdzies tak okolo 100 ms czyli mw zgodnie z
oszacowaniem ]

do góry

W dniu piątek, 29 marca 2013 12:23:11 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 29 marca 2013 11:44:39 UTC+1 użytkownik firr kenobi napisał:
>
> > w zasadzie to mozna tez tego nie olewac tylko
>
> > wtedy zrobi sie to ew konkurs na optymalizowanie
>
> > operacji wczytywania pliku z dysku - tez bardzo
>
> > ciekawa sprawa, w zasadzie to dla mnie wlasnie
>
> > nawet ciekawsze tyle ze nie znam sie na tym
>
> Jest ciekawe, można zrobić dwie kategorie:
>
> a) czas wykonania całego programu
> b) czas wykonania bez czasu wczytania
>

to nawet bylby dosyc rozwojowy konkurs -

gdyby w pierwszym wypadku to pewnie nalezaloby
zarzucic asynchroniczny read na pliku i juz w trakcie wczytywania go przetwarzac -
nie wiem
czy da sie tak robic w takiej malej skali
czasowej tj w ciagu mw kilkudziesieciu
milisekund - moze..

do góry

W dniu piątek, 29 marca 2013 13:52:54 UTC+1 użytkownik firr kenobi napisał:
> to nawet bylby dosyc rozwojowy konkurs -
To czy bedzie rozwojowy czy nie, bedzie zalezalo od tego
kto sie ile w trakcie konkursu nauczy :)

Trochę zabawy przy tym jest... może napiszę...
nie wiem jeszcze.


> gdyby w pierwszym wypadku to pewnie nalezaloby
> zarzucic asynchroniczny read na pliku i juz w trakcie
> wczytywania go przetwarzac - nie wiem
Można coś lepiej wykombinować niż wczytanie pliku do RAM
jednym wywołaniem funkcji read?

Pozdrawiam

do góry

W dniu piątek, 29 marca 2013 15:33:01 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 29 marca 2013 13:52:54 UTC+1 użytkownik firr kenobi napisał:
>
> > to nawet bylby dosyc rozwojowy konkurs -
>
> To czy bedzie rozwojowy czy nie, bedzie zalezalo od tego
>
> kto sie ile w trakcie konkursu nauczy :)
>
>
>
> Trochę zabawy przy tym jest... może napiszę...
>
> nie wiem jeszcze.
>
>
>
>
>
> > gdyby w pierwszym wypadku to pewnie nalezaloby
>
> > zarzucic asynchroniczny read na pliku i juz w trakcie
>
> > wczytywania go przetwarzac - nie wiem
>
> Można coś lepiej wykombinować niż wczytanie pliku do RAM
>
> jednym wywołaniem funkcji read?
>

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

do góry

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?
Pozdrawiam

do góry