Chytrý a chytřejší

Jako programátor, který programuje od útlých dětských let, od roku 1996 v C a od roku 1998 v C++ a od roku 2007 v Seznamu se dodnes divím, jak někdo ještě dnes může neustále srovnávat cokoliv s STL (a nedejbože s boost). _COKOLIV_ bude rychlejší než STL a _COKOLIV_ bude přehlednější než boost.

Že je něco rychlejší, než shared_ptr v STL kontejneru mě tedy až tak nepřekvapuje.

PS: S STL mám právě bohaté zkušenosti ze Seznamu, kde se divoce používá.

Existuje hodně implementací STL a třeba ta od týmu clangu (libc++) je hooodně rychlá. Microsoftí STL.NET je také dost rychlá (narozdíl od jejich nativní). Zde ale nejde o STL. shared_ptr je velice jednoduchá třída, na té se nedá nic zkazit. Zde jde ovšem spíš o překladač a jeho optimalizace.

Jistě je to možné, ale některé konstrukce třeba právě kontejnerů v STL znemožňují používat různé optimalizace, například děsivý alocator, ještě děsivější streamy (zkuste si je rozšířit), z principu nemožnost nebo dokonce zákaz používání stringů v režimu COW, či s čítačem referencí v režimu R/O. Spoustu věci je skryté, interní, a není zde možnost to změnit.

Nerozumím větě "kde se jinak shared_ptr divoce kopíruje.". Co to znamená? On se tem váš chytrý ukazatel divoce nekopíruje? Pokud jsem z dosavadního popisu pochopil, tak ona ref class není nic jiného, než když bych já napsal class Něco: public RefCntObj (objekt s intruzivním počítáním referenci). Optimalizovat se tady moc dobře nedá. Divím se, že zrovna v podání C++/CX to má být rychlejší. Pokud vím, tak je to postaveno na COM+, kde metody AddRef a Release jsou virtuální, což znamená koukat do nějaké tabulky adres, která zrovna jako na podporu nemusí být v cache. Když použiju čistě šablonové řešení intuzivního čítače, vyšvihne překladač do kódu vlastní instrukce příčítání a odčítání jedničky s testem na nulu. Pokud navíc se čítač nachází u objektu, nemám zde nebezpečí výpadku stránky jako u CX. V případě shared_ptr z STL mám dokonce pocit, že tam hrozí dva výpadky stránky, protože čítač je jinde, než objekt, jelikož čítání není intruzivní. Tam bych viděl problém s rychlostí.

A ještě jedna věc. Dodnes jsem nepochopil, proč se při pošoupávání prvků v kontejnerů v STL používají operátory přiřazení. Má to děsivý overhead.

#3 (posledni odstavec)

Od toho jsou v C++11 rvalue reference, diky nimz lze implementovat "move" semantiku.

#4 nemám zkušenost s STL a C++11, ještě jsem neměl čas zkoumat zdrojáky. Ale předpokládám, že tam budou používat move semantiku s operátorem přiřazení, což je sice lepší, ale ne ideální. Ideální je samozřejmě operátor přiřazení vůbec nepoužívat, není jeho smyslem kopírování objektů, ale spíš "synchronizaci" stavu jednoho objektu s jiným, což není totéž.

@2 Když mám shared_ptr a napíšu auto ptr1 = ptr2, kopíruje se. V C++/CX, je-li ptr2 handle, auto ptr1 = ptr2 zavolá AddRef na ten objekt (i to jen někdy, podle úvahy překladače). To je vždy rychlejší než vytvoření nového objektu. C++ je se svými kopírovacími konstruktory trochu specifické, a v C++/CX se dá toto kopírování obejít (v C++/CLI rovněž, tam nastávají ale jiné problémy).
Move semantika zrychluje STL výrazně, nejlepší na tom je, že stačí program překompilovat bez úprav v C++11 a je hned rychlejší.

