Administrace komentářů

1a) Pokud je volání malloc p*pomalejší než volání custom alokátoru, pak celkový čas custom-alokátoru včetně vnitřní alokace, vyčerpávající celý chunk díky k alokacím je p + k. Pokud bych to řešil pomocí malloc, pak by byl čas p*k. Z toho plyne, že aby byla alokace pomocí custom alokátoru rychlejší, stačí, aby chunk byl velký alespoň p/(p-1) alokací. To je i pro vcelku zanedbatelný faktor 1.1 pouze 11 akolací. To jsme furt v řádu max jednoho kilobyte, tak kde je ta spousta nevyužité paměti?

1b) Malloc nedělá žádnou fyzickou alokaci, tu dělá systémové volání o jednu úroveň níže než malloc. Malloc je úplně stejný alokátor, jako ten náš testovací, akorát řešící generický případ včetně fragmentaci paměti atd... Malloc fyzicky alokuje velké chunky paměti a dále je rozděluje.

2b) Přidání volání omp_get_thread_num do testu nemá měřitelný vliv na rychlost vykonání kódu. Použití malloc místo custom alokátoru zpomalí můj testovací příklad na 12jádru více než desetkrát. Tomu říkáš stejně malý?

4) V tom případě si vyvracel předpoklad, který tu nikdo neříkal a který je zcela evidentní. Ano, ztratit čas implementací rychlejšího algoritmu má smysl pouze v případech, kdy čas ztrávený tímto algoritmem tvoří podstatnou část běhu programu. To je snad jasné každému, ne?

Navíc jsi neprezentoval jen jeden konkrétní případ, na závěr svého příspěvku jsi slovy

"tuto zkušenost mám již opakovaně"

generalizoval - sice ne explicitně, ale implicitně ano.

5) Malloc je knihovní funkce a většina jejího kódu běží v userspace. Její rychlost na OS tedy příliš nezávisí: závisí především na kvalitě libc knihovny, která může být přes různé OS stejná: např. glibc není problém provozovat na unixu, linuxu i BSD. Tvoje tvrzení by tak bylo možná pravdivé u velkých alokací dělaných pomocí přímého mapování fyzické paměti (mmap), ale tady se bavíme o malých alokacích a tam je to s prominutím prostě nepravda, v tomto případě nejvíce času nespotřebuje OS a systémová volání, ale userspace knihovní kód.

Už vůbec netuším, jak by se v rychlosti malloc projevil jiný procesor - co konkrétně na staré 486 šlo při mallocu (relativně k rychlosti CPU) pomalu a na haswellu jde rychle?

Malloc funguje defakto úplně stejně, jako custom alokátor: naalokuje od jádra OS velký kus paměti a ten pak po kouskách přiděluje jednotlivým voláním malloc. To, co dělá malloc složitým jsou dvě věci a) řešení fragmentace paměti, vyhledávání volného bloku atd... , b) mezithreadová synchronizace (týká se některých implementací mallocu, některé todle řeší). Pokud můžeš ušetřit na jedné z těchto věcí, pak se Ti hodí si napsat vlastní alokátor.

Tj. pro případ A - např. pokud hodně alokuješ a chceš všechno uvolnit najednou, a případ B - pokud hodně alokuješ v různejch threadech a neceš si alokovaný věci mezi threadama půjčovat. Právě proto jsou Tvoje námitky proti custom alokátoru nesmyslný: psát vlastní alokátor s omp critical jde právě proti tomu, co můžeš vlastním alokátorem ušetřit. Stejně jako výtka, že ten jednoduchý alokátor neřeší fragmentaci paměti - on ji totiž neřeší úmyslně právě proto, že je jednoduchý a kdyby ji řešil, tak nemá smysl ho psát, protože malloc už napsaný je.