Vlákno názorů k článku Velikost objektů v Javě od mmmmario - Vrtá mi hlavou, k čemu bych mohl v...
-
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.
-
Rax (neregistrovaný)
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é.
-
Pavel TišnovskýZlatý podporovatelaneb 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
-
Pavel TišnovskýZlatý podporovatel
Hmm popravde jsem ten kod netestoval, ale bitblt odzadu bude podle me hodne pomaly kvuli architekture cache (1st i 2nd level - same vypadky). Musim to ale vyzkouset v praxi...
Jinak movb/movw jsme taky pouzivali, ale to bylo v dobach 286, kde se fyzicky skutecne prenasela data z pameti do pameti.
-
Pavel TišnovskýZlatý podporovatel
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); } -
Karel (neregistrovaný)
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.
-
Rax (neregistrovaný)
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.
-
Filip JirsákStříbrný podporovatelPokud 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.
