# Správa paměti

## Dynamická velikost

### Automatické proměnné

│ • uložené v rámci
│ • zabírají prostor na zásobníku
│ • zásobník má omezenou velikost


### Paměťová složitost

│ • podobně jako časová ⟦O(f(n))⟧
│ • ⟦n⟧ bude «velikost problému»
│   ◦ nemusí nutně být pouze vstup
│ • alokace na zásobníku – ⟦O(1)⟧ OK
│   ◦ ⟦O(\log n)⟧ – obvykle OK


### Jazyk C

│ • proměnné mají konstantní velikost
│ • alokace tedy pouze ⟦O(1)⟧
│ • pozor ale na počet proměnných


### Rekurze

│ • podobné omezení – max. ⟦O(\log n)⟧
│ • např. merge sort, binární hledání
│ • co backtracking?
│   ◦ exponenciální čas
│   ◦ lineární hloubka rekurze


### Meze rekurze

│ • co stromové struktury?
│   ◦ může a nemusí být OK
│   ◦ hloubka ne vždy ⟦O(\log n)⟧
│ • koncová rekurze
│   ◦ lze v konstantní paměti
│   ◦ v C to ale není povinné


### Dynamická alokace

│ • bez striktních omezení
│ • adresní prostor
│   ◦ 64b bez problémů
│   ◦ omezený pro ≤ 32b adresy
│ • paměť není nekonečná


### Standardní C

│ • knihovna: ‹malloc›, ‹free›
│ • vyžaduje interakci s OS
│ • ‹malloc› je (trochu) magický


## Dynamická živost

### Statická živost

│ • lokální proměnné
│ • život = rozsah platnosti
│ • jednoduché ale omezující


### Dynamická živost

│ • dynamická paměť
│ • rozhoduje se za běhu
│   ◦ např. v podmínce
│ • významný zdroj chyb


### Uvolnění

│ • konec živosti objektu
│ • ukazatele dále existují
│   ◦ jsou již ale «neplatné»
│   ◦ mrtvý objekt nesmí být použit
│ • koordinace je kritická


### Klasifikace chyb

│ • použití po uvolnění
│   ◦ lze rozlišit zápis/čtení
│ • dvojité uvolnění
│ • chybějící uvolnění (únik)


### Použití po uvolnění

│ • dereference neplatného ukazatele
│   ◦ nedefinované chování
│ • čtení → nesmyslná hodnota
│ • zápis → poškození dat
│ • ohrožení metadata alokátoru


### Dvojité uvolnění

│ 1. neplatný ukazatel
│    ◦ poškození metadat
│    ◦ nedefinované chování
│ 2. omylem platný ukazatel
│   ◦ uvolní jiný objekt
│   ◦ další použití je pak UB


### Únik zdrojů

│ • objekt nebyl uvolněn
│   ◦ striktně – už nebude použit
│   ◦ volně – neexistuje ukazatel
│ • situačně závislé
│   ◦ použití může být zbytečné


### Obecněji o zdrojích

│ • paměť není jediný zdroj
│ • platí stejná pravidla
│   ◦ zdroj ~ objekt
│ • soubory, mutexy, atp.


### Pseudostatická živost

│ • statická živost je přirozená
│ • nelze vždy použít i když stačí
│   ◦ dynamicky velké pole
│   ◦ jiné zdroje než objekty
│ • syntaktické párování alokace/dealokace