Objekty, paměť a Garbage Collector
Náš jazyk již umí primitivní datové typy - čísla a text. Přidání dalších základních typů (boolean, jiné čísla, znak) je akorát aplikací nám již znamých vzorů, a tak je přeskočíme, a navíc se náš jazyk obejde bez nich.
Složitější typy jsou složené z jiných typů (ať už primitivních či nikoliv), u skriptovacích jazyků převážně listy a objekty (struktury). U nich již není vhodné je kopírovat kdykoliv je chceme použít, zbytečně by nám rostlo využití paměti, a tak je třeba umět dobře pracovat s pamětí. Je proto vhodné mít možnost sdílené paměti, ale zde nastává druhý problém - kdy se můžeme zbavit nevyužité paměti, resp. jak zjistíme že paměť již není využívána?
Je zde několik možných postupů:
Nechat správu paměti na uživateli
Pro nás nejjednodušší způsob, který často používají nízko úrovňové jazyky, například C či C++. Zde uživatel jazyka musí manuálně uvolnit paměť. Zapomene-li ji však uvolnit, zůstane "využitá", i když ji program již nepotřebuje. A naopak uvolní-li ji moc brzo, je zde nebezpečí chyby, která může mít katastrofální důsledky - natolik, že americká vláda nedoporučuje tyto jazyky používat.
Předpočítat použití paměti
Naopak asi nejsložitější způsob - před spuštěním programů zkontrolovat a spočítat od kdy do kdy je paměť používaná, a přidat kód na uvolnění. Tento způsob se sice používá i v C a podobných, nicméně pouze na primitivní paměť, jinak je primárním jazykem postaveným nad tímto modelem jazyk Rust. Je složité pro to napsat program, a i to používat - není to vhodný model pro skriptovací jazyky kde chceme mít možnost rychle nabastlit kód.
Počítání referencí
Počítání referencí je jednoduchý způsob sledování využité paměti - počítáme, kolik ukazatelů na danou paměť máme, a jakmile dosáhne nuly, víme že paměť je nevyužitá. Tento způsob se občasně používá v C++ či Rustu pro paměť u které není lehké zjistit její "životnost", kdy ji ještě budeme používat. Má však jednu velkou nevýhodu - ve smyčce (rekurzy), tedy když na sebe navzájem ukazují dva objekty, se paměť nikdy neuvolní i když nebude používaná (v JS syntaxi: a = {}; b = { a }; a.b = b;), což není úplně uživatelsky přívětivé a pro uživatele našeho jazyka by to znamenalo nutnost hlídat si rekurzy.
Garbage Collector
Forma GC je sice i počítání referencí (RC), ale většinou je pod pojmem GC myšlen "Mark and sweep GC". Funguje na principu viditelnosti - nevidím-li paměť, není využitá. Najde se proto jeden či více kořenových objektů, ze kterých se kontroluje viditelnost, například v JS je tento kořenový objekt "scope", tedy to co je vidět uvnitř code blocku {}.
Pár příkladů:
let a = {}
{
let b = {}
a.b = b
}Zde na konci programu bude b stále existovat, i když už není přímo viditelné - je nepřímo viditelné skrze a. Přidáme-li však a.b = 0 na konec programu, b se odebere, jelikož už nebude dostupné.
{
let a = {}
let b = { a }
let a.b = b
}Tady se na konci odebere a i b, což by se v RC nestalo - u každého totiž je jedna reference, i když jsou ty reference navzájem.
Mark and sweep
Samotný mark and sweep algoritmus sice nebudeme implementovat (hezkým způsobem by byl na dlouho), ale je dobré ho znát, samotný algoritmus totiž není složitý.
Paměť budeme ukládat do seznamu a uložíme si u nich hodnotu "označení". Kdykoliv budeme chtít promazat paměť ("trigger garbage collection"), odebereme ze všech buněk označení, vezmeme kořenovou paměť a postupně označíme veškeré buňky které navštívíme po cestě. Poté veškeré neoznačené buňky jsou nevyužité a můžeme je pročistit.
Kdy promazat paměť
Zde je balanc výkonu a využití paměti - pročištění paměti musí projít všechny objekty, a to i když je nečte celé zabere čas - dost na to, aby došlo k výrazné ztrátě výkonu, budeme-li promázavat paměť až moc často. Nepromažeme-li ji však všas, bude zbytečně zabírat paměť. Zde docházíme k postupnému vylepšování heureistik, například X alokací, X alokovaných bajtů, po X času, není-li dostupný dostatek paměti, etc.
Knihovna kterou používáme ji promazává automaticky každých X alokovaných bajtů.
Co je kořenová paměť
Zde záleží na daném jazyku. Obecně je tím myšleno jakákoliv paměť která sice nemusí mít objekt kterým je vlastněna, ale je viditelná. Tedy přímo proměnné, avšak ne jejich obsah
let a = { b: { val: 1} }Zde je kořenová paměť a, ale již ne b uvnitř a - i když je to separátní paměťová buňka (další objekt), není dostupný mimo nadřazený objekt. Nebude ani kdyby byl sdílený:
let a = { b: { val: 1 }}
let c = { b: a.b, a: a }a i c jsou zde kořenovou pamětí, a to i když je a uvnitř c (je dostupné i mimo), a b není, i když je dostupný ze dvou bodů.
V našem případě to však nemusíme řešit, knihovna kterou použijeme si sama zjišťuje co je kořenová paměť a co není (pro více informací doporučuji přečíst tento článek (EN)).
Které buňky navštívit
U objektů všechny hodnoty všech klíčů, u seznamu všechny hodnoty v seznamu.
Běžně by jsme museli přidat vlastní kód který by říkal jak navštívit všechny hodnoty, knihovna gc má však implementaci traity Trace (též z knihovny), sloužící tomuto účelu, pro běžně používané typy jako Vec či HashMap. A pro běžné objekty poskytuje dvojici maker které stačí přidat pomocí derive.
Implementace
Přidáme knihovnu gc s feature derive. Features je způsob, kterým lze zapnout či vypnout části knihovny. Používá se pro odebrání knihoven které nemusí být třeba. Běžně bývá feature derive, která přidává závislost na macro systému (proc-macro), či serde, pro serializaci a deserializaci do běžných formátů (json, yaml, toml, etc). Bez těchto feature se zbytečně nestahuje a neinstalují tyto knihovny, což zrychlí kompilaci a, v některých případech, zjednoduší nastavení projektu (knihovna může vyžadovat nainstalovaný program, který nebude vyžadován když nebude zapnutá feature). Též se používají pro výběr z různých implementací (například použitý http klient).
Do Cargo.toml pod dependencies, vedle itertools, přidáme
gc = { version = "0.5", features = ["derive"] }Tato knihovna nám dá implementaci Gc<T>, chytrému ukazateli (smart pointer) podobnému chováním k Rc<T>, který však používá mark-and-sweep GC.
Na všechny objekty které mohou být vlastněné Gc<T> je nutné přidat implementaci Trace a Finalize (obojí z knihovny). Pro standartní objekty je již implementace dostupná, a pro naše sktruktury je stačí přidat do derive.
GC se týká pouze exekutoru, a tak budou veškeré změny probíhat v exec.rs.
Cell
Rust nám zakazuje mít vícero &mut pointerů či mít &mut a & na stejnou paměť naráz z důvodu správnosti chování programu. Chytré pointery nám však umožňují získavat z různých částí programů pointery i naráz, a proto nám nemohou jednoduše dát &mut.
Mezi chytré pointery patří Rc, Arc ale i Gc. Je v nich, ale i mimo ně, však dobré mít možnost data upravovat, a k tomu slouží tzv. Cell typy.
V praxi se používají OnceCell (LazyCell a další varianty) pro paměť kterou je třeba upravit právě jednou po její inicializaci (používá se pro singleton, nebo například pro přihlášení, kde se odhlášení provádí zavřením připojení, programu či obdobně), RefCell pro možnost úpravy na jednom vláknu (uvnitř Rc) a Mutex pro možnost úpravy na vícero vláken (uvnitř Arc). Specifika jsou vysvětlená v dokumentaci pro cell.
Gc však kvůli svým specifikům implementuje vlastní variantu RefCell pod názvem GcCell. GcCell však není náhradou Gc, jen umožňuje upravovat hodnotu uvnitř Gc, a tak budeme často používat Gc<GcCell<T>>.
GC pro Scope
Nejdříve přidáme možnost sdílet scope pro funkci. Testovací kód pro ověření funkčnosti vypadá takto:
let testprint = 0;
function test() {
let variable = 1;
function testprintfn() {
print(variable)
}
testprint = testprintfn;
}
test();
testprint();Momentálně selže s variable not found, jelikož funkce testprintfn se uloží do proměnné testprint, ale jakmile skončí funkce test, pročistí se scope pro test a s ním i variable.
Musíme dělat šolichání s proměnnou (nastavení testprint na testprintfn) jelikož náš jazyk momentálně neumí vracet hodnoty z funkcí, a tak přenastavení proměnné je jediný způsob jak vrátit hodnotu. Vracení přes return přidáme za chvíly.
A zde by nám Rc pro uložení pointeru na scope nepomohl, jelikož se již zde jedná o rekurzy - scope obsahuje pointer na funkci testprintfn, která by si uložila pointer zpátky na scope, a paměť by se nikdy neoznačila jako nevyužitá.
Pro samotnou implementaci chceme udělat následující úpravy:
scope by se měl ukládat jako seznam pointerů na scope objekty, nikoli přímo objekty
definice funkce by si měla udělat kopii daného seznamu (zkopírovat pouze pointery)
při spuštění by se měl dočasně nahradit seznam scope seznamem z funkce, po skončení spuštění opět navrátit do původního stavu
Upravíme proto náš Context struct aby jednotlivé scopes "obalil" do Gc<GcCell<T>:
pub struct Context {
scopes: Vec<Gc<GcCell<HashMap<String, Type>>>>
}Touto úpravou dostaneme chyby v našem impl Context.
Je potřeba změnit způsob jakým přidáváme a používáme jednotlivé scopes. Přidávání je snažší, stačí objekt který se momentálně vkládá (HashMap::new()) obalit Gc::new(GcCell::new()):
impl Context {
fn add_scope(&mut self) {
self.scopes.push(Gc::new(GcCell::new(HashMap::new().into())));
}
...
}define změníme tak, aby nebral mut referenci na poslední item, protože s mut referencí na Gc nemůžeme manipulovat, a místo toho použijeme borrow_mut z GcCell:
impl Context {
...
pub fn define(&mut self, ident: String, value: Type) {
self.scopes.last_mut().unwrap() .insert(ident, value);
self.scopes.last() .unwrap().borrow_mut().insert(ident, value);
}
...
}Mezery v kódu nemění jeho podstatu a jsou zde kvůli čitelnosti. Jiné formátování nevadí, a mimo porovnání mezery uprostřed řádku spíše překáží, můžete je proto bez obav odebrat či pozměnit.
update změníme obdobně:
impl Context {
...
pub fn update(&mut self, ident: String, value: Type) -> bool {
for scope in self.scopes.iter_mut().rev() {
for scope in self.scopes.iter() .rev() {
if let Some(v) = scope .get_mut(&ident) {
if let Some(v) = scope.borrow_mut().get_mut(&ident) {
*v = value;
return true;
}
}
false
}
...
}GcCell nám totiž umožňuje dostat &mut T z &GcCell<T> (obdobně jako jiné cell typy), a proto není potřeba mít mut referenci na celý array. V tomto případě (a v případě define) by jsme i mohli odebrat mut z &mut self, jelikož ani nepotřebujeme upravovat Context objekt (narozdíl od push).
get je první kde změníme i definici funkce, místo &Type bude vracet přímo kopii Type. Je to z toho důvodu že u Gc nemůžeme zaručit validitu reference (Garbage collector by ji mohl kdykoliv odebrat), a máme na výběr dvě možnosti - vrátit Gc, což nám v našem případě stejně nepomůže jelikož Gc je celý scope a ne přímo vybraná hodnota, nebo vracet kopii. Kopie nám však nevadí, jelikož objekty které nebudeme chtít kopírovat (list, objekt) budou za Gc sami o sobě, a tak se zkopíruje akorát reference.
impl Context {
...
pub fn get(&self, ident: &str) -> Option<&Type> {
pub fn get(&self, ident: &str) -> Option< Type> {
self.scopes.iter().rev().find_map(|scope| scope .get(ident) )
self.scopes.iter().rev().find_map(|scope| scope.borrow().get(ident).cloned())
}
...
}get sice změnil návratovou hodnotu, nicméně jediné místo kde se používá je uvnitř impl Exec for Expression (část Expression::Identifier(ident)), s clone. My ten klon vytvoříme již dříve, a tak tam není .clone() již potřeba, ale nám to nevadí, pouze zbytečně zkopíruje paměť.
Trace, Finalize
Aby jsme mohli použít typ uvnitř Gc, je třeba aby měl implementaci Trace a Finalize. Jsou to různé traity protože je relativně běžné mít vlastní implementaci pro Finalize a nechat si zaimplementovat Trace automaticky, a rust neumí částečný trait derive. My však vlastní Finalize nepotřebujeme a budeme tak referencovat obojí v našich derive.
Používáme Type uvnitř Gc v našich scopes - scope je Gc<GcCell<HashMap<String, Type>>>. U Type tedy do derive přidáme Trace, Finalize:
#[derive(Clone, Debug, PartialEq, Trace, Finalize)]
pub enum Type { ... }Trace a Finalize, obdobně jako Debug a ostatní, vyžadují aby hodnoty uvnitř též implementovali Trace a Finalize.
Již existuje implementace pro String a i64, je proto nutné je přidat jen pro Function:
#[derive(Debug, Trace, Finalize)]
enum Function {
Native(Rc<NativeFunction>),
UserDefined(Rc<FunctionDefinition>)
}Zde však narážíme na problém - Rc nemá implementaci pro Trace a Finalize.
Rc jsme používali aby jsme mohli mít vícero referencí na objekt aniž by jsme ho museli kopírovat, jelikož funkce mohou být velké, a brzo budou moci i mít referenci na scopes. Když jsme ale teď přidal GC, můžeme použít raději to.
Vytvoříme si dva typy - HeapCell a HeapType.
HeapCell je malým wrapperem nad Gc<GcCell<HeapType>> s implementací pro PartialEq, Clone, Debug, Trace a Finalize.
#[derive(Clone, Debug, Trace, Finalize)]
pub struct HeapCell(Gc<GcCell<HeapType>>);
impl HeapCell {
fn new(t: HeapType) -> Self {
Self(Gc::new(GcCell::new(t)))
}
}
impl PartialEq for HeapCell {
fn eq(&self, other: &Self) -> bool {
Gc::ptr_eq(&self.0, &other.0)
}
}Do Type přidáme variantu Heap(HeapCell) a vytvoříme si malou wrapper funkci pro zjednodušení práce:
#[derive(Clone, Debug, PartialEq, Trace, Finalize)]
pub enum Type {
Number(i64),
String(String),
Void,
Heap(HeapCell)
}
impl Type {
fn heap(t: HeapType) -> Self {
Type::Heap(HeapCell::new(t))
}
} HeapType si zadefinujeme jako enum s jednou hodnotou - Function. Později k němu přibyde Array a Object.
#[derive(Debug, Trace, Finalize)]
pub enum HeapType {
Function(Function),
}A upravíme Function tak, aby nepoužíval Rc, a aby UserFunction byla nová struktura místo přímo použití typu z parseru.
#[derive(Debug, Trace, Finalize)]
enum Function {
Native(NativeFunction),
UserDefined(UserFunction)
}UserFunction bude ukládat definici funkce z parseru, to se nezmění, ale zároveň i seznam scopů které se mají přidat při volání funkce.
Stále však používá Rc, protože parser nám vrací Rc<FunctionDefinition>. Aby jsme se vyhnuli chybě, použijeme tag unsafe_ignore_trace, které používá derive Trace. To značí, že trace nemá procházet tento objekt. Unsafe je z toho důvodu, že obsahuje-li FunctionDefinition Gc objekt, nemusel by program fungovat správně. FunctionDefinition však Gc obsahovat nemůže, protože parser vůbec knihovnu gc nepoužívá. Navíc zdejší užití unsafe není zcela v souladu s pravidly rustu - porušením podmínky (referencí Gc) se nestane undefined behaviour (UB), ale dojde k neuvolnění paměti (memory leak), což je nepříjemné, ale nedojde k špatnému chování programu.
V rustu je úmluva psát u unsafe kódu popisek SAFETY s odůvodněním bezpečnosti kódu. Clippy umí přidat pravidlo které vyžaduje tyto komentáře, některé knihovny a programy jej používají (například rust compiler sám o sobě).
#[derive(Trace, Finalize)]
struct UserFunction {
// SAFETY: FunctionDefinition comes from parser which doesn't use or reference Gc
#[unsafe_ignore_trace]
def: Rc<FunctionDefinition>,
/// scopes které byly vidět při definici funkce, aby je funkce mohla referncovat
scopes: Vec<Gc<GcCell<HashMap<String, Type>>>>,
}NativeFunction se změní jen minimálně - přidá se Trace, Finalize a znova unsafe_ignore_trace, jelikož nelze sledovat funkce:
#[derive(Trace, Finalize)]
struct NativeFunction {
name: String,
// SAFETY: function definitions shouldn't depend
#[unsafe_ignore_trace]
body: Mutex<Box<dyn Fn(Vec<Type>) -> Type>>
}Dále akorát upravíme kód aby pracoval s novými typy.
impl ToString for Type {
fn to_string(&self) -> String {
match self {
Type::Number(num) => num.to_string(),
Type::String(string) => string.clone(),
Type::Void => "void".to_string(),
Type::Heap(heap) => match heap.0.as_ref().borrow().deref() {
Type::Function(func) => match func {
Function::Native(native) => format!("<native function {}>", native.name),
Function::UserDefined(defined) => format!("<user defined function {}>", defined .ident)
Function::UserDefined(defined) => format!("<user defined function {}>", defined.def.ident)
},
}
}
}
}impl Context {
...
pub fn define_native_func(&mut self, name: String, body: impl Fn(Vec<Type>) -> Type + 'static) {
self.define(name.clone(), Type::Function(Function::Native(Rc::new(NativeFunction {
self.define(name.clone(), Type::heap(HeapType::Function(Function::Native( NativeFunction {
name,
body: Mutex::new(Box::new(body))
}))));
}
}U definice změníme typ a naklonujeme scopes. To naklonuje Vec referencí, což bude relativně malá struktura, levná na zkopírování. Dle datových struktur by jsme mohli spíše zvolit linked list Gc referencí, nicméně toto je pro nás jednodušší a nejspíše i rychlejší na moderních procesorech.
impl Exec for Rc<FunctionDefinition> {
fn exec(&self, ctx: &mut Context) -> Type {
ctx.define(self.ident.clone(), Type::Function(Function::UserDefined(self.clone())));
ctx.define(
self.ident.clone(),
Type::heap(HeapType::Function(Function::UserDefined(UserFunction {
def: self.clone(),
scopes: ctx.scopes.clone()
})))
);
Type::Void
}
}A nakonec spouštění funkcí, rovnou i s přidáním scopů:
impl Exec for FunctionCall {
fn exec(&self, ctx: &mut Context) -> Type {
let func = self.func.exec(ctx);
let args = self.args.iter().map(|arg| arg.exec(ctx)).collect();
match func {
match &func {
Type::Heap(HeapCell(ptr)) => match ptr.borrow().deref() {
HeapType::Function(func) => match func {
Function::Native(native) => (native.body.lock().unwrap())(args),
Function::UserDefined(defined) => {
ctx.add_scope();
for ident in defined.def.args.iter() {
ctx.define(ident.clone(), Type::Void);
}
for (ident, value) in defined.def.args.iter().zip(args.iter()) {
ctx.define(ident.clone(), value.clone());
}
ctx.scopes.extend_from_slice(&defined.scopes);
let result = defined .body.exec(ctx);
let result = defined.def.body.exec(ctx);
ctx.scopes.truncate(ctx.scopes.len() - defined.scopes.len());
ctx.pop_scope();
result
}
},
_ => panic!("expected function in function call")
},
_ => panic!("expected function in function call")
}
}
}Kvůli pravidlům rustu, jelikož Type má nyní Drop implementaci, resp. jedna z hodnot má Drop implementaci (Gc), nemůžeme vzít field a zahodit zbytek. Rust nám však nabídne použít referenci, proto změníme match func a na match &func.
Matchujeme pro Heap(HeapCell(ptr)). Pointer musíme derefencovat, přes borrow dostaneme z Gc<GcCell> struct GcCellRef, a přes deref z něj &HeapType. Mimo match nemusíme řešit, jelikož rust automaticky zavolá deref pro převod typů u volání funkcí.
GcCellRef je objekt který drží Gc na živu, aby nám nezmizel pod rukama. Obdobné objekty dává Rc, Arc, Mutex a podobně.
Mají na sobě Drop implementaci, aby při zahození provedli akci - u Rc se sníží počet referencí, a dosáhnul-li počet 0, zahodí paměť.
extend_from_slice bere slice, i.e. cokoliv co vypadá jako read-only array, a přidá ho do Vec.
truncate naopak nastaví maximální velikost, v našem případě na velikost předchozí, a zahodí se přesahující objekty.
Tímto by měl náš původní kód fungovat:
let testprint = 0;
function test() {
let variable = 1;
function testprintfn() {
print(variable)
}
testprint = testprintfn;
}
test();
testprint();
result=Void
output=[Number(1)]