@6 ne to je nesmysl. V obou pripadech se prenese adresa a zavola se AddRef, jak v pripade cisteho C++, tak v pripade CX. V C++, pokud je to napsano opravdu dobre se zadna metoda nevola a ihned za kopirovanim adresy nasleduje instrukce inc counter. Pri prenosu adresy (tedy kopie a pak destrukce sama sebe), prekladac v ramci optimalizace tyto dve instrukce eliminuje. Otazkou je, zda tam zustane test na nulu. Pridanim move semantics do chytryho ukazatele lze manipulaci s counterem eliminovat uplne.

@7 Když je ptr2 na zásobníku, tak čisté C++ kopíruje vždy. Move sémantika funguje jen pro rvalues.

@8 Sorry, ale proč mi to říkáte. Mne nemusíte učit C++ a ani jsem v příspěvku toto neřešil. Řešil jsem jen to, že nevěřím tomu, že počítání referenci je rychlejší v řízeném kódu než v nativním. Pokud něco takového vy nebo autor (nevím, kdo je kdo) pozorujete, pak máte někde chybu. Nedivil bych se, kdyby chyba byla v STL. Co se týče chytrých ukazatelů a počítání referenci, schválně jsem se podíval, jak vypadá kopírování počítaného ukazatele v mé verzi chytrého ukazatele. K tomu dodám, že má verze řeší separátně počítání v režimu MT a ST, proto je následující kód lehce delší:

//kopírování adresy
00E2D2E7 mov dword ptr [esi],edi

//test zda to není NULL
00E2D2E9 test edi,edi
00E2D2EB je 0E2D308h

//test zda čítač nemá horní bit nastaven na 1 - ST, nebo 0 - MT
00E2D2ED mov eax,dword ptr [edi]
00E2D2EF test eax,eax
00E2D2F1 js 0E2D305h

//MT verze
00E2D2F3 mov dword ptr [esp+34h],1
00E2D2FB mov ecx,dword ptr [esp+34h]
00E2D2FF push ecx
00E2D300 push edi
//InterlockedIn­crement
00E2D301 call ebx
00E2D303 jmp 0E2D308h

//ST verze
00E2D305 inc eax
00E2D306 mov dword ptr [edi],eax

//to je vše.
Tento kód je nainlinován na každé místo, kde se pointer kopíruje. Žádné volání kopírovacích konstruktorů

Uměl byste vyšvihnout rychlejší kód? U testů lze provést ještě optimalizaci tak, aby se chytal dobře odhad skoků, pak je dobré, když procesor v režímu ST odhaduje správně (v režimu MT je tak velký overhead na InterlockedIn­crement, že neuhodnutí skoku je proti tomu prd)

A ještě se vrátím k tomu článku a k uvedenému kódu. Autor stvořil nádhrerny proxy pointer, který nazval nevhodně jako Shared. Ve skutečnosti to vypadá

Ref->SharedPtr->T

Při každém přístupu dochází k dvojnásobné dereferenci, tedy k dvojnásobné pravděpodobnosti výpadku stránky z procesorový cache. Osobně se divím, že je to prý rychlejší. Spíš bych se zaměřil na chybu v testovacím algoritmu, který pravděpodobně nahrává jedné straně. A proboha lidi, nepoužívejte shared_ptr!!!

@9
1. Evidentně máte ve znalostech C++ mezery. A navíc v C++/CX žádný řízený kód není, nikdy nebyl a asi ani nikdy nebude (ale možná MS překvapí) :-)
2. Když tomu nevěříte, napište si to (v C++/CX).
3. SharedPtr se tak jmenuje, protože je sdílený. Rychlejší to je proto, že překladač s handly na ref třídy zachází jako s pointry. Akorát to není poznat ze syntaxe.

@10 myslim ze je zbytecne v diskuzi pokracovat. Osobne mam stejny nazor na Vas a samotny clanek povazuji za spatny.

@11 "Řešil jsem jen to, že nevěřím tomu, že počítání referenci je rychlejší v řízeném kódu než v nativním."

To jste psal o C++/CX. Doporučuji zjistit si, co je C++/CX. Jinak Vám Váš názor neberu, máte na něj právo. Navíc mnoho lidí si plete C++/CLI s C++/CX, takže to beru s nadhledem.

