Jak copy-on-write udělalo náš projekt zase použitelným

7.2.2013 16:23 | Přečteno: 2577× | Programování | | poslední úprava: 8.2.2013 14:40

V našem projektu s otevřeným zdrojovým kódem canal se zabýváme statickou analýzou nad programy přeloženými do LLVM IF. To vyžaduje vytvoření objektu pro každou proměnnou zpracovávaného programu, což s sebou nese zvýšené paměťové nároky. A zde hraje copy-on-write klíčovou roli.

Princip fungování copy-on-write

Základním principem copy-on-write je pozdržení vytvoření celkové kopie objektu tak dlouho, dokud to není potřeba - tedy dokud se do objektu nezapisuje. Při realizaci této metody se třídy, které mají mít tuto vlastnost, vybaví počítadlem, které se inkrementuje při vytvoření kopie; při zápisu do daného objektu se pak v případě, že počítadlo je nenulové (tedy existuje kopie), vytvoří fyzická kopie objektu a původní počítadlo se dekrementuje. Implementačně se třída využívající copy-on-write obvykle obalí do jiné třídy, která zajišťuje tuto funkcionalitu.

Při implementaci je tedy potřeba odchytit dvě operace - vytváření kopie a zápis do objektu. Vzhledem k tomu, že je náš projekt napsán v C++, to umožňuje snadno rozlišit, které objekty jsou modifikovatelné, a které ne (díky klíčovému slovu const). Vytvořili jsme tedy obalující třídu (šablonu), která při vytváření kopie objektu (ať už pomocí kopírovacího konstruktoru či virtuální metody clone) zvýší vnitřní počítadlo. Navenek je dále schopna se "přetypovat" na původní třídu - a to za pomoci konstantních metod (které nevytváří kopii objektu) i nekonstantních metod (u kterých se naopak kopie objektu vytváří). Tohoto je možno dosáhnout mimo jiné pomocí operátor *, ->, případně operátoru přetypování.

Zde je vhodné zmínit jednu nepříjemnou vlastnost C++:

class Trida {
    const int& get() const;
    int& get();
};
Trida t;
const Trida& c;
const int& a = c.get(); //Zavola se const metoda
const int& b = t.get(); //NEzavola se const metoda!

Pro copy-on-write by bylo vhodné, aby se při přiřazení do proměnné b volala konstantní metoda, zatímco ona se volá nekonstantní (která v kontextu copy-on-write způsobí zbytečnou kopii). Tento problém lze vyřešit buď magií se šablonami (jen v omezené míře; viz dále), přejmenováním nekonstantní metody (třeba na mutable_, neboť mutable je klíčové slovo) nebo použitím ošklivé konstrukce.

Naše implementace

Pro náš projekt jsme postupně vyzkoušeli dvě implementace, které se liší přístupem k danému problému - jedna implementuje copy-on-write pro konkrétní třídy (interně nazvaná COW), druhá obaluje všechny objekty v mapě objektů (interně SharedDataPointer). Obojí však řeší problém domén, což jsou naše reprezentace proměnných analyzovaného programu. Všechny třídy, kterých se copy-on-write týká, jsou pak potomci třídy Domain.

Přístup pro třídy (třída COW)

V tomto přístupu bylo snahou při vytváření instance domény vytvořit objekt, který se bude tvářit jako doména (bude potomkem třídy Domain) a interně si bude držet instanci vlastní domény, pro kterou bude dělat delegaci volání metod. Protože v projektu často pracujeme i se základní třídou Domain, implementuje třída COW všechny metody této třídy. Pro přetypování z Domain na potomka používáme vlastní šablonovou funkci, což umožňuje nejen přetypování z COW třídy na instanci obalené třídy, ale zároveň to řeší (s pomocí menší šablonové magie) problém s přiřazením nekonstantních objektů do konstantních (více viz zde).

Vlastnosti tohoto přístupu:

