R-stromy a moje bakalarka :-/ – Offtopic – Fórum – Programujte.com

Lidi co si o tom myslite, dostal jsem za ukol do existujici implementace databazove aplikace, ktera umi mimojine cist data do R-stromu, udelat paralelismus pro vkladani a dotazovani na ten R-strom. Vyvijelo to par ucitelu databazistu z katedry informatiky. Nedari se mi to tim paralelismem poradne zrychlit a ted jsem tak premyslel nad tim, jak bych to cele napsal ja a trochu se divim.

Kdyz chci implementovat R-strom, tak to jako jakykoliv jiny strom funguje tak, ze znam vlastne jen korenovy prvek toho stromu. Ten obsahuje odkazy na potomky. Takto tim stromem prochazim. Nikde by tam nemelo dochazet k zadne kolizi a nemusim v prubehu mechanizmu iterace pouzivat zadne kriticke sekce, kdyz je to dobře (resp. normálně) udělané.

Ale v tomhle pripade to tak neni. nechapu proc, ale vsechny uzly stromu spravuje jedina sdilena trida - jakasi cache pro uzly. Kdyz se pozaduje nejaky uzel, musi se k nemu pres tuhle tridu. Tu jsem musel celou osetrit kritickyma sekcema. A to neni vsechno. Aplikace si zaznamenava do sdilene tridy taky ruzne statistiky a to vse V PRUBEHU ITERACE STROMU (takze dalsi kriticke sekce)  mimoto pouziva taky sdileny MemoryPool, ktery krome toho ze nefunguje moc dobre, musi byt zase osetreny kritickyma sekcema takze soubeh zase zhorsuje. Cela aplikace je dost slozita na to, abych ji mohl/chtel pochopit a menit mechanismus jak funguje, protoze bych to musel cele prekopat. 

Vysledek je, ze ve vice vlaknech jsou dotazy na prvky v R-stromu rychlejsi cca jen o 10-30% (na serverovem procesoru co ma 20 jader), vic se to nehne, protoze se to porad blokuje.

Mam trochu obavy z toho, co rekne ucitel na to, ze to je o tak malo rychlejsi. Ale zase si rikam, ze kdyz to maji takhle napsane, tak pro prece nemuzou nic vic cekat  

Co si myslite?

Vlastne, davam to sem proto, ze tak jak tomu rozumim se mi to zda PODIVNE, ale ze tu prispiva treba nejaky dobry programator se zkusenostmi co rekne, ze se to tak treba musi delat z toho a onoho duvodu...nevim z jakeho, jsem jen student :-)

no minimalne statistiky a podobne bych nedelal kritickejma sekcema, ale atomickejma operacema ... (pokud to jde)

zajimave by mohlo byt treba na prvni urovni zamykat jen jednu vetev stromu, a ne cely,... u paralelniho pristupu do jine casti by to pak nezdrzovalo... (to same testy, aby zasahovaly nahodne vsude)  ... ale bude zalezet, jak to cele vypada

KIIV: jde prave o to, ze teoreticky, v pripade cteni ze by se za normalni implementcxe nemuselo nic zamykat - jenom se cte a to se navzajem neovlivuje. Jenomze tady to takhle neni. Vy znate nejaky duvod, proc pri implementaci stromu pouzivat vlastni cache, misto abyste nechal C++ aby si organizovalo pamet samo? Napriklad je tam taky MemoryPool - kdyz se vytvari nejake promenne, nevytvari se normalne ale berou se z te MemoryPool. Jestli mi rozumite, tohle vsechno jsou veci, ktere ten paralelismus brzdi, protoze tam musim vsude strkat kriticke sekce. Vubec nechapu proc to takhle komplikovane maji udelane a navic se tam pak spatne dela paralelismus.

http://en.wikipedia.org/…/Memory_pool Tady ctu, ze MemoryPool je z najakeho duvodu rychlejsi nez malloc a operatory new. Rekl by mi ale nekdo, jestli je rychlejsi i v pripade, ze pouzivam vlakna a ty se budou v tom vlastnorucne napsanym memory pool blokovat? Mozna ze pouzivat memoruy pool je rychlejsi v pripade jednovláknové aplikace, ale je to pak i rychlejsi i ve vicevlaknovych aplikaci? Potrebuju se v ramci te bakalarky nejak obhajit ze to tam proste nemuzu udelat lip hernajs   

Oukej, tak uz se to vyresilo, pry se pocitalo s tim ze ten paralelismus tam nebude kdovi jaky.