Java: byte to 8 boolean

[Jakub Galgonek]

A ještě jedna věc. Násobení velkých matic tímhle primitivním způsobem bude pomalé už z principu. Druhou matici opakovaně procházíte po sloupcích. Kdyžtak tu druhou matici aspoň transponujte ať se k oběma přistupuje sekvenčně. Takhle je všechno schované za výpadky cache u druhé matice.

Jo, tím se to (pro matici 2000x2000) stáhne na 5s, což je 18x rychlejší, než ta původní implementace.

[Reklama]

[Filip Jirsák]

Ještě tu nezazněla jedna věc. Při násobení matic jsou jednotlivé prvky výsledné matice na sobě nezávislé, je to tedy ideální kandidát na paralelizaci – když máte dost jader, může jednu buňku matice počítat jedno jádro. Pak je možné řešit takové optimalizace, aby jednotlivá vlákna výpočtu s výhodou používala data načtená jiným vláknem.

[Tomáš Marný]

Ještě tu nezazněla jedna věc. Při násobení matic jsou jednotlivé prvky výsledné matice na sobě nezávislé, je to tedy ideální kandidát na paralelizaci – když máte dost jader, může jednu buňku matice počítat jedno jádro. Pak je možné řešit takové optimalizace, aby jednotlivá vlákna výpočtu s výhodou používala data načtená jiným vláknem.

Např. dnešní překladače Fortranu tohleto udělají za vás samy.

[kolemjdouci]

A ještě jedna věc. Násobení velkých matic tímhle primitivním způsobem bude pomalé už z principu. Druhou matici opakovaně procházíte po sloupcích. Kdyžtak tu druhou matici aspoň transponujte ať se k oběma přistupuje sekvenčně. Takhle je všechno schované za výpadky cache u druhé matice.

Správná poznámka, zvláště pro matice velkého rozměru.
Jen tak pro pošťouchnutí: násobení matic n x n uvedeným naivním algoritmem má časovou náročnost O(n^3). Existují však poněkud sofistikovanější algoritmy s náročností klesající k O(n^2.38). Pro matice 20000 x 20000 to teoreticky (samozřejmě se to v reálu bude brzdit někde jinde) znamená zrychlení téměř 400násobné...

[Jakub Galgonek]

Jen tak pro pošťouchnutí: násobení matic n x n uvedeným naivním algoritmem má časovou náročnost O(n^3). Existují však poněkud sofistikovanější algoritmy s náročností klesající k O(n^2.38). Pro matice 20000 x 20000 to teoreticky (samozřejmě se to v reálu bude brzdit někde jinde) znamená zrychlení téměř 400násobné...

Jen tak pro pošťouchnutí: Asymptotickou složitost nemůžeš takto přímo porovnávat, pokud má něco složitost 1000*n^2.38, tak je to pořád O(n^2.38), ale pro matice 20000x20000 to nebude rychlejší, než něco se složitostí n^3.

[Reklama]

[technomaniak]

Takže jsme pořád na úrovni hospodských keců? 

Och já naivka si myslel že tu někdo konečně předvede důkaz, a zase big shit. Se nedivme, že to tu tak vypadá, to je skoro jako práce na dálnici. Jeden maká a 5 lopat mudruje o ničem .....

viz. Talk is cheap, show me the code ;-).

[Jakub Galgonek]

Jsi pěkný kus diskuze přehlédl, ne?

[RAII]

Jirsáku, furt křičíš že chceš důkaz. To to nevidíš? Důkazy máš všude kolem sebe. Pro příklad Android. Vnitřně linux s klíčovými knihovnami napsanými v C. Na povrchu číhá Java jež běží pod Dalvikem. Nemusím ani říkat že Android vykazuje abnormální žravost oproti konkurenci, takže potřebuje X jader k rozumnému chodu. Ty však jako zažraný Javista odpovíš: Nedal jsi důkaz ... Uvědom si, že vlastním odmítnutím stavu věcí, stav věcí nezměníš. Pouze budeš mít dobrý pocit xD

[Filip Jirsák]

Och já naivka si myslel že tu někdo konečně předvede důkaz

Nezapomněl jste napsat, důkaz čeho očekáváte? Důkaz, že neefektivní kód lze napsat v jakémkoli jazyce, jste podal vy sám. Jaký chcete další?

Důkazy máš všude kolem sebe. Pro příklad Android.

Tvrzení s velkým kvantifikátorem nelze dokázat příkladem. OpenOffice nebo Firefox také nedokazují, že C++ je pomalé.

[Tomas]

Jirsáku, furt křičíš že chceš důkaz. To to nevidíš? Důkazy máš všude kolem sebe. Pro příklad Android. Vnitřně linux s klíčovými knihovnami napsanými v C. Na povrchu číhá Java jež běží pod Dalvikem. Nemusím ani říkat že Android vykazuje abnormální žravost oproti konkurenci, takže potřebuje X jader k rozumnému chodu. Ty však jako zažraný Javista odpovíš: Nedal jsi důkaz ... Uvědom si, že vlastním odmítnutím stavu věcí, stav věcí nezměníš. Pouze budeš mít dobrý pocit xD

Uvedomujes si vubec, ze vykon aplikace je VZDY zavisly na tom kdo ji psal? Je spousty aplikaci napsanych v C++, ktere jsou line jako prase. Nemuzes proste navysit vykon jen volbou jazyka, ale hlavne tim jak aplikaci napises. Je to uplne to same jako navysovat vykon pomoci lepsiho HW. Algoritmus je vzdy nejdulezitejsi. Jinak ja mam velmi rad C++, ale takhle hanit Javu je opravdu trapnost. Obzvlaste kdyz o tom opravdu nic nevis. Precti si nekdy clanky pana Tisnovskeho, abys aspon tusil jak hloupe se vyjadrujes.

[perceptron]

raii, vy mate dobry pocit, ze dokola tvrdite "java sucks, lebo je pomala"?

a na rozumnejsiu notu, co rozumiete presne pod 'android vykazuje abnormalni zravost oproti konkurenci'?

mate nejake exaktne data, ze android na analogickom hardveri bezi rychlejsie nez windows phone alebo ios? alebo mate ine exaktne data, ktore dokazuju zravost? (a dufam, ze nevyleziete s tvrdenim, ze baterka na nokii 3310 vydrzi 7 dni a na androide jeden).

a opat, ako som sa pytal vyssie: who cares? (okrem verklika "java je pomala, c++ rulezz")

vasou logikou by sme mohli ist donekonecna: windowsy napisane v c++ tiez ziadne terno a linux v cistom c tiez ziadna velka slava, trollity troll.

[RAII]

to perceptron: zkušenosti ... myslím že sekající se aplikace, jež by na to neměli nárok mluví za vše (zkuste rozběhnout androida 4 na 512 MB RAM ... bude to stát za starou belu)...Je pravda že novější verze to výrazně zlepšili, ale furt je to špatný (a jiné aplikace na marketu tímto trpí furt). Jako poměr lze třeba vzít IOS. Mnohem lépe využívá výkon zařízení. A Who cares? Ano, je to tak. Nebudete věřit, ale nepřišel jsem sem s cílem všechny přesvědčit aby se vysrali na Javu a šli do C++, do této dlouhé a bohužel zbytečné diskuze jsem byl zatažen poté, co jsem tvrdil že optimalizovat v Javě bitovými operacemi je zbytečná práce, neb je nenažraná, takže jakákoli takto drobná optimalizace se ztratí. Bohužel, někteří vytáhli do holi war, a já nemohl zůstat pozadu xD

[perceptron]

"ios mnohem lepe vyuziva vykon zarizeni", lebo a) apple ma de facto tri zariadenia a nie tritisic, ergo moze optimalizovat prave tak ako to robia na hernych konzolach b) ich zariadenia su high-endove, teda trochu inde, nez vami argumentovane 512mbove zariadenie, ktore sa dnes predava za 50 eur v bazari

to vas argument opat mozeme poslat do roviny "zkuste rozbehnout windows 7 na 512MB ram, bude to stat za starou belu, ergo c++ suxalot"

"jine aplikace tim trpi furt", lebo su mnohokrat zle napisane. napr. pisu asi tak efektivne, ako hore uvedeny kod pre pracu s maticami a podobne. alebo, aby som nekydal, v androide 4.x sa zmenilo pre pracu s databazami, kde sa data neloaduju v hlavnom vlakne, akurat nie kazdy vyvojar na to prisiel.

ja stale netusim, co ine chcete oznamit svetu, len nez java je pomala; nepoviete v porovnani s cim; a ak poviete, tak vase porovnavane veci su z ineho sveta

pointa tejto debaty je v tom, ze na houby budete robit wtf mikrooptimalizacie, ked vas kod algoritmicky smrdi na kilometer a vase znalosti jazyka a platformy su biedne, pripadne na urovni bulvarneho dennika

[prezek]

...novější verze to výrazně zlepšili...

Když už chceš psát měkké Y, tak aspoň takhle: "novější verzové to výrazně zlepšili".

Podle některých výroků je vidět, že jsi úplně mimo mísu, tak se nediv, že lidé nevěří věcem, které předkládáš jako fakt bez rozumného zdůvodnění.

Takovíhle hraní si s bitama je třeba pouze u low level vývoje (nastavování příznaků v registrech a tak podobně).

Například ukazuje na malou fantazii a zkušenosti. Velká část ne low level programů, které jsem psal, vyžadovala bitové operace (např. výpočet CRC pro kontrolu dat). A tvrdit člověku, kterému vyřešení domácího úkolu může přinést body navíc, že je Java pomalá, to je taky výrok hodný zápisu na pamětní listinu.
Páni, dneska jsem nějak zlej a agrsivní, radši půjdu spát, dobrou

[Filip Jirsák]

Je pravda že novější verze to výrazně zlepšili

Chcete tím říct, že starší verze byly napsané v Javě a novější ne? Nebo jinak, existuje nějaký výklad tohoto tvrzení, který by vaše tvrzení "Java je pomalá" nevyvracel (ve smyslu, že je nepravdivé, nikoli ve smyslu, že je pravdivý opak), ale podporoval?

jsem tvrdil že optimalizovat v Javě bitovými operacemi je zbytečná práce

Bitové operace se nepoužívají jen k optimalizacím. Jakákoli optimalizace není zbytečná práce právě tehdy, pokud vím, že jí zlepším úzké místo v aplikaci. Na ničem jiném to nezáleží.