• + Může nezávisle na sobě obalovat jakoukoliv třídu - některé třídy tedy mohou využívat copy-on-write, některé nemusí.
• + Zasahuje všechny vytvářené instance této třídy - které se mohou tvořit na více místech (v našem případě tedy i prvky domény reprezentující pole).
• - Nevýhodou je nutnost delegace metod všech předků dané třídy, což vyžaduje jejich explicitní výčet v definici třídy COW.

Přístup pro místo (třída SharedDataPointer)

V našem projektu máme mapu, která drží všechny proměnné použité při analýze programu. Dalším řešením tedy je při ukládání do této mapy obalit veškeré domény, a při jejich čtení nedělat kopii a při zápisu ano.

• + Relativně snadná implementace (stačí změnit jednu třídu, která pracuje s mapou).
• - Funguje jen na úrovni dané mapy (pokud i jiná struktura by potřeboval copy-on-write, je potřeba to pro ní napsat separátně).

Výsledky

My jsme se nakonec rozhodli pro druhý přístup, neboť vyžaduje méně změn v kódu a protože většina dat je uložena na jednom místě. Pro efektivní využití bylo však potřeba kód ještě projít a zjistit místa, kde dochází ke kopiím - spousta těch míst totiž tvořila kopii i v momentě, kdy to nebylo potřeba (třeba operátor porovnávání). A jaké byly výsledky (měřili jsme čtyři programy z Coreutils) ?

• true (180 řádek LLVM bytecode): stará verze 0,09s, maximum 14,8 MB RAM; nová 0,01s a 7,27 MB
• sleep (357 řádek LLVM bytecode): stará verze 0,33s, maximum 41,9 MB RAM; nová 0,01s a 7,73 MB
• chroot (782 řádek LLVM bytecode): stará verze 1,48s, maximum 110,2 MB RAM; nová 0,03s a 9.17 MB
• wc (2 194 řádek LLVM bytecode): stará verze 60,29s, maximum 2 477,9 MB RAM; nová 0,31s a 36,6 MB

Zdroj.

Závěr

Díky použití copy-on-write se nám povedlo nejen náš projekt zrychlit, ale především ho učinit použitelným pro další programy (již se zvládneme zpracovat více než 70 programů z Coreutils). Zároveň to náš projekt zrychlilo, neboť již není potřeba provádět operace na objektech, které byly kopiemi jiných objektů.

Projekt canal se zabývá statickou analýzou nad programy v jazyce C přeloženými do LLVM bytecode (potenciálně však i pro další jazyky přeložené do LLVM). Tento přístup umožňuje zjistit nadmnožinu všech možných hodnot proměnných v programu. Naší snahou je toto umožnit nad co největším množstvím programů. Tento projekt je vytvářen pod Fakultou informatiky Masarykovi univerzity a podporován společností Red Hat.

       

Komentáře

[phpGuru]

nemohl by nekdo 'normalne', napsat, wo co de

[Jan33]

To je jednoduché, vytvoří si objekt A a když chceš zapisovat, vytvoří se kopie ... jo tak, ty bys rád věděl co je canal, hmm, tak to taky nevim.

[phpGuru]

hm, a tim se usetri co? Ze se neco zapise do kopie misto do toho A originalu? A co se vubec zapisuje? Jak vypada ten objekt? Jak vypada to zapisovani?

Ja to fakt nechapu.

[gogloid]

Ušetří se nutnost vytvoření vlastní kopie (což může chvíli trvat, zvlášť u větších objektů), stejně jako paměťová náročnost. Některé jazyky toto řeší za tebe, v C++ je však toto plně v tvých rukách (celá práce s pamětí je v tvých rukách). Stejně tak pokud se nad více objekty provádí stejná operace, tak pokud by u všech dopadla stejně, tak má smysl to dělat jen u jedné (což ušetří další, především časové, prostředky).

[Magog]

Já osobně tento text chápu jako konkrétní případ toho, jak copy-on-write může velmi výrazně snížit HW nároky.

[phpGuru]

jak ja si pamatuji, tak se tahle finta pouziva (pouzivala?) kdysi u forku, kdy se nenalozi cela nova procesni struktura ale zpocatku jen absolutni minimum s tim, ze novy process vlastne ani kopii nechce nybrz by to narocne zkopirovane za chvilku premlatil uplne necim novym, protoze exec.

