Rychlost std::list.insert() – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Rychlost std::list.insert() – C / C++ – Fórum – Programujte.comRychlost std::list.insert() – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Seph
~ Anonymní uživatel
37 příspěvků
11. 4. 2014   #1
-
0
-

Nazdar, z určitých důvodů nemůžu v jedné aplikaci použít std::list, takže jsem se vrhnul na vytvoření vlastního listu. Problém nastal při testování rychlosti mého výtvoru s std::list. Zezačátku to bylo fajn, několik operací můj list zvládal rychleji než std::list. Pak ale přišel zlom při testování insert() funkce. Konkrétně případu insert funkce kdy se přidávají prvky do prázdného listu. Moje implementace je zhruba o 30% pomalejší. Operace mého listu jsou zhruba takové:

nainstaluj první uzel;
for (opakuj dokud jsou prvky ke vložení)
{
      alokuj uzel;
      vlož do něj hodnotu prvku [i];
      připoj uzel na konec;
}

Operace alokuj uzel sestává z jednoho volání malloc a následného zavolání odpovídajícího konstruktoru nad objektem (new (pointer) T [size]). Toť vše. Zjistil jsem, že právě tato alokace mi tam žere všechen ten čas. Když jsem ji odmazal, a na místo ostatních závislých operací (na ní) přidal nezávislé se stejnou časovou spotřebou, rychlost byla stejná jako u std::list (smutné ...). Takže k jádru mé otázky, zná tady někdo vnitřní realizaci STL listu pro GCC 4.8? Pokoušel sem se číst zdrojáky, ale autor byl zřejmě pán strachu a děsu, takže to má psychika nedokáže vydržet (rozuměj, psalo to prase, aspoň tak se to jeví mému oku). Můj odhad je, že std::list používá memory pool pro uzly. Z toho, co sem si všim tak alokuje uzly a vkládané objekty odděleně. To by mohlo vysvětlovat tu rychlost, ale radši se zeptám.

Nahlásit jako SPAM
IP: 80.188.252.–
Reklama
Reklama
KIIV+42
God of flame
11. 4. 2014   #2
-
0
-

zalezi na use casu .. sic nechapu, proc bys nemohl pouzit std::list (snad jen ze by to byl skolni projekt)

kazdopadne i na vkladani a mazani z nahodne pozice vyjde lip std::vector (i pres to, ze pri vkladani a mazani presouva cele bloky pameti) a pokud to kamos meril dobre, tak to tak vychazi do temer 200B struktur... (cache prediction je pekna svine)

takze pokud zkousis nejakou takovouhle rychlost, testni i vector a pak uvidis co je lepsi implementovat ..

btw: memory pool to podle me v std::listu nepouziva...

Nahlásit jako SPAM
IP: 93.91.152.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Seph
~ Anonymní uživatel
37 příspěvků
11. 4. 2014   #3
-
0
-

Píšu kernel. To proto nemůžu použít STD list. Inu, máš pravdu, díky cache je vektor určitě rychlejší, jednotlivé uzly listu jsou rozházené všude možně takže je tam plno cache miss, kdežto dynamické pole je pěkně kompaktní. Mne však teď vadí právě to, že nejsem schopen přijít na to, jak to dostat (můj list) na úroveň std::listu bez memory poolů. Nebo je taky možné že používá std::list zóny, naalokuje paměť pro nody najednou a taky ji najednou uvolní (ušetřil by spoustu systémových volání). Při čtení zdrojáků sem narazil na to že uzly mají vlastní alokátor, bohužel se mi nepodařilo najít kde je implementovaný. Proto se ptám, potřeboval bych nasměrovat na řešení. V samotném algoritmu přidání uzlů by neměl (jak jsem uvedl v otázce) být ňáký rychlostní exces ne?

Nahlásit jako SPAM
IP: 80.188.252.–
KIIV+42
God of flame
11. 4. 2014   #4
-
0
-

byt tebou, tak si to necham na reseni pozdeji... vis co se rika o "premature optimalisation" :)  (it is a root of all evil :D)

Nahlásit jako SPAM
IP: 93.91.152.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Seph
~ Anonymní uživatel
37 příspěvků
11. 4. 2014   #5
-
0
-

Inu, je to tak. Zatím to dám k ledu. Ale, víš. Dráždí mne to. Třeba teď sem testoval push back operaci, a, byla v mém podání rychlejší než je v std::list. A to je fakt divné, protože funkce insert která vkládá do prázdného listu funguje jako push back operace, akorát mnohokrát opakovaná. Asi je ten nečitelnej STL kód výsledkem magie či co ... ničím jiným to nevysvětlím.

