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

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.

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...

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?

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

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.

#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?)

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?

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é.

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?

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

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.