Neco takoveho jsem ale v clanku nevycetl.

[depka]

a stale pouziva viz man fork

Under Linux, fork() is implemented using copy-on-write pages, so the only penalty that it incurs is the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child.

[stativ]

COW se AFAIK používá v clone(), které fork() volá. Má to smysl i proto, že clone() se používá i při implementaci vláken a tam se některé věci vůbec nekopírují.

[Sten]

Potřebují vytvářet velké množství kopií stejných objektů zabírajících hodně paměti, s tím, že později do libovolné kopie může (ale nemusí) být zapisováno. Tak si řekli, proč vlastně kopírovat ty objekty v případech, kdy se do nich nezapíše? A tak vytváří jen jakože-kopie, které ve skutečnosti sdílí paměť, a teprve při prvním zápisu vytvoří skutečnou kopii. Podle analýzy na konci to evidentně ušetří hodně paměti a výkonu.

[phpGuru]

diky za odpoved. Samozrejme se vtira otazka, odkud prichazi ten pozadavek vytvaret kopie, ktere pak nejsou potreba.

[pavlix]

Samozrejme se vtira otazka, odkud prichazi ten pozadavek vytvaret kopie, ktere pak nejsou potreba.

Tuhle otázku jsem níže naťuknul taky.

[Bystroushaak]

Díky za čtivý článek.

BTW: To tě někdo donutil ho sepsat, nebo jsi to udělal sám od sebe? Já jen že by bylo fajn číst tu víc podobných, programátorsky orientovaných článků, tak by mě zajímalo jakou mám naději, že se toho někdy dočkám.

[gogloid]

Naději rozhodně máš; jestli narazím na další věc, kterou stojí za to publikovat, tak budu :) Nebylo to z donucení, jde o skutečné použití této metody v našem projektu. Jen mě mrzí, že jsem to nepsal před dvěma měsíci, kdy jsme to implementovali, kdy jsem o tom měl větší přehled...

[pavlix]

Já musím říct, že jsem měl chuť si článek přečíst, ale je pro mě ohromně nesrozumitelný. Napříklat jsi nejsem jistý, že ta část o kopírování tříd se skutečně týká kopírování tříd a ne instancí. Prostě totální zmatek. Ale kdybys tohle trochu uhladil, tak by se mi něco takového líbilo mezi články.

[pavlix]

Doufám, že to vyznělo správně jako konstruktivní kritika a ne jako trollování :).

[gogloid]

Ano, vyznělo :) Psal jsem to dnes, tak se na to zkusím zítra podívat a případně nějaké věci ujasnit.

[gogloid]

Tak jsem se snažil to trochu upravit - je ještě něco výrazně nesrozumitelného?

[pavlix]

Já po tobě ani nežádám, abys to upravoval, to je zcela na tobě. Ale jestli máš pocit, že ti to pomůže, tak…

Při realizaci této metody se třídy, které mají mít tuto vlastnost, vybaví počítadlem, které se inkrementuje při vytvoření kopie

Tuhle část snad chápu, takže tuším, že tím máš namysli asi spíš že se inkrementuje místo vytvoření fyzické kopie, tudíž to „při vytváření kopie“ by rozhodně zasloužilo reformulovat.

Ale to už jsem řešil v jiné diskuzi, že mnozí mají stále ještě náhled na OOP pokažený implementačními detaily C++. Obecný popis toho, co chceme dělat, by neměl vyžadovat přepnutí mozku na C++ mód :D.

Takhle, já tě nechci nijak prudit, ale celý ten článek vypadá jako když jsi ho psal pro sebe, tedy pro člověka, který do toho vidí. Já jsem z něj byl schopný pochytit co obecně obnáší copy-on-write (což už jsem znal), nějaké ty statistiky jak to pomohlo.

Ale že bych bez zkoumání samotného kódu chápal, co se vlastně děje, jestli se to nějak uplatí i u nových objektů, a hlavně, proč je pro daný projekt relevantní zrovna kopírování existujících objektů.

