Vykonostni triky
5 views
Skip to first unread message
Jan Seidl
Jun 26, 2010, 2:13:27 PM6/26/10
to perl_cz
Zdravim.
Jiz nekolik dni se snazim o co nejrychlejsi zpusob, jak setridit
ohromne kvantum dat, presne receno stringu v dalo by se rici pevnem
formatu z cca 20fajli do jednoho. Z mnoha duvodu to je treba delat
perlem a ne treba Cckem kde by asi mnoho problemu ktere mam odpadlo.
Jelikoz stringu je neco kolem 37milionu (a budou pribyvat), neni mozne
nacteni do pameti a sort. Nasadili jsme tedy metodu, kdy nacitam z
kazdeho fajle jeden radek (zapomel jsem rict, ze v tech fajlich jsou
stringy jiz serazeny) do hashe, potom je zesortuju, prvni zesortovany
prvek vkladam do vystupniho fajle a nactu ze souboru z ktereho byl
tento string string dalsi. Sesortuju... Tento zpusob funugje velice
kvalitne nicmene potreboval bych aby pracoval rychleji (jen pro
predstavu, tech 37M zaznamu trva cca 490vterin).
Pouzil jsem tedy misto hashe a sort na hash pole a binarni zarazovani
(vlastne princip binarniho hledani ale misto toho ze hledam nejaky
prvek, tak se hleda misto kam prvek vlozit). To mi beh zrychlilo cca o
20s. Dale jsem provedl optimalizaci vsech regexu, ktere jsem nahradil
za substr popr uplne zrusil, coz mi poskytlo dalsi zrychleni. Dale
jsem pak zkousel nahradit klasicke open a $row = <FILE> za sysread a
nacital jsem velke vstupni bloky do bufferu, ktery jsem nasledne
parsoval a to same na vystup. Nakonec jsem i nasel vyhodne konstanty
kolik radku nacist do vstupu a vystupu aby to bylo co
nejeefektivnejsi, ackoliv casove zrychleni je trosku sporne (dle
profileru je zrychleni v i/o opecacich slusne ale zpomaleni se projevi
jinde), avsak rychlost je stale nedostacujici. Posledni pokus byl
zainlajnovani nekterych funkci, coz take nepatrne pomohlo, nicmene
jsem ted s napady v koncich. Dalsi moznost ktero budu v dohledne dobe
testovat je binarni nacitani. Tzn. nactu jen dva fajle, porovnam a
vystup porovnam s dalsim, atd... Zatim testy vypadji docela slibne.
Navic by byla mozna paralelizace, pokud ovsem neni brzda prave cteni a
zapis na disk.
Pokud mate nekdo napad jak na to, ci dalsi 'performance' triky, budu
rad kdyz se semnou o ne podelite.
Jiz nekolik dni se snazim o co nejrychlejsi zpusob, jak setridit
ohromne kvantum dat, presne receno stringu v dalo by se rici pevnem
formatu z cca 20fajli do jednoho. Z mnoha duvodu to je treba delat
perlem a ne treba Cckem kde by asi mnoho problemu ktere mam odpadlo.
Jelikoz stringu je neco kolem 37milionu (a budou pribyvat), neni mozne
nacteni do pameti a sort. Nasadili jsme tedy metodu, kdy nacitam z
kazdeho fajle jeden radek (zapomel jsem rict, ze v tech fajlich jsou
stringy jiz serazeny) do hashe, potom je zesortuju, prvni zesortovany
prvek vkladam do vystupniho fajle a nactu ze souboru z ktereho byl
tento string string dalsi. Sesortuju... Tento zpusob funugje velice
kvalitne nicmene potreboval bych aby pracoval rychleji (jen pro
predstavu, tech 37M zaznamu trva cca 490vterin).
Pouzil jsem tedy misto hashe a sort na hash pole a binarni zarazovani
(vlastne princip binarniho hledani ale misto toho ze hledam nejaky
prvek, tak se hleda misto kam prvek vlozit). To mi beh zrychlilo cca o
20s. Dale jsem provedl optimalizaci vsech regexu, ktere jsem nahradil
za substr popr uplne zrusil, coz mi poskytlo dalsi zrychleni. Dale
jsem pak zkousel nahradit klasicke open a $row = <FILE> za sysread a
nacital jsem velke vstupni bloky do bufferu, ktery jsem nasledne
parsoval a to same na vystup. Nakonec jsem i nasel vyhodne konstanty
kolik radku nacist do vstupu a vystupu aby to bylo co
nejeefektivnejsi, ackoliv casove zrychleni je trosku sporne (dle
profileru je zrychleni v i/o opecacich slusne ale zpomaleni se projevi
jinde), avsak rychlost je stale nedostacujici. Posledni pokus byl
zainlajnovani nekterych funkci, coz take nepatrne pomohlo, nicmene
jsem ted s napady v koncich. Dalsi moznost ktero budu v dohledne dobe
testovat je binarni nacitani. Tzn. nactu jen dva fajle, porovnam a
vystup porovnam s dalsim, atd... Zatim testy vypadji docela slibne.
Navic by byla mozna paralelizace, pokud ovsem neni brzda prave cteni a
zapis na disk.
Pokud mate nekdo napad jak na to, ci dalsi 'performance' triky, budu
rad kdyz se semnou o ne podelite.
Jakub Kotrla
Jun 26, 2010, 5:46:42 PM6/26/10
to perl_cz
Ahoj,
z hlediska algoritmu resis neco, cemu se rika vnejsi trideni, s tim, ze mas vyhodu v setridenosti filu.
Problem je imho docela dobre prozkouman viz napr. - http://en.wikipedia.org/wiki/Polyphase_merge_sort
coz jsi defakto vymyslel taky - nacitani vice radku nez jednoho.
Technicky to jen slevas, ze?
Pokud by slo o zrychleni na urovni zmeny algoritmu, potrebujes datovou strukturu s co nejrychlejsim insertem a getMin.
Myslim, ze na to jsou delane nejake haldy - http://en.wikipedia.org/wiki/Heap_(data_structure)
Nicmene naprogramovat je uz neni uplne trivialni, hadal bych z ena to bude neco na cpanu - napr http://search.cpan.org/~jmm/Heap-0.80/lib/Heap.pm.
Muze byt zajimave napsat si pouze implementaci takove struktury v C a pouzit ji pak v Perlu (nedelal jsem ale verim, ze to jde).
Pokud bys mel napriklad pevny pocet vstupnich souboru, mohl by jsi trideni nahradit napevno vytvorenymi ify - defakto naimplementujes tridici sit.
(takova vec se da generovat, takze technicky neni ruzny pocet vstupnich souboru zabranou).
Samotne porovnani v pameti je rychle, jde o co nejmensi pocet cteni a zapisu - a pak to pujde az do minimalizace nejakych cache-miss, planovani disku a to uz clovek neovlivni.
JK
2010/6/26 Jan Seidl <unaven...@gmail.com>
Jan Seidl
Jun 29, 2010, 5:02:48 AM6/29/10
to perl_cz
Ahoj,
diky za tipy. Urcite zvazim ten Heap;) Nicmene ted to resim pres
pole, coz je podle me nejrychlejsi dynamicky prvek v perlu (pevnou
strukturu pouzit nemuzu) jinak ne ze by me uz nekolikrat nenapadlo,
jestli by to nebylo jednodussi cele napsat v cecku, ale proste to
nejde;)
Jinak porovnavani v pameti je v pohode, dokonce jsem myslim docela
odladil to nacitani a vypisovani po blocich pomoci sysread, syswrite.
Teda porad nevim jestli by neslo lepe ten vystupni buffer, ktery delam
pres pole a join (spojovani pres tecku je docela pomale kvuli tomu ze
to pokazde delat realoc?) Ale zjisitl jsem, ze je docela velke
zpomaleni na funkcich ktere parsuji ty vstupni fajle (oni totiz nejsou
uplne stejne a musi se lehce unikovat - samozrejme bez regularnich
vyrazu).
Aktualne zkousim nacteni a porovnani pouze dvou fajli (tzn fakticky
jednoduchy if radek vetsi mensi), takze algoritmus velice jednoduchy,
nicmene je vetsi mnozstvi zapisu a datove narocnosti na disk. Zase
vyhoda ze by se to dalo poustet i paralelne. Zatim se to tvarilo
rychle, nez jsem to zacal parsovat, tim se to nekolikrat zpomalilo.
Ted to musim zkusit odprofilovat.
Mimochodem, musim doporucit profiler NYTProf (http://search.cpan.org/
dist/Devel-NYTProf-4.03/lib/Devel/NYTProf.pm), jsem s nim dost
spokojen=)
On 26 čvn, 23:46, Jakub Kotrla <ja...@kotrla.net> wrote:
> Ahoj,
> z hlediska algoritmu resis neco, cemu se rika vnejsi trideni, s tim, ze mas
> vyhodu v setridenosti filu.
> Problem je imho docela dobre prozkouman viz napr. -http://en.wikipedia.org/wiki/Polyphase_merge_sort
diky za tipy. Urcite zvazim ten Heap;) Nicmene ted to resim pres
pole, coz je podle me nejrychlejsi dynamicky prvek v perlu (pevnou
strukturu pouzit nemuzu) jinak ne ze by me uz nekolikrat nenapadlo,
jestli by to nebylo jednodussi cele napsat v cecku, ale proste to
nejde;)
Jinak porovnavani v pameti je v pohode, dokonce jsem myslim docela
odladil to nacitani a vypisovani po blocich pomoci sysread, syswrite.
Teda porad nevim jestli by neslo lepe ten vystupni buffer, ktery delam
pres pole a join (spojovani pres tecku je docela pomale kvuli tomu ze
to pokazde delat realoc?) Ale zjisitl jsem, ze je docela velke
zpomaleni na funkcich ktere parsuji ty vstupni fajle (oni totiz nejsou
uplne stejne a musi se lehce unikovat - samozrejme bez regularnich
vyrazu).
Aktualne zkousim nacteni a porovnani pouze dvou fajli (tzn fakticky
jednoduchy if radek vetsi mensi), takze algoritmus velice jednoduchy,
nicmene je vetsi mnozstvi zapisu a datove narocnosti na disk. Zase
vyhoda ze by se to dalo poustet i paralelne. Zatim se to tvarilo
rychle, nez jsem to zacal parsovat, tim se to nekolikrat zpomalilo.
Ted to musim zkusit odprofilovat.
Mimochodem, musim doporucit profiler NYTProf (http://search.cpan.org/
dist/Devel-NYTProf-4.03/lib/Devel/NYTProf.pm), jsem s nim dost
spokojen=)
On 26 čvn, 23:46, Jakub Kotrla <ja...@kotrla.net> wrote:
> Ahoj,
> z hlediska algoritmu resis neco, cemu se rika vnejsi trideni, s tim, ze mas
> vyhodu v setridenosti filu.
> coz jsi defakto vymyslel taky - nacitani vice radku nez jednoho.
>
> Technicky to jen slevas, ze?
> Pokud by slo o zrychleni na urovni zmeny algoritmu, potrebujes datovou
> strukturu s co nejrychlejsim insertem a getMin.
> Myslim, ze na to jsou delane nejake haldy -http://en.wikipedia.org/wiki/Heap_(data_structure)
>
> Technicky to jen slevas, ze?
> Pokud by slo o zrychleni na urovni zmeny algoritmu, potrebujes datovou
> strukturu s co nejrychlejsim insertem a getMin.
> Nicmene naprogramovat je uz neni uplne trivialni, hadal bych z ena to bude
> neco na cpanu - naprhttp://search.cpan.org/~jmm/Heap-0.80/lib/Heap.pm.
> Muze byt zajimave napsat si pouze implementaci takove struktury v C a pouzit
> ji pak v Perlu (nedelal jsem ale verim, ze to jde).
>
> Pokud bys mel napriklad pevny pocet vstupnich souboru, mohl by jsi trideni
> nahradit napevno vytvorenymi ify - defakto naimplementujes tridici sit.
> (takova vec se da generovat, takze technicky neni ruzny pocet vstupnich
> souboru zabranou).
>
> Samotne porovnani v pameti je rychle, jde o co nejmensi pocet cteni a zapisu
> - a pak to pujde az do minimalizace nejakych cache-miss, planovani disku a
> to uz clovek neovlivni.
>
> JK
>
> 2010/6/26 Jan Seidl <unavenslun...@gmail.com>
> ji pak v Perlu (nedelal jsem ale verim, ze to jde).
>
> Pokud bys mel napriklad pevny pocet vstupnich souboru, mohl by jsi trideni
> nahradit napevno vytvorenymi ify - defakto naimplementujes tridici sit.
> (takova vec se da generovat, takze technicky neni ruzny pocet vstupnich
> souboru zabranou).
>
> Samotne porovnani v pameti je rychle, jde o co nejmensi pocet cteni a zapisu
> - a pak to pujde az do minimalizace nejakych cache-miss, planovani disku a
> to uz clovek neovlivni.
>
> JK
>
Michal Svoboda
Jun 29, 2010, 7:40:08 AM6/29/10
to per...@googlegroups.com
Jan Seidl wrote:
> Zdravim.
> Jiz nekolik dni se snazim o co nejrychlejsi zpusob, jak setridit
> ohromne kvantum dat, presne receno stringu v dalo by se rici pevnem
> formatu z cca 20fajli do jednoho.
> Zdravim.
> Jiz nekolik dni se snazim o co nejrychlejsi zpusob, jak setridit
> ohromne kvantum dat, presne receno stringu v dalo by se rici pevnem
> formatu z cca 20fajli do jednoho.
> Pokud mate nekdo napad jak na to, ci dalsi 'performance' triky, budu
> rad kdyz se semnou o ne podelite.
> rad kdyz se semnou o ne podelite.
Začal bych asi zde
http://search.cpan.org/~creamyg/Sort-External-0.18/lib/Sort/External.pm
(podle pravidla prve CPAN a pak samo domo)
Michal Svoboda
Reply all
Reply to author
Forward
0 new messages