Tak chlapci, už se konečně dohodněte, který z vás dvou je ten chytrý a který je ten chytřejší ;-)

Ondřej Nováčisko, [9]: Samozřejmě, že lze vyšvihnout výrazně lepší a rychlejší kód. To, že neumíte dobře assembler x86 je naprosto zřejmé.

Jinak samozřejmě počítání referencí je drahá operace a je to jeden z nejpomalejších garbage collektorů.

Ale většina různých knihoven používá počítání referencí ve výrazně optimálnější verzi, než kód předvedený v 9. To je děs a hrůza, to jsem ještě neviděl. To je zatím asi nejpomalejší implementace počítání referencí, které jsem měl čest za svých 25 let programování vidět.

Vzhledem k tomu, že na root chodím asi jednou za měsíc a nebudu mít čas čekat na kolečko schválení příspěvků, pak reakce na příspěvek a případně moje reakce, napíšu to naráz:

Kód pana Nováčiska z [9] je nejhorší možný, který nasbíral všechna negativa, která existují. Každá dobrá implementace shared_ptr je výrazně efektivnější a méně problematická. Ondřej Nováčisko by udělal dobře, kdyby namísto objevování kola si nějakou efektivní knihovnu prozkoumal.

Stručný výčet některých negativ kódu v [9]:

1) Někdo musí rozhodnout, zda kód bude single threaded, nebo multi threaded. Asi programátor, každopádně programátor je pak nucen zabývat se ptákovinami a řešit věci. Špatné rozhodnutí pak o tom, zda multi threaded je zdrojem těžko hledatelných chyb.

2) Při přetečení čítače se mu automaticky překlopí čítač do druhé polohy, tedy původně single threaded se změní na multi threaded a naopak. Nijak to nemá ošetřené.

3) Zbytečně ztrácí čas testem na NULL. To prakticky není v čítači referencí nikdy potřeba.

4) Na kódu je vidět neoptimalizace. Například první tři instrukce v kódu MT by šlo nahradit jedinou instrukcí push dword 1.

Pomíjím, že celý úsek kódu není konečný, například z ničeho nic se vyčarovalo v registru ebx adresa InterlockedIn­crement, takže někde předtím se musí naplnit.

Jinak pro jeho informaci, celé přičtení jedničky proměnné k pointeru, které je threadově bezpečné je v x86 assembleru na 2 instrukce. Záměrně neuvedu kód, ať si taky zahledá. Nevolá se přitom žádný podprogram ani nedochází ke skokům. Tedy efektivita úplně báječná.

To je důvod, proč knihovny, které haní samozřejmě mohou být velmi efektivní a mnohem efektivnější, než tu popisuje.

Jinak o STL si také nemyslím nic moc dobrého, ale na druhé straně spíše proto, že nekontroluje správnost parametrů čímž mohou vznikat obtížně hledatelné chyby a také proto, že není rozšířitelná. Například některé třídy bez virtuálních metod jsou zbytečně konečné. A nakonec také proto, že používá nejasně velké integery.

Ing. Miloslav Ponkrác

Ondřej: takové malé nakopnutí (lock prefix): http://ref.x86asm.net/#column_x :-)

[16] Instrukce Lock má obrovský overhead na víceprocesorových systémech. Řádově tak 100x pomalější běh, než když je INC bez LOCKu. Příkaz InterlockedIn­crement navíc bývá právě implementován jako LOCK INC []

[15] Tak a teď vám to celé vyvrátím levou zadní.

1) Ano, programátor to musí rozhodnout. Kdo by to měl rozhodovat? Valná většina čítačů se konstruuje jako ST a jen v případě, že objekt musím sdílet do jiného vlákna stačí pointeru nastavit MT. Na to mám funkci getMT(), která vrací this, ale vynuluje nejvyšší bit.

2) To si děláte legraci. Z principu nelze vytvořit tolik referencí, protože každý pointer zabere 4 bajty. Takže i kdybych obsadil každou čtveřici referencí, nikdy se mi to číslo nepřeklopí