A když už popisuješ konkrétní metody jak toho dosáhnout, tak bych chtěl nejdřív vědět, co daná metoda obnáší, a pak teprve pracovat se specifickými pojmy jako šablonová funkce apod.

Něco ve stylu (a teď kecám, protože jsem to zdaleka všechno nepochopil)...

Nové instance tříd se vytvářejí běžným způsobem. Ale protože canal dělá … a k tomu potřebuje často udržovat kopie již existujících instancí, které z důvodu, že …, často zůstávají nezměněné, a protože bychom neradi měnili celý datový model, rozhodli jsme se použít metodu copy-on-write. Umožnuje nám to ušetřit paměť, protože nemusíme alokovat … až do chvíle, kdy se do nového objektu zapisuje.

A teď bych očekával technické vysvětlení toho, jak je možné se vyhnout té alokaci…

Místo stovek bajtů pro celý objekt tak můžeme alokovat proxy objekt, který obsahuje informaci, že je zatím nezměněný a odkaz na datový objekt, který využíváme pouze pro čtení. První zápis pomocí proxy objektu způsobí zkopírování datového objektu a zrušení příznaku pouze pro čtení. Od této chvíle se prostřednictvím proxy objektu čte a zapisuje nový datový objekt. Když se nový proxy objekt klonuje, znovu se označí jako read-only.

Ve skutečnosti je tam potřeba ten reference counting kvůli dealokaci, ale nechtěl jsem ty ukázky příliš komplikovat.

Minimálně takhle nějak bych si představoval text, který mi má předat něco nového.

[gogloid]

Zápisek měl poukázat na dvě věci:

• na dva způsoby řešení (pro třídu a pro místo)
• že to může mít opravdu velký přínos

Účelem nebylo vysvětlení copy-on-write, ani k čemu je to dobré, ani jestli ho využijete ve svých projektech - šlo mi především o to ukázat, že když už se rozhodnete ho využít, abyste měli nějakou inspiraci jak.

Pro mne z toho plyne důležitá zkušenost, že jsem to měl napsat před dvěma měsíci, když jsme to implementovali, a ne až nyní - v ten moment bych nejspíš napsal dvakrát tak dlouhý zápisek, který by to rozebíral víc ze široka (a tedy by i nejspíš pokryl věci, které ti tam chybí).

[pavlix]

na dva způsoby řešení (pro třídu a pro místo)

Subjektivně vnímám, že tento účel nesplnilo.

že to může mít opravdu velký přínos

Tento účel splnila ta tabulka časů a nebyl by k tomu potřeba zbytek článku.

šlo mi především o to ukázat, že když už se rozhodnete ho využít, abyste měli nějakou inspiraci jak.

Opět subjektivně vnímám jako nesplněné.

Pro mne z toho plyne důležitá zkušenost, že jsem to měl napsat před dvěma měsíci, když jsme to implementovali, a ne až nyní - v ten moment bych nejspíš napsal dvakrát tak dlouhý zápisek, který by to rozebíral víc ze široka (a tedy by i nejspíš pokryl věci, které ti tam chybí).

To je dost možné. Ono taky záleží na tom, jak moc má člověk na to psaní chuť a čas.

[Miloslav Ponkrác]

Očekávané nadávky na C++ pod článkem týkající se C++. => Tentokráte splněno. Už jsem si myslel, že ne, ale pavlix se opět postaral. Takže díky pavlixovi je zase svět srozumitelně předvídatelný a dokonale deterministický. A tedy krásný, nádherný a bez nebezpečí, ale nuda a bez překvapení.

---

Jinak článek je opravdu velmi nesrozumitelný. Obsah je zajímavý, ale zabila to neschopnost psát.

Každé sdělení (článek, dopis, …) má mít úvod, stať a závěr. Z úvodu by mělo být nastíněné co se bude text řešit, jak to bude řešit, co nebude řešit, o co se jedná, pro koho je, pro koho není, atd.

Stať by měla slíbené v úvodu učinit. A závěr by to měl ukončit.