Nahlásit jako SPAM
IP: 80.188.252.–
KIIV+42
God of flame
11. 4. 2014   #6
-
0
-

#5 Seph
Urcite to nejpomalejsi co jde, je mit spojovej seznam, kam se vklada na konec a musi se kvuli tomu pokazdy konec najit (projit celej seznam)... takze pokud mas to a staci ti jen vkladat na konec a odebirat ze zacatku (pripadne pruchod), tak si udrzuj krom zacatku i konec... ale pokud ti to opravdu drhne hlavne na alokaci (nebo jeste zkontroluj, jestli to nedrhne na konstruktorech), tak jedine ve stylu vectoru - alokuje se pomoci asi mallocu blok a nad jednotlivejma mistama se pak vola explicitne konstruktor/destruktor (samozrejme az kdyz je to potreba), pripadne se to presouva pomoci memmove a tak (nebo jestli pouzivaji i realloc?)

Nahlásit jako SPAM
IP: 93.91.152.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Seph
~ Anonymní uživatel
37 příspěvků
11. 4. 2014   #7
-
0
-

Obě dvě implementace (std i moje) používají i pointer na konec chainu, takže operace push back je O(1). A teď ta největší sranda, std::list používá obyčejný implicitní std alocator který opravdu není memory pool, žádný jiný alokátor sem tam nenašel (jeden co tak vypadal byl typedef na standardní alokátor...ehm). Takže oni tam dokonce volají 2x alokátor kdežto já jen jednou. A přesto je to hrozivě pomalí. A ty konstruktory? No, testuji to s datovým typem long, takže konstruktory možná budou drhnout, naštěstí ale ne teď. Teda, je to záhada. Zejtra si s tím zase pohraju (jak vyjde čas) a pak sem šoupnu zdroják. Kouknul by ses pak na něj prosím?

Nahlásit jako SPAM
IP: 80.188.252.–
z
~ Anonymní uživatel
268 příspěvků
12. 4. 2014   #8
-
0
-

A proč by se používal jiný, než implicitní alokátor, když jsi ho nespecifikoval? Výchozí alokátor v GCC je new_allocator, takže jednoduchý new/delete, který je zase jen jednoduchý malloc/free. A na každý prvek je jedna alokace (prev/next/data pohromadě). Na to ani nemusíš procházet zdrojáky, které jsou mimochodem bez problému čitelné.

Nahlásit jako SPAM
IP: 88.101.8.–
Seph
~ Anonymní uživatel
37 příspěvků
12. 4. 2014   #9
-
0
-

Vnitřně to může používat pro alokaci uzlů jinou metodu využívající poslaný alokátor (mPooly, zóny). Ty to přečteš? Super, si šikovnej..., některé lidi ale z toho kódu akorát začne bolet hlava. No, když už si tady, můžeš mi pomoci objasnit tu rychlost?

Nahlásit jako SPAM
IP: 80.188.252.–
z
~ Anonymní uživatel
268 příspěvků
12. 4. 2014   #10
-
0
-

Rozdíl v rychlosti objasnit nedokážu. U mně se ani neprojevuje.

Nahlásit jako SPAM
IP: 88.101.8.–
Seph
~ Anonymní uživatel
37 příspěvků
12. 4. 2014   #11
-
0
-

Takže, začal jsem dělat svůj list odznovu. Uvidíme jak si povede. Při dalším kouknutí do zdrojáků std::list jsem si všiml že funkce insert() používá místo push_back() funkci emplace_back() (V případě C++11). Výhoda je, že se objekt v tomto případě nekopíruje (jako při použití push_back), ale rovnou vytvoří na místě. To musí být znatelné zrychlení (ačkoli, máme move konstruktory takže to zrychlení taky nemusí být moc velké). Toto by mohlo být vysvětlení proč je v mém listu funkce insert tak pomalá oproti std::list::insert(). ALE, tato výhoda by se neprojevila, pokud by jsme do kontejneru vložili nějaký primitivní datový typ (v mém případě long). Takže, furt nevím čím to je. 

Nahlásit jako SPAM
IP: 80.188.252.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 79 hostů

Podobná vlákna

Namespace std; / using std::***; — založil Nadšenec

Std::streamsize — založil Sony

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý