Evidentne vam to stale neni prilis jasne. Kolekce s JVM nemaji vicemene nic spolecneho a jsou to tridy jako jakekoliv jine. (java.util.)List je jen interface implementovany v (java.util.)ArrayList a (java.util.)LinkedList. Veci, tykajici se JVM, jsou v balicku java.lang.
Článěk napíše o java.util.List, ale scala.collection.immutable.List. To už je konkrétní implementace scala.collection.immutable.Seq.
Vrtá mi hlavou, k čemu bych mohl v Javě využít kontejner typu LinkedList, když jediné co tam můžu strčit je Object / reference / pointer. Kontejner typu ArrayList mi přijde mnohem výkonnější za všech okolností. Snad jediná nevýhoda pole / ArrayListu je re-alokace a té se dá většinou předcházet.
Poradíte mi nějakou výhodu spojového seznamu oproti poli (obecně) v jazycích jako je Java, která má pouze pointery? A s konstantní dobou vložení / odebrání elementu na mě nechoďte, protože pokud nemáte někde schovanej iterátor tak na to místo odebrání musíte zdlouhavě doskákat.
Hlavní rozdíl mezi polem pointerů a spojovým seznamem je nutnost neustále kopírovat pointery při přidávání/odebírání uprostřed pole. V Javě je však natolik velký jiný overhead, že se to nemusí na první pohled projevit.
Námitka proti iterátoru je relevantní, spojový seznam se hodí hlavně na úlohy které nepotřebují přístup přes index.
Je mi jasné, že při modifikaci pole uprostřed se musejí prvky "napravo" zkopírovat nebo přesunout. Ale protože v Javě tam budou jenom "light" pointery, nikoli "heavy" vlastí data, tak toto "přeskládání" bude podle mě vždy *velice* rychlé. A tato rychlost mi převáží jakoukoli jinou výhodu spojového seznamu.
Teď mě ještě napadlo zamykání (třeba kvůli grarbage collectoru). Má tam spojový seznam nějakou výhodu oproti poli?
Právě že ne, pole je vždy (alespoň doufám) jeden celek paměti, kde jsou jednotlivé elementy (zde reference / pointery) zaskádány pěkně jeden za druhým. Takže, jestli chci jeden odstranit nebo přidat na i-tou pozici, tak to udělám v konstantním čase. To že musím zbytek posunout je mi jasné, ale jelikož pracujeme s pointery, nemělo by to být zas až tak pomalé.
Nesouhlasím s tím, co je pomalé a co není.
Spojové seznamy mohou být pomalejší než pole, i když to na první pohled není vidět. Je pravdou, že přidat prvek na začátek pole znamená, že se přesunou zbývající prvky v poli. Pro pole pointerů na to v procesorech existuje jediná(!) instrukce. Samozřejmě, že jak se CISCové procesory přibližují RISCovým, tak tahle výhoda odpadá, protože tyhle instrukce se zpravidla hůře zpracovávájí v superskalárně.
Největší rychlost při práci s poli ukazatelů dosáhneme pokud pole zabírá méně než paměťovou stránku, případně cluster stránek v procesorové cache. Naproti tomu, spojový seznam nemusí mít všechny prvky ve stejném clusteru a tak procházení spojového seznamu může být znatelně pomalější, než přeskládání pole.
Když do 100prvkového kontejneru vložím prvek na 50. pozici, musím
- u klasického pole překopírovat 50 ukazatelů
- u spojového seznamu projít 50 záznamů (než 50. prvek naleznu).
Věřte mi, že pokud má kontejner 100 prvků, bude lepší použít klasické pole. Dokonce, pokud má pole 1024 (resp 512 na 64bit), pak pořád je pole rychlejší. V závislosti na velikosti cache stránky to může být i více.
Teprve při velkých kontejnerech může být spojový seznam lepší.
Spojové seznamy mají výhodu v případě, že potřebujeme vkládat a odebírat z obou stran. Tam bude klasické pole trpět. Ale při náhodném odebírání "odprostředka" to není až tak zřejmé.
aneb vzdy je nutne provest benchmark na REALNYCH datech :-)
> je pravdou, že přidat prvek na začátek pole znamená, že se přesunou zbývající prvky v poli. Pro pole pointerů na to v procesorech existuje jediná(!) instrukce.
Jestli myslis movs nebo rep mov(b/w/d/q), tak mam pocit, ze by se pri posunu muselo jit od konce pole, coz mega zpomali pristup pres cache. Nebo (pravda, uz jsem v asm x86 dlouho nedelal) mohou tyto instrukce presunovat blok, ktery se prekryva s destination?
Jsou tam instrukce na řízení směru, a ty instrukce opravdu přesouvají blok bajt po bajtu, nebo spíš slovo po slově (procesorový slovo). Já jsem takto za doby 386tek realizoval například scrolování obrazovky (dokonce si to poradilo i latch VGA karty, protože fyzicky dělá načtení a uložení)
Instrukce blokových přesunů se ale špatně zpracovávají superskalárně, zpravidla vytíží celou instrukčné frontu. Následující kód může být někdy rychlejší, než ta instrukce
rep: lea edi,[esi+ecx*4]; U mov eax,[edi] ; U dec ecx ; V mov [edi+4],eax ; U jnz rep ; V
jj vim ze REP MOVS[D,Q] uz neni nejrychlejsi, kdysi jsme si merili, jaka konstrukce je na danem procaku nejvykonnejsi. Kupodivu (i kdyz to ma vysvetleni) se ukazalo, ze je nejrychlejsi smycka s MOVAPS, ale nesmi se moc rozvinout - dobre hodnoty jsou pro 2x-8x rozvinuti, potom vykonnost zase klesa (ale toto se urcite bude menit CPU od CPU).
Tak jsem si to trosku zmeril a mate pravdu, kopirovani "dopredu" je rychlejsi jen asi o 1%, coz je nekde na hranici presnosti mereni, takze je to skutecne prakticky totozne. Memmove takto interne pracuje (kvuli prekryvum obou oblasti):
#include [stdio.h] #include [string.h] #include [time.h] #define LENGTH 10000000 int buf[LENGTH]; int main(void) { int d, c1, c2; c1 = clock(); for (d=0; d!=1000; d++) { memmove(buf+16, buf, LENGTH-16); } c2 = clock(); printf("Time1: %d\n", c2-c1); c1 = clock(); for (d=0; d!=1000; d++) { memmove(buf, buf+16, LENGTH-16); } c2 = clock(); printf("Time1: %d\n", c2-c1); }
Máte pravdu jen za předpokladu, že se spojovým seznamem pokoušíte simulovat pole. Pak je pole samozřejmě rychlejší než jeho simulace. Viz váš "než najdu 50. prvek".
Spojový seznam však dává lepší výsledky pro seznamy. Úloha typu "přidat paní Vomáčkovou do seznamu za pana Vomáčku" je rychlejší se spojovým seznamem. Jakmile totiž najdete pana Vomáčku* pak už je to jen o převěšení 2 pointerů.
*Pole může být v tomto rychlejší, pokud budete hledat podle klíče, podle kterého je pole setříděné. Protože lze použít metodu půlení intervalu a najít pana Vomáčku rychle. Pokud máte ale pole seřazené podle id nebo rodného čísla, tak najít někoho podle příjmení je prohledání všech prvků, stejně jako u spojového seznamu.
Pochopitelně bavíme se o velkých věcech, ne o triviálnostech se 100 prvky, pro 100 prvků skutečně spojový seznam asi moc velký smysl nemá.
Pole je samozřejmě rychlejší pro operaci náhodný přístup přes index, o tom není sporu. Ne vždy je ale náhodný přístup přes index potřebný a proto není nutné použít pole a je možné použít spojový seznam. Spousta algoritmů totiž nepracuje s indexy, ale například s následujícím nebo předchozím prvkem, s prvním nebo posledním prvkem a podobně.
REP MOVSD samozřejmě znám, ale představa že když je to jediná instrukce tak je nejrychlejší je od základu mylná, dneska se paměť kopíruje úplně jinak a hlavně podstatně rychleji.
Pokud víte, že k seznamu budete přistupovat vždy jen sekvenčně (např. přes iterátor resp. foreach) a přidávat/mazat budete vždy jen na začátku nebo na konci, ušetříte tím zbytečné kopírování. Ty předpoklady jsou velice často splněné třeba při konstrukci XML DOMu nebo při získávání dat z databázového resultsetu.
Nevím jak je to přesně v Javě, ale obecně u GC systémů je možné mít nefragmentovanou paměť, takže správce paměti potřebuje jenom ukazatel na první volné místo. V té hlavičce objektu máš velikost objektu, takže na další se dostaneš. Přes objekty iteruješ jenom v případě GC a to obvykle jenom přes nově vytvořené živé objekty (záleží na implementaci), takže na rychlost to nemá velký vliv.
skoda ze se clanek nevenuje vysvetleni realne spotreby pameti, ale vybira si jen alokaci nekterych datovych typu bez toho sileneho overheadu kolem.
napriklad nechapu, jak muze jeden editor (netbeans, nejosekanejsi verze jen pro C/C++) a jedna obyc hra (minecraft, holy zaklad bez pluginu, novy svet) sezrat dohromady gigabyte pameti. zkousel jsem netbeansy spoustet s limitem pameti na 200 MiB, ale za chvili to zacalo swapovat a GUI chvilema vubec nereagovalo.
jen pro srovnani, spotreby pameti Java 7 vs. gcc 4.7 ze zname Computer Language Benchmarks Game:
http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=java&lang2=gcc
40x az 60x vetsi spotreba pameti u identickyho programu neni pro Javu zadnej problem
Je to daň za vysloveně tragicky implementovaný správce paměti v Javě a částečně také bad-practice s inmutable objekty a nedá se s tím nic moc dělat. Na toto téma se diskutovalo mnohokrát, ale k žádnému uspokojivému řešení se zatím nikdy nedospělo. Pokud se ti to nelíbí, nepoužívej Javu.
tak treba ghc - implementace haskellu - jako ciste funkcionalniho jazyka je na immutable "objektech" cely postaven a presto je na tom co se tyce spotreby radove lip nez java. mozna to i krome kvality kodu souvisi s tim, ze nebezi ve virtualnim stroji, ale kompiluje se primo pres gcc/llvm/clang do nativniho kodu.
NetBeans nejsou editor, ale IDE. Nevím, jak v případě C/C++, ale v případě Javy drží v paměti informace o projektu a všech třídách a vazbách, aby programátorovy usnadnily práci (to je účel IDE, kdyby ty nápovědy a pomůcky nechtěl, použije jen editor). To, že IDE potřebuje hodně paměti, vychází z toho, jaké služby má poskytovat – a ve spotřebě paměti na desktopu má IDE konkurenci podle mne jen ve zpracování videa a velkých obrázků.
A zvládne Geany něco jako http://blog.v6ak.com/2013/01/grahamuv-problem-v-jave-je-ukecany-vadi.html ? (Toto je jen stručný náznak, co takové IDE umí.)
Jinak přejmenování metody není triviální operace, musí se hledat všechna použití.
To budou Netbeans bud spatne napsane, protoze Eclipse (+- srovnatelne co se tyce featur) me jede bez problemu na komplu s 256 MB RAM (Java + C vyvoj).
Minecraft, tam asi zalezi, jak je reprezentovan herni svet, precejen voxely jsou z hlediska spotreby pameti vlastne ta nejnarocnejsi struktura pro 3d modely :)
<blockquote>To budou Netbeans bud spatne napsane, protoze Eclipse (+- srovnatelne co se tyce featur) me jede bez problemu na komplu s 256 MB RAM (Java + C vyvoj).</blockquote>
fakt ? v jakem prostredi ? co na browzdani webem ? predstavuju si hola x-ka s fvwm a freenx clientem a nadupanejsi masinou na druhem konci ;-)
Kdysi jsme v jednom mudu napsaném v Javě přepsali práci s řetězci. Paměťové nároky spadly z 400MB na 60MB. Takže já osobně u programů, kde se pracuje hodně s texty, jako prvního podezřívám programátora "z" + " " + "používání" + " zřetězení " + "na naprosto nevhodných místech".
V první řadě bych chtěl říct, že moje vlastní zkušenosti jsou velice podobné; programy psané v Javě jsou výrazně pomalejší a náročnější na paměť, než jiné (třeba C/C++) varianty, co toho uměly zhruba stejně tolik. Proto jsem v dobách kdy jsem byl úplný BFU (teď už jen tak trochu BFU :3) se naučil Java programy ignorovat a nepoužívat. Čas od času se mi samozřejmě stalo, že jsem si nevšiml, že je to v Javě, ale brzy to bylo "sakra, ten program je tak náročný a pomalý... vždyť toho tolik nepotřebuje... hele, není to v Javě? *klik* *klik* ... no jasně, je. Uninstall"...
Na druhou stranu ale musím souhlasit s názory, že Vaše příklady jsou poněkud nešťastné. Netbeans jsou IDE, tedy obsahují velké množství funkcí jako pomůcky při programování. Kupříkladu já na PC používám QtCreator (psaný v C++), který umí refactoring (fakt perfektní, nic lepšího jsem neviděl - i když uznávám, že ve chvíli, kdy vytáhnu šablony a především složité šablonové struktury, už leccos přehlédne) a detekuje chyby v kódu a ve chvíli, kdy otevřu trošičku větší projekt (1 - 2MB zdrojového kódu), sežere okolo 150MB RAM. Samozřejmě, když jsem používal DevC++, nároky byly někde jinde, jenže to i funkce, které to umělo.
Příklad s Minecraftem je taktéž lehce nešťastný. Ten ukládá každou krychli, i když je to jen vzduch, do paměti a nemusí se to zdát, ale těch kostek je tam opravdu hodně. Nedávno jsem si taky dělal takový jednoduchý voxelový engine a ty paměťové nároky jsou docela srovnatelné. Sám Notch, původní autor Minecraftu, přiznává, že hra není optimalizovaná (spíš naopak).
Takže v případě těchto programů jsou větší nároky na paměť pochopitelné a řekl bych, že nevyhnutelné. Ale samozřejmě nepopírám, že kdyby byly dělány v např. C/C++, ušetřilo by se velké množství výkonu.
Příklad s Minecraftem je taktéž lehce nešťastný. Ten ukládá každou krychli, i když je to jen vzduch, do paměti a nemusí se to zdát, ale těch kostek je tam opravdu hodně. Nedávno jsem si taky dělal takový jednoduchý voxelový engine a ty paměťové nároky jsou docela srovnatelné. Sám Notch, původní autor Minecraftu, přiznává, že hra není optimalizovaná (spíš naopak).
MC nepoužívá octree, tj. každá elementární kostička má svoji sólo reprezentaci? :o To je dosti drsné. :)
No, tak teď doufám, že jsem neplácl nějakou blbost *kapka* nicméně takové jsou moje informace, byť mohou být zastaralé (přinejmenším soudě dle mého rychlého Googlení). Nicméně nebyl by octree docela nepříjemným zpomalením pro random access, který může být používán nejen pro pokládání a odstraňování objektů, ale i detekci kolizí?
Neřekl bych. Obecně jde o nárůst operační složitosti z lineární (přímý přístup do [obrovského] pole) na logaritmickou (průchod stromem), což za rapidní pokles nároků na paměť obvykle stojí. Průchod octree bude pomalejší než přímý přístup k prvku pole; na druhou stranu naopak nebude nutné zkoumat množství jednotlivých elementů, když se třeba výpočet kolize dvou objektů odehraje ve vysoké úrovni stromu (tahle agregace pomůže i k ořezávání neviditelných částí scény při renderingu apod.).
Samozřejmě je vždy třeba zvážit všechny okolnosti konkrétní situace. Zde tedy např. rozměry světa, stupeň jeho rozmanitosti (tj. zda se vyplatí čistý octree, nebo nějaká hybridní struktura), frekvence a rozsah změn uspořádání světa (naprostá většina hmoty je po většinu času statická) apod.
Myslím si tedy, že nějaká adaptivní struktura by tomuto enginu v součtu prospěla, pokud ji nemá.
> v dobách kdy jsem byl úplný BFU (teď už jen tak trochu BFU :3) se naučil Java programy ignorovat
Mam pocit, ze kedysi to byvalo horsie. Myslim, ze u mna zabil Javu StarOffice (vtedy novy produkt, bol to StarOffice?), to bolo tusim v nej. To ked sa mi zacalo loadovat, chcelo sa mi plakat. Potom som skusil este par Java aplikacii a cele roky som sa jej vyhybal oblukom.
Ale mam pocit, ze dnes to lieta celkom svizne.
No, já už situaci moc nesledoval, ale taktéž jsem porůznu četl a slyšel, že se Java poslední dobou výrazně optimalizuje.
U mě to zabily prakticky všechny aplikace, co jsem zkoušel (od stahovačů, přes hry až po editory a IDE). Poslední dobou jsem používal pouze program Esmska, protože jsem nenašel C/C++/... alternativu a vzhledem k řídkému využití prostě akceptuji, že reaguje pomaleji.
Asi nejsmutnější na tvém komentáři je, že StarOffice byl z velké části psaný v C++. Takže v rychlosti běhu programu je java nevinně a jako obvykle je to vinna autorů. Jenže tohle je obvyklé klišé: Když je pomalý program v javě, může za to java, když je pomalý program v čemkoliv jiném, může za to programátor.
Původní StarOffice (ten jsem nikdy neměl) byl původně v C++, ale Sun poté, co to koupil, do toho nacpal Javu, aby svět přesvědčil o její důležitosti. Pamatuju si PC s Celeronem 1,1 GHz a 192 MB RAM, bylo to kolem roku 2003. OpenOffice se na tom pouštěl víc než půl minuty (první start). Nevím, jestli to bylo Javou, nebo špatnými programátory, ale chápu, že to někoho mohlo odradit. Zejména z pohledu pamětníka AmiPro 3.0, který bylo rychlejší i na stroji s 10x pomalejším taktem CPU.
> Jenže tohle je obvyklé klišé: Když je pomalý program v javě, může za to java, když je pomalý program v čemkoliv jiném, může za to programátor.
S tímhle se setkávám celkem často, proto se snažím dávat si na to pozor. Proto nepopírám, že za pomalé programy v Javě nemohou jejich autoři, problém je ale v tom, že drtivá většina programů v Javě, se kterými jsem se setkal byla výrazně pomalejší a v žádném jiném jazyce jsem se s tím nesetkal.
Skutecne hodne zalezi na programatorech, protoze pokud nekdo zvoli pro implementaci *neceho* Javu, tak by mel vedet, proc si zvolil prave tuto platformu a jake to prinese vyhody a nevyhody.
Problem Javy obecne je v GUI, protoze AWT/Swing proste nejsou implementovany tak, aby behaly s rychlou odezvou. Samotna rychlost programu v Jave neni vetsinou kriticka (a da se navic dost dobre vyladit), ale uzivatele stvou pomale odezvy GUI. Tady Sun zaspal minimalne 10 let, uvidime, jestli JavaFX(2) bude znamenat zmenu, nebo bude Java na desktopu porad preslapovat.
Pametovou narocnost resi do znacne miry compressed oops popr. alternativni VM (JamVM), GC se da taky vyladit, jen to *** GUI je problem (SWT je reseni jen nekde).
Pravda, to je dost vseobecny problem skolstvi, hlavne v tom, ze se nakonec nejak nedaji do kupy vsechny informace z ruznych predmetu (algoritmizace, HW, vycislitelnost a slozitost) :/
Pro informaci - u vas byl studijni plan zalozen ciste a jen na Jave, nebo tam byly i dalsi jazyky, napriklad s odlisnym paradigmatem?
Jo, něco podobného jsem taky říkal, když jsem se bavil s pár učiteli. Díky tomu, že jsem se programování věnoval už před výškou, prošel jsem určitým vývojem a teď vidím, jak bych s tím bojoval, kdybych už neměl za sebou dané zkušenosti z dob, kdy jsem měl čas si s tím hrát.
No, já jsem jeden ročník opakoval kvůli jednomu pitomému elektrotechnickému předmětu, takže se mi mísí dva odlišené přístupy. Když jsem začal chodit do školy, všechno jsme měli čistě v Javě. Programování v C++ byl pouze volitelný předmět. V jednom povinném jsme si hráli na úrovni HW, to bylo v C, ale že by nás to nějak učili se říct nedá.
Později upravili jeden předmět tak, že jsme v něm měli dělat v C# a v nějakém volitelném neobvyklém jazyce (bylo doporučeno logické programování, ale byl možný i třeba Python) a C++ se stal předmětem povinným.
Ve volitelném předmětu a v navazujícím studiu (zde povinný předmět) jsme pracovali v Prologu, ale jen krátce. V tomto (navazujícím) studiu už všechno má být v C/C++, Java a C# jsou spíše okrajovou záležitostí.
Takže čistě v Javě ne, ale v prváku jsem nic jiného neviděl. Nyní se spíš přechází na C/C++.
Není zač.
Tak to nevím, ale Visual Studiu jsme dělali i v C++. Jeden spolužák měl docela průšvih, když se snažil o něco jako petici proti učitelovi, který odmítal odevzdání projektů v čemkoliv jiném.
Nicméně nám škola umožňuje si stáhnou a používat MS produkty zdarma (studentská licence); nejen Visual Studio, ale i MS Office, Windows apod. Podle EULA máme právo používat dané produkty i po skončení studia, ale už nesmíme nově instalovat a nemáme právo na aktualizace. Aspoň tak jsem ji pochopil.
Napadá mne, že bych měl zmínit, že existuje svobodná knihovna s metodou "assertSize", která dokáže změřit velikost objektem obsazené paměti a v případě, že nepředvídaně vyroste schodit testy:
http://openide.netbeans.org/tutorial/test-patterns.html#memory