Sám jsem COW implementoval mnohokrát, ale přesto jsem článku neporozuměl zcela. Pochopil jsem, že účelem článku nebylo vysvětlit princip COW, nicméně tím, že druhý odstavec ho „jakoby“ vysvětluje spoustu lidí zmátl a očekávali, že se tedy dozví co to ten COW je. Následně se řeší marginální a vedlejší problém, který vzniká když se kdosi pokouší implementovat COW na const/non const v C++. Pak se ukazují nějaké dva přístupy.

Následně se dostane na třídu SharedDataPtr, která je věrnou kopií třídy shared_ptr obsažené přímo ve standardní knihovně C++. S výjimkou, že standardní knihovna má tuto třídu thread safe, zatímco v článku zmíněná SharedDataPtr nesmí přijít do multithreadové prostředí.

Článek obsahuje některé kvalitní a zajímavé věci a úvahy, a moc bych si přál články takového typu číst častěji. Navzdory strašnému slohu, přeházenému pořadí sdělení v textu oproti logice snižující srozumitelnost textu. Přesto bych byl rád, aby takovéto články vznikaly.

[gogloid]

Chybami se člověk učí; zatím mě komentáře neodradily od toho, abych tvořil další podobné články (když budu mít o čem psát), a snad již budou srozumitelnější. Tento článek už upravovat nebudu, neboť by to nejspíš vyžadovalo kompletní přepsání, a to se mi z různých důvodů nechce.

Po zběžném pohledu je shared_ptr obsazen až v C++11, což jej, bohužel, činí pro náš projekt zatím nepoužitelným.

[pavlix]

Tento článek už upravovat nebudu, neboť by to nejspíš vyžadovalo kompletní přepsání, a to se mi z různých důvodů nechce.

Není zapotřebí vypilovávat tenhle jeden článek, spíš se opravdu těším na zlepšení u těch příštích :).

[Bystroushaak]

Tento článek už upravovat nebudu, neboť by to nejspíš vyžadovalo kompletní přepsání, a to se mi z různých důvodů nechce.

Já být tebou, tak to moc nehrotím. V čechách je problém najít texty o programování, které jsou určeny lidem, jenž už o programování něco vědí. Takové to běžné meziprogramátorské povídání, které se dá najít třeba na redditu. Co ovšem není problém, je sehnat tu tisíc úvodů do něčeho, zas a stále znova. Nechápu proč, imho nemusí být každý blogpost srozumitelný pro všechny kdo náhodou půjdou kolem.

[Miloslav Ponkrác]

Protože od určité úrovně vyžaduje od čtenáře určité teoretické nebo matematické znalosti. A nebo napsat 100 × delší úvod, který nejdříve vysvětlí ty teoretické nebo matematické znalosti použité pro danou věc.

A protože se v Čechách razí, že teorie je fuj, takže člověka to brzy odradí psát kvůli tomu články 30 × delší.

Momentálně v zahraničí se razí jakýsi kompromis, kdy se teorie nahradí dogmaty a prohlášeními „jenom takto je to správně“, kdy autor smixuje 10 % teoretických znalostí a 90 % vlastních předsudků či co se mu líbí a přetaví to do podoby „takto jedině je to správné“. Na toto téma je dokonce i mnoho amerických knih.

Jediná cesta v každém oboru od určité úrovně je začít studovat teorii, souvislosti mezi jedinými věcmi, apod.

A nebo se nakrmit dogmaty, kdy nikdy nevíte, co je lež a co pravda. (Takových dogmat je velmi mnoho zejména v tom jak správně OOP programovat.)

A vysoký level v programování a sw inženýrství už bez vlastních rozsáhlých znalostí teorie nedáte vůbec.

Není problém psát články o vyšší úrovni, ale je otravné psát ty úvody pro ty, kdo neznají teorii, souvislosti a další. Nakonec kdo na teorii dlabe, nechť se jednoduše vzdá toho, že by přesáhl určitou úroveň. Protože to stejně jinak nedopadne.

[Josef Kufner]

