Něco málo o optimalizaci

Oct 10, 2005 – 14:04

Comments

gospoda
gospoda
O tech pointerech je to dost zasadni zjisteni. Docela bych se o tom rad dozvedel vic. Nemate nekdo nejake linky (mimo tech z prezentace) o problematice ?
gospoda
gospoda
Bill Gates ohlasil kdysi koncept PC, kde kazda operace bude provedena v oka-mziku. Ze by podle nej byly tak velke rezervy v optimalizaci ?
Miloslav Ponkrác
Miloslav Ponkrác
Já bych řekl, že je potřeba nad články, byť renomovaných autorů taky přemýšlet. Nebrat to jako dogma a vědět, že každý, i odborník je postihnutý často jednostranným pohledem.

I datové struktury přes pointery se dají vytvářet v souvislé oblasti paměti a tím pádem je pak naprostý nesmysl to, co píše ten pán z Microsoftu. Pokud máte bloky dat přes pointery v souvislé paměti, pak cache samozřejmě funguje efektivě a swap neswapuje. Takové datové struktury přes pointery v souvislém prostoru paměti jsou samozřejmě mnohem efektivnější, než tupé pole. Je to proto, že většinou sofistikované datové struktury zabírají méně místa, než tupé pole a tak je méně důvodu ke swapování a cache je efektivnější. Ale myslel jsem, že takový pán z Microsoftu bude základní věci znát. K alokaci v souvislém bloku paměti slouží třeba ve Windows lokální heapy.

Mimochodem, každý kdo trochu více programoval ví, že prosté použití operace ve stylu new je sama o sobě poměrně drahá a neefektivní. Proto se v mnoha případech vyvinuly objekty a přístupy, které slouží k efektivní alokaci dynamické paměti na heapu. Dobře to znám třeba z C++.

Pokud daný programovací jazyk nemá možnost ovlivňovat efektivitu operace new (jako třeba Java), pak se to řeší často tak, že je snaha alokovat na zásobníku, což je podstatně efektivnější operace.

Takže, co jsem se vlastně nového dozvěděl?
David Majda
[3]: "I datové struktury přes pointery se dají vytvářet v souvislé oblasti paměti a tím pádem je pak naprostý nesmysl to, co píše ten pán z Microsoftu."

Slajdy samozřejmě zjednodušují, jsem si jistý, že na přednášce bylo důkladně vyvětleno, že není problém ani tak v pointerech ale ve způsobu používání "spousta objektů na heapu alokovaných propojených přes new/malloc propojených přes pointery". Že třeba sekvenční průchod typickým spojákem bude pomalejší než průchod polem se stejnými položkami.

"Takže, co jsem se vlastně nového dozvěděl?"

Zejmě nic :-)
Miloslav Ponkrác
Miloslav Ponkrác
Jenomže to je stejný problém alogoritmizace. Všechno je o vhodném výběru algoritmu. Já z toho mám prostě dojem, že ten pán z Microsoftu znovuobjevuje Ameriku. Možná je to trend poslední doby, že se vyvíjejí vývojářské nástroje, které se vás snaží odstínit od co největšího počtu věcí, takže následkem toho mnoho lidí zapomíná přemýšlet nad vlastnostmi algoritmů a prostě jenom bouchá kód. A pak rozdávají moudra. Moc se omlouvám, že to píšu takhle s despektem.

Pokud povaha dat je taková, že mi stačí obyčejné pole, proč toho nepoužít. Ale pokud často děláte takové akce, jako je vkládání prvků doprostřed pole, nebo častá změna velikosti pole, může se stát, že veškerý výkon utlučete na těchto operacích navzdory tomu, že procházejí polem je rychlejší, než třeba spojákem. Takže jde jenom o to ušít vhodné datové struktury pro konkrétní úlohu. Někdy vyjde jako nejlepší pole, někdy spoják, někdy strom, někdy něco jiného. Generalizovat se tady nedá. Každý typ datové struktury mé své silné a své slabé stránky a záleží na tom, abych si správně vybral, co zrovna potřebuji.

