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.
Poznámka redakce: Tento článek původně vyšel v autorově blogu na AbcLinuxu.cz. Na Fedora.cz vychází v původní podobě se souhlasem autora.
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 je počítadlo 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++, můžeme 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áří). Toho je možno dosáhnout mimo jiné pomocí operátorů *, ->, případně pomocí 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 potomky 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 třídy COW 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 canal/lib/Utils.h).
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 by i jiná struktura potřebovala copy-on-write, bylo by potřeba to pro ni 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)?
| program | řádků LVVM bytecode | stará verze | max. RAM | nová verze | max. RAM |
|---|---|---|---|---|---|
| true | 180 | 0,09 s | 14,8 MB | 0,01 s | 7,27 MB |
| sleep | 357 | 0,33 s | 41,9 MB | 0,01 s | 7,73 MB |
| chroot | 782 | 1,48 s | 110,2 MB | 0,03 s | 9.17 MB |
| wc | 2 194 | 60,29 s | 2 477,9 MB | 0,31 s | 36,6 MB |
Zdroj: Canal 2 Release Notes.
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ž zvládneme zpracovat více než 70 programů z Coreutils). Zrychlení bylo dosaženo, 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 umožnit to nad co největším množstvím programů. Tento projekt je vytvářen pod Fakultou informatiky Masarykovy univerzity a podporován společností Red Hat.