Však ono stačí odkázat na vhodné zdroje a shrnout prerekvizity do jednoho odstavce. Kdo ty rozvleklý kecy má číst pořád dokola.

[Bystroushaak]

Kdo ty rozvleklý kecy má číst pořád dokola.

Jo.

[pavlix]

Očekávané nadávky na C++ pod článkem týkající se C++.

Zřejme jsi si spletl vlákno.

nicméně tím, že druhý odstavec ho „jakoby“ vysvětluje spoustu lidí zmátl a očekávali, že se tedy dozví co to ten COW je.

Což mimochodem není můj případ, jak se gogloid mylně domníval.

Přesto bych byl rád, aby takovéto články vznikaly.

To už jsem psal výše. Kdyby se vytáhly obsah i forma do srozumitelné úrovně, rád bych to viděl mezi vydanými články.

[Miloslav Ponkrác]

„Zřejme jsi si spletl vlákno.„

Nespletl, cituji:

„Ale to už jsem řešil v jiné diskuzi, že mnozí mají stále ještě náhled na OOP pokažený implementačními detaily C++. Obecný popis toho, co chceme dělat, by neměl vyžadovat přepnutí mozku na C++ mód“

[pavlix]

To není kritika C++.

[Miloslav Ponkrác]

Mě hlavně fascinuje, jak všichni hledají to správné OOP.

Pochopil jsem, že žádný jazyk, který existoval, existuje a bude existovat podle zastánců čistého OOP neobsahuje to správné a dokonale čisté OOP.

Pochopil jsem už dávno, že mainstreamově prezentovaná touha po správném OOP je chiméra, něco jako sektářská víra.

Jo a k Vaší větě: Napsat pod článek věnující se primárně C++, že by se popis prolému neměl vyžadovat OOP v přepnutí na C++ mód je – vysvětlitelné pouze aplikací lysohlávek před tím, než jste začal psát. Případně nezvladatelnou nenávistí k C++, kterou už nedokážete potlačit, a zřejmě to dáváte najevo i na koncertech, na zastávkách autobusů, píšete to na sloupy veřejného osvětlení, atd. – tedy v úrovni obsesivně-kompulzivní poruchy.

[Sten]

Pochopil jsem, že žádný jazyk, který existoval, existuje a bude existovat podle zastánců čistého OOP neobsahuje to správné a dokonale čisté OOP.

Smalltalk.

Pochopil jsem už dávno, že mainstreamově prezentovaná touha po správném OOP je chiméra, něco jako sektářská víra.

To je samotná touha po čistě OOP jazyce. V praxi velmi rychle zjistíte, že jsou běžné situace, které s OOP jazykem řešíte půl hodiny při odtržení jednorázové definice od jejího použití, zatímco s dobrou podporou funkcionálních jazyků to máte za pět minut a přehledně (třeba řazení podle řetězce xorovaného nějakou hodnotou — funktor vs. lambda).

[pavlix]

Mě hlavně fascinuje, jak všichni hledají to správné OOP.

Mě spíš facinuje, že jsi můj příspěvek sice nepochopil, zato ti to nijak nebrání dělat chytrého.

[kralyk z abclinuxu]

Hm, to API mi není moc jasný (nezkoumal jsem dopodrobna), ale na první je celkem zřejmé, že to není ani exception-safe ani thread-safe. Skoro bych možná nevynalézal kolo a podíval se, jak to mají řešeno jinde...

[kralyk z abclinuxu]

*první pohled, samozřejmě...

[gogloid]

Vzhledem k tomu, že výjimky ani vlákna zatím nevyužíváme, tak jsme zatím exception-safety ani thread-safety neřešili. API jsme postavili na míru našemu projektu po inspiraci jinými implementacemi (přestože to nemusí být vidět).

[Miloslav Ponkrác]

To, že výjimky nepoužíváte neznamená, že tam výjimka nemusí vzniknout.

[Sten]

Exception-safety je v C++ velmi jednoduché řešit, pokud ji řešíte rovnou od začátku, v naprosté většině případů úplně stačí dodržovat RAII. Přidávat podporu později je noční můra.