Kromě toho rozhodně není správná informace, že při použití pole se nemůžete dostat do situace, kdy cache selhává a swapuje se jako blázen. Bohatě stačí dostat se do situace, kdy prostě přistupuji k prvkům pole náhodně, tedy ne sekvenčně a můžu být úplně ve stejné situaci, kdy nadměrně zatěžuji operační systém, který nestíhá obsluhovat výpadky stránek a tedy swapuje jako blázen.

Obecně platí podle mých zkušeností, že rozsáhlejší struktury, ke kterým se nepřistupuje sekvenčně mají větší výkon právě při použití pointerů a dynamických datových struktur. Tedy mám skoro opačnou zkušenost, než se popisuje. Jenomže je tu jedno velké ale! Ten větší výkon není automaticky, ale s pointery a dynamickou pamětí musí člověk vědět, jak má zacházet, jinak výsledek není takový, jak by mohl být. Protože dnes už málokdo umí algoritmizovat, spíše se prosazuje trend bouchání kódu z předpřipravených hotových knihoven, pak mnoho lidí dojde k závěru, že pointry jsou pomalé. Ale IMHO to není pravda, podle mě je to právě naopak, jenomže prostě většina lidí už efektivně programovat neumí a pak píše takové články, které obsahují jenom půl pravdy.

Je třeba ještě na doplnění napsat, že pokud člověk chce uložit pět prvků do nějaké struktury, tak nemá smysl přemýšlet, co použije. Pak prostě klidně bez přemýšlení to strčím do pole a není co optimalizovat. I o tom je optimalizace, optimalizovat jenom to, co má smysl a co má SKUTEČNÝ vliv na rychlost.




David Majda
[5] Já bych neřekl, že Raymond znovuobjevuje Ameriku. Jen ukazuje, že někdy je lepší "optimalizovat na cache" než "optimalizovat na óčka" (óčka = O(n*log(n)) apod.). Mě tohle třeba doteď nenapadlo.

Že to je závislé případ od případu a že je nutno přizpůsobit datovou strukturu povaze dat a apliakce, je samozřejmé.

Jinak Raymonda Chena si jako programátora dost vážím - občas je poučné číst jeho blog. Rozhodně bych o něm nemluvil s despektem.

K tomu, že programátoři dnes neumějí efektivně programovat: Na toto téma by se dalo dlouze diskutovat, na což teď nemám čas. Troufnu si ale říct, že je to způsobeno jednak víceméně konstantním počtem opravdu schopných lidí v kontrastu s expanzí IT jako oboru a pak také ekonomikou (schopnost "efektivně programovat" není trhem tolik ceněna jako jiné schopnosti, a tedy i programátoři potenciálně schopní programovat efektivně nejsou nuceni se to neaučit, případně to umí ale nevužijí, protože to od nich není požadováno - přednější je třeba rychlost dodání řešení nebo jiné vlastnosti).
Miloslav Ponkrác
Miloslav Ponkrác
No, ono je lepší optimalizovat na obojí. Pokud nemáte opravdu rozsáhlé struktury, tak "optimalizovat na cache" vám v podstatě žádné výsledky nepřinese a v podstatě nemá smysl se tím vůbec zabývat. Pokud máte rozsáhlé struktury, tak se stačí držet pravdidla, že příbuzné věci, ke kterým se společně najednou přistupuje by měly být v paměti vedle sebe a to je v podstatě celá "optimalizace na cache". Líp to nevymyslíte, to je celé kouzlo. A udržet příbuzné struktury vedle sebe je mnohdy mnohem snažší s pointery, zvláště pokud nemůžete mít sekvenční přístup k prvkům. Tedy tvrdím, že často platí pravý opak toho, co napsal Raymond Chen.

Co se týká poslední odstavce naprosto souhlasím. Ekonomické zákony IT si vynucují rychlé programování, nikoli efektivní programování. Jsem nucen se tomu také podřizovat a tento aspekt chápu. Proto jsem taky psal, že optimalizovat se má tam, kde to má smysl.

Add comment

It is not possible to add comments to posts older than one month.