3) U intruzivního čítání je to nutné, jinak byste pracoval s counterem na adrese NULL, která není přístupná. Jo už jsem uvažoval, že bych jako NULL dal ukazatel na nějaký plonkový čítač, který by citani NULL referencí umožňoval. O intruzovní čítání v tomoto článku jde především

4) Kód vypadl z optimalizátoru MSVC. Je to po aplikaci /O3 a po inlinování těchto bloků do kódu. Jsou tedy vždycky optimalizované svému okolí. Tatáž část tedy vypadá v různých částech kódu různě. Proto třeba se do EBX ukládá adresa na InterlockedIn­crement, která se používá vícekrát. Zdánlivé neoptimality vychází z toho, že některé instrukce lze zpracovávat superskalárně, jiné nelze a tak je někdy opis rychlejší, než kratší zápis

Přičtení jedničky u vícejádrových procesorů není bezpečné! U takových čtyřjader je opravdu potřeba použít instrukci LOCK, což je vlastně InterlockedIn­crement. Instrukce LOCK znamená serializaci instrukcí, flush instrukční cache, zámek sběrnice, tím pádem zdržení o ostatních procesorů. Dále se flushuje zápisová cache, čtecí cache, a to všechno jen proto, aby se někde přičetla jednička. I nepodařený odhad skoku zabere méně taktů, než LOCK. LOCK je příšerně drahá.

A ještě k tomu LOCKu. Kdysi jsem se zabýval, prot Microsoft Windows používá volání Call InterlockedIn­crement namísto provedení LOCK INC. Důvod mne překvapil po tom, co jsem si prohlédl, jak se liší kód na jednojádrovém a dvoujádrovém procesoru. Zatímco na jednojádrovém procesoru je na adrese kam ukazuje CALL uvedeno INC [adresa] a RET. Tak u vícejádrového procesoru je tam tatáž instrukce s LOCK INC [adresa]. Ten CALL totiž vede do KERNEL32.DLL, který existuje ve vícero verzích. Stejně tak existuje vícero verzí různých zámků typu EnterCritical­Section a podobně, která ve verzi pro jedno jádro je mnohem jednodušší, protože u ní je nižší riziko race conditions.

Opakuji instrukce s prefixem LOCK je velice drahá, je to serializační instrukce, která způsobí, že se nejprve vyčká, až se dokončí všechn instrukce před ní, pak se vykoná ona sama jediná a následně se začnou vykonávat následující instrukce. Je to asi tak, jako byste ve škodovce zastavili linku, pak vyrobili jedno auto a pak tu linku zase spustili. Dále je potřeba s tím, že čtená adresa se bude načítat z paměti a ne z cache a bude se zapisovat do paměti a ne do cache. Pokud se sejde víc LOCKů současně, pak jde už tak mizerný výkon do kytek. Nějaké info jsem našel tady:

http://stackoverflow.com/questions/2538070/atomic-operation-cost

[17]: Pane, LOCK INC by nebyl schopen splnit požadavky InterlockedIn­crement. Když se podíváte na dokumentaci této funkci, tato funkce kromě přičtení musí ještě vrátit předchozí hodnotu. A to pomocí LOCK INC není schopna. A pokud jí načte později, tak vzhledem k multithreadovému prostředí mohla být mezitím změněna.

Takže ano, aniž bych znal jak to MS provádí, tak sotva to bude implementováno pomocí LOCK INC.

Nehledě na to, že INC instrukci skutečný programátor nepoužívá, protože je neefektivní sama o sobě. Je špatně optimalizovaná v procesorech a díky tomu, že nastavuje příznaky odlišně než většina jiných instrukcí způsobuje dodatečná zpoždění v procesoru, protože potřebuje extra čas na vyřízení této odlišnosti.

Ale uznávám, v době Windows 95 musela InterlockedIn­crement používat LOCK INC, protože na 386 procesoru jiná možnost nebyla. Návratovou hodnotu pak musela odhadnout z příznaků. Ale už na 486 procesoru jsou k dispozici mnohem lepší instrukce, které hodnotu vrátí přímo.

---

Protože v Microsoft Visual C/C++ trochu dělám, tak si tipnu, že takovou neoptimalitu, jako je trojice instrukcí za MT částí tento kompilátor neprovede. Stejně tak takovou hovadinu, že by použil instrukci INC.

Takže buď používáte verzi kompilátoru z muzea, nebo jste nastavil optimalizaci špatně. MSVC optimalizuje velmi dobře a jeho asm výpisy jsem mnohokrát viděl. Dokonce jsem je občas používal i na studium, jak dobře psát v asm, než jsem došel dál, než jsou schopnosti automatického kompilátoru.

---

Ad 1) Programátor to ale nemůže rozhodnout. Princip shared_ptr je, že se sdílí data na více místech. Občas ani nemůžete tušit, kam všude se dostane. Jen v případě, že rozkopírujete proměnnou po x místech ve stejném threadu lze nebrat multithreading v úvahu.

Čítač je velmi často v objektech, kde se používá copy on write (COW), a programátor to často ani nemusí vědět. Respektive je naprosto zbytečné ho tím otravovat.

A znovu říkám. Stačí JEDINÁ chyba v rozhodnutí programátora, že nějaký čítač není multithreading a celé, zdůrazňuji celé to letí do kopru. Čas od času, velmi zřídka, to prostě zkolabuje, chyba je těžko opakovatelná a téměř se nedá nasimulovat ani předvést.

Toto rozhodování bude vést k tomu, že programy začnou být méně spolehlivé a nedá se to v zásadě dost dobře otestovat. A velmi těžko se na to přichází.

Ad 2) Pokud předpokládáte, že vyrábíte pouze nezchybné programy, pak máte pravdu.

Ad 4) To už je naprostá hovadina. Vím, jak procesor optimalizuje a tyhle neoptimality rozhodně kromě zdržování k ničemu nepřispějí. Ostatně ty 3 instrukce co jsem dal za příklad, nebo instrukce inc není nic, co by kromě zhoršení dělalo něco jiného.

LOCK především může znamenat naprosto cokoli. Je to implementačně závislé a procesor se snaží LOCK instrukci zoptimalizovat. LOCK nenutí procesor k serializaci všech instrukcí, pouze k serializaci přístupů na jeden kousek paměti. Procesor to ví.

Jestli dovolíte, nemám už chuť na Vás reagovat. Jste velmi sebevědomý a nelámete si hlavu s pravdivostí Vašich argumentů. Mohl bych stejně tak reagovat na zbytek, ale odpustím si to.

„Kdysi jsem se zabýval, prot Microsoft Windows používá volání Call InterlockedIn­crement namísto provedení LOCK INC.“

Jednoduše proto, že Microsoft plánuje, plánoval a realizoval časem, že InterlockedIn­crement je tzv. instrinsic funkce, tedy falešná funkce.

V 64 bitovém kompilátoru kompilátor nic nevolá, jen rovnou inlinuje co je třeba.

Tedy Microsoft plánoval ve svém kompilátoru, že InterlockedIn­crement bude přímo kompilátor nahrazovat inline nejvhodnější implementací. To je to co jste zpozoroval, kompilátor dohazoval jiné věci.

---

Kromě toho, Microsoft Windows je programováno multiplatfromně, což je hlavní důvod. Většina procesorů, tedy skoro vše kromě x86, nemá instrukci LOCK, nebo jí nemá tak efektivně.

U většiny procesorů se provádí zamykání paměťového místa zvlášť.

Kdysi existovalo Windows NT na Alpha procesory, na MIPS, i na řadu dalších procesorů. Teprve časem to MS zkrouhnul jen na x86 a na Itanium.

Mimochodem, i na to m Itaniu je LOCK, a tedy Interlocked neefektivní, a dokonce to MS uvádí v dokumentaci.

---

Jinak řečeno, způsob zamykání pro atomické operace je implementačně závislý a každý procesor nabízí jiný způsob.

---

„Opakuji instrukce s prefixem LOCK je velice drahá, je to serializační instrukce, která způsobí, že se nejprve vyčká, až se dokončí všechn instrukce před ní“

