zdá se mi, že pokud vaše aplikace rušení používala nové/smazat (malloc/free), pak by aplikace rušení více zasahovala do testu bez recyklace. Ale nevím, jak je implementován váš test rušení.
V závislosti na tom, jak recyklujete (tj. pokud nedej bože používáte mutexy pthread), může být váš recyklační kód pomalý (gcc atomic ops by bylo při implementaci recyklace 40x rychlejší).
Malloc, v nějaké variaci po dlouhou dobu alespoň na některých platformách, zná vlákna. Použijte přepínače kompilátoru na gcc, abyste si byli jisti, že to dostanete. Novější algoritmy udržují fondy malých částí paměti pro každý vlákno, takže nedochází k žádnému nebo jen malému blokování, pokud má vaše vlákno tuto malou položku k dispozici. Přehnaně jsem to zjednodušil a záleží na tom, jaký malloc váš systém používá. Navíc, pokud půjdete a přidělíte miliony položek k provedení testu.... no, pak tento efekt neuvidíte, protože skupiny malých položek jsou omezené velikosti. Nebo možná budete. Nevím. Pokud byste položku uvolnili hned po přidělení, pravděpodobněji ji uvidíte. Uvolněné malé položky se vrátí do seznamů malých položek, nikoli do sdílené haldy. Ačkoli "co se stane, když vlákno B uvolní položku přidělenou vláknem A" je problém, který může nebo nemusí být řešen ve vaší verzi malloc a nemusí být řešen neblokujícím způsobem. Jistě, pokud jste se okamžitě neuvolnili během velkého testu, pak by vlákno muselo svůj seznam malých položek mnohokrát doplnit. To může zablokovat, pokud se o to pokusí více než jedno vlákno. Nakonec halda vašeho procesu v určitém okamžiku požádá systém o paměť haldy, která se samozřejmě může zablokovat.
Takže používáte malé paměťové položky? Pro váš malloc nevím, co by bylo malé, ale pokud máte <1k, je to určitě malé. Přidělujete a uvolňujete jeden po druhém, nebo přidělujete tisíce uzlů a poté uvolňujete tisíce uzlů? Přidělovala vaše aplikace rušení? Všechny tyto věci ovlivní výsledky.
Jak recyklovat pomocí atomových operací (CAS =porovnat a vyměnit):
Nejprve přidejte pNextFreeNode do svého objektu uzlu. Použil jsem void*, můžete použít svůj typ. Tento kód je pro 32bitové ukazatele, ale funguje i pro 64bitové. Pak vytvořte globální recyklační hromadu.
void *_pRecycleHead; // global head of recycle list.
Přidat do recyklační hromady:
void *Old;
while (1) { // concurrency loop
Old = _pRecycleHead; // copy the state of the world. We operate on the copy
pFreedNode->pNextFreeNode = Old; // chain the new node to the current head of recycled items
if (CAS(&_pRecycleHead, Old, pFreedNode)) // switch head of recycled items to new node
break; // success
}
odstranit z hromady:
void *Old;
while (Old = _pRecycleHead) { // concurrency loop, only look for recycled items if the head aint null
if (CAS(&_pRecycleHead, Old, Old->pNextFreeNode)) // switch head to head->next.
break; // success
}
pNodeYoucanUseNow = Old;
Použití CAS znamená, že operace bude úspěšná pouze v případě, že položka, kterou měníte, je stará hodnota, kterou předáte. Pokud dojde k závodu a jiné vlákno se tam dostane jako první, stará hodnota bude jiná. V reálném životě se tento závod děje velmi zřídka. CAS je jen nepatrně pomalejší než skutečné nastavování hodnoty, takže ve srovnání s mutexy...je to rock.
Odebrání z hromádky výše má podmínku závodu, pokud rychle přidáte a odeberete stejnou položku. Vyřešíme to přidáním verze # k datům CAS. Pokud provedete verzi # ve stejnou dobu jako ukazatel na hlavu recyklační hromádky, vyhráváte. Použijte svazek. Nestojí nic navíc k CAS 64 bitům.
union TRecycle {
struct {
int iVersion;
void *pRecycleHead;
} ; // we can set these. Note, i didn't name this struct. You may have to if you want ANSI
unsigned long long n64; // we cas this
}
Poznámka:U 64bitového operačního systému budete muset přejít na 128bitovou strukturu. takže globální recyklační hromada nyní vypadá takto:
TRecycle _RecycleHead;
Přidat do recyklační hromady:
while (1) { // concurrency loop
TRecycle New,Old;
Old.n64 = _RecycleHead.n64; // copy state
New.n64 = Old.n64; // new state starts as a copy
pFreedNode->pNextFreeNode = Old.pRecycleHead; // link item to be recycled into recycle pile
New.pRecycleHead = pFreedNode; // make the new state
New.iVersion++; // adding item to list increments the version.
if (CAS(&_RecycleHead.n64, Old.n64, New.n64)) // now if version changed...we fail
break; // success
}
odstranit z hromady:
while (1) { // concurrency loop
TRecycle New,Old;
Old.n64 = _RecycleHead.n64; // copy state
New.n64 = Old.n64; // new state starts as a copy
New.pRecycleHead = New.pRecycledHead.pNextFreeNode; // new will skip over first item in recycle list so we can have that item.
New.iVersion++; // taking an item off the list increments the version.
if (CAS(&_RecycleHead.n64, Old.n64, New.n64)) // we fail if version is different.
break; // success
}
pNodeYouCanUseNow = Old.pRecycledHead;
Vsadím se, že pokud budete recyklovat tímto způsobem, uvidíte zvýšení výkonu.
Tato otázka má řadu dobrých odpovědí:Ve vícevláknovém C/C++ zamyká malloc/new haldu při alokaci paměti.
Panuje shoda v tom, že existuje zamykání. Takže velká alokace nebo ta, která vyžaduje nějakou výměnu, by mohla zablokovat menší alokaci v jiném vlákně, i když ta menší by mohla skončit, nebýt probíhající větší alokace.
Nový gcc je bezpečný pro vlákna, pokud kompilujete s podporou pthreads, ale to není to, na co se ptáte.
Vím, že ve Windows si můžete vytvořit vlastní haldu, kterou lze použít k nastavení paměti na začátku vašeho programu. Nejsem si vědom žádných volání linux/unix, která by dělala podobné věci.
To je opravdu skoro stejné jako tato otázka.
V podstatě malloc není definováno jako bezpečné pro vlákna, ale implementátoři mohou volně přidat implementaci, aby byla bezpečná pro vlákna. Z vašeho popisu to zní jako vaše konkrétní verze.
Pro jistotu, slovy Obi-Wana:"Použij zdroj, Luku." malloc zdroj bude k dispozici a je obecně velmi snadno čitelný.
@Marku, standardní zdroj GNU libc můžete získat od
$ git clone git://sourceware.org/git/glibc.git
$ cd glibc
$ git checkout --track -b glibc-2_11-branch origin/release/2.11/master
Viz také zde. Pamatujte, že malloc je v manuálové sekci 3 -- je to funkce knihovny, takže nebude ve zdrojových kódech vašeho jádra. Možná si však budete muset přečíst brk ,sbrk , getrlimit a setrlimit a podobně, abyste zjistili, co jádro dělá.
Ještě jeden odkaz:projekt GCC.
Dobře, ještě jeden (můžem kdykoli přestat):zde je stránka, ze které si můžete stáhnout zdroje. Rozbalte soubor a měli byste jej najít na ./malloc/malloc.c .
Ve vícevláknových systémech malloc() a free() (a new / delete ) obvykle používají synchronizační primitiva, aby bylo bezpečné volat z více vláken.
Tato synchronizace také ovlivňuje výkon některých aplikací, zejména aplikací, které provádějí mnoho alokací a dealokací ve vysoce paralelních prostředích. Účinnější vícevláknové alokátory paměti jsou aktivní oblastí výzkumu – viz jemalloc a tcmalloc pro dva známé.