Opakuji, že LOCK je implementačně závislý.

Operace s LOCK je samozřejmě dražší. Protože způsobuje atomičnost zápisu.

Nicméně základní problém, který tu je je – jak moc je drahá a co to stojí. A je skutečně dražší, než Váš kód, nebo levnější?

Vy jste si prostě našel, že LOCK je fuj, a že je NĚJAK drahý, netušíte jak. Tak namísto toho vyrobíte složitější a dražší kód, abyste se v určitých případech LOCK vyhnul. Ale tušíte, jestli jste si polepšil, jestli jste opravdu vylepšil kód?

LOCK není nekonečně drahý. LOCK je nějak měřitelně drahý. Má určitou neefektivitu za kterou nabízí užitečnou funkci – atomičnost operace. Váš kód je také dražší, než efektivita pouhé jediné instrukce na přičtení. Vyplatí se to? Neodpovídám ani nepředjímám, jen dávám otázky.

Osobně bych nenechal programátora v čítači referencí nic rozhodovat. Osobně bych pouze dal jedinou informaci. Program je buď single thread, nebo multi thread. Následně bych měl inline funkci

inline AtomicIncremen­t(uint32_t volatile * ptr)
{
asm "mov eax, ptr"
#if (PROGRAM == SINGLE_THREAD)
asm "add dword ptr [eax], 1"
#else
...
}

Čímž bych dosáhl vyšší efektivity. A je to nejblíže tomu, co dělá Microsoft v jádře Windows.

Má smysl reagovat? Opravdu je to výstup z MSVC. Jenom jsem si neuvedomil, že pro MT čítání nepoužívám InterlockedIn­crement ale InterlockedXAdd (+1). Proto ta jednička v tom volání. Nevíte jak kód pokračuje, třeba překladač pak tu jedničku rovnou někde používá. Opravdu dávno nepíšu v ASM. Jestli chcete vidět, jak vypadá zdroják tak asi takto:

class RefCntObj {
static const natural fastFlag = (~natural(0)) << (sizeof(natural) * 8 - 1);
public:

RefCntObj():cou­nter(fastFlag) {}

void addRef() const {
if ((counter & fastFlag)) ++counter;
else addRefMT();
}

bool release() const {
if ((counter & fastFlag) != 0) {
return --counter > 1;}

protected:
mutable natural counter;

void addRefMT() const;
bool releaseMT() const;
};

Datový typ natural je size_t (závisí na platformě).

Výstup je z MSVC 2008

K vašemu bodu 1). Pokud programátor ví, že většina objektů není MT safe, což opravdu není, v mých knihovnách nic není MT Safe, musí se postarat, aby všechny objekty byly v nějakém zámku, nebo se vůbec mezi vlákny nesdílely. RefCntObj má možnost zapnout sdílení pointerů bez nutnost zamykaní. Pokud to jednou zapnu, to tehdy, kdy dávám pointer do jiného vlákna, pak už se o to nemusím starat

Koukam, ze ten kod neni cely, diskuzak pozral vetsinu znamenek. Az se dostanu ke compu, tak ho hodim do pastebin

Instrukce LOCK je opravdu fuj, a bude hure. Uz mam dokonce v navrhu verzi citace pro MT bez locku a bez testovani, kde se budou citat countery normalne. Rikam countery, kazde vlakno bude mit vlastni. Ale vemte si, ze sdileni mezi vlakny je obecne fuj, protoze prijdou procesory nCube a NUMA architekturou , kde bude vyhodne nez sdilet radeji posilat zpravy.

V knihovne mam COW retezce. Nejsou MT safe. Uplne v prvni verzi nez prisli MT countery jsem tam mel funkci isolate, ktera se pouziva pro prenos objektu do jineho vlakna obycejnym kopirovanim. I to je rychlejsi nez LOCK a navic se dva procesory nemusi neustale tahat o jednu pametovou stranku, kazdy ma sva data u sebe, Aby se minimalne sdilelo mezi vlakny

Celý hlavičkový soubor (bez MT části, která se dá ale odhadnout)

http://pastebin.com/mjgWVTVS